contest & vp 记录

掀起热火朝天的大生产运动 （ $\color{green}\bf\Delta$ 表示 `contest` ，$\color{blue}\bf\Delta$ 表示 `vp`。 $\red\bigstar$ 表示已补完。 # $\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` ，感觉实属一般。 ## **赛后** - **C** Sequence Scores 这个题压根就不用 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)$ 求出。 - [[DP记录]ARC114D Moving Pieces on Line](https://www.luogu.com.cn/blog/command-block/post-ji-lu-arc114d-moving-pieces-on-line) - [[数学记录]ARC114E Paper Cutting 2](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-arc114e-paper-cutting-2-post) - [[??记录]ARC114F Permutation Division](https://www.luogu.com.cn/blog/command-block/post-ji-lu-arc114f-permutation-division) - **总结** 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` ，感觉还行。 ## **赛后** - **E** Mex Mat 将 $A_{i,j}=A_{i-1,j-1}$ 的位置称为好位置。打表发现若 $\min(i,j)\geq 5$ 则 $A_{i,j}$ 必为好位置。 则对 $O(n)$ 个不好的位置模拟，好位置批量计算即可。 - [[图论记录]ARC107F Sum of Abs](https://www.luogu.com.cn/blog/command-block/post-ji-lu-arc107-sum-of-abs) - **总结** 本场发挥稳定，没有手抖和降智，但也没有出彩表现，就整了一些中规中矩简单题。 # $\color{green}\bf\Delta$ ARC 115 $\red\bigstar$ ## 赛时 > 60min 通过 ABCE 开 A ，降智了，乱想一些奇怪的东西， 15min 才做掉。 BC 都是憨憨构造题， B 取矩阵边界，C 考虑下界就得到答案了。 D 想了半天都不会。转而看 E ，发现是白给线段树题，于是很快做掉了。 然后就啥也不会，摸了。被后浪吊打。 最后大概得了个 `Rank 83, Performance 2573` ，感觉还行。 ## **赛后** - **D** Odd Degree 考场上大概想了一半吧…… 考虑图为一棵树的情况，选出奇度点集合 $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)$。 - [[??记录]ARC115F Migration](https://www.luogu.com.cn/blog/command-block/post-ji-lu-arc115-migration) - **总结** 在 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]移动金币](https://www.luogu.com.cn/problem/P5363) 的子问题。 E : [[NOIP2018 提高组] 赛道修建](https://www.luogu.com.cn/problem/P5021) 类似物。 F 想了一会，不会，遂知难而退。 插入原场面，成绩为 `Rank 82, Performance 2616` ，感觉还行。 ## **赛后** 看了看 `friend` 榜，人均 ABCDE ，罚时还巨大低。流下了没有技术含量的泪水.bmp 本场 `ATC` 的风格体现得并不是很明显，难度相对低，对中国选手而言比较白给。 手速不太行，而且 E 题手抖搞出一发罚时，除此之外没啥问题。 看了看 C 的做法，其实可以 $1\log$ 的，还是我想复杂了。 F 属实牛逼，单独开个文章学习一下。 - [[??记录]ARC116F Deque Game](https://www.luogu.com.cn/blog/command-block/post-ji-lu-arc116f-deque-game) # $\color{green}\bf\Delta$ ARC 117 ## 赛时 > 10min 通过 AB A 是憨憨构造题，随便咋搞。 B 排序后每次能操作的是一个后缀，于是差分，$+1$ 再乘起来。 然后开 C ，似乎和 ARC 107 E 非常相似……我还研究过这个真值表，结论是不可做 /yun 头铁了 1h 啥也不会，溜了。 成绩为 `Rank 702, Performance 1636` ，感觉拉跨。 ## **赛后** - **C** Tricolor Pyramid 官方解法和我猜想的也差不多……其实再多试错几次就好了。 将三种颜色看做 $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$ 定理。 - **D** [[NC记录]ARC117D Miracle Tree](https://www.luogu.com.cn/blog/command-block/nc-ji-lu-arc117d-miracle-tree) 其实赛时已经想到欧拉序乱搞了，只是怀疑正确性，没敢写。 - **总结** 顺风场拼手速，逆风场练脑子。 对于真正有 ATC 风格的思维题还是不太适应，难度评分很低的题对我来说依然较为困难…… # $\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](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-cf1295f-good-contest) 计算贡献系数即可。 - [[DP记录]ARC104F Visibility Sequence](https://www.luogu.com.cn/blog/command-block/dp-ji-lu-arc104f-visibility-sequence) - **总结** 解题思路不够清晰明确，导致实现效率低下。 # $\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$ 的位。 具体操作见代码 ： [评测记录](https://atcoder.jp/contests/agc031/submissions/21886877) 插入原场面，成绩为 `Rank 158, Performance 2431` ，感觉还行。 ## **赛后** - **总结** 若做出同等难度的题目，水平较低的场中，`Performance` 会更高。目前来看，简单场更容易上分。 除机制外的具体原因？难的场区分度低（对于我这种蒟蒻），熟练度低导致罚时高，且卡题情况多见。 换句话说，其实是 `ARC` 的难度断点更加适合低水平选手罢了…… # $\color{blue}\bf\Delta$ ARC 105 $\red\bigstar$ ## 赛时 > 通过 ABCDE A 是迫真人肉搜索， B 瞎猜结论 gcd。 C 题搜索方案后贪心，有点麻烦，但本质不难。 D 题是个博弈，分类讨论。 - $n\bmod 2=0$ 先手每次选择最大的一袋加入同一堆中（由于异或是**不进位**的加法，这样很难被异或掉）。 若第 $1,3,5...$ 大的和与第 $2,4,6...$ 大的和相同，则先手必败，否则必胜。 - $n\bmod 2=1$ 此时后手是 $\rm Nim$ 游戏的先手。 后手只需每次将目前最大的一袋加入最大的一堆，不难发现这一堆总能大于其余的总和，故后手必胜。 E 题又是个博弈。 若只剩两个联通块（一个含 $1$ 另一个含 $n$），则接下来只会把内部的边连完，根据还能连的边的奇偶性即可得到答案。解题的关键在于奇偶性。 若两个大小为奇的联通块相连（合并），会新增奇数条可以连的边，但也会扣掉一条边，故无影响。 若两个合并的联通块中有一个偶数，则会新增偶数条可以连的边，但也会扣掉一条边，剩余边数奇偶性改变。 分类讨论 ： - $n\bmod 2=1$ 合并结束时两个联通块一定一奇一偶，合并产生的影响是固定的，直接计算答案。 - $n\bmod 2=0$ 若初始时与 $1,n$ 所在的两个联通块为双奇或双偶，则无法改变。 假设此时对 A 利好，若 B 改变，则 A 下一回合改回来。由于奇有偶数个，故最终不会改变。 若初始时与 $1,n$ 所在的两个联通块一奇一偶，则先手可以控制其变为双奇或双偶，于是必胜。方法类似。 最后 5min 过掉了 E。搞出了很多罚时。 插入原场面，成绩为 `Rank 55, Performance 2685` ，感觉不错。 ## **赛后** - **总结** 思维题做得挺爽，多练练吧。 找性质的时候，不要从顶层设计入手，而是尝试从一些杂碎入手。 思维方式只能慢慢地改…… - [[DP记录]ARC105F Lights Out on Connected Graph](https://www.luogu.com.cn/blog/command-block/arc105f-lights-out-on-connected-graph) # $\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` ，感觉还行。 ## **赛后** - **总结** 整了一些中规中矩简单题。目前看来水平大概在 $2400$ 左右，还有点不稳定。 - [[数学记录]ARC112E Cigar Box](https://www.luogu.com.cn/blog/command-block/arc112e-cigar-box) - [[??记录]ARC112F Die Siedler](https://www.luogu.com.cn/blog/command-block/post-ji-lu-arc112f-die-siedler) # $\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$ ，通过适当地操作，可以 ： - 消除整个 $S_1$ ，消除整个 $S_2$ 但饶过某一列。 - 消除整个 $S_2$ ，消除整个 $S_1$ 但饶过某一行。 将必须消除的行数，必须消除的列数，可以自由选择是行或列的数目，都统计出来，然后枚举究竟消几行几列取 $\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\}$ 。 $n$ 更大时，加入是 $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` ，感觉还行。 ## 赛后 - [[图论记录]ARC106E Medals](https://www.luogu.com.cn/blog/command-block/post-ji-lu-arc106-medals) - [[数学记录]ARC106F Figures](https://www.luogu.com.cn/blog/command-block/post-ji-lu-arc106-medals) - **总结** 这场比赛的题目较为套路，没有什么思维量，然而我却暴露出很多问题。 第一个是心态不够稳定，纯粹只是害怕，讨厌当下的境遇，又畏惧未来的麻烦。心态放松一点，发挥会平稳很多。 第二个是思考的方向不对，我总结了以下三个原则 ： - 思路严格化。对于每一个做法，都要从复杂度，信息利用率等等角度作基本的思考，不能只是根据感觉草草判断。 迷雾中的一线光明是诱人的，大光中的一缝暗影是令人疑惧的，然而它们都只是本来的大小。 - 要把时间花在主要矛盾上。对于那些希望不大的方向，判断出阻力之后，尽早试着转向。换了好几个方向都思考不出来，也是正常的。 # $\color{blue}\bf\Delta$ AGC 028 ## 赛前 差不多两个月没打 vp 了（国赛附近几场没有记录）……下午就是集训队互测，来一场试试。 ## 赛时 A 题 lcm 和 gcd 搞搞就没了，因为边界问题 WA 了一发。 B 题，发现贡献都是求和，没有乘积，于是可以分别考虑每两个位置之间的贡献。发现是一堆阶乘求和，推一推变成上指标求和。 此时过去 36min ，看来反应变慢了……后面的题想了 20min 都不会，睡大觉。 插入原场面，成绩为 `Rank 142, Performance 2358` ，感觉一般。 ## 赛后