contest & vp 记录

· · 个人记录

掀起热火朝天的大生产运动 （

# $\color{green}\bf\Delta$ ARC 114 $\red\bigstar

赛时

通过 AB

第一次尝试 ARC。

A 是个憨憨搜索。习惯了 CF 的 1A 感觉解法有点怪，所以 15min 才做掉，还丢了两发罚时。

B 是个显然的题，符合要求的集合一定是若干环的组合，而每个连通块恰有一个环，所以统计连通块数目即可。很快就做掉了。

接下来搞 C ，试了几次直接 DP 都做不了。考虑每次向序列中插入最大值，拆贡献后 DP 得到 O(n^3) 做法，不会优化，于是就挫了。

后面的题都没心思看。

最后得了个 Rank 655, Performance 1687 ，感觉实属一般。

赛后

这个题压根就不用 DP 啊……直接大力拆贡献就好了。

对于一个给定的序列，一种操作数目最小的构造方法是 ： 找出最小值，并对这个值的覆盖区间进行操作，然后除去这个值，分治为若干段处理。

考虑在一次操作的左端点将其统计。

对于位置 A_i ，若存在 A_j=A_i ，使得 j<i 且 \min_{k=j}^i\geq A_i ，那么其可以被从 A_j 开始的一次操作顺便处理掉。

反之，则没有其他操作能处理这个位置，故该位置是某个操作的左端点。

枚举 i,c 表示在第 i 个位置填写 c ，求该位置为某个操作左端点的方案数。

总方案数显然是 m^{n-1}。

对于不合法的方案，枚举（从右到左第一个符合条件的） j 求和可得 ：

S(i,c)=m^{n-i}\sum\limits_{j=1}^{i-1}m^{j-1}(m-c)^{i-j-1}

该式容易利用递推 O(nm) 求出。

A 耗时较长，提取问题本质的过程还不够严谨迅速，对一般组合问题的分析缺乏经验和耐性。

B 性质非常顺利的看了出来，还算没掉链子。

C 体现出了发散思维上的不足，在思考时往往走错方向就一去不返。

这是两重作用的结果 : 技巧积累并不是瓶颈，但应用经验（尤其是多方向试错）的缺乏限制了方向的判断。积累往往造成先入为主的反面效果，而混淆了问题的本质。

另外一点，在思考问题时要先对难度等级进行预判，在赛场/考场上能快速筛选掉很多过于复杂的思路，节省时间。

\color{blue}\bf\Delta ARC 111

赛时

通过 ABCD

这个 A 正常点了，分别维护余数和商，进行快速幂即可。5min 做掉了。

B 又是个并查集题，每个连通块分别处理，树的贡献是 n-1 ，其他任意图的贡献都是 n（至少能看成一棵基环内向树）。5min 做掉了。

C 是个构造题，难度开始起来了……一开始没啥方向，发了一会呆，心一横决定随便构造些方法，至少得到些强的上界。

想了一会发现只需要让最重的人不停跑就好了，拿到货了就让第二重的人跑，每个联通块分别处理就做完了。这个用了 20min。

D 又是构造题，好像很经典的样子。

显然 c_i 相等的点一定是若干个强连通分量（根据基图的连通性），把将连通分量建立好后，其余的边从大指向小即可。

中途几次忘记保证有解白想半天……

然后不知道怎么构造强连通分量，甚至想要动用欧拉回路，但感觉太复杂了就没有继续想。

后来想到缩强连通算法 Tarjan ，那我随便找一颗 dfs 树然后其他边尽力向上指试试。好像卡不掉，那就交一发试试。过了！

这时候只剩 40+min 了，看了看 E 发现不对劲，印象中群友有提到过 ARC 出类欧，于是离场看了看真是类欧……又发现最后一题难度分奇高，遂弃赛。

插入原场面，大概得了个 Rank 175, Performance 2319 ，感觉还行。

赛后

本场发挥不错，主要靠的是运气和灵感。对组合问题的分析果断了一些……

但还是因为一些小失误弄出了两发罚时，下次要小心对待。

\color{blue}\bf\Delta ARC 059 \red\bigstar

赛前

vp 作为一种活动在机房内持续……

