另类做题记录（一）

逆天的记录。

PART I

不知道。

*1809. EDU 145

https://codeforces.com/contest/1809.

E. Two Tanks

如果 $c+d$ 固定，那么答案应该时随着 $c$ 的增加先不变，再递增，最后又不变的顺序进行的，而且每次的差值只有 $1$ 。找出这两个位置即可。代码。

F. Traveling in Berland

如果当前位置油价是 $1$ ，那么肯定能加满就加满（会用完）， $2$ 的话能加多少加多少。设 $f_{i}$ 代表 $i$ 到下一个油价是 $1$ 的位置的位置， $s_{i}$ 代表代价，倍增这个过程即可。代码。

G. Prediction

对于一个合法的排列 $p$ ，删除 $a_{p_i}$ 最小的 $p_i$ ，新的 $p'$ 必定合法。

设 $f_{i}$ 代表填完 $(i,n]$ 的方案数，初始 $f_n=1$ ，考虑 $a_i$ 填的位置：

不填在当前第一个位置，不影响后面元素的前缀 $\max$ ， $f_{i-1}\stackrel{+}{\leftarrow} f_{i}(n-i)$ ；
填在当前第一个位置。设 $lst_i$ 代表最大的 $j$ 使得 $a_i-a_j>k$ ，那么 $(lst_i,i)$ 都需要出现在 $i$ 之前，则 $i-lst_i-1$ 需要填入 $n-lst_i-2$ 个位置（除了第一个）。

双指针求 $lst$ ，时间复杂度 $O(n)$ 。代码。

*1854. Div1 889

https://codeforces.com/contest/1854.

B. Earn or Unlock

如果前 $k$ 个能恰好被解锁，那么答案是 $\sum_{i=1}^k a_i - (k-1)$ 。对于解锁情况可以使用 DP 来解决：设 $f_i$ 代表前缀 $i$ 是否恰好能被解锁，那么 $f_{j+a_i}\leftarrow f_j(j\ge i)$ ，这个过程可以使用 bitset 加速。代码。

*1856. Div2 890 (Done)

https://codeforces.com/contest/1856.

C. To Become Max

没调出来，我是菜狗！

$n$ 只有 $1000$ ，想的暴力一点，枚举最终成为答案的数 $a_i$ 。一开始肯定要利用 $a_{i+1}$ 让 $a_i$ 变得尽可能大，这样的代价是最小的。当 $a_i>a_{i+1}$ 时怎么办？利用 $a_{i+2}$ 让 $a_{i+1}$ 变大。

如果操作次数足够多，那么最终的序列肯定是形如 $x,x-1,\cdots,a_n+1,a_n$ 的。也就是说，依次枚举 $j\in[i+1,n]$ ，当 $a_j\ge a_{j-1}$ 时，至多就可以让 $a_i$ 变大 $a_j-a_{j-1}+1$ ，此时更新答案即可。如果不满足， $a_j$ 在后续的更新过程中肯定要变成 $a_{j-1}-1$ ，否则无法使 $a_i$ 变得更大，提前更新 $a_j$ 即可。代码。

D. More Wrong

看上去就很分治。当前点 $r$ 在 $[l,r]$ 中最大的充要条件是 $Q(l,r-1)=Q(l,r)$ ，根据此分治下去即可。代码。

E. PermuTree

只要更改子树内的权值分布，就可以达到贡献最大化，所以是个树上背包状物，可以通过 E1，代码。

对于 E2，我们要思考如何高效解决“把儿子大小构成的数集合分成差尽可能小的两部分”。子树中不同的 $siz$ 最多只有 $\sqrt{n}$ 种，二进制拆分掉保证物品个数不多于 $\log n$ 个，然后是可行性背包采用 bitset 优化，单次时间复杂度是 $O\left(\cfrac{n\sqrt{n}\log n}{w}\right)$ 的。

如何将其搬到树上？简单。如果存在一个重儿子，它比所有轻儿子都重，这样可以直接得出答案。否则会造成一个分治的效果，每次问题规模必定减半，时间复杂度为 $O\left(\cfrac{n\sqrt{n}\log^2 n}{w}\right)$ 。实际效率非常高。代码。

*1859. Div2 892

https://codeforces.com/contest/1859.

D. Andrey and Escape from Capygrad

