『ACM C++』HDU杭電OJ | 1418 - 抱歉 (拓撲學:多面體歐拉定理引申)

来源:https://www.cnblogs.com/winniy/archive/2019/03/01/10459075.html
-Advertisement-
Play Games

嘔,大一下學期的第一周結束啦,一周過的挺快也挺多出乎意料的事情的~ 隨之而來各種各樣的任務也來了,嘛畢竟是大學嘛,有點上進心的人多多少少都會接到不少任務的,忙也正常啦~端正心態 開心面對就好啦~ 今天突然回顧了一下《從你的全世界路過》這本書和電影,莫名的感悟涌上心頭,收集到了一些走入人心的一些語句: ...


  嘔,大一下學期的第一周結束啦,一周過的挺快也挺多出乎意料的事情的~ 隨之而來各種各樣的任務也來了,嘛畢竟是大學嘛,有點上進心的人多多少少都會接到不少任務的,忙也正常啦~端正心態 開心面對就好啦~

  今天突然回顧了一下《從你的全世界路過》這本書和電影,莫名的感悟涌上心頭,收集到了一些走入人心的一些語句:

  1、在季節的車上,如果你要提前下車,請別推醒裝睡的我,這樣我可以沉睡到終點,假裝不知道你已經離開。

  2、世事如書,我偏愛你這一句,願做個逗號,待在你腳邊。但你有自己的朗讀者,而我只是個擺渡人。

  3、我淋過的最大的雨,是那一天你在烈日下的不回頭。

  4、這世界是你的遺囑,而我是你唯一的遺物。

  5、我希望有個如你一般的人,如山間清爽的風,如古城溫暖的光,從清晨到夜晚,由山野到書房,只要最後是你,就好。

 

 

今日興趣新聞:

MWC 2019 新品彙總:5G+ 摺疊屏開啟的新時代?

鏈接:https://mbd.baidu.com/newspage/data/landingsuper?context=%7B"nid"%3A"news_11274128788158220226"%7D&n_type=0&p_from=1

 

 

------------------------------------------------題目----------------------------------------------------------

抱歉

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6147    Accepted Submission(s): 2891

Problem Description

非常抱歉,本來興衝衝地搞一場練習賽,由於我準備不足,出現很多數據的錯誤,現在這裡換一個簡單的題目:
前幾天在網上查找ACM資料的時候,看到一個中學的奧數題目,就是不相交的曲線段分割平面的問題,我已經發到論壇,並且lxj 已經得到一個結論,這裡就不
多講了,下麵有一個類似的並且更簡單的問題:
如果平面上有n個點,並且每個點至少有2條曲線段和它相連,就是說,每條曲線都是封閉的,同時,我們規定:
1)所有的曲線段都不相交;
2)但是任意兩點之間可以有多條曲線段。
如果我們知道這些線段把平面分割成了m份,你能知道一共有多少條曲線段嗎?

Input

輸入數據包含n和m,n=0,m=0表示輸入的結束,不做處理。
所有輸入數據都在32位整數範圍內。

Output

輸出對應的線段數目。

Sample Input

3 2
0 0

Sample Output

 3
------------------------------------------------題目----------------------------------------------------------  

(一) 題目分析:

     題目一上來懵了,很短的題目,也很容易讀懂什麼意思,但就是沒有思路下手,對數學背景也不太清楚,還是一道中學奧數題,AC率還很高,我居然還不會做,去看了一下杭電的discuss之後才發現,這其實就是多面體歐拉定理的輸出結果而已。

    後面會引申多面體歐拉定理。

 

(二)AC代碼:

#include<stdio.h>
using namespace std; 
long long int n,m;
int main() 
{
    while(scanf("%d%d",&n,&m) && (n||m))
        printf("%d\n",n+m-2); 
    return 0; 
}

  註:因為代碼太簡單就不分塊了,主要是引出多面體歐拉定理。

 

(三)AC截圖:

 

