Codeforces Round #708 Div2题解

唉,确实能力下降了不少。E2硬是到嘴边的DP没推出来。也算是进一步了解目前Codeforces相比几年前的难度变化。虽然这一场是一个div2 only,但个人感觉这场dev2 only还是偏水了一些。因为题目分easy version和hard version之后,相当于给了一个梯子。(虽然给了梯子我还是没想到,我是真的菜)

AB题就不做了,太水了浪费时间。


C2. k-LCM (hard version)

算是一个简单构造题。我会说这个题我当时礼拜玩和弟兄姊妹吃饭的时候想的吗。其突破点是那个$\frac{n}{2}$,这个立马让人想到我直接除2之后,LCM直接就是$\frac{n}{2}$。顺着这个很快就能推出奇数的时候-1凑偶数。然后就开始疯狂-1。

Codeforces Round #708 k-LCM 构造
水题。显然,对于任意n,当k=3时有解。显然,ai=1时不影响最小公倍数。那么当k>3时,就拿1充数就行。不仅水,而且我有种我做过类似题的感觉……
具体题解见此

D. Genius

这个题一般。虽然目测就知道是DP,但是32m的内存限制简直就是告诉你这个就是状压dp。其突破点其实是,如果一直往右的话,中间跳过题目是没有意义的。因为是以绝对值+IQ。于是就绕咯。最后加个tag的特判、状压啥的,但这些都不是事。

Codeforces Round #708 Genius DP
这个题上来就提醒你注意内存限制只有32m。就是一脸要状压DP的节奏。
具体题解见此

E2. Square-free division (hard version)

就很气。硬是没推出来。维护left的方法想到了,dp的大概方向想到了,就没推出来。不过我当时想的时候,主要是集中于O(nk)的方向在想。毕竟O(nk)最坏得有400w的规模,想着400w可能会T。结果题解是$O(nk^2)$,8000w的规模,这都不T我是没想到的。

不过另外一个角度上讲,我觉得我DP的优化这一块可能得再熟悉熟悉了。假设我对各种优化非常熟悉,那我觉得按照我的操作,我很可能会先$O(nk^2)$T一发,然后再看优化。而我现在不够熟悉,就不敢T这一发。

千言万语一个字,

Codeforces Round #708 Square-free division DP
首先,乘积是平方数只有一个可能:他们的素因数中,出现奇数次的素因数一致。因此对于任意数,第一件事情就是换成那些出现奇数次素因数的乘积。于是问题转化成了,分段,且每段不能有相同的数。那么dp[i][j]表示,到i为止,改j个数,最少需要分几段,其实是一个自然的想法。我其实也想到了这一层。问题是怎么维护这个dp呢?显然,自然的想法是,找i-?和j-?推过来咯。到这我就确实没想到了。
具体题解见此

我觉得还是得再加大力度。感觉脑子已经锈了,这些讲道理显然是应该都能顺手过的,都不是啥真的有难度的题目……还是自己太水……