只能跳到 $[l,b]$ （否则没有意义），合并线段，二分查找。代码。

*1858. Div2 893 (Done)

https://codeforces.com/contest/1858.

D. Trees and Segments

考虑 $O(n^2)$ DP 预处理出前后缀改 $j$ 次得到的 $0$ 的最大长度，然后枚举中间 $1$ 的长度，双指针扫。代码。

E. Rollbacks

实际上这是个大暴力题。

set 记录所有数的位置，不同数的个数经典只维护最小位置数的贡献，删除操作直接将序列长度减掉但是保留序列，回滚直接回滚。代码。

*1860. EDU 153

https://codeforces.com/contest/1860.

D.

*1354. EDU 87 (Done)

https://codeforces.com/contest/1354.

C2. Not So Simple Polygon Embedding

大致思路是观察获得多边形的旋转度数，然后解三角形。代码。

D. Multiset

权值树状数组直接维护。代码。

E. Graph Coloring

二分图染色，然后背包判断可行性。代码。

F. Summoning Minions

必定是放满 $k-1$ 张后，拿剩下的放完就扔（会产生 $b\times (k-1)$ 的贡献），最后再放一张。

放置顺序必定满足 $b$ 递增（否则可以交换），然后根据此进行 DP： $f_{i,j}$ 代表前 $i$ 张选 $j$ 张不是用完就扔的。代码。

G. Find a Gift

如果知道其中 $x$ 个是石头，那么就能用这 $x$ 个去确定另外 $x$ 个数当中有没有石头。先找到 $1$ 个石头，然后从头开始倍增找到第一个没有石头的区间。要确定这段有石头的区间的第 $1$ 个石头位置，可以二分。如何找到一个石头？不知道，采用随机化。随机找到一些位置，找到当中最重的，那么可以确定那个是石头。代码。

*1867. Div2 897

https://codeforces.com/contest/1867.

D. Cyclic Operations

赛时结论假了一部分，只因！

最后图大概形如一个内向基环树森林之类的东西，链上的可以一次满足 $k-1$ 个，环的大小必须为 $k$ 。注意 $k=1$ 的特判。代码。

PART II

本着题是用来刷的原则，我们从 ARC 4 题场，且有英文题面的开始。

进度可视化。

ARC 058

对远古 bot 来说，好难。

C. Iroha and Haiku

Portal.

数据范围很小，因此考虑想得暴力一点。当后缀和超过 $X+Y+Z$ 时，再记录就没有意义（因为好区间不可能再被选取到），这样直接状压后缀和序列（将后缀和中出现的数存储起来），便可以简单判断是否出现了好区间。

如果从满足条件的区间考虑，会发现一个序列不一定只有一个好区间，这样很容易导致算重。因此对答案取补集，考虑计算没有满足条件的子区间的方案数。

设 $f_{i,j}$ 表示考虑序列前 $i$ 位，当前后缀和状压后为 $j$ 。转移时采用刷表法，枚举最后一个填的数，计算新的后缀和，如果满足条件便统计答案。代码。

D. 文字列大好きいろはちゃん

Portal.

时间旅人逆转了此处的时间。

太困难了！

ARC 059

这场怎么这么简单。

C. Children and Candies

Portal.

$f_{i,j}$ 代表前 $i$ 个人分了 $j$ 个糖果的答案，直接转移。代码。

D. バイナリハック

Portal.

容易发现这是个骗子题，打的字符串是什么跟答案没有关系。设 $f_{i,j}$ 代表 $i$ 次，那么可以打一个字符（贡献为 $f_{i-1,\max\{j-1,0\}}$ ， $j=0$ 时相当于打一个回车），撤回一个字符（贡献为 $2\times f_{i-1,j+1}$ ，因为撤回的是什么没关系）。代码。

ARC 060

做这个东西上瘾。

B. Digit Sum

Portal.

如果 $b<\sqrt{n}$ ，直接枚举即可。否则 $n$ 是 $b$ 进制下的两位数，解不定方程即可。代码。

C. Tak and Hotels

Portal.

倍增处理出能走到的最远位置。代码。

D. ???

死灵法师抹除了此处的灵魂。

这是一个字符串，以后再说。

ARC 061

阿巴阿巴阿巴。