太晚的 ARC 洛谷没有爬，有点不方便，于是打算尝试一场较早的。

鉴于大家觉得之前的几场难度有点高，我偷偷看了看难度评分，选了一场比较平缓也没有难题压轴的 Round。

赛时

30min All kill

这个 A 不是 联合省选2020 D1T3 的 5 分暴力吗？ 这手气……

B 中字符串只有小写字母，枚举过半的字符，然后随便做。

C 当各个 x 确定时就是个暴力卷积题。为一个区间时，利用乘法分配率，还是个暴力卷积题。

D 发现被删掉的按键为 0/1 是没有要求的，而显现的按键是有要求的，不妨看做每一步按键都有两种方案，最终除掉 2^{|s|}。

观察数据范围，考虑 \rm DP ，设 f[n][m] 为按了 n 次键，字符串长度为 m 的方案数，则有转移 ：

\begin{aligned} f[i][0]&=f[i-1][0]+f[i-1][1]\\ f[i][j]&=2*f[i-1][j-1]+f[i][j+1] \end{aligned}

写完就过了。ARC 059，就这？

插入原场面，大概得了个 Rank 4, Performance 3200 ，感觉牛逼。

赛后

这一场感觉确实没有什么运气成分，只能说发挥平稳，没有降智，也没有手抖搞出罚时。

感觉这一场的题目 ATC 的风格体现得并不是很明显，难度相对低，而且白给 C 是中国选手的传统艺能。

还是老话说得好，“一个人的命运，当然要靠自我奋斗，但也要考虑到历史的进程……”

\color{blue}\bf\Delta ARC 107 \red\bigstar

赛前

四题场体验比较奇怪……本着 vp 为 contest 服务的原则，我们决定回到六题场。

再次偷看了难度评分，选了一个平缓又没有难题压轴的场。

赛时

30min 通过 ABCD

A 是个乘法分配律憨憨题。 B 随便化化式子。

C 看起来有点复杂，找几个性质 ：

于是对行列分别考虑置换数，将能交换的两个位置连边，一个联通块内部可以任意置换，于是答案是联通块大小的阶乘的乘积。

D 设 f[n][m] 表示 n 个数和为 m 的方案数，有转移 f[n][m]=\sum\limits_{k=0}f[n-k][2(m-k)] 。

不难用类似前缀和的方法优化。

26min 内做了四题，感觉很稳。看 E 发现巨大神必……

打了个表发现奇怪性质，想了 30min 出了个奇怪做法，但没写完。

出了场发现性质是错的，正解实现其实非常简洁。

插入原场面，大概得了个 Rank 99, Performance 2523 ，感觉还行。

赛后

将 A_{i,j}=A_{i-1,j-1} 的位置称为好位置。打表发现若 \min(i,j)\geq 5 则 A_{i,j} 必为好位置。

则对 O(n) 个不好的位置模拟，好位置批量计算即可。

本场发挥稳定，没有手抖和降智，但也没有出彩表现，就整了一些中规中矩简单题。

\color{green}\bf\Delta ARC 115 \red\bigstar

赛时

60min 通过 ABCE

开 A ，降智了，乱想一些奇怪的东西， 15min 才做掉。

BC 都是憨憨构造题， B 取矩阵边界，C 考虑下界就得到答案了。

D 想了半天都不会。转而看 E ，发现是白给线段树题，于是很快做掉了。

然后就啥也不会，摸了。被后浪吊打。

最后大概得了个 Rank 83, Performance 2573 ，感觉还行。

赛后

考场上大概想了一半吧……

考虑图为一棵树的情况，选出奇度点集合 S ，若 |S| 为奇数，则方案数为 0 (显然) ，否则方案数恰为 1。

证明考虑归纳。

设 f[u] 为处理子树后，是否留有奇点。根据结论，若子树内奇点个数为奇数，则 f[u]=1 ，否则 f[u]=0。

若各个子树的 f 的和（包括本点）为偶数，则将其全部连接即可得到合法方案。显然方案是唯一的。

于是， {\rm Ans}[k]=[k\bmod 2=0]\dbinom{n}{k}

接下来考虑连通图，求出图的一颗生成树。

