最近也是一直找不到特别好的题目做（好吧其实是我自己比较颓），感觉BZ上的题太多是大家理性愉悦的产物实在是做不动，POI已经做了几届也不想再做下去了，PA实在是太神了不懂波兰文实在是对不起啊，CF的话今天随便找了一场vp结果过了AB后颓了一个多小时...所以最后还是跟着策爷做TC吧呜呜呜。既然TCO2013在picks的博客上有中文题面+题解那么就做它吧。

[4.7]完结撒花，爽！TCO的题果然非常有趣（感觉比BZOJ什么的高明到不知道哪里去了呢）

现在做了几题

36

【TCO13 Round 1A 250】HouseBuilding 直接枚举最后是哪两个数暴力算就好了。

【TCO13 Round 1A 500】TheForg 显然最优答案一定是经过了某一个线段的端点，枚举这个端点再枚举从原点跳到这个端点经过了多少步然后枚举每一条线段判断就好了。被卡常数FST实在是爽（明明是你忘记break了）

【TCO13 Round 1A 1000】DirectionBoard 同TJOI2013循环格，样例都一样这位省选出题人到底是什么心态> >

【TCO13 Round 1B 250】EllysPairs 从小到大排序一次拿第[tex]i[/tex]小的和第[tex]i[/tex]大的配对，计算答案。

【TCO13 Round 1B 500】EllysFigurines 爆枚一维的消除状态，另外一维直接贪心取

【TCO13 Round 1B 1000】EllysReversals 这题还是挺simple的，自己开始傻逼了一下。如果没有偶数的要求显然所有排列都可以达成，有了这个限制可以每两个设为一组，因为可以翻转前两个字符所以每一组的相对顺序和组内两个字符的顺序都是不要紧的。开始傻逼没有判奇数串剩下那个字符是否相等愉快FST了爽！

【TCO13 Round 1C 250】TheArray 枚举最大值出现在哪一个位置，那么它的取值一定是对从两端开始一直走[tex]d[/tex]走到这个位置时的值取min。

【TCO13 Round 1C 500】TheOlympiadInInformatics 二分答案，然后直接扫一遍贪心判定。

【TCO13 Round 1C 1000】TheKnights 显然每一个位置的贡献是独立的，只要计算每一个位置被控制的概率就好了。可以发现大部分位置是等价的，我们可以根据[tex]a,\ b[/tex]把棋盘划分成至多[tex]5 \times 5[/tex]个等价的区域，每一个区域就暴力好了。

【TCO13 Round 2A 300】TheLargestString 开始各种想贪心，然后各种WA样例，样例良心实在是喜闻乐见。最后还是只能DP解了。令[tex]dp_{i,j}[/tex]表示前[tex]i[/tex]个字符取了[tex]j[/tex]个的最优解，然后就可以转移了。

【TCO13 Round 2A 600】TheMagicMatrix 可以发现一个[tex]n\times n[/tex]的满足条件矩阵和由一个边长[tex]n-1[/tex]的矩阵与一个0到9之间的整数（每行每列和模10的值）组成的二元组一一对应。那么如果存在一行一列没有限制，就可以直接用公式[tex]10^{(n-1)^2-m+1}[/tex]得到答案，否则就用高斯消元，把模10拆成模2和模5分别计算自由元个数就好了。

【TCO13 Round 2A 1000】ThePowers 这题好神啊。。首先把可以被表示成[tex]i^j(j >1)[/tex]的数删掉，然后按照在[tex][1,A][/tex]范围内出现的最大次幂对剩下的数分组。然后问题就变成了[tex]i \in [1,x],\ j \in [1,B][/tex]，问[tex]ij[/tex]的取值个数，因为[tex]x[/tex]很小，我们可以分别求[tex]ij[/tex]在[tex][(k-1)B+1,kB][/tex]，这样就可以直接用容斥搞了。开始gcd的地方忘记开long long调了一个多小时真是不能多说。

【TCO13 Round 2B 250】FruitTrees 分别考虑每两种树之间的贡献，令[tex]f_i[/tex]为两种树中有一对距离是[tex]i[/tex]时的最近距离，这个求了间距的gcd之后可以暴力搞，然后枚举三种树中起始位置的相对距离得到答案。

【TCO13 Round 2B 500】ScotlandYard 令[tex]f_{i,j}[/tex]为第[tex]i[/tex]个城市和第[tex]j[/tex]个城市往后最多多少步才不能得到两条等价的路径。然后就是记忆搜大法，如果出现了环答案就是-1。