(四)解後分析:

    多面體歐拉定理:

      多面體歐拉定理是指對於簡單多面體,其頂點數V、棱數E及面數F間有著名的歐拉公式:V-E+F=2。簡單多面體即錶面經過連續變形可以變為球面的多面體。

      V+F-E=X(P),V是多面體P的頂點個數,F是多面體P的面數,E是多面體P的棱的條數,X(P)是多面體P的歐拉示性數。 如果P可以同胚於一個球面(可以通俗地理解為能吹脹成一個球面),那麼X(P)=2,如果P同胚於一個接有h個環柄的球面,那麼X(P)=2-2h。 X(P)叫做P的拓撲不變數,是拓撲學研究的範圍。

      引申其他的歐拉公式

    分式里的歐拉公式

      a^r/(a-b)(a-c)+b^r/(b-c)(b-a)+c^r/(c-a)(c-b)

      當r=0,1時式子的值為0 當r=2時值為1

      當r=3時值為a+b+c

    複變函數論里的歐拉公式:

      e^ix=cosx+isinx

      e是自然對數的底,i是虛數單位。它將三角函數的定義域擴大到複數,建立了三角函數和指數函數的關係,它在複變函數論里占有非常重要的地位.

      將公式里的x換成-x,得到:

      e^-ix=cosx-isinx,然後採用兩式相加減的方法得到:

      sinx=(e^ix-e^-ix)/(2i),cosx=(e^ix+e^-ix)/2.這兩個也叫做歐拉公式。將e^ix=cosx+isinx中的x取作∏就得到:

      e^i∏+1=0. 這個恆等式也叫做歐拉公式,它是數學里最令人著迷的一個公式,它將數學里最重要的幾個數學聯繫到了一起:兩個超數:自然對數的底e,圓周率∏,兩個單位:虛數單位i和自然數的單位1,以及數學里常見的0。數學家們評價它是“上帝創造的公式”,我們只能看它而不能理解它。

    三角形中的歐拉公式

      設r為三角形外接圓半徑,r為內切圓半徑,d為外心到內心的距離,則: d^2=r^2-2rr

    拓撲學里的歐拉公式:(多面體歐拉公式)

      v+f-e=x(p),v是多面體p的頂點個數,f是多面體p的面數,e是多面體p的棱的條數,x(p)是多面體p的歐拉示性數。

      如果p可以同胚於一個球面(可以通俗地理解為能吹脹而綳在一個球面上),那麼x(p)=2,如果p同胚於一個接有h個環柄的球面,那麼x(p)=2-2h。

      x(p)叫做p的歐拉示性數,是拓撲不變數,就是無論再怎麼經過拓撲變形也不會改變的量,是拓撲學研究的範圍。

      在多面體中的運用:

      簡單多面體的頂點數v、面數f及棱數e間有關係

      v+f-e=2

      這個公式叫歐拉公式。公式描述了簡單多面體頂點數、面數、棱數特有的規律。

    初等數論里的歐拉公式:

      歐拉φ函數:φ(n)是所有小於n的正整數里,和n互素的整數的個數。n是一個正整數。

      歐拉證明瞭下麵這個式子:

      如果n的標準素因數分解式是p1^a1*p2^a2*……*pm^am,其中眾pj(j=1,2,……,m)都是素數,而且兩兩不等。則有

      φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)

      利用容斥原理可以證明它。

      

      參考:https://www.phb123.com/shijiezhizui/renlei/20095_2.html

 

註:我還是個渣渣輝,代碼可能寫得不夠高效不夠好,我也會努力優化,如果有更好的解法,真心希望您能夠評論留言貼上您的代碼呢~互相幫助互相鼓勵才能成長鴨~~


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 簡單粗暴學建造者模式,含Mybatis框架源碼中建造者模式運用分析。 ...
  • 題意 "題目鏈接" 可持久化01Trie板子題 對於兩個操作分別開就行了 cpp include using namespace std; const int MAXN = 4e5 + 10, SS = MAXN 42 + 10; const int B = 31; inline int read( ...
  • Node.js 是一個基於 Chrome V8 引擎的 JavaScript 運行環境,用來方便地搭建快速的易於擴展的網路應用。Node.js 使用了一個事件驅動、非阻塞式 I/O 的模型,使其輕量又高效,非常適合運行在分散式設備的數據密集型的實時應用。在阿裡雲的Centos系統上,可以採用NVM安 ...
  • 早些年做CRM用到的一個金額轉換函數,今天從舊項目中拿出來記錄一下。金額轉換的函數方法有很多,都很不錯。不過這個是小崔剛工作的時候寫的一個轉換函數,多少還是有點紀念意義。如有問題請朋友們指出,小崔及時修正。謝謝啦! 廢話不多說直接上代碼: 以上是基礎轉換代碼,在這個基礎上進行二次改造: 運行結果: ...
  • 登錄驗證碼 Servlet / 從請求中獲取數據,獲取驗證碼的session的值轉為String類型, 銷毀,防止返回後驗證碼不刷新,重新驗證成功 判斷驗證碼是否相同(忽略大小寫) 相同:創建user對象調用service層的方法驗證返回結果是否為空 為空:創建session:儲存錯誤信息,轉發,登 ...
  • 本文是接著上篇博客寫的:Spring boot 入門(三):SpringBoot 集成結合 AdminLTE(Freemarker),利用 generate 自動生成代碼,利用 DataTable 和 PageHelper 進行分頁顯示。按照前面的博客,已經可以搭建一個簡單的 Spring Boot ...
  • 小談: 帖主妥妥的一名"中"白了哈哈哈。軟工的大三狗了,也即將找工作,懷著絲絲忐忑接受社會的安排。這是第一次寫博客(/汗顏),其實之前在學習探索過程中,走了不少彎路,爬過不少坑。真的挺感謝一路上的前輩們的博客也好,隨筆也好,哪怕是評論,或多或少解決了一些問題。我感覺學技術的過程中,記錄下自己解決問題 ...
  • 長期以來都想用python對Excel進行一些列的操作,但由於某種神秘的力量控制著我,一直未果,今天有幸用requests模塊和BeautifulSoup模塊進行爬蟲練習,拿到了一大批數據,照我以前,都只是用字典啊、列表啊,或者文本文件存放,之前沒覺得哪裡不好,但今天的我很奇怪,怎麼看怎麼不爽,而且 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...