2020中興捧月傅里葉派記錄

前段時間看到了同學轉發的中興通訊的比賽鏈接，之前也沒有參加過算法類的比賽，這次打算報著試一試的態度參加下，增加下經驗。在初步看了幾個門派的題目簡介后，發現只有傅里葉派比較適合自己，所以最終選擇了傅里葉派。

文章目錄

題目描述

設計思路

算法描述

總結

參考

題目描述

在某片遙遠的大陸上，居住著兩個世代友好的部落，分別是部落A和部落B。他們一起耕耘勞作，互相幫助，親如一家。久而久之，部落里的每個人都在對方部落里找到了志趣相投，互相欣賞的好朋友。有的人性格熱情開朗，好朋友很多；有的人性格沉穩內斂，好朋友相對少一些。

每到秋天豐收的季節，這兩個部落的人民都會聚集在一起舉行盛大的“豐收祭”，來祈禱下一年的風調雨順。今年的豐收祭馬上又要舉行了。為了進一步增進兩個部落的友誼，也為了明年能有一個好收成，這兩個部落的祭司們商量后決定：在今年的豐收祭前舉辦一場特別的“擊鼓傳花”游戲。只不過游戲中并非有人真的擊鼓，并且所傳遞的“花”也不是真的花，而是等待在豐收祭上獻上的祭品。

游戲規則如下：

1. 兩個部落的所有人都可以事先準備自己的祭品，且每個人的祭品樣式都不同，每一個祭品都分別盛放在一個相對應的木托盤里；準備此祭品的人熟悉自己的祭品；

2. 每個人可以準備的祭品數量不限；祭品的最小不可分割單位是1份；

3. 游戲開始后，在整個游戲過程中，每個人都能且只能將祭品（包括木托盤）傳遞給自己在對方部落里的好朋友們，每個好友可以接收的祭品數量不限；

4. 收到祭品的人必須在盛放此祭品的木托盤上刻上自己的名字（代表留下自己美好的祝愿），隨后按按照上一條規則，繼續傳遞；

5. 如果祭品回到最初準備此祭品的人手中，此人也在木托盤上刻上自己的名字之后，終止傳遞；

6. 木托盤上不允許出現重復的人名，如果無法滿足此條件，則不再繼續傳遞該祭品；

7. 當所有的祭品都不再傳遞后，游戲結束；

游戲開展得非常順利。游戲結束后，祭司們將收集同時滿足如下三個條件的祭品用于接下來的豐收祭活動：

1. 此祭品回到了最初準備它的人手中；

2. 盛放此祭品的木托盤上至少有4個名字，至多有14個名字；

3. 如果有多個木托盤上的名字完全一樣（不區分名字的排列順序），則從其中隨機選擇一個木托盤所對應的祭品。

已知這兩個部落里的所有人都不重名，并且部落A的人和部落B的人之間的好朋友關系以附件的csv數據表格文件給出，其中行索引代表部落A中的人，列索引代表部落B中的人，表格中的數字“1”代表他們兩人是好朋友，“0”代表他們兩人不是好朋友。請問：

如果以木托盤上的名字的數量對用于豐收祭的祭品分類，每一類分別最多有多少個祭品？

木托盤上有4個名字的祭品最多有（）個；木托盤上有6個名字的祭品最多有（）個；木托盤上有8個名字的祭品最多有（）個；木托盤上有10個名字的祭品最多有（）個；木托盤上有12個名字的祭品最多有（）個；木托盤上有14個名字的祭品最多有（）個；

設計思路

依據數據來看，A部落有256個人，B部落有640個人。A部落和B部落的人只能給對方部落的人，以人為節點建圖，可以發現這是一個二分圖。excel數據中給的是鄰接矩陣，我們轉換成鄰接表，然后題目的問題轉化成：每個節點出發可以有很多條路徑，問其中環的數量有幾個，并且是路徑大于等于4小于等于14的環的數量，最后要去重。我們以每個節點作為起點，進行DFS，并進行計數，統計每種長度的路徑條數，最后再去重。(此處感謝群里的大佬提供的思路！)

算法描述

1.將B部落的人用編號0-639表示，將A部落的人用編號700-955表示，將excel中的鄰接矩陣轉換為鄰接表。

2. 第一列表示i號節點，第二列數字表示有k個好朋友，再后面k列的數字就表示好朋友分別是誰。

3.對每個節點開始進行深度優先搜索，對i個節點，開始先賦給vis數組初值，所有節點都沒訪問過，訪問i，然后依次訪問與他相鄰的點，一直遞歸下去，直到找到訪問過的節點。若該節點被訪問過，則判斷該節點是不是根節點，如果是則滿足題意，記錄該路徑長度，返回。否則，就此節點就不再遞歸，直接返回。由于題目只要路徑為4-14的環，所以設置遞歸深度小于等于14。

4.由于用DFS算出來的結果是會出現重復：

比方說1->2*->3->4*->1 用星標記另外一個部落

由于是無向圖：

他會出現1->4*->3->2*->1

也會出現3->4*->1->2*->3

也會出現3->2*->1->4*->3

……

如果循環節是i就會由i * 2種可能會被DFS到，所以要去重，最后路徑長度為i的數量的要除以i * 2，最后得到去重結果。

5.剪枝優化

在第二階段的數據集變成了1344 * 1344。進行暴力DFS會做很多無用功。所以要進行剪枝優化。打算把在上述的算法中，路徑1->2*->3->4*->1在別的節點的DFS中還會出現3->4*->1->2*->3，這實際上是一個圈，我們需要在DFS中避免這種重復的計算。考慮到在第i個節點統計完圈了以后，在第i+1個節點中，如果訪問到第i個節點，那么我們直接跳過這個節點，就可以避免在后面的dfs中重復出現前面統計過的點。那么我們只需要創建一個數組vv[]，用來統計哪些節點之前統計過，然后給他附上DFS過的標記，再后面的節點的統計的時候可以直接跳過這個點，就可以不重復算某個圈，這樣就可以在后面的DFS達到剪枝的效果。

總結

期間被其他事情耽誤了很久，想出來剪枝優化的方法已經是5.8，可惜最后程序沒有調試出來。二階段只有五分的得分（一階段結果完全正確）。總得來說還是自己能力不足。這次比賽暴露了自己的不足，對于數據結構和算法了解比較少。非常感謝群里各位大佬的討論，參考了各位同學的思路后，自己才知道如何去把問題抽象出來。在有了思路后，在百度，google，github搜索相關問題和代碼，參考了一些文章，自己也學習了關于圖論的一些知識。接下來有時間的話要重點熟悉下基本的算法，刷力扣題目，不斷提升自己的編程能力。

賽后看大家在群里討論題目的各種解法，老師官方的回復是，給的csv數據集有一定規律可以利用。當然，如果有很強的編程能力，DFS+剪枝也是可以很快給出結果的（C++最快1min之內可以出結果）。關于規律的利用，可以往QC-LDPC碼這個方向考慮，這是5G數據信道的編碼方式。如果有興趣可以研究下。

參考

學習圖的算法過程中參考的一些寫的不錯的文章，發出來供大家參考。

Graph

Depth First Search or DFS for a Graph

The DFS tree and its applications

無向圖深度優先遍歷及簡單路徑

無向圖 深度優先遍歷 c語言實現

圖的深度優先遍歷DFS （鄰接矩陣實現） c語言

無向圖的幾個基本算法應用

算法-無向圖(連通分量，是否有環和二分圖)

圖論–二分圖–二分圖的定義及其判斷定

有向圖無向圖判斷有環(求環的長度)

5G游戲 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。