ACC026简要题解

这场AGC是时间正好在NOI之前休养生息的日子里，果断选择了放弃(虽然也从没有用大号打过)。在随便做完了前几题之后就踏上了去长沙的旅程。NOI系列比赛总是休闲无比，咕咕不断，竟然连开幕式都能咕，今天AK了一下笔试之后就来刚后两题，没想到居然刚出来了。看来自己状态还不错，可能是一个好兆头吧。希望明、大后两天可以稳定发挥。

B

一道挺简单的题。

假设(A<B)或者(D<B)那么显然是无解的，否则先让(A)尽可能减去(B)，然后每天晚上过后剩余的数量就相当于与(A-TB)膜(D)同余的最小的大于(C)的数。求gcd即可找到最小的那天。

C

一道暴力题。

枚举左边的颜色，那么两个串都长成什么样可以确定，做一个(O(n^{2}))的暴力dp即可。
总复杂度是(O(2^{n}*n^{2}))

D

一道数据范围有点小小的题。

有点难解释，我组织一下语言。。。

考虑最终染色的方案。假设有两个同一列且相邻的格子颜色相同，那么它们旁边同行的每队格子颜色显然也相同。这还会波及到其他格子，假设确定了这一列，那么其他能影响到的格子也都会被确定。

用f[i][j]表示考虑了前(i)列，行数最小的这种情况发生在(j)的方案数。

假设新加入的一列高度没有(j)，那么显然影响不到当前列，枚举这一列有没有出现情况，出现在哪里即可。

假设影响到当前列，那么这一列(min(h_{i},h_{i-1}))的部分都会被确定，这一列高出的部分就随意涂了。

第二维离散一下一起转移，枚举出现情况的位置时用一个等比数列求和。

复杂度(O(n^{2}))

E

一道实际上没有那么难的题。

f[i]表示只管(i)到(n*2)中的所有(ab)都出现的字符对，能够造出的字典序最大的字符串。

分几种情况考虑。

假设(s[i])配对的字符不在状态里，那么(f[i]=f[i+1])。

假设(s[i]=a)，那么判断一下后面是否有(b)在(a)之前的情况，如果有的话那么这个(a)不会在答案内，否则在这个(a)与和它配对的(b)之间一定没有其他字符,(f[i]='ab'+f[posb(i)+1])。

假设(s[i]=b)，考虑它被选的情况。假设它和与它配对的(a)之间有其他的可选的(b)，那么显然选进去才会更优，不断重复这个过程，最后选出的是一个区间的('ba')对，再加上一个后缀dp串即可。

F

一道很有意思的题。

首先，先手一定拥有选走所有奇数下标或者偶数下标的方案。

考虑后手的应对，假设先手选走一个数之后分成的两段有一段长度是偶数，那么后手只需要指定选这边，就会变成先手后手拿完了一段，每个人拿到的数奇偶性相同，并且选择权在后手的情况，这显然还不如直接选走一种下标来得优。这样就可以发现，当(n)是偶数的时候，答案就是之前考虑的两种中较大的那种。

否则n是奇数，且每一步先手都会选择一个数取走，使得两边数量都为奇数，等后手选择选完其中一边之后再继续考虑另一边，不难发现先手选到的都是偶数下标。这时候换一个思路，考虑二分答案。令(s_{i})表示奇数下标权为1，偶数为-1求出的前缀和,(sum_{i})表示奇／偶数下标的权值和。那么假设一个前缀满足(s_{i}+sum[0]>=mid)，这时这个前缀很危险，如果先手先拿走第(i+1)堆的话，后手一定要拿第(i)堆。继续考虑，假设存在(j(j<i))满足段([1,j-1])和段([j+1,i-1])都很危险的话，那么(j)也是危险的，这种情况只需要维护一个前缀最值即可。倒着也是如此，这样就可以(O(n))求出所有危险的前后缀，假设存在一个下标满足选了之后两边都很危险，那么先手可以一定获得胜利。

复杂度(O(nlogsum ai))