考虑不在生成树内的边集的任意一种状态，若原先要求的奇度点为偶数个，则考虑完这些边的影响后，要求树边形成的奇度点仍然为偶数个。于是问题转化为树的情况。

于是，则有 {\rm Ans}[k]=[k\bmod 2=0]2^{m-n+1}\dbinom{n}{k}

最终，将各个连通分量的答案卷积即可。若朴素实现，复杂度为 O(n^2) ，若使用分治 FFT ，复杂度为 O(n\log^2n)。

在 A 题降智，进一步反映了积累造成先入为主的反面效果。

E 题实属出题人失误送分……看来上分一半还得靠场。

思考 D 题时一定程度上被数据范围误导了，提取问题核心矛盾的能力仍然不足。

\color{blue}\bf\Delta ARC 116 \red\bigstar

赛时

60min 通过 ABCDE

A 用约数个数定理，讨论一下 2 因子个数即可。

B 排序后随便求和。

C 我的想法有点复杂，先考虑相邻两个数必须不同的情况，记 d[x][k] 为长度为 k 且结尾为 x 的序列个数，这里 k 只有 O(\log n) 级别，不难利用约数求和 O(n\log^2n) 求解。

然后相邻相同的元素用插板法计算方案即可。感觉这题还挺有意思的，可为什么难度评分这么低呢……

D ：[SDOI2019]移动金币 的子问题。

E : [NOIP2018 提高组] 赛道修建 类似物。

F 想了一会，不会，遂知难而退。

插入原场面，成绩为 Rank 82, Performance 2616 ，感觉还行。

赛后

看了看 friend 榜，人均 ABCDE ，罚时还巨大低。流下了没有技术含量的泪水.bmp

本场 ATC 的风格体现得并不是很明显，难度相对低，对中国选手而言比较白给。

手速不太行，而且 E 题手抖搞出一发罚时，除此之外没啥问题。

看了看 C 的做法，其实可以 1\log 的，还是我想复杂了。

F 属实牛逼，单独开个文章学习一下。

\color{green}\bf\Delta ARC 117

赛时

10min 通过 AB

A 是憨憨构造题，随便咋搞。 B 排序后每次能操作的是一个后缀，于是差分，+1 再乘起来。

然后开 C ，似乎和 ARC 107 E 非常相似……我还研究过这个真值表，结论是不可做 /yun

头铁了 1h 啥也不会，溜了。

成绩为 Rank 702, Performance 1636 ，感觉拉跨。

赛后

官方解法和我猜想的也差不多……其实再多试错几次就好了。

将三种颜色看做 0,1,2 ，则题目中的运算 a\otimes b=-(a+b)\bmod 3。（没错，就是凑的，但也只可能这么凑了吧）

于是可以分别统计贡献，答案即为

(-1)^{n-1}\sum\limits_{i=0}^{n-1}\binom{n-1}{i}c_i

注意需要 \rm Lucas 定理。

\color{blue}\bf\Delta ARC 104 \red\bigstar

赛前

一场 vp 两小时是吧，那一天四场不是问题啊 /cy

赛时

通过 ABCD

AB 是拿来凑数的吧，一个小学数学，一个暴力题。

C 有点意思，发现合法的方案每个联通块中的区间都一样长，区间 DP 即可。有若干细节。

班主任来和我商量备考学考的事情，花掉 5min

D 分数规划后变为有负次数的 OGF ，边乘边除即可 O(n^3k)。中间想错了几次细节。

E 题写到一半。

插入原场面，成绩为 Rank 84, Performance 2601 ，感觉还行。（怎么老是精准命中这个名次）

赛后

继续写了 15min 把 E 题过了。

大力搜索位置的排序情况，然后套上 [数学记录]CF1295F Good Contest 计算贡献系数即可。

\color{blue}\bf\Delta AGC 031

赛前

第一次尝试 AGC 的 vp。

发现好多 AGC 被散做污染了，趁把题面看完之前，赶紧打几次 vp 。

赛时

通过 ABC

A 各个字符只能选一个或不选，将出现次数加一乘起来。

B 发现可供操作的同色球对子中，只需要考虑中间没有同色球的那些（即相邻的那些）。记 f[i] 为只触发 \leq i 的操作的方案数，随便 DP 一下。

