contest & vp 记录

rlc202204 · 2023-07-18 12:54:55 · 个人记录

\color{blue}\bigstar Educational Codeforces Round 81 (Rated for Div. 2) \color{red}\checkmark

赛时：

通过前四题。

A, B, C 较为简单。

D 题数论题，之前做题时做过，所以很快就过了。

但之后发现之前的做法虽然是的对的，但我的理解是错的。

E 题没有思路，想了一个多小时也不会。

赛后：

E 题是一个很有意思的线段树，其实是有可能做出来的。主要是赛时分析不够耐心，对这类题目不够熟练。

F 题大概是一个分段优化的动态规划，很有意思。

• [数论记录]CF1295D Same GCDs

• [DS记录] CF1295E Permutation Separation

• [DP记录]CF1295F Good Contest

总结：

写代码基本问题不大，但是对问题的分析和转化依然不够熟练。

\color{blue}\bigstar Codeforces Round 638 (Div. 2)

赛时：

并不完全是这场比赛，因为第五题很多同学都做过，所以老师就换成了 Educational Codeforces Round 97 的第五题和第六题。

A 题很简单的贪心。

B 题很有意思，若 \sum_{1 \le i \le k}a_i=\sum_{2 \le i \le k+1}a_i，则会得到 a_1=a_{k+1}，所以最终的答案是以 k 为周期。

所以我们只需要将所有出现的数随便排成共 k 个，重复 n 次即可。

C 题也是贪心加分类讨论。

前三题做的还行。

D 题做了一个多小时，还是有点意思。

首先最少天数可以直接确定，即二进制下的位数。

我发现最终如果序列是 a_1,a_2,\dots,a_n 那我们总共会有 (n+1)+a_1\times n+a_2 \times (n-1) + \dots + a_{n-1} \times 2+a_n 个细菌。

那我们就可以先二分高位的值，看最高位至少是多少才能使后面可以满足最后的细菌大于等于要求个数，然后从大到小确定即可。

当然 D 题好像还有很好写的做法。

D 题耗了太多时间，E 题是之前作业提单中的题话说题单中49道就8道没做结果这道恰好没做，当然之前打了暴力当没有过，现在稍微想了一下就像出来了转化，然后开始写。

不到 20 分钟写完，结果一交上去 WA on test 103，然后比赛结束了。。。。

赛后：

发现原来是答案的初值写成了 0，改成 1 就过了。

F 题看不懂，也不想看了。

当然这场比赛的原第五题我做过，挺有意思的。

• [DP记录]CF1437E Make It Increasing

总结：

D 题耗了太多时间，CF 的题不能想复杂了，还是要观察题目的性质和结论。

\color{red}\bigstar Educational Codeforces Round 152 (Rated for Div. 2)\color{red}\checkmark

赛时：

做出 ABD。

A 题很简单。

B 题一眼就知道绝对不是模拟，想了一下就会了，直接按照取模后的数排序，也很快过掉。

C 题上来第一个想法是哈希，但觉得哈希会被卡，于是去找规律，想到写一个函数去判断两个复制之间的大小，然后从小到大排序，再统计，统计可以用 x = y 等价于 x \le y 并且 y \le x。

然后就磕了 1 个小时也没写对，过了样例但没过。

然后就去看 D 题。

D 题第一眼是线性 dp，然后再想了想发现几个有趣的性质。

如果有连续的非 0 段，这一段所有数都可以只花一个硬币，如果这段中有 2，那同时这段两边的 2 个 0 也都可以一起变色，否则只能其中一个变色。

然后我们只需对每段分开统计即可。是一个贪心。

众所周知我不会用循环去处理这种分段，于是写了并查集。

然后一发就过了。

回过头来继续看 C 题，发现哈希才是正道，然后开写。

结果我很智障，偏要等比数列求和而不是预处理，下标还打错好多，最后没写完。

最后是 Both division 并且 show unofficial 的 2143 名。

赛后：

哈希做法过了 C，但是 C 题的正解真的很巧妙，学到了。

E 题赛后自己独立做了一下，然后感觉这题好像没有那么难，直接乱搞好吧。

第一遍只写了一个单调栈加暴力枚举没过，然后想了一下发现这东西可以优化，还是单调栈，然后复杂度玄学但是过了？

F 题很有意思，希望以后自己能独立做出这种题。

• [Str记录]CF1849C Binary String Copying

• [杂题记录]CF1849E Max to the Right of Min

• [图论记录]CF1849F XOR Partition

\color{red}\bigstar Codeforces Round 889 (Div.2)

赛时：

通过 A,B,C1。

A 题很简单，特别像学校有一次模拟赛的题。

B 题上来就觉得最长的肯定是 1 开始的若干个，想了一会儿就想到了证明，如果 x \not |n 则答案不会超过 x-1，而最后答案肯定没多大，所以直接枚举就好了。

C1 题不会，没思路，感觉样例简直是逆天，啥规律也没有。

