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小时内删除侵权内容。