2018 ACM-ICPC Asia Qingdao Regional Contest

Upsolving

G. Repair the Artwork

题目大意：

给出一个数列\(\{a_n\}\)，\(a_i\in\{0,1,2\}\)，\(n\le100\).

每次操作可以选择一个区间，该区间不可以包含\(a_i=1\)的位置，将区间中的\(a_i\)都变为\(0\).

问恰好\(1\le m\le10^9\)次操作后满足不存在\(a_i=2\)的方案数，对\(10^9+7\)取模。

题解：

考虑容斥，令\(S\)为下标集合且\(i\in S\to a_i=2\)，设\(f(S)\)为不覆盖\(S\)和\(a_i=1\)的任意位置的区间数量，则\(ans=\sum\limits f(S)^m\times(-1)^{|S|}\).

令\(dp[i][j][k]\)为前\(i\)个位置，最后一段连续的可覆盖位置有\(j\)个，\(f(S)=k\)的方案数（包含容斥系数）。

转移是\(O(1)\)，从\(dp[i-1][j][k]\)转移到\(dp[i][j+1][k+j+1]\)，或从\(dp[i-1][j][k]\)转移到\(dp[i][0][k]\)，枚举时满足\(j\in[0,i),k\in[j*(j+1)/2,i*(i-1)/2]\).

时间复杂度\(O(n^4)\).

I. Soldier Game

题目大意：

给出一个数列\(\{a_n\}\)，\(-10^9\le a_i\le10^9\)，\(1\le n\le10^5\).

可以将数列\(\{a_n\}\)划分为若干不相交的子区间，每个子区间的大小为\(1\)或者\(2\)，最小化最大的区间和减去最小的区间和的值。

题解：

将问题转化为连通性问题，\(i\)向\(i+1\)连权值为\(a_i\)的边，向\(i+2\)连权值为\(a_i+a_{i+1}\)的边，若只用权值范围在\([l,r]\)之间的边可以让\(1\)和\(n+1\)连通则\(r-l\)是可行解。

令\(R(l)\)为使得\([l,r]\)是可行解的最小的\(r\)，显然\(R(l)\)随\(l\)的增大单调不降，我们可以用双指针来\(O(n)\)枚举所有可能成为答案的解。

用线段树维护区间最左的两个点和最右的两个点的连通性即可\(O(\log{n})\)完成单次修改，总时间复杂度\(O(n\log{n})\).

Replay

开场 9min，Z 把 M 的到签了。

之后 D 分类讨论了 C，准备写的时候被 Z 打断了（因为 Z 觉得他的做法更好写。。。）。过了一会 Z 又觉得他的做法不对，然后换 D，在 29min 的时候过了。

然后 W 想了 J，觉得是一个前缀和，但是并没有想清楚。随后 W 找 Z 讨论，Z 瞬间想了一个假的二分，然后 W 写错了一次二分，写对了一次二分，Z 写对了一次二分，总共带来了 -3。随后 W 找到了二分的反例，然后想清楚了正解，但是没有考虑 0，又 WA 了一次。最后在 D 的帮助下 62min 时过了。

之后 D 和 W 一起看 E，W 猜了一个贪心二分，在 86min 的时候交了一发，但是判断少了一个情况。之后打印了代码（但是放在了旁边？？？）。

随后 D 去看 D，快写完时觉得自己的做法有问题，隔了一会 W 看了之后发现没有问题。写完后在 127min 过了。

在这之间，Z 一直在推 L。终于推出来 prufer 序列做法之后，分别没考虑 \(m=0\) 和 \(n=m\)，-2 后在 142min 过了。

之后 D 没有想到 E 二分的反例，去看了一遍代码，发现了 W 代码中的错误，在 156min 过了。

在这中间，W 把 F 推了一些情况，然后给 Z，找到规律后在 172min 过了。

Z 和 D 接着想了一会 G（其实早就会了 \(\mathcal{O}(n^{4})\) 的做法，没敢写）。

然后 Z 和 W 讨论了一段时间 K，Z 写了一段时间以后 T 了 3 发。开始以为是 map 和 set 的常数问题，但是后面 W 发现是没有离散化导致复杂度不对。之后没改干净又 WA 了一次。在 276min 过了。

之后 Z 开始用 \(\mathcal{O}(n^{4})\) 莽 G。但是最后可能因为快速幂的常数问题 T 了。Game Over

updt：G不光是快速幂的问题，dp状态冗余和memset也是原因，修改后可以卡过。