Codeforces Div.2 大合集

天不生卷王，万古如长夜！

PART I

下次晚上早点睡！

*1809 (EDU)

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

D. Binary String Sorting

直接枚举断点即可计算。代码。

E. Two Tanks

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

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$ 填的位置：

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

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

*1856 (Div. 2)

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(\dfrac{n\sqrt{n}\log n}{w}\right)$ 的。

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

*1354 (EDU)

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$ 个石头位置，可以二分。如何找到一个石头？不知道，采用随机化。随机找到一些位置，找到当中最重的，那么可以确定那个是石头。代码。

*1848 (Div. 2)

https://codeforces.com/contest/1848。

A. Vika and Her Friends

偶数能抓。代码。

B. Vika and the Bridge

存所有颜色的位置。代码。

C. Vika and Price Tags

在 $(0,b)\rightarrow (b,b)\rightarrow (b,0)$ 中循环，辗转相除处理即可。代码。

D. Vika and Bonuses

以 $20$ 为循环节，暴力枚举，求抛物线的顶点。代码。

E. Vika and Stone Skipping

如果跳 $g$ 次，需要满足：

$$2x\prod X_i=(2f-g+1)g$$

求的就是 $2x\prod X_i$ 的奇因数个数。

直接维护即可。注意模数过小时逆元的爆炸问题。代码。

F. Vika and Wiki

次数越大一定是越趋近于全 $0$ 的，直接倍增答案即可。代码。

*1837 (EDU)

https://codeforces.com/contest/1837/。

C. Best Binary String

不难猜到将有数的东西向左右扩展就是答案。代码。

D. Bracket Coloring

不难猜到答案最大为 $2$，根据此构造即可。代码。

E. Playoff Fixing

不难发现 $2i,2i+1$ 是一组的，并且这玩意儿存在子问题。

记录可以随便填的个数和可以随便排列的个数便不难计算出这一层的方案数。代码。

F. Editorial for Two

二分加贪心即可。代码。

PART II

大打出手！

*1821 (EDU)

https://codeforces.com/contest/1821。

E. Rearrange Brackets

一定是删掉右边的 ()，其贡献就是其深度（外面套了多少个括号）。

操作是什么？发现能将其最外层的括号单独移动出来，贪心即可。代码。

F. Timber

一棵树倒下之后会占用 $k$ 的空间，因此答案为 $2^m\dbinom{n-mk}{m}$。

然后发现需要容斥。其中钦定一棵树会产生左右倒的分身，那么答案是 $2^{m-1}\dbinom m 1 \dbinom{n-(m+1)k}{m}$。直接做即可。代码。

*1891 (Div. 2)

https://codeforces.com/contest/1891。

D. Suspicious logarithms

发现 $f,g$ 的变化都不多，因此直接暴力碾过去即可。代码。

E. Brukhovich and Exams

将 $\gcd$ 为 $1$ 的和本身为 $1$ 大段的划分成极长连续段，直接贪心即可。代码。

F. A Growing Tree

发现每次加边只需要给节点打上一个标记来抵消修改，需要查询到根的距离，用大融合一题的方式去做即可。这里选择直接拉了一个 LCT，代码。

*1661 (EDU)

https://codeforces.com/contest/1661。

D. Progressions Covering

我们从后往前扫描数组，这样就可以发现贪心加就可以了，因为加的是最大的还不会浪费。那么记录总操作数 $op$ 和当前加的和 $s$。对于当前的数，操作数是 $\left\lceil \cfrac{b[i]-s}{k}\right\rceil$（实际这个 $k$ 需要根据 $i$ 调整），往前扫一个，当前的和就减少了操作数，操作数会减少 $i+k-1$ 时增加的操作数。代码。

E. Narrow Components

看到 $n=3$ 和区间查询不难想到线段树，初始假设所有点都不在一个连通块内，然后合并两段区间时暴力并查集合并即可。代码。

F. Teleporters

可以将原问题划分成几段，然后对于每一段放置传送器的话分的约均匀越好，全局的最小两相邻传送机距离应该是一个（尽可能满足平均），这样就可以用 $f(x,k)$ 来表示 $0\rightarrow x$ 中额外插入 $k$ 个的最小代价，显然是好求的。

直接二分需要安装的传送机数量？我们好像没有办法 check，只知道最多传送机数量的话没有一个合适的贪心策略。我们对另一个条件——总花费进行考虑。因为花费越大直接意味着传送机数量越少。

注意到 $f(x,k-1)-f(x,k)$ 随着 $k$ 的增大单调不增，这样可以在外层二分其值 $v$ 来代表一个段内的最小传送机距离，找出一个 $f(x,k-1)-f(x,k)\ge v$ 的最大 $k$，而 $k$ 越大花费越小，直接利用 $k$ 来进行贪心求出每一段的最小代价，与 $m$ 比较来确定二分的答案。

设二分出来的答案是 $k$，选完之后 $m$ 的值还有剩余，我们尽可能多的值选择 $k+1$ 来榨干 $m$ 的剩余价值。

时间复杂度 $O(n\log^2 V)$。代码。

*1795 (EDU)

https://codeforces.com/contest/1795。

A. Two Towers

实际上说的是只能有一个不满足的位置。代码。

