神牛笔记：吉林大学ACM总结（fennec）

╰半橙微兮° 2022-08-09 12:55 208阅读 0赞

其实在北京比赛完的时候，我就想写了，不过还是早了点，直到上海比赛结束，大家的心中都不是太好受。郭老师有句话：你们这样做也是对的，不成功就成仁。让我的心也能安慰了不少。
    我是从大一下学期开始接触ACM的，那时候我们学校才刚刚起步，siyee，wjiang师兄可以说是我的领路人了，冲名次，比做题真是一种幸福的感觉。
    大二上学期很有幸与siyee队长，jack学长一起代表学校参加了比赛，那时候我的心情是很放松的，对自己的目标也是ac一道就万岁：）这也是今年我对windsbu说的话。毕竟那时不是队长，所以对我来说，最重要的就是完成队长布置的任务，其次就是在比赛中做出一道适合自己的题目。去年的最好结果是学校排名第九，大家虽然有种遗憾的感觉，但是毕竟是进步了。
    到了大二下学期的选拔赛，涌现出了好多人才，很多人都很有能力，但是有一点最遗憾的是：许多人接触的比较晚，可能是因为热身赛或者选拔赛才了解了ACM，而我们学校的ACM训练只是一个课余的活动，不能与许多学校专业的训练来相比。这样的结果是，缺乏底子好的老选手，即使出现了有很强能力的同学，也不能在极短的时间里使他们达到一个相当的高度！
    经过了暑假的集训，学校在队伍人选上很是下了一番功夫。从队员到队伍，无不精心研究。可能连统计学的许多知识都用上了：）
    最终很高兴能够与codecpp，wind，组成了jojer队，开始我是不太好意思使用jojer这个名字的，我害怕对不起这个名字，所以先暂时叫做j2吧。由于经验少，刚开始训练的时候有一种摸不到头脑的感觉，许多时候知道有问题，但就是不知道该怎么解决，walkoncloud老师就曾经批评过我：你们队伍就是一个“神经病”带着两个“小神经病”一起“神经病”。这当然只是一种玩笑，但是确实是我们队伍初期的症状，什么事情都没有章法，这时候我们只好使用最原始的方法：讨论加总结。每次比赛结束后无论题目简单与否都要首先将所有题目讨论一遍，将做错的，不会的都分配到人继续将它解决。然后大家单独写赛后总结，交到我这里，在经过分析后，再开集体会议，批评+自我批评并制定下一步策略。用我的话说：这种方式挽救了我们，让我们在极短的时间里磨合了起来。
    我们队伍最后的分工是：
    wind主要负责读题，读题时要将重点难点标记出来，构想出初级的边缘测试数据。并主要负责计算几何以及一些需要推理的数学题目。
    codecpp主要负责1-2简单题目，1到中档搜索题，以及编译方面的题目。和wind对边缘题目以及简单题目形成互补，以及调试上的帮助。
    fennec主要工作是对wind，codecpp读过的题目进行分类，分析，对简单题目直接决定分配的人手，对中档题的复杂度，题型进行准确分析，引导思考方向。在有时间的情况下组织对较难题目的深层讨论。
    我想最后我们还是基本实现这几方面内容的。
    具体到了比赛，首先就是网上预赛：两次比赛感觉是发挥了自己的能力，这也算是队伍第一次最严肃认真的比赛了，大家都很尽力，光从赛后东方饺子王的战绩上就能感觉到！
    在北京赛区，我们很快的作出了三道题目，但在后面wa在了两道题目的上面。这没有什么太好说的，我们队伍这时候最大的缺点在于对于wa题目的处理。但是最后还是因为罚时少，取得了学校排名第七的成绩。这也是一个可以接受的成绩。
    从北京回来就有好多是要做，接连的补作业，以及期末考试，将训练计划打散了不少。这也是很正常的，毕竟在学校和老师看来，学习是最重要的，我们不是培养一个ACM机器。
    在上海的比赛就有些不尽人意了，一是疲劳，二是对题目难度缺乏正确的估计，三是一开始比赛的时候就有些乱套，四是没有专心地做一个题，结果都没有做对。但是很多问题都是因为我在大局上把握的失误，我也感觉很自责，不过一切都过去了，希望后来人能够吸取教训吧。