C 有点意思，若不限 a,b 则是格雷码。

将所有输出异或 a ，则问题转化为 a=0。

由于有 2^n-1 （奇数）步，若 b 含有偶数个 1 ，则无解。

否则，先考虑 b 全为 1 ，且有 m 位的情况，即从 000...0 到 111...1 。称此时的答案为“步进码”。

构造方案如下图 ：（可以先大力搜索 m 较小的情况观察规律）

接下来考虑一般情况。

设 b 中为 0 的位有 m 个。

对于 b 中为 1 的位，用步进码处理。将每个步进码复读 2^m 次，缝合上正反交替的格雷码来处理为 0 的位。

具体操作见代码 ： 评测记录

插入原场面，成绩为 Rank 158, Performance 2431 ，感觉还行。

赛后

\color{blue}\bf\Delta ARC 105 \red\bigstar

赛时

通过 ABCDE

A 是迫真人肉搜索， B 瞎猜结论 gcd。

C 题搜索方案后贪心，有点麻烦，但本质不难。

D 题是个博弈，分类讨论。

E 题又是个博弈。

若只剩两个联通块（一个含 1 另一个含 n），则接下来只会把内部的边连完，根据还能连的边的奇偶性即可得到答案。解题的关键在于奇偶性。

若两个大小为奇的联通块相连（合并），会新增奇数条可以连的边，但也会扣掉一条边，故无影响。

若两个合并的联通块中有一个偶数，则会新增偶数条可以连的边，但也会扣掉一条边，剩余边数奇偶性改变。

分类讨论 ：

最后 5min 过掉了 E。搞出了很多罚时。

插入原场面，成绩为 Rank 55, Performance 2685 ，感觉不错。

赛后

\color{blue}\bf\Delta ARC 112 \red\bigstar

赛前

在爆肝的路上一去不复返了（汗）

赛时

60min 通过 ABCD

A 白送，B 看错题白送。此时 20min 过去了。

C 题是博弈论，显然可以划分子树为子问题。

称拿掉根的金币的人为后手，记 f[u] 为从 u 点出发，先手和后手获得的硬币只差，e[u] 表示先后手会不会转化。

对于 u 的直接儿子 v ，分为三类 ：

  1. f[v]>0,e[v]=0
  2. f[v]\leq 0,e[v]=0
  3. e[v]=1

先手首先拿完第一类，然后两人交替争夺第三类，最后某个倒霉蛋连续吃掉剩下的第二类。

于是不难转移。

D 首先观察性质，无论从哪里出发，总可以前往墙壁，然后可以转外圈，所以从外圈上出发时最劣的。

某个地面若可以到达，相当于点亮了一行一列。要么点亮全部的行，要么点亮全部的列。

将同行同列的地板连边，每个联通块分别考虑，可以用一个外圈的地板作为跳板，连接这个联通块。（若包含外圈，则无需连接）

用 bitset 维护每个联通块覆盖的行列集合。

插入原场面，成绩为 Rank 86, Performance 2613 ，感觉还行。

赛后

\color{green}\bf\Delta ARC 119

赛前

两个星期没打比赛啦，终于有个良心 ARC 可以打了。

赛前几乎把这事忘了，在写一些零零碎碎的东西，还剩两分钟的时候才开始准备，有点匆忙。

稳住，不慌.jpg

赛时

通过 ABCDE

A 暴力枚举 b 即可。

B 一开始看错题意，浪费了一些时间。此时 zhoukangyang 老哥手感火热，已经切掉三题了 /fad

操作中 0 能跳过 1 的段，于是只考虑 0 的移动。

发现将 S 中第 i 个 0 与 T 中第 i 个 0 匹配是最优的。

结论 ： 记 S 中第 i 个 0 的位置为 p^S_i ，类似地有 p^T_i ，则答案为 \sum\limits_{i}[p^S_i\neq p^T_i]

两边往中间走即可构造对应方案。

C 先考虑如何判定某个序列 a_{1\sim n} 能否被清除。

操作是可逆的，于是任意操作都不影响序列能否被清除。

对于 a_i 先将后面的数两个两个加上 a_i。

这样，对于 a_{1\sim n-1} ，相当于做了个前缀和。对于 a_n 则是奇数或偶数位置的和。

