AT/CF记录

· · 个人记录

$\color{red}★$ 表示分析过程曲折复杂，且有启发的题。 $\color{yellow}★$ 表示两者兼有，神仙题！ ❤️ 我也不知道为什么但就是比较喜欢 上述标记和题目难度没有必然关系。 ## ARC187 ### A 略 ### B 发现，对于一对 $(i,j)$ 如果满足 $a_i\le a_j$，那么 $i\sim j$ 每个点都在一个连通块里。因为对于 $i<k<j$，要么 $a_i\le a_k$ 要么 $a_k\le a_j$。 所以有 $(i,i+1)$ 不连边的条件： $$ \min_{j=1}^{i}a_j>\max_{j=i+1}^{n}a_j $$ 令 $A$ 里满足该条件的 $i$ 共有 $x$ 个，那么 $f(A)=x+1$。 于是对于每个 $i$ 去考虑多少种方案中 $(i,i+1)$ 不连边。令 $p_i$ 表示 $1\sim i$ 的最小值，$s_i$ 表示 $i\sim n$ 的最大值（$-1$ 分别视为 $m$ 和 $1$）。 考虑枚举 $1\sim i$ 的最小值 $x$，则 $i+1\sim n$ 的最大值必须 $<x$，所以 $s_{i+1}<x\le p_i$。 考虑前半部分，如果 $x\ne p_i$，那么必有一个 $-1=x$。考虑看哪些 $-1=x$，则剩下的只要 $>x$ 即可。令 $q$ 为 $1\sim i$ 中 $-1$ 的个数，所以方案为： $$ \begin{aligned} \sum_{i=1}^{q}C_{q}^{i}(m-x)^{q-i}&=\sum_{i=0}^{q}C_{q}^{i}1^i(m-x)^{q-i}-(m-x)^{q}\\ &=(m-x+1)^{q}-(m-x)^q \end{aligned} $$ 否则如果 $x=p_i$，那么所有 $-1$ 只要 $\ge x$ 即可，即为 $(m-x+1)^q$。 考虑后半部分，由于只要 $<x$，所以在 $1\sim x-1$ 中任选，即为 $(x-1)^{p-q}$，$p$ 为 $-1$ 的总数。两部分相乘即为总方案数。 ## ARC201 ### A 令 $cnt_a$ 为执行 $a+b$ 的操作数，$cnt_b$ 为执行 $b+c$ 的操作数，则要最大化 $\min(cnt_a,cnt_b)$。 发现减少一个 $cnt_a$ 最多只会增加一个 $cnt_b$，所以可以先最大化 $cnt_a$ 后调整。 对于 $i$，如果 $a_i+c_i\le b_i$，那么 $cnt_a$ 和 $cnt_b$ 分别加上 $a_i$ 和 $c_i$ 即可；否则优先处理 $cnt_a$，令 $x=\min(a_i,b_i)$，$y=\min(b_i-x,c_i)$，则分别加上 $x,y$ 即可，同时减少 $cnt_a$ 以增加 $cnt_b$ 的次数最多为 $\min(x,c-y)$。 最后处理，如果 $cnt_a\le cnt_b$，不需要减少了，答案就是 $cnt_a$。否则，令 $s$ 为最多减少的次数，如果 $cnt_a-s\ge cnt_b+s$，则答案为 $cnt_b+s$，否则就是 $\frac{cnt_a+cnt_b}{2}$。 ### B 不断执行如下操作（每个体积都可以添加无限个价值为 $0$ 的物品）： - 若 $w$ 为偶数，那么可以将体积为 $1$ 的物品合并为体积为 $2$ 的物品，并将 $w$ 和所有物品体积除 $2$ 显然不影响答案。合并的时候显然将价值从大到小相邻合并最优。 - 若 $w$ 为奇数，那么将体积为 $1$ 的物品中最大价值取出，再变成第一种情况即可。 ### C 首先容易想到建出 Trie，考虑统计答案。 令每个字符串的结尾点为关键点，将 Trie 上只有一个儿子的点补上一个叶子，于是问题转换成选出若干个关键点，使得所有根到叶子的路径都经过选出的点的方案数。 这东西可以树形 dp，在线每次修改只会修改一条链。 ### D 如果将 $A$ 和 $B$ 递增排序，那么最优的方案肯定是选取一个点 $s$ 分成 $[1,s-1]$ 和 $[s,r]$ 两段区间，然后每段区间 $a_i$ 和 $b_i$ 交替相加。 要求 $[s,r]$ 区间 $a_i$ 和 $b_i$ 交替相加结果都 $\ge m$ 且 $s$ 最小，因为 $s$ 越大 $\max(a+b)$ 越大。然后直接二分即可。 ## CF2150 ### D 首先思考哪种状态是合法的，设 $p_i$ 表示 $i$ 位置上的人数，容易发现 - $p_i$ 的值是一段连续区间，假设是 $[L,R]$。 - $\forall i\in (L,R)$，$p_i$ 是奇数。 是合法的充要条件，模拟过程可得到。 于是考虑统计权值和，假设 $L=1$，则枚举 $R$，不妨换一种形式表达 $p$： - $p_1=2q_1+x(1\le x\le 2)$， - $p_i=2q_i+1(1<i<R)$， - $p_R=2q_R+y(1\le y\le 2)$。 考察 $q_i$ 的性质，容易发现 $\sum q_i=\frac{n-x-y-(R-2)}{2}$，然后求 $\sum 2q_i a_i$。然后发现 $q_i$ 是轮换对称的，所以 $q_i$ 的期望值就是 $\frac{n-x-y-(R-2)}{2R}$，于是就变成 $w \frac{n-x-y-(R-2)}{R}\sum a_i$，其中 $w$ 为 $q_i$ 的方案数，用隔板法可求。 ### F 第一步选 $k=3$，因为 wxr 说加的边最多。 然后考虑第二步直接选 $\lceil\frac{d}{2}\rceil+1$，其中 $d$ 为原图任意一棵生成树的直径，接下来说明对于每个点对一定存在长度为 $p=\lceil\frac{d}{2}\rceil$ 的路径。 - $dis_{u,v}\ge p$，把树上 $u,v$ 路径拿下来，先若干步 $2$ （由于第一步是可行的）后再若干步 $1$ 即可。 - $dis_{u,v}<p$，考虑找到点 $x$ 使得 $|u\leadsto x\bigcup u\leadsto v|=p+1$，这样的 $x$ 是一定存在的，因为考虑距 $u$ 最远的点，其距离一定是 $\ge p$ 的（直径某一端点 $t$）。然后考虑构造，分类讨论即可。 ## CF2152 ### F 首先把条件改一下，因为 $y$ 有序，假设选了 $p_1,p_2,\cdots,p_k$，则等价于要求 $\forall i\ge 3,y[p_{i}]-y[p_{i-2}]>z$。 所以考虑对于每个 $i$，找到前面第一个 $j$ 满足 $y_i-y_j>z$，记为 $t_i$，则 $p_{i-2}\le t[p_i]$。 然后再考虑，区间 $[l,r]$ 选出来的子集一定可以包含 $\{r-1,r\}$，否则将后两个替换为 $r-1$ 和 $r$ 一定不劣，于是考虑从 $r-1$ 和 $r$ 开始跳 $t$，这个可以倍增预处理，如果跳到某个位置相同后，则要将其中一个数 $-1$，然后变成子问题。 ### G 首先将题目要求转换为，有多少个 $u$ 满足 $a_u=1$ 且子树内没有其他 $1$。然后有子树，有翻转，考虑括号序。将 $a_u=1$ 进来和出去分别看为 $1$ 和 $3$，$a_u=0$ 看为 $0$ 和 $2$，则转为求最长的 $131313\cdots$，用线段树维护即可。对于子树翻转，交换 $1,0$ 和 $2,3$ 即可。 ## CF2159 ### D2 首先需要注意几个关键性质： - 选取的右端点一定是后缀最小值，不然替换后一定不劣。 - 任何区间代价都 $\le 2\log V$，形如 $[1,2]$、$[2,4]$、$\cdots$。 - 增加一段的代价 $\le 3$，如果 $\ge 4$，一定能分成两段，使得分别为 $2$ 和 $\lceil \frac{x}{2}\rceil$。 考虑对于一个右端点 $i$，求出 $w(l,i)\le j$ 的最左的 $l$，记为 $f_{i,j}$，考虑然后求。即枚举左边加入段的代价，设 $L_{i,j}$ 表示 $\mathtt{cost}(l,i)\le j$ 的最左的 $l$，那么容易转移 $f_{i,j}=\min \{L_{f_{i,j-k}-1,k}\}$。 差分算答案即可。 ### E 先考虑求 $[x^k]F(n)$。直接做显然不好做，注意到 $n\le 3\times 10^5$，考虑分块。 假设块长为 $B$，先递推算出 $F(0\sim B-1)$，这一部分时间复杂度 $O(B^2)$。然后要求出任意一个 $F(n)$，还要算出 $F(0,B,2B,\cdots,\lfloor \frac{N}{B}\rfloor B)$，假设当前要求 $F(m)$。 由于 $F(m)=f^m$，其中 $f=ax^2+bx+c$，考虑一种常见思路，即先求导。 $$ F(m)=f^m\\ F'(m)=mf^{m-1}f'\\ F'(m)f=mF(m)f' $$ 考察 $[x^{k-1}]$（以下记 $F[k]$ 表示 $[x^k]F(m)$）： $$ F[k]kc+F[k-1](k-1)b+F[k-2](k-2)a=m(F[k-1]b+2F[k-2]a)\\ F[k]=\frac{(m-k+1)bF[k-1]+(2m-k+2)aF[k-2]}{kc} $$ 所以先求出 $F[0]$ 和 $F[1]$ 便可递推算了，这一部分时间复杂度 $O(\frac{N^2}{B})$。 然后每次询问 $n,k$，只需要算 $F(n\bmod B)\cdot F(\lfloor \frac{n}{B}\rfloor B)$ 的第 $k$ 项，假设两个多项式长度分别为 $p,q$，则这一部分时间复杂度是 $O(\min(p,q))=O(B)$ 的。所以取 $B=\sqrt N$ 最优。 现在是求前 $k$ 项的和，只需要将 $F(0,B,2B,\cdots)$ 做一遍前缀和即可。 ### F 将路径上的点拿出来建序列，则 $f$ 是一个滑动窗口。 首先发现由 $f(l,p\sim p+l-1)$ 构成的函数值是一个单谷函数，证明考虑如果 $f(l,p)<f(l,p+1)$，则 $f(l,p+1)$ 为第一次出现，将对后 $l$ 个产生贡献。 于是枚举 $l$，分成 $\lceil \frac{n}{l}\rceil$ 段，考虑对每一段找到其极值点，然后放到优先队列里每次往左右扩展即可。 考虑二分，首先考虑将区间里的数从大到小覆盖未覆盖的数，区间长度为 $l$，则对于一段平台，如果位于谷底左侧则一定作为后缀出现，否则作为前缀出现。假设当前二分区间为 $[L,R]$，对于中点 $mid$ 其函数值为 $v=f(l,mid)$，如果 $v$ 第一次出现的位置为 $s\ge L$，则一定是作为前缀出现，否则是后缀，根据此移动 $L,R$ 即可。由于谷底可能是中间一段区间，所以需要注意二分写法。 总询问次数 $O(n\log^2 n+m)$。 ## CF2154 ### D 出得好。注意到每次割掉一个叶子需要考虑的最少，只需要保证当前不在这个点即可。联想到题目 $3n$ 的限制，考虑当前的深度的奇偶。执行 $1$ 操作后奇偶一定会发生变化，所以只需要让猫猫当前的深度跟当前叶子的深度不一样即可。 ### F1 由于 $n\le 3000$，考虑直接枚举 $k$。先想如何判断一个序列是否满足，即对于 $a_i\le k$，必须要求 $a_i$ 前面有 $a_i-1$ 个数也 $\le k$；对于 $a_i>k$，必须要求 $a_i$ 前面有 $a_i-k-1$ 个数也 $>k$。 在知道这个过后，容易通过组合计数算出合法的方案数。 ## AGC074 ### B 考虑不变量。首先很显然的是交换不会改变和，然后再注意到由于长度相等，所以等价于两个区间里的 $1$ 下标分别加和减定值 $x$，所以交换不会改变 $1$ 位置的下标和。 容易发现上面两个条件合起来是充要的。考虑怎么构造，不妨设 $f_i$ 和 $g_i$ 分别表示 $A$ 第 $i$ 个 $1$ 的下标和 $B$ 第 $i$ 个 $1$ 的下标，考虑最终使 $f_i=g_i$。将其分成 $f_i<g_i$ 和 $f_i>g_i$ 两类，相当于第一类的 $1$ 要向右移，第二类要向左移。于是容易想到将两类对应起来，为了不影响后续操作，第一类要从后往前改，第二类要从前往后改。每次可以将 $|f_i-g_i|$ 相差较小的那个归位，那么操作次数是 $O(cnt_1)$ 的，如果 $cnt_1>cnt_0$ 翻转即可。 ### C 神奇构造。考虑 $\text{or}$ 一个数的本质，相当于将 $p$ 中这些位抹除，于是想构造出 $p_1\le p_2\le p_3\le \cdots$，那么 考虑递归构造。 先考虑 $n$ 是奇数，先将 $(n-1)/2$ 构造出来，并复制一份，记当前最高位为 $d$，将第二份 $d+1$ 位设为 $1$，显然原来 LIS 为 $i$ 的变为 $2i$ 了，考虑通过第 $n$ 个数来调整出 $2i+1$。考虑将第 $n$ 个数设为 $p_{n-1} \text{ or }2^{d+2}$，然后把 $a_{2i+1}$ 设为 $a_{2i}$，$a_{2i} =a_{2_i}\text{ or }2^{d+2}$，即是否抹去 $p_n$ 的最高位。 $n$ 是偶数只需在 $n-1$ 的基础上加一个元素即可。 ## AGC002 ### F 先考虑判定。容易发现一个充要条件，即对于任意前缀颜色 $0$ 的个数需要大于等于其他颜色种类数。于是考虑设 $f_{i,j}$ 表示已经放了 $i$ 个颜色 $0$ 的球，$j$ 种其他颜色的球的方案数。转移只需考虑下一个放哪种球，放非颜色 $0$ 的球时要一次放满 $k-1$ 个，通过组合数算即可。 ## AGC006 ### D 看到中位数，考虑二分+01序列。即新序列 $b_i=[a_i\ge x]$。考虑这个01序列的变化规律，手玩容易发现当相邻两个 $b$ 相等时会向上拓展，直到被其他相邻段合并。然后再观察到影响答案的是距离终点最近的相邻段，并且唯一，于是这道题就做完了。 ## AGC007 ### C 没啥思路，考虑手玩一下。比如当 $n=3$ 时： ![](https://cdn.luogu.com.cn/upload/image_hosting/jhf1iyzv.png) 考虑变到 $n=2$ 每段长度的期望，容易得到 $$ \frac{8d+5x}{6}\ \ \ \ \ \frac{8d+15x}{6}\ \ \ \ \ \frac{8d+25x}{6}\ \ \ \ \ \frac{8d+35x}{6} $$ 发现这又是一个等差数列，并且分析第一段得到首项为 $\frac{(2n+2)d+5x}{2n}$，第二段减第一段得到公差为 $\frac{(2n+4)x}{2n}$。于是只需要算出每一步的期望长度 $\frac{\sum_{i=0}^{2n-1}(d+ix)}{2n}=d+\frac{2n-1}{2}x$。 ## CF2168 ### B 考虑到如果答案为 $n-1$ 一定可以确定出这段区间有 $1$ 和 $n$。由于单调性，所以可以二分出包含 $1$ 和 $n$ 的最短前缀和最短后缀，便得到了 $1$ 和 $n$ 的位置集合。 第一个人只需简单的返回 $1$ 和 $n$ 的先后顺序即可。 ### C 拜谢 @wxr_。考虑到增删元素操作，我们为了还原出本来的序列，考虑返回一个异或和为 $0$ 的子集。打表发现 $1\sim 20$ 异或和为 $0$ 的子集个数恰为 $2^{15}$。 发现 $1\sim n$ 的子集异或和在 $0\sim 2^{\lfloor\log (n)\rfloor +1}-1$ 均匀随机，考虑归纳证明。 ## ARC209 ### A ⑩ 首先判断最开始不合法和 $k$ 是奇数的情况。那么第一个人每次操作会使序列不合法，第二个人每次要让序列合法。 可以证明第一个人只会不断删除一侧的字符，直接判一下就好了。 ### B $\color{red}★

