CF1575K Knitting Batik
首先不难分析，如果两个矩形不相交，方案数为 \(k^{nm-rc}\)；如果两个矩形完全重叠，方案数为 \(k^{nm}\)。
对于两个矩形不完全重叠的情况，显然在两个矩形之外的部分可以随意涂色，重点考虑两个矩形之间的一些限制。对于第一个矩形，在不与第二个矩形相交的部分没有限制，可以任意填色。在对这部分填色时，第二个矩形相应位置的颜色也就确定了，由于两个矩形相交，所以也对应了部分重叠位置的颜色，就是一个不断对应的过程，直至把两个矩形填满。
最后总结出来就是除了第二个矩形之外的位置都可以随意涂色，方案数就是 \(k^{nm-rc}\)。
CF1579G Minimal Coverage
设最长线段长度为 \(l_{max}\)。可以证明，最后的答案一定在 \(l_{max}\) 和 \(2\times l_{max}\) 之间。
我们发现这道题并没有一个保证正确性的一个贪心策略，对于每一条线段它向左或向右放置都是有可能的，当然前提是答案不能超过 \(2\times l_{max}\)，题中线段的长度并没有很大，考虑 dp。
dp 状态：\(dp_{i,l}\) 表示当前第 \(i\) 条线段的终点到最左边的距离为 \(l\) 时，到最右边的距离。最后的答案即为 \(\min(l+dp_{n,l})\)。
具体地，对于第 \(i\) 条线段，长度为 \(a_{i}\)，如果向左放，转移就是
\(dp_{i,\max(j-a_{i},0)}=\min(dp_{i,\max(j-a_{i},0)},dp_{i-1,j}+a_{i})\)
向右放时注意判断到左边界的距离不能超过 \(2\times l_{max}\)
\(dp_{i,j+a_{i}}=\min(dp_{i,j+a_{i}},\max(dp_{i-1,j}-a_{i},0))\)
CF1580C Train Maintenance
根号分治
发现火车使用是有周期性的，\(x_{i}+y_{i}\) 是它的周期。
对于 \(x_{i}+y_{i}>\sqrt{m}\) 的情况，最多只会有 \(\sqrt{m}\) 次贡献改变，所以我们暴力修改，记录一个差分数组。
对于 \(x_{i}+y_{i}\le \sqrt{m}\) 的情况，最多不会有超过 \(\sqrt{m}\) 种 \(x_{i}+y_{i}\)，我们对每一种 \(x_{i}+y_{i}\) 用一个数组记录以它为循环中每一天的具体贡献。统计答案时枚举每个循环长度，加上此天贡献即可。
注意删除时判断当前火车是否在修，若在修因对答案减 \(1\)。
CF1607G Banquet Preparations 1
设 \(suma=\sum_{i=1}^n a_{i}\)，\(sumb=\sum_{i=1}^n b_{i}\)，\(mxa=\sum_{i=1}^n\min(a_{i},m)\)，\(mxb=\sum_{i=1}^n\min(b_{i},m)\)
分别表示鱼肉总重、猪肉总重、最多能吃的鱼肉数量和最多能吃的猪肉数量。
不妨设 \(suma\ge sumb\)，\(suma<sumb\)时同理即可。
下面进行分类讨论：
1.\(suma-mxa\ge sumb\)，也就是说无论吃多少鱼肉，鱼肉总数都比猪肉总数多，此时就尽可能多地吃鱼肉，剩下的吃猪肉。
2.\(suma-mxa<sumb\)，此时我们很容易知道当 \(suma+sumb-n\times m\) 为奇数时答案为 \(1\)，\(suma+sumb-n\times m\) 为偶数时答案为 \(0\)。
下面我们来构造。
设答案为吃 \(x\) 克鱼肉，则会吃 \((n\times m-x)\) 克猪肉。
那么方程就是：\(suma-x=sumb-(n\times m-x)\)
解得：\(x=\frac{suma-sumb+n\times m}{2}\)
CF1607H Banquet Preparations 2
首先显然只有 \(a_{i}+b_{i}-m_{i}\) 相同的菜才有可能最后相同，所以先将 \(a_{i}+b_{i}-m_{i}\) 相同的菜分到一组，然后再考虑组内的划分。
对于第 \(i\) 道菜，我们设最后它的 \(a_{i}\) 变成了 \(x_{i}\)，这个 \(x_{i}\) 的取值一定是一段连续的区间，设这段区间为 \([l_{i},r_{i}]\)，那么有 \(l_{i}=\max(a_{i}-m_{i},0)\)，\(r_{i}=a_{i}-\max(m_{i}-b_{i},0)\)。
对于每道菜都求出 \(l_{i}\) 和 \(r_{i}\)，则最后两道菜在同一组的条件就是两道菜的区间 \(l\)，\(r\) 有交。
那问题就可以转化为在数轴上有若干条线段，我们要在数轴上放最少数量的点，满足每条线段上至少放一个点。
贪心
将区间按右端点从小到大排序。首先对于最左侧的线段，我们必须在上面放一个点，考虑贪心地将这个点放在最右侧，那么这个点所能覆盖的线段最后的答案相同，将这些线段删除，再重复操作。
CF1615D X(or)-mas Tree
发现我们只关注 popcount 的奇偶性，而 \(popcount(x\bigoplus y)\equiv popcount(x)+popcount(y)\pmod 2\)。所以我们可以直接将一条边的权值根据其 popcount 的奇偶性改为 \(0\) 或 \(1\)，那么所有的异或值只能为 \(0\) 或 \(1\) 了。
将路径上的异或和转化成两个点到根的距离的异或和。那么如果两个点之间的路径奇偶性等于 \(1\)，则这两个点到根的路径 popcount 不同（所有点到根的 popcount 只会是 \(0\) 或 \(1\)）；反之，则相同。
因此转化为了这样一道题：有两个集合，第 \(i\) 个条件表示 \(u\) 和 \(v\) 在同一个集合，或不在同一个集合，求出一组解。用扩展域并查集求解即可。
最后遍历整棵树，如果当前节点和它的子节点不在同一个集合，那么边权为 \(1\)，反之，就为 \(0\)。
CF1547G How Many Paths?
首先可以判断输出 \(-1\) 的就是可以经过环到达的点，输出 \(0\) 的就是从点 \(1\) 搜索不到的点。
从节点 \(1\) 做一次 dfs，开一个栈记录只经过而还未回溯的点，在遍历到它的时候将它加入栈顶，遍历结束弹出栈顶。那么对于一个节点 \(u\)，它的子节点 \(v\) 已经到过，则
1.\(v\) 在栈中，则构成一个环，打上 \(-1\) 的标记。
2.\(v\) 不在栈中，则到达 \(v\) 的路径有 \(\ge 2\) 条，打上 \(2\) 的标记。
对于打上 \(-1\) 和 \(2\) 标记的节点，它所能到达的节点也要被打上标记，但是注意 \(-1\) 标签可以覆盖 \(2\) 标签，但 \(2\) 不能覆盖 \(-1\)。
最后，还没有被打上标签的，节点 \(1\) 能够到达的点都被打上 \(1\) 标签，剩下的就是 \(0\) 标签了。
CF1555E Boring Segments
双指针
首先将线段按照权值排序，双指针的过程中，加入一条线段 \([l,r]\)，在线段树上将区间 \([l,r-1]\) 加一，删除该线段时就在线段树上将区间 \([l,r−1]\) 减一，判断区间是否被完全覆盖就查询 \([1,m-1]\) 的最小值是否大于零即可。
CF1575L Longest Array Deconstruction
考虑对于两个点 \(x\)，\(y\) \((x<y)\)，它们对答案有贡献的条件：
1.\(a_{x}<a_{y}\)
2.\(x-a_{x}\le y-a_{y}\)
\(x-a_{x}\) 表示在坐标 \(x\) 之前要删掉多少个数才能使 \(x=a_{x}\)，显然需要 \(x\) 前删掉的数的个数小于等于 \(y\) 之前删掉的数的个数。
同时，我们稍微推一下这个不等式，发现它也满足：\(x<y\)
所以这就变成了一个二位偏序的问题。
将所有数字按照 \(i-a_{i}\) 从小到大排序，然后求出 \(a_{i}\) 的最长上升子序列的长度，可以用二分或者树状数组求解。
CF1598E Staircases
很容易想到一个暴力的 dp，\(dp_{i,j,0/1}\) 表示以 \((i,j)\) 位置向右或向下的阶梯数量，转移就是 \(dp_{i,j,0}=dp_{i,j-1,1}+1\)，\(dp_{i,j,1}=dp_{i-1,i,0}+1\)。如果没有修改，答案就是 \(\sum_{i=1}^n \sum_{j=1}^m dp_{i,j,0}+dp_{i,j,1}-1\)。
考虑修改 \((x,y)\) 的贡献，即为加上或减去经过这个点的所有合法楼梯的数量，那么我们向四个方向搜索并组合，累计修改即可。
CF1606E Arena
发现每个英雄在每轮结束时受到的伤害是一样的，那么设 \(dp_{i,j}\) 表示还有 \(i\) 个英雄没死，对每个活着的英雄的总伤害为 \(j\) 的方案数。
明显我们不能让场上只有一个英雄剩下，那么在 dp 过程中忽略掉 \(i=1\) 的转移即可。
每一轮对每个英雄的伤害是 \(i-1\)，然后我们枚举剩下多少个英雄，将其设为 \(k\)，那 \(dp_{i,j}\) 可以转移到 \(dp_{k,min(j+(i-1),m)}\)，\(i-k\) 表示了在这一轮死了的人数，方案数需要乘上 \((min(j+(i-1),m)-j)^{i-k}\)。因为每个英雄是有标号的，所以转移的时候还要再乘上 \(C_{i}^{i-k}\)。
CF1593F Red-Black Number
因为 \(n\) 的范围很小，可以直接 dfs 搜索，一共四维状态，\(vis_{i,j,k,l}=0/1\) 表示当前到第 \(i\) 个数字，染成红色组成的数 \(\bmod A=j\)，染成黑色组成的数 \(\bmod B=k\)，染了 \(l\) 个红色的数字是否被搜到。复杂度 \(O(n^2 ab)\)。
CF1616E Lexicographically Small Enough
设 \(s\) 经过交换后的字符串为 \(s'\)，枚举 \(s'\) 和 \(t\) 公共前缀长度为 \(l\)，则 \(s'[1,l]=t[1,l]\) 且 \(s'[l+1]<t[l+1]\)。
对于每一个位置 \(i\)，我们维护出使得到此位置 \(s'\) 和 \(t\) 前缀相等的最少操作次数，并计算使得 \(s'[1,i-1]=t[1,i-1]\) 且 \(s'[i]<t[i]\) 的最少操作次数。后者中的最小值即为答案。
对于前者，每次从当前位右边找到最近的 \(t[i]\) 移过来并维护答案；对于后者，每次从当前位右边找到最近的 \(c<t[i]\) 移过来并计算答案。
所以我们对字符集里每个字符按顺序记下其出现位置。这样，每次要找到最近的某个字符，就取该字符最早的没有被使用过的出现位置。
CF1551E Fixed Points
由于把前 \(i\) 个数删到仅剩 \(j\) 个数的代价为 \(i-j\)，设 \(dp_{i,j}\) 表示把前 \(i\) 个数删到仅剩 \(j\) 个数能获得的最大的 \(i=a_{i}\) 个数，则 \(dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-1}+[j=a_{i}])\)，最后在所有满足 \(dp_{i,j}\ge k\) 的 \(i-j\) 取最小值即可。
CF1613E Crazy Robot
考虑一个点想要走到实验室，那么它周围的空单位（已经确定为 '+' 的不算）只能有一个或者没有。所以直接从实验室 bfs 即可。
CF1616D Keep the Average High
首先将所有的 \(a_{i} \gets a_{i}-x\)，这样只要满足 \(a_{l}+a_{l+1}+\cdots+a_{r-1}+a_{r}\ge 0\)。
对于 \(a_{i} (i\in[2,n])\)，如果 \(a_{i}+a_{i-1}+a_{i-2}<0\) 或者 \(a_{i}+a_{i-1}<0\)，显然就不能选 \(a_{i}\) 了，于是将 \(a_{i}\gets inf\)。
CF1548B Integers Have Friends
可以发现最后答案区间内的数作差 gcd 大于1，维护一个差分数组，求出最长的子区间使得该区间 gcd 大于1。用 st 表和二分求解即可。
CF1554C Mikasa
设最终答案为 \(k\)，由异或性质可知：\(n\bigoplus k>m\)。
令 \(p=m+1\)，即求出最小的 \(k\)，使 \(n\bigoplus k\ge p\)。
我们按位考虑（从高位到低位），用 \(x_{i}\) 表示数字 \(x\) 在二进制下的第 \(i\) 位。
那么一共有四种情况：
1.\(n_{i}=p_{i}=1\)，此时 \(k_{i}=0\)。
2.\(n_{i}=p_{i}=0\)，此时 \(k_{i}=0\)。
3.\(n_{i}=0,p_{i}=1\)，此时 \(k_{i}=1\)。
4.\(n_{i}=1,p_{i}=0\)，此时 \(k_{i}=0\)，注意此时 \(n\bigoplus k\) 一定大于 \(p\)，所以直接 break，后面数位全部填 \(0\) 即可。
CF1556C Compressed Bracket Sequence
首先一个显然的性质是任何序列数量都不为零，表明每一对左右括号序列至少会产生 \(1\) 的贡献。
设此时给出 \(a\) 的左括号，\(b\) 的右括号。要求 \(a>b\)，那么左括号多了 \(a-b\) 个。
我们将多出来的设为 \(res\)，考虑 \(res\) 可产生贡献的所有情况：
1.显然不能再对当前数对产生贡献。
2.对后面新的数对且右括号多的与之产生贡献。
3.而在与后面的右括号匹配的同时，也意味着它跨过了至少两个数对，会产生额外的贡献。
注意细节统计即可。
CF1560E Polycarp and String Transformation
首先很容易得到结论：从字符串 \(t\) 的末尾向前遍历，越早出现的字符越晚被删掉，所以我们将字符串从后向前遍历一遍即可。
然后我们统计出每个字符出现的次数，设为 \(cnt_{i}\)，如果它在第 \(q\) 轮被删除，那么它在初始串中的出现次数为 \(\frac{cnt_{i}}{q}\)。
如果任意一个 \(cnt_{i}\) 不能整除 \(q\)，那么就无解，输出 \(-1\)。
求出初始串长度后，按照题中的操作过程得到的解检验一遍即可。
CF1572A Book
如果想要理解第 \(x\) 章就必须理解第 \(y\) 章，那么我们可以连一条 \(y\to x\) 的边，使用优先队列对图进行拓扑排序，将阅读次数小的放在前面，若阅读次数相同则按照阅读章节编号排序。显然如果有环，输出 \(-1\)。假设现在有一条 \(u\to v\) 的边，如果 \(u\) 大于 \(v\)，就需要在下一次才能理解第 \(v\) 章。最后直接输出阅读次数最多的章节读了多少遍。
CF1582F1 Korney Korneevich and XOR (easy version)
我们发现值域非常小，考虑用值域来解决这道题，用数组 \(f_{i}\) 来存 \(i\) 这个数能异或的值，那么对于每一个 \(a_{i}\)，先用 \(f_{a_{i}}\) 的值更新答案，再将这个异或出来的值加入 \(\sum_{i=a_{i}+1}^{v} f_{i}\)，\(v\) 为值域。用 \(vis_{i,j}\) 表示在 \(f_{i}\) 中 \(j\) 有没有出现过，如果没有出现就加入这个值，时间复杂度为 \(O(n+v^{3})\)。
CF1575D Divisible by Twenty-Five
数据范围很小，暴力即可。
CF1611F ATM and Students
双指针，每一次向右移动一次右指针，然后不断向右移动左指针直到满足条件，这个过程中维护当前剩下的钱即可。
CF1582E Pchelyonok and Segments
如果从前往后考虑，我们不知道第一个区间长度是多少，因此从后往前 dp。设 \(dp_{i,j}\) 表示第 \(i\) 位的后缀中，存在一个满足条件且最长区间长度为 \([l,r]\) 为 \(j\) 的 \([l,r]\) 区间和的最大值。
转移时首先 \(dp_{i,j}\gets dp_{i+1,j}\)，然后计算 \([i,i+j-1]\) 的区间和 \(s\)，若 \(s<dp_{i+j,j-1}\) 则可以选择 \([i,i+j-1]\)，令 \(dp_{i,j}\gets \max(dp_{i,j},s)\)。
由于区间长度不超过 \(\sqrt{n}\) 所以时间复杂度为 \(O(n\sqrt{n})\)。