CodeForces Record
CF Round#802 Div.2
A. Optimal Path
题意：给一个\(n*m\)的矩阵，\(a(i, j) = (i - 1)m + j\)，求一条从\((1, 1)\)到\((n,
m)\)的最小权值路径。
题解：总步数是确定的，横向移动和竖向移动分别会为后面的每一步增添一个额外的代价，贪心做一下。
B. Palindromic Numbers
题意：给定一个大整数，求另一个与之长度相同的数，使得二者之和为回文数。
题解：构造，如果首位是9，那么一定可以满足回文数为全1，否则构造全9的回文数。
C. Helping the Nature
题意： 给定数组\(a\)，可以使一个前缀或一个后缀都减一，可以使数组整体加一，求最少次数使得数组元素变为完全相同。
题解：
转换为对差分数组操作，就变成了单点加一和减一，和不修改，前两种是唯一可以改变差分数组的操作，要让差分数组变为全0，再考虑整体需要加或者减几次。
D. River Locks
题意：
有若干水闸，前面的水满了会溢到后面去，每个闸有自己的容量，多次询问若要求\(t\)时间内将所有水闸放满，至少需要打开几个闸门的入水口。
题解：
注意到前面的水可以留到后面，后面不能去前面，所以一定是打开最前面若干个闸门的入水口，因此不断对前缀做判断即可。这里注意要规避掉某个极大的闸门在前面，放满它的时间是整体时间的平静。
E. Serega the Pirate
题意： 有一个\(n*m\)的矩阵，里面填有\(1\)到\(n*m\)，从\(1\)开始走，可以走重复的格，但是要严格按照升序\(1, 2, 3
...\)走，求是否有解，如果没有的话求有几种方案可以交换两个数的位置使得存在解。
题解：
做题的时候想到的是并查集来判断解存不存在，但是很脑筋急转弯的是只要每个点都存在一个相邻的更小的值，那么就一定存在解，可以归纳证明。
基于此考虑没解的情况下怎么求方案数，交换两个点只会影响交换的两个点周围的点以及本身，那么找一个周围都更大的点\(x\)，可能的方案只可能是一个点在\(x\)及周围，另一个在\(x+1\)附近，因此暴力枚举方案，依次做暴力验证即可，注意这里可能会有重复的方案。
F. Puzzle
题意： 给出两个\(2*n\)的01矩阵，可以交换两个相邻位置的数，求最少次数使得矩阵1变为矩阵2。
题解：
乍一看像是dp，但是不太好描述状态。考虑一个退化的情况，如果只有一行，那么直接按顺序分配即可，那么扩展到两行。不妨假定把竖向的操作提到最前面，已经完成了竖向的操作，那么两行内就直接按顺序分配即可。
这道题有个很新颖的想法就是换一种计算一行内情况的方式，正好是01数组，两个数组的前缀和做差，再求绝对值的和就是需要的操作次数。
那么在这个基础上考虑，纵向的移动相当于把一行的前缀和的后缀减一，另外一行的前缀和的后缀加一，考虑怎么让这个和最小。
考虑从左到右扫描，在某一列遇到了1，记第一行前缀和差为\(f_{1}\)，第二行前缀和差为\(f_{2}\)，如果\(f_{1}\)和\(f_{2}\)异号，不妨假设\(f_{1} \gt 0, f_{2} \lt 0\)，那么说明第一行前面有多余的1，第二行缺少了1，这是把第一行的1移动下来一定是最优的。
证明如下，考虑一个情况如下矩阵，那么在右上角及其右侧的第一行对于1的需求由矩阵中任何的1移动而来需要的代价是相同的，左下角及其左侧也是一样的。
\[\begin{pmatrix} 1&0\\ 0&1\\ \end{pmatrix}\]
其他的情况可以手玩一下，可以得出类似的证明，而且当\(f_{1}\)和\(f_{2}\)异号时，一定是刚刚变为异号，即绝对值为1，因此这种情况下把多余的1纵向交换到另一行一定是最优解，贪心从左到右扫描即可。
CF Round#930 Div.1
A. Bitwise Operation Wizard
题意：已知\(n\)，有一个未知的\(n\)的排列\(p\)，可以交互查询\(p_{a} | p_{b}\)与\(p_{c} | p_{d}\)的大小关系，在\(3n\)次内找出任意一组答案\(x, y\)使得\(p_{x}
\oplus p_{y}\)最大。
题解：最后的异或没看到被坑惨了，题意玩一下，查询可以直接用来比大小，那么先找到最大值，一定存在一组答案是由最大值\(p_{x}\)参与的，另一个数要满足跟它二进制互补，但是查询只有或。第一次查询找到所有或起来最大的\(p_{y}\)集合，他们一定弥补了\(p_{x}\)二进制中所有的0，那么在其中找最小值就是不含有\(p_{x}\)中所有的1。
B. Pinball
题意：一个球在一个一维平面内滚动，每个位置表示球的滚动方向'>'或者'<'，滚动后这一位置会变化为反向，问从每个位置开始滚动需要多久才可以滚出去。
题解：手玩一下，球的运动路径就是沿着一个方向一直走，碰到反向前形成了一条反向的路径，反向后在另一个方向重复这个过程，实际上就是反向到球出发的距离和的两倍。因此，考虑一下球最后的落点，这个方向只会走一次，顺便维护一下左侧的'>'和右侧的'<'即可。
C. Pokémon Arena
题意：\(n\)个人打比赛，每个人有\(m\)维的属性和出场费\(c_{i}\)，任何一个人只要某一维不低于对手就可以战胜他，初始1号在擂台上，战胜他就可以替代他守擂，你可以花费等量的钱来为任意选手永久提升任意的属性，求最小花费的方案使得第\(n\)个人打上擂台。
题解：首先分析一下这个背景，可以得到两个结论：
- 永久属性提升可以视作一次性提升：考虑你通过比较一个提升过的属性来攻擂，那么直接提升属性到攻擂者一定不会更差
- 一位选手不会多次登台：既然可以看作一次性提升，那么如果出现选手两次攻擂，直接消除掉中间的过程答案一定更优
然后发现就可以去掉dp的后效性了，直接做一个dp：f[i]表示第i人守擂的最小花费。可以发现dp的转移是不定向的，那么直接建图跑最短路。进而发现这个图边集是爆炸的，每个状态都有\(nm\)个转移方式，那就要优化建图，直接拆点，把每个维度按照数值排序，只在相邻数值的点对间建边，那么就可以把边的数量压缩到\(nm\)级别，最后跑一个最短路得到f[n]。
D. Bitwise Paradox
题意：给定两个数组\(a,
b\)和一个常数\(v\)，定义一个子区间\([l, r]\)是好的，当满足\(b_{l} | ... | b_{r} \geq
v\)，定义区间得权值为\(max(a_{l}, ..,
a_{r})\)。支持两种操作，单点修改\(b\)，区间查询好的子区间的权值中的最小值。
题解：看着就很像线段树，但是很难决定区间去维护什么，遇事不决就直接维护答案，考虑如何合并两个线段上的节点。父节点的答案取子节点的最小值，再考虑跨区间的情况.
或操作从高位按位考虑，只考虑更高位是紧约束的情况，分情况讨论：
如果\(v\)这一位是0，那么跨区间如果取了1，低位再怎么取都没有约束了，直接按照取1带来的约束更新答案，如果跨区间取了0，相当于没有新的约束增加，继续枚举下一位。
如果\(v\)这一位是1，那么跨区间必须取1，更新约束继续。
幸好权值为\(a\)的区间最大值，因此取1带来的约束就是一次最大值的更新，不同位置的1带来的约束是互不影响的，可以按位独立考虑。那么如果要取1，如何能让跨区间的权值最小呢，那就是跨区间包含了左节点区间中最右侧的1，或者包含右节点区间中最左侧的1，那么额外维护一下这个信息就可以在\(O(logV)\)时间内合并两个区间了。这里\(a\)的区间最值需要用RMQ与处理一下，总复杂度为\(O(qlogNlogV)\)。
CF Round#934 Div.2
A. Destroying Bridges
题意：给一张完全图，求删去\(k\)条边后，点1不可到达的编号最大的点。
题解：手玩一下最优解盯着点1的边删就行。
B. Equal XOR
题意：将2个n的排列打乱为等长的两部分，各选出\(k\)个值，使得两边的异或和相同。
题解：构造，如果两个一样的数在一侧直接选，如果还剩就从异侧里面补。
C. MEX Game 1
题意：博弈，轮流从数组里面取数，使得Alice得到的数组的mex最大。
题解：发现从0开始，如果有至少两个数，那么一定是不急着拿的，只考虑出现一次的数，第一个可以先手直接拿，第二个就会成为瓶颈。
D. Non-Palindromic Substring
题意：定义字符串为\(k-good\)，即存在长度为\(k\)的非回文子串，定义字符串的权重为所有\(k-good\)的\(k\)之和，多次区间查询子串的权重。
题解：这个\(good\)是一个非常强的约束，当\(k\)为偶数时，要求字符串完全由一个字符组成，当\(k\)为奇数时，要求字符串由两个字符交替组成，特别地当\(k =
len(str)\)时需要特判。因此本题转换为了多次对区间子串求是否为回文串，manacher解决。
E. Tree Compass
题意：定义染色操作，对树的任一节点和任一距离\(d\)，染色所有到该点距离为\(d\)的点，求一棵树的最小染色次数。
题解：很容易想到树的直径，讨论一下链的退化情况，按照链的长度分为：奇数，模4余2，模4余0，共三类情况，并可以给出由中心开始的染色方案。扩展到树的普通情况，基于链的性质，链外的路径一定不会更长，因此从中心开始的染色方案一定可以覆盖直径以外的节点，固可按照直径链的退化情况进行构造。
F. Counting Is Fun
题意：对于一个数组，可以选择一段长度大于1的子数组进行区间减操作，如果一个数组可以通过若干次操作变为全0数组，则称其为好的。求长度为\(n\)的，初始元素范围在\([0, k]\)中的好数组一共有多少个。
题解：
首先要把这个好的定义转换一下，主要的限制来源于长度要大于1，这意味着需要满足\(a_{i} \leq a_{i-1} + a_{i+1}\)，对于数组两端可以认为\(a_{0}=a_{n+1}=0\)，满足这个条件即为好数组。
然后考虑统计，一个简单的想法是dp，状态一定要有\(k^2\)表示这个约束，时间复杂度太大，那么这种计数问题通常就要往容斥原理的方向考虑，定义\(a_{i} \ge a_{i-1}+a{i+1}\)时，位置\(i\)是坏的。定义\(f(x)\)表示集合\(x\)中所有位置都是坏的的数组个数，那么根据容斥原理好的数组总数为\(\sum (-1)^{|x|}f(x)\)。
接下来考虑怎么求这个容斥，\(f[i][j][0/1]\)表示：\(a_{i}=j\)，考虑\([1, i)\)位置中有至少奇数/偶数个坏位置的方案数，那么转移方程如下：
位置\(i-1\)无所谓是不是坏的（容斥原理）：\(f[i][j][l] = \sum f[i-1][j][l]\)
位置\(i-1\)一定是坏的：\(f[i][j][l] = \sum f[i-2][j'][l^1] * (k-j'-j)\)
dp式前缀和优化一下就可以得到\(O(n^2)\)的写法。
CF Round#941 Div.2
A. Card Exchange
题意：给定\(n\)个数，可以选择\(k\)个相同的数变为\(k-1\)个任意数，求操作后最少剩几个数。
题解：只要能开始操作，答案就是1。
B. Rectangle Filling
题意：给定一个二维黑白染色矩阵，操作是选择两个颜色相同的块，将这两个块对应的矩形染为这个颜色，求是否能将矩阵染成纯色。
题解：手玩一下，不能染为纯色的充要条件是黑色和白色各站住了对侧最边缘的一条（左右/上下）。
C. Everything Nim
题意：一堆石子，每次要从所有所有堆中拿走一样多的石子，不能操作的输。
题解：差分一下变成从一堆石子里面取，然后倒着推一下状态，只考虑数量是否为1就可以。
D. Missing Subsequence Sum
题意：构造一个数组，子序列的和可以覆盖\([1,n]\)，但是不能含有\(k\)。
题解：首先构造\([1,k-1]\)，类似二进制的方式构造，最后一步跟\(k\)做差算一下，然后后面很简单地缺什么加什么，例如得到\([1,k-1]\)后添加\(k+1\)，子序列和对应\([1, 2k]\)，然后添加\(2k+1\)，注意这次开始会引入新的缺陷\(3k+1\)，然后逐次添加缺陷即可，会发现缺陷每次会倍增，因此构造的数组不会超过\(log2_{2}\)级别。
E. Folding Strip
题意：一个01纸带，定义合法的折叠是指折叠后空间上重合的纸袋数字相同，求经过合法折叠后纸带最短的长度。
题解
看着很像回文串相关，区间dp相关，但是仔细想做不了一点，全是后效性和影响。因此尝试找性质，提出一种可能：在每个相邻的相同数字之间都折一下，是一种合法的折叠方案。证明从奇偶性考虑，这样折叠后按照下标考虑，所有的0和1奇偶性一定不同（相同的就被折叠了），因此在空间上重叠的一定都相同，方案合法。这样折叠之后不可能再次折叠了，而且通过回文的性质可知，局部的回文折叠不会影响更长的回文串，因此这个折法是最优方案。
考虑怎么求解最后剩余的纸带长度，从空间上一层一层摊开，可以认为纸带先往一个方向延申，遇到需要折叠的地方再调转方向，这样就可以模拟一个数轴，记录纸带到达的最左侧和最右侧，做差即为折叠后并在一起的纸带的长度。实际代码特别短，这道题很有意思。
F. Missing Subarray Sum
题意：有一个回文数组，给出所有子数组的和，但是去掉了其中一个，尝试还原数组。
题解：回文的性质很好地限制了数组的构成，但是不太好找出被删掉的数是什么。那么分情况讨论一下：如果数组是奇数长度\(2k+1\)，那么子数组的和构成的序列中，应该会有\(k+1\)个出现过奇数次的和，且保持一样的奇偶性；如果数组是偶数长度\(2k\)，应该会有\(k\)个出现过奇数次的和，且都为偶数。那么就可以根据这个性质得出，删掉的数到底是本应出现奇数次的中心对称回文的和，还是一个本应出现偶数次的和。
分情况讨论，如果删掉的是本应出现奇数次的和，也就是删掉了一个中心对称的回文和：那么我们先当作没有删，去重建这个数组，可以发现相当于得到的数组相比于原数组，会有两个数合在了一起，对应着被删掉的和的位置。举例来说原数组在\(a_{x}=3,a_{x+1}=2\)，那么在重建数组中只会得到\(a_{x}=5\)，因为区间和\(a_{x+1, n}\)被删掉了。同样地，如果是删掉了偶数次的和，那么会有一个数被拆开成两个数。
那么我们比较重建数组的子数组和与给出的删掉一个数的原数组和，排序后第一个不同的和\(t\)就代表着两个数组的差异。对于两个数合二为一的情况，说明原数组的和刚好只包含了两个数之一，对于拆开的情况，则是重建的和包含了拆开的两个数之一。无论哪个情况，这个和都包含着回文数组和的一半，再加上从中心到达两个数之一的子数组之和。
如果删除的不是数组的最大值\(sum\)，那么就可以通过\(2 * t - sum\)来算出删掉的和，补全后重建即可。如果删除的正好是数组的最大值，那么仍然这么做，可以发现\(t=a_{1, n - 1}\)，依然可以还原出删去的值。
CF Round#953 Div.2
A. Alice and Books
题意：给定\(n\)个数，分为两堆，每堆取编号最大的，求最大的和为多少。
题解：答案即为前\(n-1\)个数中的最大值加上第\(n\)个数。
B. New Bakery
题意：卖\(n\)件货物，可以选定一个\(k\)，前\(k\)件卖出的货物中的第\(i\)件以\(b-i+1\)的价格卖出，其余按照固定价\(a\)卖出，求最大获利。
题解：想办法卖高价，\(k \leq b
- a\)，考虑一下边界条件。
C. Manhattan Permutations
题意：定义排列的曼哈顿距离为\(\sum |p_i - i|\)，构造距离为\(k\)的\(n\)的排列。
题解：手玩一下，曼哈顿距离一定为偶数，且最大的情况为倒序排列。考虑构造，从正序排列开始，如果\(k\)够大则交换首位元素，否则交换首元素与某一中间元素停止。这样的交换方法不会对序列中间的距离产生影响，可以方便地缩小问题的规模。
D. Elections
题意：\(n\)个人选举，每个人有\(a_i\)选民，还有\(c\)个不定选民会投给编号最小的候选人，当平票时选编号最小的当选。你可以选择一部分候选人出局，他们的选民会成为不定选民，问每个候选人当选最少需要出局多少人。
题解：考虑胜选的情况：如果不需要不定选民投给你，那么就要满足\(a_{x} > a_{1} +
c\)，否则就一定需要不定选民，那么\([1,
x)\)的候选人一定要出局，若还不够再考虑从后面贪心选大的出局。
E. Computing Machine
题意：给定两个01串\(s,
t\)，若\(s_{i}=s_{i+2}=0\)则可使\(b_{i}=1\)，若\(b_{i}=b_{i+2}=1\)则可使\(a_{i}=1\)，多次查询区间\(l,
r\)，对这个区间的字串进行操作最多可得到多少个\(s\)串中的1。
题解：字串只有边缘会受到影响，中间的结果与两个串直接操作没区别，边缘单独判断一下即可。
F. Large Graph
题意：给定一个数组\(a\)，循环右移得到\(n * n\)矩阵\(b\)，由矩阵\(b\)生成一张图，每个点代表矩阵中一个元素，两个点有边当两点在矩阵中曼哈顿距离不超过\(k\)，且两个点在矩阵代表的值不互质，求图中连通块的数量。
题解：当\(k \geq
2\)时，斜着的条状带构成了\(2n -
1\)个连通块，问题退化为一维，那么对于每一个质因数，添加连向最近的公共因子的边，这样可以控制每一个质因子的边的数量不超过\(O(N)\)，直接搜索即可。稍微注意一下当\(a_i =
1\)时，每个点都是独立的连通块，然后\(ans\)是\(O(n^2)\)级别的，会暴int，最后质数只要枚举到根号级别就可以，剩下的做个map搞一下。
CF Round#959 Div.1+Div.2
Codeforces Round#959 Div1+Div2
A. Diverse Game
题意：构造一个排列与给出的排列每一位都不相同。
题解：每位+1输出即可。
B. Fun Game
题意：给定两个01串\(s,
t\)，每次操作可以选定一个子区间\(l,
r\)，替换\(s_{i} = s_{i} \ xor \ s_{i
- l + 1}\)，问是否可以通过操作使\(s\)变成\(t\)。
题解：考虑前缀，异或自己1可以变成0，但是0无法变成1，如果一直到\(t\)串第一个1出现为止\(s,
t\)都可以匹配，那么后面任何想要更改的位都可以通过这个1来逐位操作。
C. Hungry Games
题意：给定一个数组\(a\)，代表蘑菇的毒性，如果要吃掉一个区间\(l,
r\)的蘑菇，会按照顺序吃，毒性每累积到\(x\)或更高，毒性会刷新清零，问有多少个字区间吃完后毒性累积不为0。
题解：对于每一个点求出到哪里毒性清零，然后从后往前递推一下即可。
D. Funny Games
题意：给定一个数组\(a\)，进行\(n-1\)次操作，每\(i\)次操作可以任选一个\(u, v\)满足\(|a_u
- a_v| \equiv 0 \ mod \ i\)，会添加一条\(u,
v\)之间的边。尝试给出一种方案使得图连通。
题解：样例猜个结论，一定有可行解，根据抽屉原理，模数总会有两个相同的，因此从\(n-1\)开始倒序构造，每次任选两个模数相同的点连起来即可。
E. Wooden Game
题意：给出\(n\)棵树，每次可以任选一棵砍掉一个子树，记其大小为\(x\)，求可以得到的最大的\(\sum xor(x)\)。
题解：一棵大小为\(x\)的树可以得到\([1,
x]\)的任意结果，只需要一个一个的砍掉，直到剩下的大小为需要的结果。那么逐位构造答案，如果只有一棵树的大小这一位为1，那么直接减去这个大小继续构造，如果多于一棵则后续所有位都可以为1。
F. Stardew Valley
题意：给定一张无向图，有一部分边必须要选，一部分边可选，找出一条欧拉回路。
题解：必须选的边会导致一部分点的度数为奇数，但是加边不太好加，换一个思路从所有边往下删边，删非必选的边。
只考虑非必选边，搜索出一棵生成树，自下而上地遍历，若点的度数为奇数，删去与父亲连接的边，这样总能调整到所有的点都为偶数。（因为度数总和一定为2的倍数，所以根节点的度数奇偶性也可以得到保证）又由于图中保证了必选边的连通性，得到的图一定具有欧拉回路。
G. Minecraft
题意：给定\(n\)个数，求一个数\(x\)使得\(\sum
a_{i} \ xor \ x =
s\)，其中数为大数，以01串形式给出，01串的长度为\(k\)。
题解：先不考虑复杂度，很显然的想法就是按位考虑dp，但是问题是状态数目爆炸，想办法压缩状态。观察发现有效的状态其实非常少，因为\(x\)的这一位会造成\(n-cnt_i\)或者\(cnt_i\)的贡献，所以有效的状态不超过\(n\)个，状态就可以被压缩到\(O(nk)\)，直接dp即可。
H. Fortnite
题意：交互题，最多三次查询找出参数\(p,
m\)，可以查询一个小写字母字符串，返回\((\sum ord(s_i)p^i) \% m\)，保证\(27 \le p \leq 50, \ p + 2 \leq m\)
题解：第一次查询\(aa\)得到\(p\)，第二次查询一定是构造一个足够大的串（至少要大于\(m\)），关键是第三次怎么得到\(m\)。
这种构造题，范围又给的很刻意，就会有一些神秘的性质。一个显然的思路是这样：记第二次查询的原始值为\(h_1\)，答案为\(a_1\)，那么显然\(h_1 - a_1 = km\)。那么如果第三次查询的原始值\(h_2\)满足\(h_1 - a_1 - 1 \geq h2 \geq h_1 - a_1 - m\)，那么就一定有\(h_2 - a_2 = (k - 1)m\)，即得到\(m = (h_1 - a_1) - (h_2 - a_2)\)。这个倒是不难想，关键是如何构造这样的\(h_2\)，注意到在这个\(p\)进制下，有些数字可能是表示不了的，因为小写字母只有1到26。
题解给了一种利用性质的构造方法，首先令第一次查询的串为\(zzzzzzz\)，我们不妨先不考虑1到26的限制，将\(a_1 + 1\)写为\(p\)进制数，即\(a_1 + 1 = \sum_{i = 0}^{i < len} d_i \ p^i\)，然后我们用\(h_1\)减去它得到一个可能不合法的\(p\)进制数。记不合法的下标集合为\(S\)，对于每个\(i \in S\)，令\(d_i = 26, \ d_{i+1} = d_{i + 1} - 1\)，得到一个合法的\(p\)进制串作为第三次查询。这样的构造一定能满足\(h_1 - a_1 - 1 \geq h2 \geq h_1 - a_1 - m\)，证明如下。
首先新构造出的值一定会更小，因为借位操作\(p \geq 27\)，因此满足\(h_2 \leq h_1 - a_1 -1\)。考虑发生借位的情况，借位操作会减去一个\(p^{i+1}\)，增加一个\(d_i \ p^i\)，因此借位操作会让构造出的\(h_2\)在\(h_1 -a_1 -1\)的基础上变小\((p - d_i)p^i\)。又因为发生借位的情况一定是\(d_i \geq 26\)，因此变小的差值为\(\delta = \sum_{i \in S} (p - d_{i}) p^{i} \leq \sum_{i \in S} 24p_{i}\)
又由于\(a_1 + 1 = \sum_{i = 0}^{i < len}d_i \ p^i \geq \sum_{i \in S}d_{i} \ p^i \geq \sum_{i \in S} 26p^i\)，所以\(\delta < a_1 + 1 \leq m\)，所以\(h_2 = h_1 - a_1 - 1 - \delta \geq h_1 - a_1 - m\)，得证构造出的\(h_2\)符合要求，通过三次查询即可算出\(p, m\)的值。
CF Round#975 Div.2
A. Max Plus Size
题意：给定\(n\)个数，可以选任意数染色，但相邻两个数不能同时染色，最大化染色数量+染色最大值之和。
题解：最大值一定会取，取最大值最多带来奇偶性导致的1的损失，考虑该损失是否可以避免，即n是否为偶数或者最大值存在在奇数位置上。
B. All Pairs Segments
题意：给定\(n\)个点，任意两点间都有一条线段，多次询问被覆盖\(k\)次的点有多少个。
题解：按坐标顺序模拟一下即可，更新覆盖的线段数量，注意一下边界。
C. Cards Partition
题意：卡片上写有1到n的数字，每种卡片有若干张，可以额外购买至多k张任意数字卡片，然后需要将所有卡片等分为若干堆，保证堆内没有相同数字的卡片，求这个堆的最大大小。
题解：堆的大小不会超过n，从大到小枚举判断，首先保证可以按此大小等分不剩余，在这个前提下显然买的多结果不会更差，只需要判断堆的数量是否小于最多种类的卡片数量即可。
D. Speedbreaker
题意：有\(n\)个城市排成一列，时刻1可以从任意一个城市开始，每个时刻可以攻占已有城市相邻的任一城市。每个城市有一个时间要求\(a_i\)，求有多少个城市可以作为起始城市使得每个城市都在其时间要求前被攻占。
题解：
想了一下暴力怎么取judge，觉得这个题我一定是思路想歪了，于是去看了一下题解。题解判断合法的方式是对于一个时刻\(t\)，所有时间要求小于等于\(t\)的城市形成的区间不能长于\(t\)，即不关注具体的攻占顺序而作出可行性的判断。
在这个基础上，起始城市相当于把某个城市的\(a_i\)置为1，对于一个时刻\(t\)对应的区间\([l, r]\)，选择城市\(x\)作为起始可能会导致区间发生变化，因此只需要枚举时间，考虑每个时刻对于\(x\)的约束求并即可。
E. Tree Pruning
题意：给出一棵树，操作是可以去掉一个叶子结点，求最少多少次操作可以让所有叶子结点深度相同。
题解：枚举最优解中叶子的深度，对于一个深度\(d\)，所有更深的点显然要被去掉，另外所有更浅的叶子也会带来一部分删除，这一部分对应的是最深子节点深度不到\(d\)的所有节点，分开统计即可。
F. Max Plus Min Plus Size
题意：给定\(n\)个数，可以选任意数染色，但相邻两个数不能同时染色，最大化染色数量+染色最大值+染色最小值之和。
题解：借着第一题的思路，考虑枚举最小值，那么限制了所有更小的数不能选，转化为第一题的问题。从小到大枚举最小值，相当于不停地做区间割，在多个区间内完成A题，即维护是否存在区间可以在取最大值的情况下不损耗1即可。