djwj233 的博客

djwj233 的博客

CodeForces Contest/VP 记录

posted on 2021-10-10 20:21:55 | under 计划 |

还是开个坑记记吧。

用 $\color{green}\Delta$ 表示 contest,$\color{Blue}\Delta$ 表示 VP。

$\color{green}\Delta$ Edu Round 115

记录

拿了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

总结

  • long long!!!long long!!!long long!!!
  • 这个菜鸡 DP 真的不行,特别是状压,同样地他 DFS 也不行。

$\color{green}\Delta$ CF Round 749 Div.2

记录

拿了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

总结

  • CF 中前面的题卡着就直接扔去写后面的题。
  • 要加强构造题的训练。

$\color{green}\Delta$ CF Round 751 Div.2

记录

拿了 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$ 的结论,错了,猜了一个和的结论,又错了。

好吧,原来正确答案是:

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

记录

拿了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

记录

拿了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

记录

拿了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

记录

拿了 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

记录

拿了 Rank 110, Performance 2181(international 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