ARC做题记录

· · 题解

感觉思维水平很差，于是写一下ARC，锻炼一下思维能力。希望可以坚持几天/px

早年ARC好恶心啊，还是从058开始做罢（做了ARC001后感觉这玩意儿和思维没啥关系）

目前口胡到ARC063。

ARC058

C

注意到 n \leq 10^4 且题目保证一定有解，故 ans < 10^5。那么直接枚举答案并检查其是否符合要求即可。

D

学校好像之前讲过类似的题，当时怎么还不会做。

考虑将路线分为两个阶段，第一个阶段就是在 (H-A) \times B 大小的矩形里瞎走，第二个阶段则是在一个 (W-B) \times H 的矩形里瞎走。

为了保证计算答案不重复，我们枚举走出第一个阶段的点 (B, i), 1 \leq i \leq H - A，其对应的踏入第二个阶段的点则为 (B + 1, i)。故此时的方案数为 \dbinom{B+i-2}{B-1} \times \dbinom{H + W - i-B - 1}{W-B-1} 答案即为所有 i 位置的方案数之和。

E

ckf某次好题选讲里唯一听懂的一道题。所以是大大的好题

正难则反。我们考虑以 f_{i,j} 表示该序列以 i 结尾、w-1=i时，S= \{ a_x,...,a_w-1 \} 状态为 j 的不合法方案数。

注意到 X+Y+Z \leq 17，所以我们可以用一个二进制数字表示整个序列最后几个和为17的数字，当某一位为 1 时，代表此处把 X/Y/Z 分割开了。比如 X=5,Y=7,Z=5，那么这个二进制数字为 00001000000100001。所以我们有转移方程 f_{i,U \cap j \times 2^k + k}= (check(U \cap j \times 2^k + k)) \times f_{i-1,j} (1\leq k \leq 10,U=2^{X+Y+Z}-1) 。则答案为 \sum_{i=0}^Uf_{n,i}

F

不会字符串，下次再说。

ARC059

C

由于 |a_i|\leq 100，故直接枚举最终修改的数然后计算贡献即可。

D

显然，如果一个字母在某区间内出现的次数大于一半，那么它在区间内任意两个位置之差的最小值一定不大于 2。所以直接枚举长度为 2 和 3 的区间并检查即可。

E

我们考虑设计 dp 状态，f_{i,j} 表示前 i 个小朋友拿了 j 颗糖，有转移方程 f_{i,j}=\sum_{k=0}^jf_{i-1,j-k}+\sum_{x_i=a_i}^{b_i} {x_i}^k。注意到这个贡献 \sum_{x_i=a_i}^{b_i} {x_i}^k 只和 i 以及 k 有关，所以可以前缀和预处理。

F

被诈骗了，想了半天。于是观察题目评分，发现只有2427！所以是可做题！

我们设 f_{i,j} 表示第 i 次操作后，前 j 字符是正确的。考虑如何转移，这里有一个神奇的事情，就是实际上只有目标串的长度是有用的，而它具体的组成对答案的计算没有影响。因为我们每次向字符串里加入的新字符只有可能是和目标串对应位置相同或者不同两种可能性，且二者是等概率发生的；每次删除字符串末尾的数字时，不管它是什么字符都不重要。

于是有转移方程: f_{i, j}=f_{i-1,j-1}+2 \times f_{i-1,j+1} ，答案自然为 f_{n,m}

ARC060

C

注意到 \sum {x_i} \leq 2500，于是考虑做背包dp。以 f_{i,j} 表示选了 i 个数，总和为 j。转移显然，答案则为 \sum f_{i, a \times i}。

D

这场纯纯的swap了 D 和 E。现在感觉 D 不是很难，不知道为啥两个月前的模拟赛上做不出来。可能是因为它放在T3的位置？

考虑最终在 b 进制下，n 的位数。显然当位数 >2 时，有 b \leq \sqrt x（关键性质），对于这一部分直接暴力枚举 b 并检查即可。位数 =1 时的检查显然。而当位数 = 2 时，有方程 a_0+b \times a_1=n,a_0+a_1=sum。整理得 (b-1) \times a_1=n-sum，直接枚举 n-sum 的因数并检查即可。

E

一眼倍增。具体实现和某次校内模拟赛T3的部分分相似。

F

很巧妙的题，有很多很震撼的结论。参考了这篇博客。

设有字符串 s， 长度为 n。定义当且仅当 \forall i \in [1,n-p], s_i=s_i+p 时， p 为字符串 s 的周期；字符串的循环节不包括字符串本身。

于是有两个显然的引理：

引理1：s 的最小周期为 n-max\_border

引理2: 若p 为 s 的周期，同时 p |n，那么有 p 为 s 的循环节。

然后有一个很不显然的结论，若 s 存在循环节且 s 的最小循环节 >1，则“全场最佳”所包含元素的最小值为 2。因为在去掉第一个字符后的字符串 s' 不再存在循环节。这是为啥呢？

引理3:若 p,q 均为 s 的周期，且 p+q\leq n，那么 gcd(p,q) 也是 s 的周期。