不断将前两个元素抵消，查看能否消完即可。

手玩能够发现，一个序列能被消除的充要条件是 ： 奇数位置和 = 偶数位置和。

写出前缀和的式子，移项，拿个 std::map 统计一下相同对子数即可。

D 这个题有点阴间，过 F 的两个大佬都跳了。

又看错了一次题意……晕。

对于红格 (x,y) 看做二分图中的一条无向边。

对于二分图中的每个联通块，取出一棵生成树。

设这个联通块包含的左侧点（行）集合为 S_1 ，右侧点集合（列）为 S_2 ，通过适当地操作，可以 ：

将必须消除的行数，必须消除的列数，可以自由选择是行或列的数目，都统计出来，然后枚举究竟消几行几列取 \max。

构造方案是在生成树上 dfs。儿子先操作，若儿子被父亲消到，则消除方向改变，否则不变。具体见代码。

有点难写……搞完已经过去了 80min。

E 我艹这不是憨憨题吗？

相邻两个数组成点 p_i=(a_i,a_{i+1})。

翻转 (l,r] 的收益是 |p_l.x-p_r.x|+|a_l.y-p_r.y|-|a_l.x-a_l.y|-|a_r.x-a_r.y| 。

处理绝对值时利用二维偏序即可。将坐标系翻转对称可以减少代码量。

成绩为 Rank 27, Performance 2977 ，感觉不错。

赛后

这个 F 好难啊，先放着吧。

\color{blue}\bf\Delta ARC 118

赛前

题做累了？来场 vp ，调整一下节奏。

赛时

30min 通过 ABC

A 二分一下并线性查找。

B 先考虑 B 数组能为实数的情况。先支付整数部分，然后选择剩余量较大的优先支付。

（然而被卡精度了……惨）

C 先考虑 n=3 怎么做，可以构造 \{6,10,15\} 。