C. すぬけ君の地下鉄旅行

Portal.

用同样颜色的边所连接成的连通块可以互相到达，不难想到建一个虚点，将这个联通块内的所有点向虚点连一个权值为 $0$ 的边，由这个连通块切换到别的连通块都需要 $1$ 的代价，因此虚点向连通块内所有点连权值为 $1$ 的边。并查集加 01 BFS 就可以完成这个过程，应该是 $O(m\log m)$ 的。代码。

D. 3人でカードゲーム

Portal.

考虑构造双射，每一个方案可以映射到一个长度为 $m$ 的序列，这个序列当中有 $n_1$ 个 $1$ ，且第 $m$ 位必定是 $1$ 。

枚举序列中不是 $1$ 的个数 $k$ ，贡献系数为 $3^{n_2+n_3-k}$ ，那么答案为：

$\binom{k+n_1-1}{n_1-1}\sum_{k-n_3\le i\le n_2} \binom k i$

后面的东西不可能直接计算，考虑增量法维护：

$\begin{aligned} S(k)&=\sum_{k-n_3\le i\le n_2} \binom k i\\ &=\sum_{k-n_3\le i\le n_2} \binom{k-1}{i}+\binom{k-1}{i-1}\\ &=\sum_{k-n_3\le i\le n_2} \binom{k-1}{i}+\sum_{k-1-n_3\le i\le n_2-1} \binom{k-1}{i}\\ &=S(k-1)-\binom{k-1}{k-n_3-1}+S(k-1)-\binom{k-1}{n_2} \end{aligned}$

然后就可以直接计算了，代码。

PART III

来源是 2015 集训队作业，实际上就是远古时期 CF 题。

第一组

呜呜呜。

[CF293B] Distinct Paths

Portal.

要求所有路径上的颜色都不相同，路径长度最大为 $k$ ，而 $k$ 最大只有 $10$ ，所以这实际上是个大暴力题。

考虑枚举所有没涂色的格子的颜色，并状压经过的路上的颜色。但是这样状态数干到了 $O((nm)^k)$ 的等级。

想一想为什么会算这么多。因为，我们计算了很多无用状态！所以：

如果还剩的颜色已经不能够填满接下来的路径，那么直接再见。
如果当前颜色是全局中唯一填的，那么填其它全局也没有出现的颜色是等效的，只需要算一次就可以了。

代码。

* [CF325E] The Red Button

Portal.

真的挺妙的。

这是个什么？不知道。先打表找规律，然后发现 $n$ 为奇数时无解。

然后呢？以下是 $n$ 为偶数时暴力跑出的答案：

0 1 0
0 1 3 2 0
0 1 2 5 4 3 0 
0 1 2 5 3 7 6 4 0
0 1 2 4 9 8 6 3 7 5 0

能看出什么吗？好像不能，那再从图上出发看看能不能发现点什么。

每个点的出度均为 $2$ ，要是 $1$ 我直接欧拉路！诶可不可以通过特殊限制搞成 $1$ 呢？还真能。

我们需要一个更好的代数形式来刻画每个点的出边。我们有：

$\begin{aligned} i\times 2\equiv (i+\frac n 2)\times 2 \pmod n \\ i\times 2 + 1\equiv (i+\frac n 2)\times 2 + 1 \pmod n \end{aligned}$

也就是说 $i$ 和 $i+\frac n 2$ 所连的边应该是同一个东西。那这好办了，想要有答案必须一人分一个，那就随便。

然后答案成了什么状物？若干个环！我们需要合并它们。

如果图上有多个环，那么必定有一对等效点不在同一个环中，交换它们分的边即可合并环。

我们已经通过暴力验证了 $n$ 为偶数时一定有解，所以这样一定可以合并所有的环（否则没得可走了）。代码。

[CF335D] Rectangles and Square

Portal.

拼成的正方形的右上角一定是一个矩形的右上角，正方形的左下角一定是一个矩形的右下角。然后怎么限制？

注意到所有矩形都不相交。这样我们可以用一些前缀和的方式直接判断一些内容。首先一定能铺满，其次正方形的边界一定由矩形的边界构成。这些都很好使用二维前缀和维护。

枚举正方形的右上角和在这条斜线上的合法左下角，时间复杂度 $O(k^2+n)$ 。代码。