假设 c 是 s 中出现次数最多的字符，并出现了 A 次，其他字符出现了 B 次。

首先考虑 A\le B，比较显然存在策略使得 f(s')=0。

然后是 A>B，设只考虑 S 中只包含 c 的偶回文子串个数为 g(S)，那么显然有 f(S)\ge g(S)。考虑将 s 重排使得 g(s') 最小且 f(s')=g(s')，那么 s' 即为答案。

再设 h(n) 表示 n 个 c 组成字符串的 f 值，那么有 h(2m)=m^2,h(2m+1)=m(m+1)。显然将 c 划分段数越多越好，即分割成 B+1 个连续段，设 l_i 分别表示每段的长度，那么 \displaystyle g(s')=\sum_{i=1}^{B+1}h(l_i)，注意到 h 是一个凸函数，满足 \displaystyle h(a)+h(b)\ge 2h\left(\frac{a+b}{2}\right)，所以我们又希望 l_i 尽量接近。

设 A=k(B+1)+r(0\le r\le B)，那么 l_i 中有 r 个 k+1 和 (B+1-r) 个 k。现在已经达成 g(s') 最小的条件，则还需要满足 f(s')=g(s')。影响因素是当 l_i 为偶数时计算了包含第 i 段的答案，那么考虑让 l_i 尽量为奇数。注意到当 a 是偶数时 2h(a)=h(a-1)+h(a+1)，所以当 l_i 中有多个偶数时便可以将其中两个变成奇数。所以最终只会剩下至多一个偶数，让其为开头即可。

ARC214

C

结论很简单。令 s=\sum P_i，当 s 是奇数时显然无解。否则令 \displaystyle a=[x^{\frac{s}{2}}]\prod \left(1+x^{P_i}\right)，则答案为 a^2-2a。

- 如果 $i\in U\wedge i\in V$，则 $i\in A$。 - 如果 $i\notin U\wedge i\notin V$，则 $i\in B$。 - 如果 $i\in U\wedge i\notin V$，则 $i\in C$。 - 如果 $i\notin U\wedge i\in V$，则 $i\in D$。 可以画韦恩图理解。然后当 $U=V$ 或者 $U=\complement V$ 时，$A,B,C,D$ 存在空集。