CodeForces Contest/VP 记录

还是开个坑记记吧。 [](https://codeforces.com/profile/djwj233) 用 $\color{green}\Delta$ 表示 contest，$\color{Blue}\Delta$ 表示 VP。 ## $\color{green}\Delta$ [Edu Round 115](https://codeforces.com/contest/1598) ### 记录 拿了`Rank 338, Performance 2078(candidate master)`。 赛时做出 ABCDE。 ABC 是弱智题，但 C 没开`long long`吃了一发罚时 D 是一个数数题，直觉挺准确的，但开始写了个假做法，吃了三发罚时 E 是个憨憨模拟题，就直接过了。 F 没搞出来是大失败。 最后 Rating：$0,\textsf{unrated}\color{red}\to\color{gray}708,\textsf{newbie}$。 ### 补题 - Prob. F 是一道 2400 的 DP 题，场上没搞出来。 看到 $n\le20$ 自然想到状压 DP，然后也想到了题解中的几个点，但就是没勇气往下搞（ 我们设 $dp_{i,0/1}$ 为当前状态为 $i$，有不合法前缀（$1$）或无不合法前缀（$0$）的最大答案，显然 $dp_{0,0}=0$，接下来考虑转移。 我们可以得出当前多余的前括号数 $x$，然后枚举下一个要加入的串 $s_k$ 满足它不在 $i$ 的二进制表示中，然后更新： $$ dp_{i+(1<<k),\ check(x,s_i)}\gets \max(dp_{i+(1<<k),\ check(x,s_i)},dp_{i,j}+w(x,s_i)) $$ 其中 $check(x,s_i)$ 表示是否合法，这可以先预处理出 $s_i$ 的最小值 $c$ 然后判断是否有 $x+c\geq0$。 求合法时的 $w(x,s_i)$ 则比较难搞，不过我们可以求出 $s_i$ 所有前缀对应的值，然后预处理所有答案。 [Code](https://www.luogu.com.cn/record/59823713) ### 总结 - `long long`！！！`long long`！！！`long long`！！！ - 这个菜鸡 DP 真的不行，特别是状压，同样地他 DFS 也不行。 ## $\color{green}\Delta$ [CF Round 749 Div.1 + 2](https://codeforces.com/contest/1586) ### 记录 拿了`Rank 529, Performance 2146(master)`。 场上做出 ABCDE。 AB 是 sb 题，随便构造构造；C 刚开始的做法假了，罚了三发，写完时已经 1h10min 了，此时 zak 已经 6 题了。 DE 倒是都切了，F 题有一个和正解差不多的思路但是没写完 最后 Rating：$\color{gray}708,\textsf{newbie}\color{black}\to \color{green}1215,\textsf{pupil}$。 ### 补题 - Prob. F 核心要点在于猜到答案是 $\left\lceil\log_k n\right\rceil$，然后分治地构造即可。 [Code](https://codeforces.com/contest/1586/submission/132337586) ### 总结 - CF 中前面的题卡着就直接扔去写后面的题。 - 要加强构造题的训练。 ## $\color{green}\Delta$ [CF Round 751 Div.2](https://codeforces.com/contest/1602) ### 记录 拿了 `Rank 44, Performance 2236(master)`。 场上做出 ABCD，没罚时。 AB 是简单题，C 是一个猜结论题，D 场上用一个魔改的 BFS 过了，好像和 std 本质相同？ E 场上胡了一个线段树做法，不过后来写了一半电脑死机了就没搞，貌似正解是分治？ 最后 Rating：$\color{green}1215,\textsf{pupil}\color{black}\to \color{Turquoise}1599,\textsf{specialist}$。 ### 补题 - Prob. E 显然最后加入的 $b$ 一定是一个单调递增的形态，所以我们对 $b$ 排序。 之后我们考虑如何去最小化 $a$ 和 $b$ 之间的逆序对数。考虑一种做法：每次选择一个位置，使**之前的比它大的数的个数和之后的比它小的数的个数最小**，然后插入。 易证这个做法的最优性，并且由于我们是从小到大插入的，因此这个位置一定是单调递增的，具有合法性。 我们考虑怎么找到这个位置，容易想到一个做法是从小到大插入 $a_i$ 中的值，然后用线段树解决。 - Prob. F 感觉像是个国王游戏那样的排序后直接贪心，不太会。 $\text{\color{black}c\color{red}mll02}$ 提出可以直接枚举代码，如按和、差、$\max$、$\min$ 排，然后拍拍拍，感觉十分有道理 我观察样例，猜了一个 $\max$ 的结论，错了，猜了一个和的结论，又错了。 好吧，原来正确答案是： ```c++ return max(s,a)==max(temp.s,temp.a) ? min(s,a)<min(temp.s,temp.a) : max(s,a)<max(temp.s,temp.a); ``` 结论猜完了就大致能证了吧。 考虑相邻两个 $(s_1,a_1),(s_2,a_2)$。若 $\max(s_1,a_1)<\max(s_2,a_2)$，则必有： $$ a_2>s_1, a_2>a_1 $$ 或 $$ s_2>s_1, s_2>a_1 $$ 成立。若是前一种，那么把顺序换成 $(s_2,a_2),(s_1,a_1)$ 会导致 $(s_1,a_1)$ 必然无法被取到。 若之前 $(s_1,a_1)$ 就无法被取到，则交换顺序对答案不造成任何影响； 若之前 $(s_1,a_1)$ 就被取到，则交换顺序使答案最大为 $1$ 且由 $a_2>a_1$ 易知之后的情况不会更优。 若是后一种，那么显然无论如何若 $(s_1,a_1)$ 被取到则 $(s_2,a_2)$ 一定能被取到。这样再把 $(s_2,a_2)$ 移到前面是没有意义的。 综上，此时取顺序为 $(s_1,a_1),(s_2,a_2)$ 不会更劣。 而若 $\max(s_1,a_1)=\max(s_2,a_2)$，则有 $\min(s_1,a_1)\le \min(s_2,a_2)$。 这样若 $a_1=\min(s_1,a_1)$，那同上把取顺序为 $(s_1,a_1),(s_2,a_2)$ 不会更劣； 若 $s_1=\min(s_1,a_1)\le a_2$，取顺序为 $(s_1,a_1),(s_2,a_2)$ 也不会更劣； 简单归纳可知对任意数列都成立。 那么这东西是怎么搞出来的捏？ 大致是一个**找不相容对**的思想吧。 ### 总结 感觉发挥还行，就是 E 没打出来体现了个人码力上的不足。 ## $\color{green}\Delta$ [Edu Round 116](https://codeforces.com/contest/1606) ### 记录 拿了`Rank 322, Performance 2160(master)`。怎么次次 Performance 上不了 IM！！ 场上过了 ABCE，C 罚了两发。 AB 是憨憨题，C 有点恶心，不过还好 Edu 罚时不痛 然后跟榜开 E，会了一个做法，然后 1h23min 的时候过了。 这时候 ZCETHAN 和我说了谷歌翻译的 D 题题面，感觉这是个思博题，就切了。 一发，怎么 WA 了？草原来是谷歌翻译的题面错了！！！ 这时还剩 10min 左右，我会了一个做法但没打完，就白给了。 最后 Rating：$\color{Turquoise}1599,\textsf{specialist}\color{black}\to \color{blue}1824,\textsf{expert}$。 ### 补题 - Prob. D 把场上的那个做法打完，还因为数组开小挂了两发。 - Prob. F 场上没开这题，后来尝试自己做。 首先有一个 $\mathcal O(nk)$ 的 Trivial DP，令 $f(x,k)$ 为询问为 $v=x,k$ 时的答案，有： $$ f(x,k)=\sum_{y\in son_x} \max\{1,f(v,k)-k\} $$ 然后我们发现 $k$ 增大时 $f(x,k)$ 不会增大，是非严格单调递减的，随着 $k$ 的增大有些删除操作不执行是更优的，考虑有没有什么 Binary Search 做法。 然后就不会了，看了题解。发现还是太 naive，只要继续往下想就可以了。 就是考虑我们对每个点都把**它什么时候开始保留是更优的**算出来，记为 $g(x)$，但是我们发现这东西不太好算。 正难则反，我们考虑反着枚举 $k$，这样就不断地有新的点被删去，这样用堆去维护当前 $f(x,k)$ 最大的点，借助并查集，$g(x)$ 的值可以方便地算出。 然后我们考虑如何处理询问。显然可以将询问离线，然后倒序处理，这可以和上面的过程一并完成。 具体地，我们删去一个点 $x$ 只改变了 $fa_x$ 的当前儿子个数，但改变了所有 $anc_x$ 的删节点个数。 这可以用树剖那一套在 $\mathcal O(n\log^2 n)$ 内算出，倒过来查子树内删的个树就可以 $\mathcal O(n\log n)$ 了。 调不出来，扔掉了。 ### 总结 - 谷歌翻译是脑瘫！！！ ## $\color{green}\Delta$ [CF Round 754 Div.2](https://codeforces.com/contest/1605) ### 记录 拿了`Rank 353, Performance 2088(candidate master)`。Performance 下 CM 了 场上过了 ABCD，BC 各罚一发。 这场是印度场，恶心得要死！！ABC 都是诈骗题，感觉毫无意义。 D 题意是一个巨大多复杂的构造题，其实也没什么思维含量，但是就一直卡着出不来（ 后来开黑过了，这时候已经 109 min 了。 E 没怎么看，听说是莫比乌斯函数。然后 F 直接 Unavailable  最后 Rating：$\color{blue}1824,\textsf{expert}\color{black}\to\color{Purple}1958,\textsf{Candidate Master}$。 ### 补题 - Prob. E 2400 的题都做不出 首先我们注意到可以有一个 $\mathcal O(qnH(n))$ 的暴力贪心，考虑怎么优化这个暴力。 先做一步很套路的转化：记 $c_i=a_i-b_i$，那么目标就是使所有 $c_i=0$。 我们发现每次变化的是 $b_1$。为了使 $a_1=b_1$，我们不可避免地要做一些在 $1$ 号位置上的全局增减，这是唯一的差别。 因此我们可以先默认 $b_1=0$ 先算一遍，然后加入更改 $b_1$ 对答案的影响。 但是，更改 $b_1$ 导致 $a_1$ 的更改量也要改变，那么后面的一大串东西也都会改。 怎么改呢？我们考虑 $f(n)$ 为第 $n$ 个位置的变化，有： $$ f(n)=-\sum_{d\mid n} f(d) $$ 因此我们可以算出 $f(1\cdots n)$ 中每个数的变化相对 $f(1)$ 变化的系数 $k_i$。 那么答案就是 $\sum_{i=1}^n |k_i x + c_i|$。我们考虑把这几个数按 $-\dfrac{c_i}{k_i}$ 排序然后 Binary Search。 不过这种题写着就来气！！！！ ### 总结 这场发挥太神必了。 - 可能得多做一些套路构造 - 要练练码力 - 最重要的，**尽量避开 Indian Round**！！！ ## $\color{green}\Delta$ [CF Round 755 Div.1](https://codeforces.com/contest/1588) ### 记录 拿了`Rank 327, Performance 2137(master)`。 场上过了 AB 两个煞笔题，然后一直在写 C，先写了几个假做法，后来会了一个巨难写的做法，然后打完调不出来 :( 最后 Rating：$\color{Purple}1958,\textsf{Candidate Master}\color{black}\to\color{Purple}2045,\textsf{Candidate Master}$ ### 补题 - Prob. C 不懂，贺了一个人的代码。 ## $\color{green}\Delta$ [CF Global Round 17](https://codeforces.com/contest/1610) ### 记录 拿了 `Rank 511, Performance 2181(master)`。 场上过了 ABCD，不会 E（ 其中 A 是机房内问 dX 的，B 的贪心我也差点不会（（（ 最后 Rating：$\color{Purple}2045,\textsf{Candidate Master}\color{black}\to\color{Purple}2089,\textsf{Candidate Master}$，还是上不了 Master ### 补题 - Prob. E 场上一个半小时还是不会，看了题解发现十分 nb。 先证明判断一个序列是不是 bad，只需看所有 $i$ 是不是满足 $(a_1,a_i,a_{i+1})$ 是不是 terrible 的，这个东西我场上也发现了，但是还是不会。 考虑设最终答案序列为 $b_{1\cdots k}$，我们枚举 $b_1$，然后有： $$ \forall i\in (1,k], b_i\ge 2b_{i-1} - b_1 $$ 我们尝试直接对每个位置二分构造这个序列，这看上去是 $\mathcal O(n^2)$ 的暴力，但是我们发现： $$ \forall i\in (1,k], b_i-b_1\ge 2(b_{i-1}-b_1) $$ 因此我们只要让 $b_2>b_1$，就能保证序列长度是 $\mathcal O(\log n)$ 的。 这样总复杂度是 $\mathcal O(n\log^2 n)$。 - Prob. I 大博弈论题，看题解。 ### 总结 自己太菜，得做写写 CF 题。 ## $\color{green}\Delta$ [CF Round 757](https://codeforces.com/contest/1614) ### 记录 拿了 `Rank 110, Performance 2181(master)`。 场上过了 A B C D1 D2。 AB 都是思博题，C 是奇妙的结论题，D1 的 DP 瞄了一眼 pbb 才会，D2 是 cmll 教的/dk 最后 Rating：$\color{Purple}2089,\textsf{Candidate Master}\color{black}\to\color{Orange}2152,\textsf{Master}$ ### 补题 - Prob. E 有一个性质，就是最后的答案肯定是关于 $x$ 单调递增的。 然后我们建一棵线段树，每次对当前答案 $<T$ 的所有位置 $+1$，对 $>T$ 的所有位置 $-1$。 [Code](https://www.luogu.com.cn/record/63895810) ## $\color{green}\Delta$ [CF Round 761](https://codeforces.com/contest/1617) ### 记录 场上只过了 A B C D1。 Unrated 所以不会掉分。 ### 补题 - Prob. D2 考虑把 $n$ 拆成 $\dfrac{n}{3}$ 和 $\dfrac{2n}{3}$。用 $\dfrac{n}{3} +6$ 次询问出一个 $1$ 和一个 $0$ 以及两块内的元素，然后 $\dfrac{2n}{3}-2$ 次搞别的块。 - Prob. E 一道好题。我们考虑这个问题的本质：$10^9$ 个点，如果两两之和是 $2$ 的整次幂则连边，求两点之间的最短路的最大值。 画出 $a_i\le 10$ 时的图，我们发现这是一棵树。下面我们尝试证明： > 考虑树中已有 $0\sim n-1$ 个点（$n\ge 0$）时再往里加入一个点 $n$ 的情况。我们找到一个 $t$ 使 $2^{t-1}<n\le2^t$，问题转化为： > > > 求证：$0\sim n-1$ 中，与 $n$ 和为 $2$ 的次幂的数有且仅有 $2^t-n$。 > > 首先，$2^t-n\ge 0$ 成立，且若 $2^t-n\ge n$，则 $n\le 2^{t-1}$，矛盾，故 $2^t-n\in[0,n-1]$。 > > 若还有一个别的数 $2^m-n\in [0,n-1](m\ne t)$，显然有 $m>t$，否则这个数一定会是负数。 > > 这样 $2^m-n\ge 2^{t+1}-n=(2^t-n)+2^t\ge 2^t\ge n>n-1$，矛盾。 > > 因此这是唯一的数。 综上所述，我们建出树求直径即可，复杂度 $\mathcal O(n\log^2 A_i)$。 ## $\color{green}\Delta$ [CF Global Round 19](https://codeforces.com/contest/1617) ### 记录 场上过了 A B C D E，各种白给但是最后救回来了一点。 B 题目看错，C 结论假了，导致过 C 时已经 50 min 左右了。 Rush 出 D E，看 F 但是最后没做出来qwq 还好没掉分。 ### 补题 - Prob. F 场上随便选了一个点当根，然后后面情况巨大多复杂。 实际上我们可以直接选最大值当根，这样处理会简单得多。 ## $\color{green}\Delta$ [CF Round 773 div.1](https://codeforces.com/contest/1641) ### 记录 场上过了 ABC。 A 是憨憨题，好像有一车人场上没开 `long long` FST 了。 B 是一个 nb 构造题，场上搞了半小时搞出一个做法然后过了。 C 是数据结构，转化完问题后一直在想离线然后各种寄，最后听 mer 说是一个弱智套路题，在线过了。 上到了 $2222$（喜） ### 补题 - Prob. D 这题有 `bitset` 卡常做法但是有点恶心。 做法是要用到一个结论：枚举 $B$ 中的每个非空子集，检查它在 $A$ 中是否出现。 对于出现的子集，若大小为奇数则 $cnt+1$，否则 $cnt-1$。 这样当且仅当 $A,B$ 互斥时 $cnt=0$，否则 $cnt=1$。这可以用 Trie 来 $\mathcal O(2^m)$ 维护。 那么搞一个双指针就可以了。 ### 总结 - 要多了解 DS 的一些套路； - 其实那题离线也能做，做不出时得换换思路。 ## $\color{green}\Delta$ [CF Round 775 div.1](https://codeforces.com/contest/1648) ### 记录 在文渊打的，大概是在 XJ 打的最后一场比赛了吧。 还下了 4 分， 场上过了 ABC，但是罚的有点多。而且 C 没时间 hack 别人了（悲） ### 补题 - Prob. D 把路径拆成三段，第一段是 $V_1(x)=S_1(x)-S_2(x-1)$，第二段是 $V_2(x)=S_3(n)-S_3(x -1)+S_2(x)$，这样两段拼起来就是答案。 问题转化为求一组 $1\le l\le r\le n$，最大化 $V_1(l)+V_2(r)-cost(l,r)$，其中 $cost(l,r)$ 是将 $[l,r]$ 联通的最小代价。 我们考虑将 $V_1(l)-cost(l,r)$ 放在一起维护，最大值称为 $f(r)$。 我们发现，可以只在线段的最右边记录这个 $f$ 值，最后一次再判。 看着就很屎 ### 总结 - 速度还是不行，式子要推得准； - 看到榜不对就直接去锁题叉人，不要犹豫。