2023 winter training short round #3 总结

2023 winter training short round #3

毒瘤构造专场

开场 A 不会，感觉是神仙构造。

B 题面过长，看着像博弈论，直接扔。

C 的题面很可爱，好像是什么原根的性质。

想了很久都只有暴力，发现给了 1e6 的样例，于是偷鸡过了

事实证明这就是诈骗题

开 D ，又是构造，于是回去写 A。

发现题读错了，是选一个子序列整体右移。

01串中相邻两个不一样：一个0，一个1，只要凑出来相邻两个都一样就行。

然后卡在 D 了，正着想怎么也做不出来。

发现最后一位可以直接出，然后可以逆推，$\frac {(n-1)n}{2}$ 中包含了 $a_n$ 和之后比它小的。

后者可以直接树状数组查

不难发现 $\frac{n(n-1)}{2}-sum(n-1)$ 是随 $n$ 单增（不严格）的，所以我们可以二分。

这里一直写WA，原来是二分的时候出锅了。

我写的二分在处理相等情况的时候取反了，这里应该取相等里面数值最大的。（反着来是降序）

最后半个小时才看B，发现是个很套路的背包

疯狂rush，过了。

对于某些细节的理解还是不够深刻（比如 D 的二分

之后要好好思考一下。