command_block 的博客

command_block 的博客

contest & vp 记录

posted on 2021-03-17 14:43:03 | under 记录 |

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

$\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)$ 求出。

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$

赛前

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

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

赛时

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)$ 个不好的位置模拟,好位置批量计算即可。

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

$\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)$。

在 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 ,感觉拉跨。

赛后

  • 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

    其实赛时已经想到欧拉序乱搞了,只是怀疑正确性,没敢写。

  • 总结

    顺风场拼手速,逆风场练脑子。

    对于真正有 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 计算贡献系数即可。

$\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 ,感觉还行。

赛后

  • 总结

    若做出同等难度的题目,水平较低的场中,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 ,感觉不错。

赛后

$\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$ ,通过适当地操作,可以 :

  • 消除整个 $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 !

成绩为 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

  • [数学记录]ARC106F Figures

  • 总结

    这场比赛的题目较为套路,没有什么思维量,然而我却暴露出很多问题。

    第一个是心态不够稳定,纯粹只是害怕,讨厌当下的境遇,又畏惧未来的麻烦。心态放松一点,发挥会平稳很多。

    第二个是思考的方向不对,我总结了以下三个原则 :

    • 思路严格化。对于每一个做法,都要从复杂度,信息利用率等等角度作基本的思考,不能只是根据感觉草草判断。

    迷雾中的一线光明是诱人的,大光中的一缝暗影是令人疑惧的,然而它们都只是本来的大小。

    • 要把时间花在主要矛盾上。对于那些希望不大的方向,判断出阻力之后,尽早试着转向。换了好几个方向都思考不出来,也是正常的。

$\color{blue}\bf\Delta$ AGC 028

赛前

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

赛时

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

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

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

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

赛后