【FAKE-ACM】2017-CCPC-FINAL泛刷总结

感觉这个CCPC-FINAL的题目非常 常规啊，感觉不少题目都能 很快口胡，作为一个向往WF的OIer，自然要刷刷国内的 毒瘤题目来提高下姿势水平辣~ 另外就是我写/看最后几题的时候HDU挂掉了……导致看不了题目

【A：Dogs and Cages】 题意：给定一个排列，问随机打乱之后期望有多少个数不在原来位置上 分析：利用归纳法的思路，考虑 n=1,2,3… ，然后会发现期望就是 1 ，因为每次在期望方案数上乘 n 的同时分母也乘了 n 另外也可以解释成每个数期望 1/n 在原来位置上，然后乘一下 n 个数就好了

【B：Same Digit】 题意：规定你只能用 D 来组成数字，然后要求你用加减乘除、开方、乘方、阶乘来构造出一个式子使其值为给定的 N ，问最少要用多少个 D 分析：感觉是道神题……不过似乎还挺可做的 因为最后得到的是个整数，所以开方出无理数之后必须要消掉，然后阶乘的数肯定都不能太大，可以稍微预处理出一点数字来 然后不知道怎么做了……感觉应该是IDA*之类的做法，因为这个东西很容易深度扩展到无限啥的

【C:Rich Game】 题意：按照羽毛球赛的规则打比赛，如果你得一分少 X 元，输一分你得 Y 元，一开始没有钱，怎样在不透支的情况下安排比分赢得最多比赛 分析：很明显如果一定要输那么就是 0:11 输（拿最多钱），反之肯定 11:9 赢最好

【D:Mr. Panda and Circles】 题意：给出若干个长度为 2Ri 的区间，问如果让这些区间中心都处在 [0,M−1] 范围内，不允许重叠（允许有空），所有空位的平方和是多少 分析：考虑第一个和最后一个区间，相当于我们现在限制的是区间的覆盖范围，接着先从这个角度写个母函数出来： ∏i=1n(x2Ri+1) 然后如果我们考虑开头结尾的那两个怎么选，然后毕竟可以开头一个结尾一个大概是 ∑j=0Rij 这样的一个式子，对每个 i 可能都有这样的选择，进行枚举然后强行放进去，最后对母函数分治FFT就好 了

【E:Evil Forest】 题意：给出若干个数，问所有数 ×1.1 向上取整的和 分析：直接做

【F：Fair Lottery】 //留坑待填……

【G：Alice’s Stamps】 题意：给你 n 种邮票， m 个邮票集合，每个邮票集合包含邮票种类区间 [l,r] ，问取最多 k 个集合的时候的最多邮票种类 分析：很明显是个DP，考虑 f(i,j) 表示前 i 个选 j 个集合，那么这里因为集合的先后没有区别，因此可以引入一个序，这时候就比较类似于选取区间最多的问题了，对 l 排序，每次取距离 i 最远的 r 来更新（延伸最长），直接转移的时候顺便记一下就好了

【H：Equidistance】 //留坑待填……

【I：Inkopolis】 题意：给出一棵基环树，兹瓷改边上颜色和同颜色连通块个数的操作 分析：既然是一棵基环树，说明影响其实比较有限 考虑树上的情况，注意因为颜色个数可能比较多，我们可以考虑利用map存下每个点旁边各种颜色的存在情况，然后如果改一条边，考虑这条边所涉及到的两个点那里的贡献即可 然后考虑环，其实也是一样的，只不过比较麻烦一点 找环直接DFS或者Tarjan应该都可以

【J：Subway Chasing】 题意：一条直线上有 n 个点，两个人在直线上走，保持x的距离 告诉你 m 条信息，告诉你一个人在 a 和 b 之间时，另一个人在 c 和 d 之间，其中 b 为 a 或者 a+1 ， d 为 c 或者 c+1 问这些信息是否矛盾，如果不矛盾，求相邻两点之间的最小距离 分析：不妨设某个点相对起始点为 di 的距离，然后我们很容易列出相应的方程，构造出若干个形如 di−dj≤X 的不等式，然后差分约束解即可

【K：Knightmare】 题意：给你一个无限大的平面，从一个点开始，按照中国象棋马跳日字的方式，每一次可以跳八个方向，问第 n 次跳完后，一共跳过多少个地方 分析：很明显有规律性的东西存在，考虑对称性，点必定是延八个方向对称的，然后暴力BFS找规律之后就可以出答案了，不过 n≤7 小的时候特判下 答案是 (n−6)×176+(n−6)(n−7)2×28+473