前段时间看到了同学转发的中兴通讯的较量链接，之前也没有加入过算法类的较量，这次打算报着试一试的态度加入下，减少下教训。在初步看了几个门派的题目简介后，发现只有傅里叶派比拟适宜本人，所以最终抉择了傅里叶派。
@[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那些事”]