我想对未来的同学有几句话要说：
    1 我们几乎没有noi上来的队员，大家只能依靠后期的更加刻苦的努力。
    2 我们没有专业的班级或者机制形成职业ACM队伍，所以大家只能尽早的投入进来，用尽一切课余时间去训练。
    3 我们不能在数目上和传统强队比拼（除非队伍中的三个人都很强），所以我们要在中低档题目的ac时间和正确率上下功夫。
    4 不要抱怨什么，你所要做的就是尽力发挥自己的全部，并在发现问题后努力改正。
    5 不要懒得动手，许多题目你觉得自己方法对了，或者怕麻烦就不写了，这是一个最大的缺点，在比赛的时候你可能需要用2-3倍于别人的罚时去做出来。
    6 不要只是追求ac数目，作出一道不会的题目胜过做出10道已经会的题目。
    7 多交流代码！不要只是闭门造车。
    8 养成良好的代码习惯。
    9 在平时做题的时候就养成紧张的好习惯，不然在比赛的时候你会很吃亏的！
    
    关于比赛的感觉：最重要的是四个字：天外有天
    
    而对于真正想继续从事ACM事业的同学，我有以下建议：
    0 首先了解C/C++，以及数据结构。
    1 首先在joj做够50题，这是基本的热身
    2 看一本算法书，清华紫皮的感觉简单点
    3 在继续做够200题，这时候应该在输入输出上不会出大问题了，并了解了基本算法。
    4 看看吴文虎，以及沙特的那本书。
    5 在joj做够400题
    6 这时候应该能够出山了，可以参加几次各类的竞赛
    7 去uva分类做题，这时候不要再在意你的题目数目了，要有目的的，分类训练了
    首先可以是动态规划，然后是搜索，然后再是动态规划，然后再是搜索…这种循环往复的方法，并加以总结，会是你自身提高最快的时候。建议一定要作总结，可以参考我后面的例子。（另外一定要用好uva的论坛功能！）
    8 在uva训练200题目的时候，可以考虑一些典型代码算法的东西了，如网络流，poly计数，匹配等等。并把这些算法做成模板！并且要加强自己的理论修养了，看看离散数学，组合数学，概率论等等数学方面的东西。
    9 总题目到达了1000的时候就可以查缺补漏了，这一段主要以套卷为主，将每次自己不会的题目搞懂就好了！并要适应比赛的节奏！
    10 在题目到达1100-1500的时候，算是小成了。这样的同学就应该能够胜任队长了。
    11 剩下的只能靠自己了：）

