Atcoder ABC & ARC & AGC 泛做记录

tongzhenxuan · 2023-02-17 19:36:41 · 个人记录

主打一个不定期，不连续更新。

ABC 130

• E difficulty: \color{blue}{1676}

  简单容斥

2. ## ABC 165 - ### F difficulty: $\color{blue}{1843}

树上主席树，注意细节，用数据结构优化求LIS

ABC 244

• G difficulty: \color{yellow}{2117}

  图上问题转树上问题 + 调整思想

我们将图上的问题转化到生成树上（这里直接采用dfs生成树），我们可以先遍历整棵树，如果有一个节点不符合要求，那么我们可以直接在它和它父亲之间反复横跳一遍（就是一个调整的思想），然后对于根节点我们判断一下，直接看最后是否要回到根节点即可。

对于 ans \le 4N 的证明，我们遍历时一条边经过两遍，反复横跳最多一次也是经过两遍，得证。

ABC 295

• E difficulty: \color{yellow}{2157}

  期望 + 巧妙的概率问题转化

首先我们想到期望的一般求法，我们会设 p_i 为第 K 大数为 i 的概率，但是我们发现这个概率是不好求的，所以根据zyp学长的建议，我们把定义改成 p_i 为第 K 大数 \le i 的概率，最后我们只要倒序操作 p_i = p_i-p_{i-1} 即可计算出它的概率，首先我们可以对已知序列计数，找出现在 i 为第几个数，从而计算出我们至少还需要多少个 \le i 的数，然后我们可以进行一个简单的组合数计算和统计。

result

• F difficulty: \color{yellow}{2306}

  数位dp + 字符串匹配的思想

不错的数位dp练手题，注意我们记录字符串匹配信息的时候只需要记录最后一个匹配到哪里就可以了，这已经包括了之前很多的信息，然后就像KMP失配之后重新跳回前面就可以了，由于数据较小我们可以暴力匹配。

result

• G difficulty: \color{yellow}{2306}

树上的并查集应用 + 强连通的理解。 这是一道不错题，将树上同一个强连通分量的节点都用一个并查集的代表点来表示，然后修改操作和树链剖分操作类似，然后并查集合并均摊 O(n \log n) （只有路径压缩）。

相似题：UVA1504 Genghis Khan the Conqueror

result

ABC 310

• F difficulty: \color{blue}{1938}

一道概率dp，开始时我考虑背包，但是我们发现出现 2,8,3,7 这样的情况时，我们的背包会把 3,7 出现的概率和 2,8 出现的概率合起来，但是这只是一个状况，不能做（甚至出现概率大于 1 的情况）。如何解决重复，观察到 K \le 10 所以我们可以直接状压。状压之后我们记录的是一个局面的概率（前 i 个数可以凑出 S），就不会把一种情况两种方案算重。然后转移的时候只要钦定选 i 投出来的数和不选的情况取或即可。最后统计答案，即统计出现 10 的局面概率和即可。

贴一篇题解

result

• G difficulty: \color{orange}{2696}

一眼看出基环树，一眼可以差分，一眼可以循环解决。

但是就是写不出来，失败链接，努力了一个早上导致下午心态崩溃直接死掉大摆。

倍增好题。

然后转头去学习题解，发现有点难看懂，倍增真的很巧妙，因为树和环都比较好倍增（即出边小于等于一条的图），所以基环树也可以倍增不过分吧？因为这样的图走 k 步的点是确定的。然后考虑怎么把 k 凑出来，我们可以模仿快速幂的写法把一位位凑出来。最后警告，因为我们的 k 是凑出来的，所以我们不能提前预处理，必须边处理边把移动图，这样才能把应该对齐的点对齐，不然的话凑 k 的时候会出现一些近的点重复计算。具体可以看代码和注释。

result

ARC 163

A,B较为简单。

• C difficulty: \color{blue}{1711}

  C题是喵喵构造题，首先看到这种sb的 \frac {1}{n} 结构，我们可以想到一些奇技淫巧。

比如我就考虑倍增 \frac{1}{2} + \frac{1}{4} + ... 形式，发现它 \frac{1}{2^k} = \frac{1}{2^k+2^{k+1}}+\frac{1}{2^{k-1}+2^k} 感觉自己又行了。但是死了，A_i \le 10^9 。

后来问了刘老师，加上题解的加持。我们发现裂项也是有关两个不同的 \frac{1}{n} 的形式，且可以多一个数，是一个很有希望的性质，\frac{1}{n} = \frac{1}{n+1} + \frac{1}{n(n+1)}，裂项移项得。然后我们就可以通过 n-1 个数构造出 n 个的情况，（就是用一次上面这个等式），我们考虑小根堆和判重，时间复杂度和数字大小都可通过。

result

ABC 309

• F difficulty: \text\color{blue}{blue}

  还可以的树状数组/线段树题，原先以为cdq

ABC 270

• F difficulty: \text\color{blue}{1834}

  建立虚点的好题。巧妙地将不好直接使用的生成树条件变成好做的边

  ABC 215

• F difficulty: \text\color{blue}{1854}

  可以直接二分答案，然后排序做后缀，因为式子的特殊性，所以可以把 x,y 分开做，也就是两个各符合条件即可，那我们可以先满足一个条件，然后再满足的集合里面取极值。

  ABC 216

• G difficulty: \text\color{blue}{1963}

  差分约束比较板的题。

hint:但是我们在做差分约束的时候可以考虑将边的巧妙定义和对答案的巧妙求解，这样我们或许可以逃过spfa制裁，使用高贵的dijkstra！

ABC 217

• G difficulty: \text\color{yellow}{2047}

  挺好的计数题，注意答案的不重不漏，我们钦定每组按最小值排序，这样就不会重复。考虑到重复的情况一定是最小值不有序的。然后我们考虑到我们dp的过程是一个个加入的，所以我们已经保证了不重不漏。

hint: 这题如果整体考虑一点都做不了，所以我们对于一个问题如果做不了可以考虑一个个元素考虑，算是换个思路。

几百年后

不定期记录好题。

AGC005D

2943 但是远古评分。

联考考到的题，赛时切了，第一眼钦定了容斥，然后找一下如何容斥，把有关联的一些东西连成图，整体dp一下就好了。

但是貌似可以组合数卷积NTT？？

ARC175C

2116

还不错的性质发现和调整。 先弱化题目然后调整满足答案。

切了。

ARC175D

2276

还不错构造题，想到了子树大小的背包，以及如何构造，但是没有想到如何数学归纳证明都是可以都取到。

构造跟AGC055C的LIS异曲同工

AGC055B

2059

发现了 ?ABC 到 ABC? ，但是没注意到操作可逆。

AGC043C

2872

巧妙的将形式转化为了博弈论。然后普通卷积。

考察了博弈的基本DAG模型，SG函数的基本性质。NIM定理。

AGC045C

2758

倒着观察结局状态，然后找充要条件，构造证明，dp。

统计结局的时候并且操作很难dp，那么我们一般考虑充要条件。

AGC055A

2070

不错的观察题，构造题。

AGC045B

2873

小结论，需要推一下不劣。正常还是比较好想的。

可以自由调节的局面，初始时可以调到极端。

AGC045A

2070

线性基好题。切了。

AGC050B

2091

区间dp好题。观察一些结论。

AGC050A

1973

小喵构造。

AT_wtf19_b

超级nfls题，贡献一样的时候，取模意义下，我们可以拿一位去平衡。

AGC055D

3506

超级结论题，再看可能还是不会做。寻找dp充要条件，构造证明。