D 搞了半天都没搞出来，应该很接近了。这个难度 gap 有点大啊…… 插入原场面，成绩为 `Rank 164, Performance 2325` ，感觉一般。 ## 赛后 - **D** Hamiltonian Cycle 先求出 $p$ 的原（特判 $p=2$），然后将 $a,b$ 写成 $g^x,g^y$。 于是问题转化为，有一个大小为 $p-1$ 的环，每次可以前进或后退 $x$ 或 $y$ 步，要求构造一个哈密顿回路。 若 $gcd(x,y,p-1)>1$ 则无解。 求出 $d=\gcd(p-1,x)$ ，此时 $d\perp y$ ，于是 $0,y,2y,...(d-1)y$ 模 $d$ 下互不相同。 可以证明，对于 $i\in\big[0,(p-1)/d\big),j\in\big[0,d\big)$ 的 $ix+jy$ 都是互不相同的。 将上述 $(i,j)$ 列成矩阵，不难发现，题目中的操作相当于在循环矩阵中四连通移动。 记 $n=(p-1)/d,m=d$ ，则要求的是 $n\times m$ 四连通循环矩阵的哈密顿环。 由于 $nm=p-1$ 是个偶数，$n,m$ 必有一个为偶数。先横走一趟，来回绕即可构造方案。 # $\color{green}\bf\Delta$ ARC 120 ## 赛时 > 45min 通过 ABCD A 题观察一下性质，讨论掉最大值就能快速算了。题出得不错。 B 题显然是 $i+j$ 相同的区域恰好被经过一次，且顺序也是定好的，故这个区域是同色的，之后就简单了。 C 题将 $A_i,B_i$ 加上 $i$ 就转化为了相邻交换构造映射最小步骤数问题。 D 题有点意思，先考虑 $A$ 只有 $0,1$ ，且 $0,1$ 个数相同的特殊情况。 此时 $0,1$ 内部匹配无贡献， $0,1$ 之间的匹配才有贡献。 如下策略可以使得所有匹配都在 $0,1$ 之间 ： 维护一个栈，从前往后扫描，加入 $A_i$ 时，若栈顶与 $A_i$ 相同，则将 $i$ 入栈并输出左括号，若不同，则弹栈并输出右括号。 接下来考虑原问题。 策略 ：保证匹配在前 $n$ 小与前 $n$ 大的 $A$之间（ $A$ 若有相同则按照编号比较大小）。 这样，每个 $A$ 的贡献都是与中位数的差值。可以证明任意其他策略都不会更优。 E 题观察了一会，啥也没看出来。 搞了搞 F ，列出一坨组合数之后就不会了…… 成绩为 `Rank 138, Performance 2368` ，感觉一般。 上黄啦！ ## 赛后 # $\color{blue}\bf\Delta$ ARC 121 ## 赛前 好久没打 vp 了，来一场爽一爽~ ## 赛时 > 通过 ABCE A 先求出最远点对（疆域四至），然后讨论其余点对“有一个是最远点对中的点”“都不是最远点对中的点”即可。 B 若三种颜色出现次数均为偶数，则答案为 $0$ 。否则有两种颜色为奇数，两种方案 ： “两个奇数色各找一个匹配”“两个奇数色各找一个，分别找两个两个偶数色匹配”，不难排序后线性扫描。 C 猜个结论，尽量让交换减少逆序对，若无法减少，则尽量不破坏下一轮能操作的逆序对。 经过三个细节题的毒打，此时已经 50min 了。 D 看了很久不会，于是开 E。 E 考虑容斥，钦定 $k$ 个匹配违反规则，然后树上背包即可。 F 似乎并不难，但时间不多了，遂弃。 插入原场面，成绩为 `Rank 66, Performance 2767` ，感觉还行。 ## 赛后 # $\color{green}\bf\Delta$ ARC 122 ## 赛前 千呼万唤始出来……话说 AGC 啥时候有啊？ ## 赛时 > 通过 ABCDE A 随便考虑一下贡献系数。 B 显然 $x$ 选中位数除以二。 C 经典的斐波那契拆分。 D 考虑按位贪心，若最高位为 $0,1$ 的数的数目均为偶数，则划分为两个子问题。否则找两堆数之间的最优匹配作为答案。 E 先用 Prho 分解，问题转化为有若干个二进制数，按合适的顺序排列，使得前缀 or 严格单调增加。 猜个结论，每次贪心地选择使得 or 的位数增加最少的数。 成绩为 `Rank 20, Performance 3130` ，感觉不错。 ## 赛后 这一场的难度断点比较靠前，便宜我了。 # $\color{green}\bf\Delta$ AGC 054 人生第一场 AGC ！ - [AGC 054](https://www.luogu.com.cn/blog/command-block/agc-054-post) 成绩为 `Rank 439, Performance 1872` ，感觉拉跨。还要多锻炼才行啊。 # $\color{blue}\bf\Delta$ ARC 106 $\red\bigstar

赛前

刚睡醒，揉眼睛…… 大吼 ：开vp！

赛时

A 枚举憨憨题，没看清题目白给 15min+2x5min

B 随便搜一下，判两类和是否相等就好。反复确认了题面，确实是这样。一遍过了。

C 是个构造题，挺平凡的，但是因为没看清题目等种种原因 WA 了很多发。

这时净时间已经过去 35min ，罚时 6 发，心态有点崩。缓了口气继续打。

D 用二项式拆开之后是平凡的。

E 能抽象成二分图匹配。考虑二分答案并用 Hall 定理判定。然而算错复杂度踌躇了好一会才开始写。

最后 3min 还在调，几乎放弃希望了。突然过了样例，一看时间还有 20s，想要交题发现网没了……

把网修好后一交，过了，就算我压哨绝杀吧。

插入原场面，成绩为 Rank 80, Performance 2593 ，感觉还行。

赛后

\color{blue}\bf\Delta AGC 028

赛前

差不多两个月没打 vp 了（国赛附近几场没有记录）……下午就是集训队互测，来一场试试。

赛时

A 题 lcm 和 gcd 搞搞就没了，因为边界问题 WA 了一发。

B 题，发现贡献都是求和，没有乘积，于是可以分别考虑每两个位置之间的贡献。发现是一堆阶乘求和，推一推变成上指标求和。

此时过去 36min ，看来反应变慢了……后面的题想了 20min 都不会，睡大觉。

插入原场面，成绩为 Rank 142, Performance 2358 ，感觉一般。

赛后