【TCO13 Round 2B 1000】LitPanels 细节题真TM恶心..枚举包围所有染色点的最小矩形框，那么一定存在一种覆盖方案使得两个矩形占据左上、右下或者左下、右上角，然后容斥一下就可以得到答案。

【TCO13 Round 2C 250】DancingFoxes 首先求出最短路，然后要求的就是两个距离为[tex]i[/tex]的人要跳多少次舞才能成为朋友，可以考虑贪心的模拟跳舞的过程，每一次跳舞都尽可以能地缩小两个人之间的距离，这样每一次跳舞距离都缩减到原来的[tex]\frac{2}{3}[/tex]级别，直接模拟然后输出就好了。

【TCO13 Round 2C 550】TheMountain 开始有一个非常naive的[tex]O(n^4)[/tex]做法，枚举山峰的中心，然后贪心的从周围往中心填数字。然后我们先枚举行，然后依次枚举列，把山峰的贡献分成左边和右边两部分，可以发现以[tex](i,j)[/tex]的中心的和以[tex](i,j-1)[/tex]为中心的山峰在[tex]j-1[/tex]左侧的部分是完全一样的，所以左边就可以直接贪心地递推。最后合并一下就好了。

【TCO13 Round 2C 1000】WellTimedSearch 相当于询问[tex]n[/tex]个点的二叉树中深度在[tex][L,R][/tex]中的点数最多有多少个，这个可以直接枚举第[tex]L[/tex]层有多少个点然后贪心。

【TCO13 Round 3A 250】YetAnotherANDProblem 显然在队列里的一定是由原集合中的一个子集and起来得到的数，如果一个数可以由[tex]\geq 3[/tex]个数and得到，那么他出现的时候一定有至少三个相同的数同时出现，所以它就会一直存在队列中，然后特判一下[tex]K \leq 1[/tex]的情况就好了。

【TCO13 Round 3A 550】Block3Checkers 好有趣的题，开始没有看到三个点都在边界的条件然后怎么也不会做，于是去膜拜了官方题解。三个A点把边界分成了三段，把图转成八连通，障碍点视为可以通过的点，最终的目标就是使得这三段联通。然后分路径相交和不相交两种情况考虑，枚举中间节点然后最短路即可。

【TCO13 Round 3A 1000】TrickyInequality 把最后[tex]m-n[/tex]个数的方案数看成关于前[tex]n[/tex]个数的和的多项式，然后要做的就是求出前[tex]n[/tex]个数的所有方案中和的[tex]i(0 \leq i \leq m-n)[/tex]次方的值，这个可以用矩乘解决。

【TCO13 Round 3B 250】SimilarSequences 大力出奇迹！把所有可能的数列都表示出来（插入的量用-1表示），然后按照-1的位置排序，然后把这些数列一个一个纳入答案，每纳入一个就和前面的数列对比一下去重，这样就可以无脑[tex]O(n^5)[/tex]了，稍微优化一下可以[tex]O(n^3)[/tex]但是既然这个能过我就没有去管了。

【TCO13 Round 3B 450】AntlerSwapping 首先如果一个集合的鹿经过若干次交换之后可以让所有鹿都平衡，那么一定存在交换次数小于集合大小的方案（相当于找一颗最大的生成森林）。于是就可以状压DP，每一个状态只可能由自己内部交换或者由两个子集合并而来，内部交换的次数可以直接视为集合大小-1，因为更优的值一定可以从子集中合并上来。判断一个集合能不能都平衡只要对角的大小排序即可。

【TCO13 Round 3B 1000】ToastJumping 第一步能跳到的点是一个凸包内的所有整点，可以证明[tex]k[/tex]步之后的点和这个凸包是相似的。然后就只需要二分步数然后判断询问点是不是在放大了[tex]k[/tex]倍的凸包里就好了。

【TCO13 Semifinal 1 300】RabbitsAndCakes 找规律大法好，打表可以找出来蛋糕数为[tex]C[/tex]时，兔子数小于等于[tex]C[/tex]或者兔子数为[tex]C[/tex]加上一个[tex]C[/tex]的约数时有解。然后就可以随便搞了。

【TCO13 Semifinal 1 550】TheGameDAG 一道有趣的题目，数据范围这么小肯定就是状压大法了。令[tex]dp_{i,j,k}[/tex]表示当前到了第[tex]i[/tex]个位置，集合[tex]j[/tex]的点可以选，是否已经选了[tex]s[/tex]到[tex]t[/tex]的边时的图有多少个（按照题目中的算法算贡献），显然对[tex]j[/tex]有贡献的只有连向每一个点的边中来自原序列中最靠后的那个，于是枚举从[tex]i[/tex]出发连向哪一个集合是最后一条边，其他边可以随便连，讨论一下[tex]k[/tex]就好了。

