共计 2656 个字符，预计需要花费 7 分钟才能阅读完成。
前段时间看到了同学转发的中兴通讯的较量链接，之前也没有加入过算法类的较量，这次打算报着试一试的态度加入下，减少下教训。在初步看了几个门派的题目简介后，发现只有傅里叶派比拟适宜本人，所以最终抉择了傅里叶派。
@[TOC]
题目形容
在某片边远的大陆上，寓居着两个世代敌对的部落，别离是部落 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 数据信道的编码方式。如果有趣味能够钻研下。
如遇到排版错乱的问题，能够通过以下链接拜访我的 CSDN。
**CSDN:[CSDN 搜寻“嵌入式与 Linux 那些事”]