然后就草稿纸加观察样例快一个多小时。

然后终于发现貌似可以然一个数很大，然后给第二个数加上，再翻倍，再个第三个数加上，以此类推，都为负数就到过来。

这样就过了 k \le 50 的 C1，但我由于智障 i-- 写成 i++ 吃了两发罚时。

然后不会 k \le 31 的 C2，我这个方法想不到怎么优化了。

D 题不会。

E 题不会期望。

F 题交互题怎么能会呢？

最后排名 2950。

赛后：

C 题没发现全变是负数或正数时只用 n-1 次操作，学到了。

• [构造记录]CF1854A1&2 Dual

\color{red}\bigstar ABC 313

赛时：

通过 ABCDE，排名 460，performance 1894。

A 题很简单。

B 题很简单，n \le 50 直接搜索，结果忘了计数器清零，样例还没测出来，吃了一发罚时。

C 题一看这不模拟赛原题吗？好像还更简单欸，直接秒了。

D 题一看交互大事不妙，但是后面的题感觉更难，只能硬着头皮想。

先想到了 n-k+1 次求出 1 与 k+1 \sim n 每个数是否相同。

然后就去想 1 与 2 \sim k，想了半天终于想了出来。

然后打完代码提交，结果 WA 了。

貌似是第一次交互题没有 TLE，非常开心。

一看就错两个点，很无语。

想了一会儿，测了一下 n=2,k=1，结果询问了 3 次。

发现如果 k=1 就没有后面的了，改了就过了。

再看 E 和 F，E 应该是找规律，F 是期望。

最终选了去做 E（赛后发现非常正确）。

E 题首先直接猜如果两个相邻元素都比 1 大肯定不行，找不到反例，证明直接想出来了。

然后相当于两个非 1 数隔了若干个 1，并且 1 的数量在不断增长。

然后好像扫一遍就做出来了？

赶紧写代码，然后提交，结果一发就过了。

还剩 5 分钟，就摆烂了。

赛后：

正常发挥吧。

• [构造记录]AT1630 [ABC313D] Odd or Even

\color{red}\bigstar Educational Codeforces Round 153 (Rated for Div. 2)

赛时：

通过 ABCD，Both Divison 排名 195，Divison2 排名 97。

A 题很有意思的题目，想了一会儿。

B 题分类讨论加贪心，题目确实不错。

C 题一眼博弈论+树状数组（上课刚讲），感觉比前两题显然多了。

D 题一看 |s| \le 100 绝对区间+插值 DP，写了个 O(n^4)，然后一大堆智障错误调了 1 个小时才过，很无语。

E 题没时间了。

然后本来结束时是 299 名，结果睡一觉起来直接变成 200 名，原来 D 题有 100 多条成功的 hack，最后捞了个 195 名，勉强上首页。

赛后：

D 题好像不用区间 DP 也行，不过反正都是 O(n^4)。

E 题是一个最短路，题目真的不错，可惜没想出来。

F 题啥玩意儿，不会。

• [DP记录] CF1860D Balanced String

• [图论记录]CF1860E Fast Travel Text Editor

\color{blue}\bigstar Educational Codeforces Round 100 (Rated for Div. 2)

赛时：

A 题直接推式子，不难，但第一次忘了操作次数必须是 7 的倍数，吃了一发罚时。

B 题灵光一现，果真是好题，根据 \min\{a+b\} \le \frac{a+b}{2} 来做。

C 题发现是大模拟，结果写完 WA on test 7，然后不知道哪儿错了，非常无奈。

于是看 D 题，没思路。

再看 E 题，这不就是一个模拟+拓扑排序吗？（话说这题是怎么评到 2400 的？）

然后就些 E 题，写了一会儿就写完了，然后依然不知道 C 题哪里错了。

由于报名了马上来的 EDU 154，所以就放弃了。

赛后：

看了测试数据才发现 C 题初值设小了，改了就过了。

这套题目的 B，D 是真的有意思，E 题个人感觉就是非常简单的图论模拟和拓扑排序。

F 题感觉是小学奥数，结果一看评级 CF 3100，洛谷黑题直接放弃。

大概是 rk1100 这个水平。

• [构造记录]CF1463B Find The Array

• [贪心记录]CF1463D Pairs

\color{red}\bigstar Educational Codeforces Round 154 (Rated for Div. 2)

赛时：

通过 AB。

A 题手算，不是 71 就是 17。

B 题感觉好难啊，看着数据范围像是区间 DP 的样子，但是 B 题绝对不会靠算法，显然结论题。

由于没有看到字符串以 0 开头 1 结尾，想了 20 分钟才想出来把字符串分两段检查，然后过了。

然后是噩梦的开始。

C 题感觉和 100 的 题一样都是大模拟，结果错了 4 发也不会。

D 题没思路。

然后就继续想 C。

最后还剩 5 分钟时突然想出了 D 题的结论，结果代码太过仓促，错了一些地方，最后没有过掉。