前言 寒假康复训练Day1，差点爆零了qwq。 题解 C - Konrad and Company Evaluation 题目要求维护，修改是把指向某个点的入边全部改成出边。考虑对点按照度数不升序排序，那么我们尝试分成两部分来做。1.对于位于左边的点，与相连的点必不可能超过。若超过，则说明有超过个点在左边且他们的度数都大于，总度数也大于，显然矛盾。因此，我们每次最多将条从左往右的边改成从右往左。2.对于位于右边的点，我们这样考虑：刚开始从右指向左的总边数不超过，且每次修改最多新增条，那么显然总共出现过的从右往左的边数不可能超过，这一步修改的总边数也不超过这个数。用维护每个点的入边，每次暴力修改...

前言 挺好一开局，要是D没被卡能把E也写了说不定还能上橙，可惜。 题解 F - Cards 题目要求 把分母拿掉，只考虑分子。根据第二类斯特林数的性质有 代入上式得 交换求和得 把组合数拆开得 化简得 再给后面的组合数乘点东西 于是就变成了 用替换，得到 最终的式子为 第二类斯特林数预处理,求解。

前言 可能当场上橙的场次，字符串防题根本看不到啊，虽然赛后也写了好久qwq。 题解 D - Tree Elimination 等价于求不同操作序列的个数，考虑树形。令为以为根的子树在节点的删除情况为的方案数，为的父亲。共三种： ，在遇到节点前被删除。 ，在遇到节点时被删除。 ，在遇到节点后被删除。 显然三个状态相互独立，考虑如何转移。将的个儿子按照排序，其中，。 如果在遇到之前被删除，那么必然在与某个儿子 相遇时被删除。依次考虑这样的，如果被删除,则必须在遇到之后被删除，则 需在遇到之前或者遇到时被删除， 则可以在遇到前被删除或遇到之后被删除但是不能在遇到时被删除。于是显然有。 如果在遇...

前言 离橙名最近的一场 题解 A - Beautiful Regional Contest 金牌只给题数最多的，然后尝试把剩下两组分成两份，每一份都比金牌人数多。 B - Beautiful Sequence 左边中间右边这样构造。 C - Beautiful Mirrors with queries 令表示为从到的期望天数。 ，那么显然后，显然有规律显然，修改无非就是把一个段切成很多个段，分别求上述值然后求和。预处理后缀积及其后缀和，用即可维护。

前言 自闭场。 题解 A - Ivan the Fool and the Probability Theory 玩一会儿（一个小时）数据以后发现答案等价于用和组成答案为或的加法式子的方案数。

前言 签到即结束，当场暴毙。 题解 A - Tile Painting 若只有一个质因数，则答案为该质因数。若有两个以上质因数，则答案为. B - 0-1 MST 显然答案为，然后我就自闭了。维护一个链表记录未被访问过的点。然后对每个未被访问过的点进行。假设当前访问到，枚举下一个点的时候就遍历这个链表，显然要么因为这条边不存在而被跳过，这部分的总复杂度为，要么就访问导致从链表中被删除，这部分复杂度为，总复杂度为。 C - Sum Balance

前言 Hape线段树题调一年我真是佛辣。 题解 A - Valeriy and Deque 发现次操作后，最大元素一定在队列顶部，这之后的每次操作就是将第二个元素放到队列尾，因此模拟前次操作即可。 B - Tolik and His Uncle 对于最左边的一列和最右边的一列考虑如下构造法，从两边往之间缩。 C - Serge and Dining Room 考虑维护值域的后缀和，如果不带修改，就是找到最大的使得带修改的话考虑区间加减，维护区间的最大值，在线段树上二分查找每个询问。 D - Fedor Runs for President 最大化基环树简单路径条数。即要求环上最小。树形套斜率优...

前言 康复训练Day3掉分辣，心疼死辣，区间翻转一生之敌。 题解 A - Messy 我的做法太憨了就8说了。赛后学长说次操作可以构造任意一个括号序列，每次操作一定可以在一个位置上放上你想放的左/右括号，所以就构造就完事了。 B - Optimal Subsequences 优先选值大的，如果值相等则优先选下标小的，按这个标准排序后前个就是长度为的目标序列，每次询问要求前个数中下标第小的，可以离线下来平衡树也可以直接上主席树。 C - Arson In Berland Forest 发现这个T具有二分性，如果T可行，对于任意t<T一定也可行。那么就二分这个T，把能点的树（指影响范围内的全...

前言 康复训练Day2。wdnmd又双叒叕是赛后1A。 题解 A - p-binary 考虑是否存在使得能被表示成个之和，即二进制表示中的个数小于等于且本身大于等于。暴力枚举就行辣。 B - Power Products 用一个长度为的记录每个数小于的质因子的次数对取模的情况，并根据剩余的最大质因子存放到对应的中，对每个数求一个补集然后查询补集出现次数就好了。 C - Rock Is Push 假设没有石头。记为在这个位置先向下走走到的方案数，为在这个位置先向右走到的方案数。那么显然有转移方程还有。分析发现被推过去的石头并不影响转弯之后的走法，只影响能沿着推石头的方向走多远，即状态转移的范围。...

前言 康复训练Day1，2019.11.21 10:10--12:10。场上写了A和B1，B2刚调完没交上赛后一发T了很窒息，关电脑准备去吃饭的时候突然想到一个T的点再打开电脑改了一下就A了。A调了一年，B1手欠写跪WA了一年，这场如果状态再好点现场打应该是可以冲个橙名的。还行吧离目标还有些距离。 题解 A - Feeding Chicken S型贪心取格子，取到的格子肯定是连通的，取到足够的R后换下个字符。 B - Send Boxes to Alice 假设共有个礼物，那么。并且对于每个可能的而言，最小费用一定是把每相邻的一段个礼物挪到这一段礼物最中间的那个所在的箱子。对于每个都可以计算费...

前言 来提供一种跑得还行(1872ms)并且比较好想(连我这个刚知道启发式合并还不会敲的人都想到了)的的做法。比赛时启发式合并那部分交给队友敲了，这几天学了一波启发式合并自己试着敲了一发，就顺便来写个博客。 题意 大概就是给你一个字符串，让你统计有多少子串可以有k个相同的字符串首位相接得到。 思路 考虑每一个子串是否可以向后延伸k-1倍，如果可以，显然对答案贡献+1.子串能往后延伸当且仅当。显然答案可以表示成。即对于任意两个后缀，只要他们的大于，就会令答案+1。我们反过来考虑，这等价于，对于任意两个前缀，只要他们的最长公共后缀大于，就会令答案+1。两个前缀的最长公共后缀等于他们的节点在后缀自动...

emmmm就是关于这个题 https://ac.nowcoder.com/acm/contest/159/F 题解是这么讲的 二分是懂了，但是后缀i+1——j中与后缀i LCP最长的后缀j'不知道怎么快速搞出来。 根据后缀数组中排名越近lcp越大的性质，所以我有个***树log复杂度求区间离x最近的数的想法，但是这个nlog^2的想法T掉了ovo 代码在这里 本地大数据跑12s心态崩了，不知道有什么地方可以优化，还是说有更优秀的求法 https://ac.nowcoder.com/acm/contest/view-submissio...