这个题确实是，自己想没有整出来。由于多考虑了一层，状态变得复杂了。
首先还是转化为有根树去做，然后考虑下自底向上的推法。因为这里多考虑一层，所以还需要考虑子节点的放置情况，也就是除了考虑i节点放A/放B/不放，还需要考虑i的子节点，有没有放B/放A/不放，这样的话可以发现所有的情况到最后可以归类为4类，1）i处放B 2）i处放A且子节点放A/放B/没但是其字节点全放A/B，或者i处不放，其字节点至少有一个放B 3）i处不放，但是子节点全为2状态 4）能保证父节点放一个B就能覆盖到往下所有未覆盖路径的任意状态。然后就可以把状态转移方程搞出来，记忆化搜索即可。
自己思考存在的问题：脱离了无后效性这个基本点在想。如果按照一遍dfs来dp的思路，应该是保证了子树推出来之后才能推更高的祖先。
wa的话，因为用了一个cur的变量，之后再用却没有正确赋值。。。
这场前四个的难度跟后面的完全不是一个div的。。。abcd都很容易出的那种。。
然后今天这个E，怎么说，思路很容易想到，一看就是数位dp，然后也比较容易发现需要保存已经用过的数字集合，所以一个下标是状压的二进制。
然后我以为就这么开心的做了，但是操蛋的是，这个需要考虑很多前导0的情况。。然后我就写炸了。。。调了巨久。。。基本上后来就是各种特殊情况往上加，呵呵，虽然最后1y但是对我来说感觉做出来跟没做出来已经没什么区别了，浪费了n个小时（本来该看射频的啊啊啊啊啊啊啊啊凉凉
丑陋的各种特判代码先放这儿，等我去扒一扒前排大佬代码（其实cf那场也就不到100人A了这个题 继续阅读“[数位+状压][DP] codeforces 1073E Segment Sum”
首先可以确定要分一个trouble，那一定是等分，这一点可以从公式化简得到。
所以难的问题是，给每一个trouble分几个人。当没有什么做法/头绪的时候，想一想贪心递推的操作（贪心是因为这个题数据量不应该是dp），大问题是否可以从小问题转化过来，每次多一个人的时候，这个人应该放到哪儿？可以试着遍历每一个trouble看看放在哪里会使得变小最多，但是这样是M^2的做法，但是这时候考虑“哪里小的最多”这个条件，以及，+1之后哪里变小的最多是完全取决于trouble的数值和他当前已经有的人的，所以可以用一个优先队列来存储“哪里变小的最多”这个信息！这样的话就是M^logM的算法了，可以通过本题。
自己当时为什么想挫了？主要是一开始想的把一个划分之后可以看成两个新的数，但是事实并非如此，新分出来的和原来的是不等价的，同一个trouble分出来的可以互相组合，但是不同德trouble之间不能组合，所以这种思路可以否定。所以其实每次都要考虑所有的trouble，取变小最多的那个，想到这里又觉得是M^2的算法，又没有继续，但是这时候思路已经是对的了，就可以考虑可以用什么优化，尤其是这种最值/顺序之类的问题，可以多考虑数据结构优化。
自己思考的时候问题出在哪儿呢？还是没有挖掘和抓住问题的本质特征：要分成一段一段的，肯定是从一段一段的堆起来的过程过来的，如果能把这个过程还原，就可以判断出来是不是满足要求。一段的话，就有开头和结尾，然后开始找开头和结尾就可以了。自己的具有猜想性质的算法，如果不能及时证明，则应该换思路或者让队友去写样例试图证明，或者打样例表。
想出来差分之后，还有一个细节是如何判断3这个界限，其实有更简单的判断方法但是我这里写复杂了。但是整个题目重点还是在于逆向想到差分。
2019.7.10更新：今天翻到这个题发现自己以前写的是真诡异，写了个新的清爽版本。。。 继续阅读“[逆向思维][差分][细节][补题] Gym-101775J Straight Master”
之所以写这个题是因为他提供了一种新的解决问题的思路。。两个暴力算法结合起来竟然就不暴力了。。
首先直接暴力枚举每个set里的余数然后解同余方程组可以得到一个Πki复杂度的算法，但是这个在k太大的时候会爆，然后k很大的时候就用了同余方程的另一种暴力解法，找到一个同余方程枚举他的所有解然后去判断其他的等式是否满足。。。这个在k比较大的时候比较快（但是感觉这俩算法组合还是有点看RP
代码基本上都是抄的书上就这。不过调了下LIMIT的范围发现从100到500000都可以过。。
题意：给出一个多项式，判断它是不是在所有整数点都取值为整数。
一个屌丝做法就是可以每次都随机数，只要数量足够一定可以把非整数判断出来。正解是利用数组差分的操作和取模的性质，自己想真的想不到。。
其实如果考虑思考方向的话，对于数据，一开始的思路应该是，既然有100个阶那肯定不是用某种解析的方式去做，而是选择一些点代入判定。这样的话问题变成了代入哪些点。首先如果分母上的数字比较小，那么可以算0-D之间的所有数字，但是D也很大，就没办法这么算了。这时候可以发现唯一可操作的只有阶的数量，然后就应该往这个方面去想了。。。当然这个数学归纳法的差分确实是有难度的，很难想到。。
沈阳赛得来的教训：模拟一定要在纸上写好所有情况再敲代码。。。
https://cn.vjudge.net/problem/SPOJ-TSUM
跟焦作选拔的时候那个题目的思路完全一样，用母函数可以考虑到所有的情况，然后去掉三个重复的和两个重复的再除以6就得到了去重后的结果。
收获主要是发现了FFT那个乘法的操作可以全部在一次循环里完成。。。神奇。。还有就是移位操作可以避免复数，而输出的时候记着要移回去原位。 继续阅读“[母函数][容斥][FFT][模板] SPOJ TSUM Triple Sums”
一开始看了很久不知道怎么求被对角线覆盖到而没有被横纵覆盖到的格子数，后来忽然发现可以把没被占用的横纵坐标标记为1啊！这样两个卷积起来就是没有被横纵占用的对角线上的格子数量了！！！然后遍历每条对角线，如果被覆盖到了就减去这上面没有被横纵覆盖到的格子！
wa点：日常LL，以及他这个操蛋的横纵坐标标识法，有点难受，得把棋盘左右反转一下才好做。
评论区大佬：嗯这个题贪心很明显啦然后nlogn方法也有很多种
http://codeforces.com/contest/980/problem/E
要使得去掉一些点之后剩下的仍然是一棵树，那么去掉的一定是叶子或者某条路上的缩点后相当于叶子的子图。。描述有点困难自行yy。。然后如何选择去掉的点？可以发现，如果i<j，那么去掉j一定不如去掉小于j的所有数，因为2^j=2^(j-1)+2^(j-2)+2^(j-3)+…..+2+1，所以贪心策略就是能不去掉大的就不去，所以要从n-1开始一个一个找（由于k<n所以节点n一定不会被去掉），怎么确定一个点是否能被保留下来，只要确定这个点到最近的保留下来的点的距离小到可以满足去掉k个的要求（想一下，如果这个点离最近的保留点太远了，远到了如果保留这个就没法保证能去掉k个点了，那就肯定不能留了），要保留这个点一定也要保留从这个点往上回溯所有的点，然后就会发现在以root为根的树上，这个01标志是连续的分布的，也就是说有一段1111然后一段000，这样的话就可以二分求分界点，而树上的二分就是lca里的倍增算法了，用倍增法查找就可以在logn时间内找到分界点，找到之后判断是否满足要求，如果满足则把分界点到当前点都标记上保留（话说这样logn不就退化了吗。。。）
wa点是距离的处理和树上倍增往前跳的时候把cur写成了i。。。
ECNU的oj，题很多的样子。。。orz
附上一篇讲树上差分很不错的blog
初学树上差分第一题吧算是，简单的分析一下就可以发现只需要求出来各条边在query中被覆盖到的次数就可以了。利用边的树上差分很容易就能求出来。每次求出lca之后分为两条链，则cf[u]++,cf[v]++,cf[lca]-=2；即可处理完毕。最后推的时候用dfs从下往上推就可以了。
继续阅读“[LCA][树上差分] ECNU OJ 3631 Delivery Service”
