AGC026 解题记录

### A Colorful Slimes 2
题意：$n$只史莱姆排成一行，每种史莱姆有个颜色$c(1\le c\le n)$。两个相邻的同色史莱姆会合体，你可以把一只史莱姆的颜色修改成$[1,10000]$之间的一个，问最少修改多少只史莱姆的颜色使得没有史莱姆会合体。

题解：$dp$入门题，把$N$以外看作无色，$f(i,j)$表示到$i$位置最后一个颜色为$j$。$O(n^3)$

### B rng_10s
题意：一家果汁店，一开始有$A$瓶果汁。每天早上你都去买$B$瓶，每天晚上，如果当前的果汁数目不超过$C$，那么老板会补上$D$瓶果汁。问你是否可以无限买果汁。
$A,B,C,D\le 10^{18}$

题解：看了一下觉得应该是个大讨论。
首先$A < B$显然不合法，判掉。
然后$B < D$也不会合法，判掉。
其他情况下，我们先把$A$减$B$减到恰好$\le C$的那个值，也就是说下一步老板会判断出$\le C$，记这个为$a$。
我们讨论一下：如果$C\le D$，那么如果要不能无限购买一定存在$x$使得：$(a+(D-B)x)\ mod\ B > C$
实际上$(D-B)x\ mod\ B$的值可以表示成倍数并且和$gcd((D-B)x,B)$有关。
我们把解写成$kx+b$的形式，判断存不存在即可。复杂度是$O(TlogV)$
~~我也不知道讨论全没有$QAQ$~~
无法想象前面的dalao怎么在$6$分钟内速$A$此题

### C String Coloring

题意：给一个长度为$2N$的字符串$S$，给每个字符涂上红蓝两色，问有多少种涂法满足红色字符从左往右读和蓝色字符从右往左读是一样的。$N\le 18$。

题解：这题题面上就挂了个牌子写着——快点使用中途相遇，再不用$600$分没了哦。
# = = ||  (汗)

我们考虑中途相遇，对前一半和后一半分开考虑。
对于每一半我们用$(a,b)$表示以$B$为底数红色正串的哈希值以及蓝色反串的哈希值。
如何让它们"遇到"呢？
设前面的二元组是$(a_1,b_1)$，后面的为$(a_2,b_2)$。发现遇到的条件是：$$a_1B^N+a_2=b_1+b_2B^N$$
实际上就是：$$a_1B^N-b_1=b_2B^N-a_2$$
对于其中一边维护一个$map$即可。$O(N2^N)$

### D Histogram Coloring

题意：给你一个宽为$N$的网格，每一列只保留下面的$a_i$个格子。你要把这个部分网格涂上红色和蓝色，满足：对于任意$2\times 2$小方格，其中红色和蓝色数量相同。问方案数。
$N\le 100,a_i\le 10^9$

题解：简单$dp$，容易发现一旦一列有两个元素相邻，那么下一列对应位置是确定的。因此，当$a_i\ge a_{i+1}$实际上就是考虑假如$b$数组是$a$排序后的结果，设$f(i,j)$表示到第$i$列，最靠下的多连通块的下端点在$[b_j,b_{j+1})$内。每次暴力转移，贡献用快速幂算，就得到了一个$O(n^3)$的做法。
但是实际上如果从横向来看，同样的，如果一行有两个元素相邻，那么下一行的对应位置也是确定的。
那么我们考虑一层一层地削掉，这里相当于每次把一个区间在最小值处分成两个区间，从上到下的递归处理。每次计算第一行有/没有相邻格子的方案数，这样就变成$O(n^2)$
题解说还有$O(n log V)$做法，不作深入研究。

### E Synchronized Subsequence

题意：给你一个长度为$2N$的字符串，包含$N$个'a'和$N$个'b'。你可以选择一些字符对，一旦你选了第$i$个'a'就必须选第$i$个'b'，问选出的位置连成的字符串字典序最大是多少。

题解：真的是好题，分析透彻就能有清晰的思路。首先发现'a'/'b'是一一对应的，有点像括号序列但又不是。那么把'b'看成$1$，'a'看成$-1$，可以发现没有'a'-'b'对跨过前缀和为$0$的地方。那么我们可以把原串分段每段讨论。
段有两种，一种是'a'开头的段我们称为$A$类段，一种是'b'开头的段我们称为$B$类段。
考虑我们的贪心策略，假设我们所有的$A/B$段已经全部选出了字典序最大的，首先我们肯定要依次拿$B$类段。容易发现我们每一次只需要找出后面字典序最大的一个$B$类段即可。这之后我们再一直往后选字典序最大的$A$类段即可。

现在考虑$A/B$类段内怎么选。
对于$B$类，我们考虑删除$'b'-'a'$对$(i,j)$答案更优的条件。发现首先$[i+1,j+1]$必定全部是$'b'$，否则一定有一个位置$'a'$左边是$'b'$，导致字典序变小。其次后面一定跟着两个$'b'$，这样才能使字典序变大，我们删除这样的$'b'-'a'$对即可。
对于$A$类，我们开头一定选的是$'a'$，接下来选$'b'$，要想选$'b'$又得先选$'a'$，一定得到$"abab..."$串。考虑到我们最后取$A$，那么$A$尽量长，于是构造尽量多的$"abab..."$即可。
拼起来如果用$SA$实现，总复杂度降为$O(n\ log\ n)$。

### F Manju Game
纯性质题，看不出来，也没中文题解，告辞。

Rockdu's Blog

导航

最近发表

大佬们的友链