ABC341 题解

时间:2024-02-22 10:05:08

ABC341 题解

A

Description

给定一个数 N N N,求长度 2 N + 1 2N+1 2N+101 交替的字符串(0 开始)。

Solution

直接模拟,注意 0-index i   m o d   2 i\bmod 2 imod21-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

给定一个行走路线(URLD),求合法起点个数。

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,拓扑即可。

在每个节点上做一遍背包,统计答案。