【TCO13 Semifinal 1 950】GameWithTree 感觉这题比550容易？虽然我不会证明。我们可以猜测所有点都是独立的，那么一个点的贡献之和这个点的深度有关而和子树形态无关（有多个相同深度的它们异或起来sg函数贡献至多为1倍）。然后考虑求sg函数，考虑以[tex]i[/tex]为根的子树，如果我们不选[tex]i[/tex]的孩子，那么情况和[tex]i[/tex]的孩子一样，否则相当于所有情况都异或上[tex]i[/tex]的孩子的sg值，显然一颗深度为[tex]i[/tex]的子树的sg函数值就是[tex]2^{i-1}[/tex]，然后DFS一遍就好了。

【TCO13 Semifinal 2 250】GoodNumbers 显然可以容斥，于是就要求同时满足在[tex]i[/tex]集合中的限制的数有多少个，这个可以再套一层容斥搞，复杂度差不多是[tex]O(n3^n)[/tex]的样子。

【TCO13 Semifinal 2 550】JumpingOnTheGrid 对于每一种方案我们在最后一个停留加能量的位置截断成两段。然后令[tex]f_{i,j,k}[/tex]表示从起点开始花了[tex]k[/tex]的时间走到了[tex](i,j)[/tex]时剩下的最多能量，令[tex]g_{i,j,k}[/tex]为从[tex](i,j)[/tex]开始花[tex]k[/tex]步走到终点的最少能量。显然最后停留的位置就是整条路径中单位时间能加最多能量的位置，而走到终点花的最大能量是有限的，所以我们最多只需要停留[tex]O(nm)[/tex]的时间一定可以到达终点，所以我们[tex]k[/tex]只需要枚举[tex]O(nm)[/tex]的时间，剩下多余的时间一定在[tex](i,j)[/tex]加能量，维护一下前缀max啥的合并一下就好了。

【TCO13 Semifinal 2 950】OneBlack 不能由左上角到达或不能到达右下角的点对答案没有影响，我们可以先把它设为障碍点然后答案乘上2。对于其他的点，对偶后只要考虑从左下到右上有多少条路径就好了，这是一个DAG直接DP一遍即可。

【TCO13 Wildcard Round 250】TheFourSquares 开始没有注意到对角线两个可能会相交然后就摆烂了..可以枚举长边上的分割线，然后就变成了两个正方形的问题，直接预处理一下随便搞搞就好了。

【TCO13 Wildcard Round 450】ModuloCounters 开始怎么也不会做啊...后来索性乱搞，想了一个很松的限制：相邻两个房间的人数和大于等于总人数，每一个房间的人数小于等于总人数，然后最小化总人数。这么写了一发居然A了..正确性我也不会证明。

【TCO13 Wildcard Round 1000】SemiMultiple 挣扎了一段时间还是决定去膜鏼了..大致就是先把模数变成奇数，然后把对模数同余的二进制位给拿出来与其他位分开考虑，在求其他位同余[tex]i[/tex]的方案数时可以考虑在总方案中剔除拿出来的二进制位的贡献，剔除每一位的时候相当于解一个方程组，因为模数是奇数所以这个方程组的每一个约数构成了一个环，这样就可以[tex]O(m)[/tex]解出。然后统计方案就好了。

【TCO13 Finals 300】ScoringSystems 开始跑一个背包，[tex]f_i[/tex]表示在第一种评分方式中得分为[tex]i[/tex]的集合在第二种方案中得分是多少，如果发现同一个得分有多种方式，那么一定不合法，最后再记一个前缀max扫一遍就好了。

【TCO13 Finals 400】PackingSquares 贪贪贪..显然是从大到小能放就放，同一个大小的最多放一个正方形，然后我们插入到边长为[tex]2^i[/tex]的正方形的时候，把能放到比它大的正方形上面的全部都丢到比它大的正方形上面，留下剩下的最后一个当做放以后的正方形的平台，一直做下去就好了。

【TCO13 Finals 1000】TBlocks 一开始被鏼爷剧透说是讨论题然后就失去了思考的勇气..膜了题解发现真TM是讨论题。首先枚举所有不确定的位置的状态，把问题变成一些位置一定放在中央。然后把冲突的点之间连上标为冲突种类的边，用并查集维护一下连通性，最后分类讨论累积答案。写起来也不是想象中的那么难写。