设 p 为 s 的最小循环节，q 为 s' 的最小循环节。显然 p 为 s' 的周期（相对位置不改变），那么由引理3，因为 p+q\leq \left\lfloor\dfrac{n}{2}\right\rfloor +\left\lfloor\dfrac{n-1}{2}\right\rfloor=n-1 ，所以有 gcd(p,q) 为 s' 的周期。若 gcd(p,q) < q ，由于 gcd(p,q) | q, q|n-1, 所以 gcd(p,q) 为 s' 的循环节，与假设矛盾；若 gcd(p,q)=p，即 p|q，则 q 为 s 的循环节，与假设矛盾。所以 s' 不存在循环节。

实现上，我们只需要判断 s 的最小周期是否整除 n 即可判断第一问的答案。对于第二问，正反各做一次kmp，保证断点 k 满足 s_1,k 和 s_k+1,n 均不存在循环节即可。

ARC061

C

爆搜。也有更高明的写法，但是还没学会。

D

考虑每加入一个点对答案数组的影响。显然此时只会影响到9个九宫格的状态，具体实现上枚举这9个九宫格对应的中心 (x,y)，并用 map 来维护此时九宫格中的点数即可。注意初始状态有 ans_0=(H-2) \times (W-2)。

E

什么学校模拟赛天天出ARC题，我不说。虽然某模拟赛题增加了边权，但你这个套路有啥区别呢。

首先考虑暴力，不难想到将所有相同公司铁路连接的联通块之间的点两两连边权为 1 的边，跑最短路。但是这样边的数量是 n^2 量级的，所以不难想到建立虚点。具体的，我们建立分层图，相同联通块中的点为一层（需要建立新点），它们之间按照原图连边权为 0 的边；对于不同分层图的同一站，统一向同一虚点连边权为 1 的边。最后跑最短路输出 \dfrac{1}{2}dis_n 即可。这样最多只有 n+2m 个点和 3m 条边了。

理解上，可以认为每次换乘需要出站再入站，虚点就承担了这个责任。

复杂度 O(n\log m)

F

组合题 too hard 4 me，不会做呜呜。

不难发现取牌的顺序就是牌上数字的顺序 S。由于第一轮是从A开始的，所以A获胜的充要条件为 \exists m \leq n_a+n_b+n_c, cnt_a=n_a, cnt_b \leq n_b,cnt_c \leq n_c ，其中cnt_x 表示 x 这个字符在 [S_1,S_2...S_m] 中出现的次数。

不妨考虑枚举 m，然后进行组合大法。

整理一下，有 ans= \sum\limits_{m=n_a}^{n_a+n_b+n_c} \dbinom{m-1}{n_a-1}(2^{m-n_a}-\sum\limits_{k=n_b+1}^{m-n_a} \dbinom{m-n_a}{k}-\sum\limits_{k=n_c+1}^{m-n_a} \dbinom{m-n_a}{k})3^{n_a+n_b+n_c-m}

但是直接枚举m,k 是肯定不行的，观察到有两个东西是组合数之和的形式。设 B_i=\sum\limits_{k=n_b+1}^{i} \dbinom{i}{k}，由组合数的意义，有 B_i=\sum\limits_{k=n_b+1}^{i} \dbinom{i-1}{k-1}+ \dbinom{i-1}{k}=B_{i-1}+ \dbinom{i}{n_b}+B_{i-1}+ \dbinom{i-1}{i}=2 B_{i-1} + \dbinom{i}{n_b}，C_i 同理。

复杂度 O(n_a+n_b+n_c)，但我逆元用的快速幂，所以带只log。

ARC062

在机房速通了一把恶心王中王的这一场。

C

感谢ClCN鸽鸽的友情翻译！顺便帮我把题也做了

对于第 i 个数，枚举 j ，每次不断将分子分母同时乘以 j ，直到满足 a_{i-1}\leq a_i\text{ and }t_{i-1}\leq t_i 为止。

D

由于布是无敌的，所以能出布就出布，不满足条件的时候出拳就行了。

E

枚举两个相对面的瓷砖，然后一通搞（？还没写，回头再说

F

被嘉宝嘲讽了，sad。没学 Pólya 定理，下次一定。

ARC063

E

先根据奇偶性判无解。然后有两个做法。

Sol1

每次选出当前已经赋值的所有点中权值 w 最小的点 u ，将其相邻无赋值点 v 赋为 w_u+1 。

以下为做法正确性证明。

设 w_u<w_v ，且有解，那么 u\to v 路径上点的权值有两种情况。

时间复杂度 O(n\log n) 。

Sol2

树形dp，设 [l_u,r_u] 表示 u 这个点以及其子树内所有点均合法时， w_u 的取值范围。显然有 [l_u, r_u]=\bigcap_{v \in son_u}[l_v-1,r_v+1] ，注意 i \in [l_u,r_u] 并不是全部合法的，需要去除奇偶性不同的情况。而后从根节点开始向下构造答案即可。

时间复杂度 O(n) 。