ABC341 题解
A
Description
给定一个数
N
N
N，求长度
2
N
+
1
2N+1
2N+1 的 01 交替的字符串（0 开始）。
Solution
直接模拟，注意 0-index 是
i
m
o
d
2
i\bmod 2
imod2，1-index 是
(
i
+
1
)
m
o
d
2
(i+1) \bmod 2
(i+1)mod2。
B
Description
一个人可以用 s i s_i si 个 i i i 国硬币换 t i t_i ti 个 i + 1 i+1 i+1 国硬币。
给定这个人最初每个国家的钱币个数，问这个人最多能有多少个· n n n 国硬币。
Solution
直接模拟，正确性证明略。
C
Description
给定一个行走路线（U、R、L、D），求合法起点个数。
Solution
直接模拟。
D
Description
给定 N N N、 M M M、 K K K，求第 K K K 只被 N N N 和 M M M 的一个整除的数。
Solution
二分，然后小学奥数。
注意： N N N 和 M M M 必须互质，即都要除以 gcd ( N , M ) \gcd(N,M) gcd(N,M)。
E
Description
给定一个 01 串，
Q
Q
Q 个操作：
-
1 l r：翻转 l l l 至 r r r 的所有字符； -
2 l r：求 l l l 至 r r r 是否是01交替串。
Solution
把所有形如 ...00... 和 ...11... 的地方加入到 set 里。
修改和查询都可以仅通过这个 set 进行。
F
Description
给定一张 n n n 个点的带点权图，每个点有 a i a_i ai 个棋子。
每个棋子在一次操作中，下放到与其相连的若干节点中，这些节点的权值和不超过这个节点本身。
问最多的操作数。
Solution
因为权值为正，所以只会下放到比自己小的点上。
所以可以建一个 DAG，拓扑即可。
在每个节点上做一遍背包，统计答案。