附录1：（动态规划总结）
    
    
    近日开始学习动态规划，特做些总结。
    ZOJ 1011 NTA 本来想从顶至下搜，但是情况复杂，要保存一牌的状态。所以过来，从到数第二牌搜起，寻找可以是最底层成立的状态，然后向前搜,以此类推。
    
    ZOJ 1013 Great Equipment 人数<100,500不太明白，但应该是数的范围。数据小，但是量多，应该是动态规划，可是选法较复杂，如果单独考虑每个人，将组合物品整体考虑，则可以省去物品组合，而且可以知道剩余物品不能在组合成新物品，这时候如果枚举的话，还是指数级，因为可以交叉组合，关键就在于如何对人数进行动态规划吗？莫非是利用前k个人可以产生的物品数进行动态规划？比如说前k个人产生了分别a，b，c，d个物品，则加上新的一人，可得新的状态，中间再用上剪枝？但似乎成了枚举。状态似乎太多了，那么对人数进行递推，但是状态集变换一下，就是abcd的某种形式。现在的难点是对状态集大小的分析，因为它关系到算法的复杂度的衡量。想到了搜索的算法，想到了剪枝。
    
    以下借用了别人的解法！
    1013,经典DP 
    只有最后结论，没有想法过程 
    
    我们设计成为这样一个规划过程 
    编号所有的车辆是１，２，３，４。。。，n 
    我们设计一个函数F 
    F(i,x,y) 表示的是前面1...i辆车中装载x件１装备，y件二装备之后 
    最多还能够装多少的３装备 
    我们需要求出F(n,*,*)就是i = n的所有的F值 
    
    设装备的重量和尺寸分别是这样的 
    weight[3],size[3],防御defence[3] 
    而汽车的容量分别是ss[1..n],ww[1..n] 
    
    规划过程: 
    1.i = 1的时候，F(1,x,y) 
    如果x * weight[0] + y * weight[1] > ww[1] 显然F(1,x,y) 不可行，我们取-1标记不可行 
    同理 x * size[0] + y * size[1] > ss[1]也是一样 
    否则　F(1,x,y)可以由除去x,y之后的剩余重量和剩余尺寸算出来 
    
    2.设<i已经算出来，计算i的时候，也就是F(i,x,y) (i > 1) 
    显然F(i,x,y)可以这样算出来，设其中有h件１装备，l件２装备在i车中，则F(i,x,y) = 
    F(i - 1,x - h,y - l) + 第i车中剩余的空间能够装下的最多的第３种装备的数量， 
    取F为这些所有的h,l的最大值，当然如果这样的h,l都找不到，则标记为函数值为-1 
    即不可行 
    
    最后得到F(n,x,y) 
    
    
    使用这个结果即可得到题目的解答 
    所有车辆中装x,y件１装备，２装备的时候还能够装下多少的３装备为F(n,x,y) 
    这些装备可以组成的组合装备套数可以马上得到，能够达到的最大防御里也可得到 
    遍历所有可能的x,y即可得到题目所求答案
    
    ZOJ 1022 Parallel Expectations 还是一道麻烦的题，首先要翻译成机器语言，然后开二维数组，存放双方运行到当前状态的值。因为只有加减，直觉（？）上感觉可以存放平均值，那么此题就可解了。
    
    ZOJ 1037 首先和容易就想到找规律，如果可以一笔画，则直线距离，否则要走一个斜线。但是没有很好的动态规划算法。
    
    ZOJ 1039 Number Game 觉得是搜索题，每一个数加入后，要去掉所有他的倍数，以及他与所有不允许的数的和（？），或者考虑动态规划，一共２^２０的状态，模拟游戏，算出所有状态的解。即构造解树。有一个假设，每个状态应该只有一个可行的出现状态。不然的话结会不唯一。不知道这种方法算不算搜索树构造动态规划的解？
    
    ZOJ 1052 题目读的好不容易啊！我感觉会用一个while(flag){ up() ；}的算法，计算每次各个容器里还能有什么。然后更新，最后再看看能否变化。得出解。感觉类似于模拟。
    
    ZOJ 1058 Currency Exchange感觉不是动态规划，更像模拟，只要注意舍入就行。
    
    ZOJ 1076 Gene Assembly 首先要定义struct，其次定义排序，可以先按大数正序，再按小数反序排序。从小至大，如果两个大数相同，则舍去小数小的（即后者）。然后利用基因位置，递推，计算到达某一位置时的最大值，可以先赋以前者的值，如果有基因以次为尾，则比较更新。利用struct的排序数组，可以加快速度。
    
    ZOJ 1092 Arbitrage 可以抽象为仁两点之间的最短距离，用三层for循环实现即可，最短距离==最大换算
    
    ZOJ 1093 Monkey and Banana  由于一块可以看成三个不同的块，所以扩充方块，简化题目，使规模成为90，其实进行排序，首先是长，其次是宽。每增加一个计算其放在前面每一个上的最大值。复杂度n*n，这道题也可以反着做，似乎能更快点。
    
    ZOJ 1094 Matrix Chain Multiplication 似乎又不是动态规划，重点只是求值，利用堆栈，即可实现。利用函数模拟也行，遇见左括号，加深一层，遇见右括号返回。
    
    ZOJ 1100 Mondriaan s Dream 被称为简单题？引用一下别人的讲解吧
    Assume you could calculate the number of different paintings for a rectangle with c columns and r rows where the first r-1 rows are completely filled and the last row has any of 2c possible patterns. Then, by trying all variations of filling the last row where small rectangles may be spilled into a further row, you can calculate the number of different paintings for a rectangle with r+1 rows where the first r rows are completely filled and the last row again has any pattern. 
    This straightforwardly leads to a dynamic programming solution. All possible ways of filling a row part of which may already be occupied and spilling into the next row creating a new pattern are genrated by backtracking over a row. Viewing these as transitions from a pattern to another pattern, their number is given by the recursive equation Tc = 2 Tc-1 + Tc-2. Its solution is asymptotically exponential with a base of sqrt(2)+1, which is not a problem for c<=11. 
    If both h and w are odd, the result is 0. Since the number of paintings is a symmetric function, the number of columns should be chosen as the smaller of the two input numbers whenever possible to improve run-time behaviour substantially. 
    Judges  test data includes all 121 legal combinations of h and w. 
    
    ZOJ 1103 Hike on a graph宽度搜索，50*50*50的复杂度,从一个状态，察看能否分成的状态。
    
    ZOJ 1107 Fat Mouse and Cheese 从起点开始，更新其所能到达的点的move值，取较大值，然后每次都选取一个最小的值，让他去更新。或者直接按照cheese的大小排序，按照这样的顺序更新。复杂度100*100*k
    
    ZOJ 1134 Strategic Game 使用backtrack算法，从叶节点开始，一步一步计算，每上升到一个父节点，分开考虑以下情况：任一个字节点选中的最小值，父节点选中的最小值。
    
    ZOJ 1136 Multiple 宽度搜索来构造除法，从起始最小数开始，做除法，保留余数，利用余数构造新数来进行计算。
    
    ZOJ 1147 Formatting Text 只需要记录前ｋ个单词保存为行，并且最后一个在最后所能得到的最小值，扩充时，令新加的在最后，前面添加，中间距离为平均值。
    
    ZOJ 1148 The Game 算出可以一步到达的点对，然后用两点之间距离的算法，或者仅仅用宽度搜索。
    ZOJ 1161 Gone Fishing 假设只用前ｋ个，则先将移动时间减去，然后再贪心，比较所有解。
    
    ZOJ 1180 Self Numbers 从前往后计算，要开一个大的bool数组，如果为０则计算
    
    ZOJ 1192 It’s not a Bug，It’s a Feature. 2^20个状态，宽度搜索。
    
    ZOJ 1196 Fast Food 前n个点，开k家店，每新加一个，假设最后一个开在后L个中，其余的k-1个在前n-L中。再利用在k个中开店，应把分配点放在中间则可。
    
    ZOJ 1206 With the Bonus 对于每个位置，需要计算所有两位的情况，状态一共10000*100*10，得出最小的。中间可以部分优化，一定要从后往前推。这样才能构造最优解！
    
    ZOJ 1213 Lubmer Cutting 首先想到的是预处理，将每个部分加上切割的浪费，再将总长也加上，就成了背包问题。如果只是１２个的话硬搜应该可以。
    
    ZOJ 1227 Free Candies 如果只有四堆的话，状态数是40^4，所以可以用动态规划解，每次考虑一个能被变化到的状态，由于这时候所有被取出来的已经消掉了，那么剩下来的是确定的，所以仅仅是宽度搜索就行了。
    
    ZOJ 1234 Chopsticks 这道题里面有的筷子可以不用，似乎增加了难度。而解题最重要的诀窍就是先不要考虑选最长的筷子，那么动态规划的时候每增加一个筷子，可以有两种方式，１　和最近的构成一双　２　不使用。感觉应该保存的是由前ｘ个构成ｍ个所得的最小值。于是复杂度是n*k，最后再考虑最长的，从后往前选，逐次去掉最长的，一直要凑够去掉的为止。
    
    ZOJ 1245 Triangles 以前做的，但是居然看不懂自己写的了：）不过有个n^3的算法，共有三种类型的三角，现仅考虑一种，每递推新一行的时候，每多一个节点，找出它前面最长的乡邻位，再比较他上一排对应的点的值，取小值。存储。如果能预处理的话。应该能减到n^2，具体的方式就是，寻找相邻位的时候，与其前面的那个点比较！
    
    ZOJ 1250 Always On the Run 首先可以利用整除来模拟构造每天的时刻表，动态规划用来递推每天可以到达的城市。
    
    ZOJ 1255 The Path 不像是动态规划，仅仅依靠搜索就行，只需要将屏幕的块分类为１，２如果可以连，则输出正确，如果加一块能将１，２互连则输出另外结果。不过如果只是用简单的动态规划模拟，每加入一个，就判断他的连通性，可能也能解题。
    
    ZOJ 1276 Optimal Array Multiplication Sequence 基本的动态规划，从两两算起，再三三，直到ｎ，每次分为两部分求值。
    
    ZOJ 1301 The New Villa 首先想到的就是宽度搜索，灯状态*所在的屋子=10*2^10，可以保存，一步一步类推。即可得解。
    
    ZOJ 1303 Jury Compromise首先将两个值相减，最后求得就是绝对值最小的，利用层数递推每次最多20(层)*20*20（数）*200，但可以剪枝，例如每层最大数纪录，如果先排序的话，算到正的某个数，就会知道肯定是递增的，以此剪枝。
    所以要注意动态规划的剪枝！
    
    ZOJ 1345 Best Deal 题目有点不太明白，但是大意应该是从最底层开始向上递推或者化成有向路。不知道是否会有环。选择要支付最少的钱的？还是选择能折合最多钱的？从所有点一起出发？路线长度可以换成支付钱数，但是路线要限制。还是不太理解题意。
    
    ZOJ 1396 The Umbrella Problem 典型题，递推的时候只需要依据规则计算每一排能到达的位置，以此类推，得到结果。
    
    ZOJ 1409 Communication System 首先还是排序，依据发射范围从大到小，然后是价钱。从上向下递推，每考虑一个的时候，如果价钱比以前的还高，排除，否则将其放入，并比较最优值（这里要注意只有当所有的都选择了以后才能比较更新），最后得出最优值。
    
    ZOJ 1425 Crossed Matchings 由[i，j]再推新的[i，j+1]时，赋初值[i，j],然后让第j+1个与前面的匹配，由贪心原则知，在其枚举时，另一行的只有与与其最近的可以得最优值。n^4的复杂度。如果考虑到数据的预处，则可能更优。
    
    ZOJ 1438 Asteroids 很简单的宽度搜索，但主要是3维，注意一下就行。
    
    ZOJ 1459 String Distance and Transform Process 很典型的题，主要比较前m个与后n个的最优值，只是纪录一下中间的变化就行，再构造出来结果。
    
    ZOJ 1462 Team Them Up 没有太多想法，感觉是从人数开始递增，但是状态很多，无法确定状态集。如果能事先找到所有的互相认识的集合就好了。但似乎又是有很多，如何才能简化？如果状态不过，可以记录前k个人的分发，依次递推。
    
    ZOJ 1479 Dweep 确实很无聊的题，很简单但又麻烦的宽度搜索。
    
    ZOJ 1499 Increasing Sequences 保存到ｋ位时所能求出的最小值。
    
    ZOJ 1520 Duty Free Shop 值需要记录分完前k个，第一种巧克力还剩多少（因为可以推出第二中还剩多少），以此类推得出结果。
    
    ZOJ 1524 Supermarket 保存购物数组，记录当前时刻如果购买各种物品所需花费的最少钱。当然得到一个新的数，然后更新当前数组。即可得解。
    
    ZOJ 1536 Labyrinth 由初始图开始进行计算，每次都得到一个更新图，在每次迭代，以次考虑每个点，以及其每个可行的路线，如果可以，就进行累加，的新图，推知答案。
    
    ZOJ 1556 Heroes Of Might And Magic 共要走50步，每一刻的状态集是：100(HP)*N(位置)*10(MP)*10(NM), 所以可以解。
    
    ZOJ 1587 UP 100 不知道宽度搜索行不行。题是看起来太麻烦了。
    
    ZOJ 1066 Squire Ice 据说很难，想了想，类似于点灯问题，从上到下计算，第一行至少有一个1，所以根据这个算出第一行的情况，然后一行一行递推，得解