B. Ideal Point

只选覆盖 $k$ 的线段即可。代码。

C. Tea Tasting

二分出每杯茶能够被哪些人喝即可。代码。

D. Triangle Coloring

答案是固定的，乘法原理乘起来即可。代码。

E. Explosions?

总花费更少，那么我们就希望炸掉的血量更多。当变成一个严格单峰函数的时候（令 $a_i\leftarrow a_i-i$ 变成单峰来处理），也就是搞成一段一段公差为 $1$ 的等差数列，就可以炸了。

容易想到通过单调栈处理这个东西，正反做两遍然后合并即可。代码。

F. Blocking Chips

二分答案，如果能向下走就向下，贪心即可。代码。

G. Removal Sequences

$a_i=0$ 一定是最后被删去的，考虑逆时旅人，令 $d_i\leftarrow \operatorname{deg}(i)-a_i$，按照这个进行拓扑排序即可求出一组合法解。

考虑求出不美好的点对，如果这张有向图的两个点直接互相可达，那么这是不美好的。bitset 直接统计即可。代码。

*1845 (EDU)

https://codeforces.com/contest/1845。

F 是 NTT，不会，也不打算学。

C. Strong Password

搞两个指针分别扫两个序列即可。代码。

D. Rating System

发现其是利用 $k$ 来消掉一个最小子段和的影响。代码。

E. Boxes and Balls

对于移动到目标状态，我们只需要消耗最小次数，剩下的来回交换刷分即可。

将问题抽象成这个东西：

• 初始前缀和序列 $s$，目标前缀和序列 $s'$；
• $\sum |s'-s|\le k$，
• $\sum |s'-s|\equiv k\pmod 2$。

设 $f_{i,j,k}$ 代表当前填前 $i$ 个数，填了 $j$ 个 $1$，$\sum |s'-s|=k$ 的方案数，考虑当前位填 $0/1$：

$$f_{i,j,k}=f_{i-1,j,k-|j-s_i|}+f_{i-1,j-1,k-|j-s_i|}$$

注意到 $|j-s_i|$ 的取值范围是 $O(\sqrt{k})$ 的，否则 $\sum$ 这堆东西会超过 $k$。只枚举这些值即可。代码。

PART III

话。

*1898 (Div. 2)

https://codeforces.com/contest/1898。

E. Sofia and Strings

为什么赛时不仔细看看。

考虑贪心去做这个东西。扫描 $t$，维护 $s$ 中可用字母的位置，如果不存在字母则直接无解，然后在位置中删去不能再被利用的字符。代码。

F. Vova Escapes the Matrix

先手判断迷宫类型。如果根本走不出去，那么全堵死；如果只有一条路，那么除了最短路的全堵死；否则，考虑每个点都记一下自己可以到哪些终点，然后对于终点只有两个的点可以进行答案的计算。代码。

*1879 (EDU)

https://codeforces.com/contest/1879。

D. Sum of XOR Functions

考虑拆位考虑贡献，记录所有值为 $x$ 的下标和，那么 $l$ 的贡献减去它们即可。代码。

E. Interactive Game with Coloring

是个套着交互皮的构造。发现一般情况下只需要两种颜色，如果同时有两个深度不同的三连单链，那么才需要三种颜色。代码。

F. Last Man Standing

对于第 $i$ 位选手，选择难度 $x$ 的题，那么它能挨的轮数是 $h_i\left\lceil\cfrac{a_i}{x}\right\rceil$。考虑枚举 $x$，用最大轮数和次大轮数的差来更新答案。可以想到用调和级数复杂度来枚举 $\left\lceil\cfrac{a_i}{x}\right\rceil$ 的值，那么问题就弱化成了区间查询 $h$ 的最大次大值，ST 表维护即可。代码。

*1839 (Div. 2)

https://codeforces.com/contest/1839.

D. Ball Sorting

可以注意到要移动就会直接移动到目标位置，而这样的话最长上升子序列就一定会被保留。用 $i$ 个 $0$，实际上就是最长上升子序列中，允许拥有 $i$ 个连续子段。设 $f_{i,j}$ 代表使用 $i$ 个 $0$，最长上升子序列以 $j$ 结尾的最大保留数，选取答案时要以 $1\sim n$ 结尾均考虑。代码。

E. Decreasing Game

结论不难猜出，然后随便判判就好了。代码。

*1834 (Div. 2)

https://codeforces.com/contest/1834。

E. MEX of LCM

可以发现有效 LCM 数量不会很多，因此只统计有效 LCM，暴力扫描，丢进 set 里即可。代码。

F. Typewriter

我们先来考虑答案是什么。每一轮一定是最后拿起一个 $p_i<i$ 的东西，然后把它放到下一轮的位置上。也就是说需要维护 $\sum [p_i<i]$，差分维护即可。代码。

*1901 (EDU)

https://codeforces.com/contest/1901。

F 是几何，不做。

D. Yet Another Monster Fight

FST 了，呵呵。

直接输出计算的答案就好了。代码。

E. Compressed Tree

设 $f_i$ 代表以 $i$ 为根的子树形成一个被删不掉的整体的最大权值之和，然后讨论一下儿子个数转移即可。代码。