“01串”三题分析:AGC045

“01串”三题分析:AGC045

Atcoder Grand赛045的ABC题都是关于01串,A题是异或和博弈,B题是字符串状态,C题主要是计数。

题目: https://atcoder.jp/contests/agc045/tasks (A,B,C)

A. Xor Battle

有0和1两人进行对战。对于变量x(初始为0),两人将按照给定的长度为\( N \)的序列 \( \{A_i\} \)进行操作,长为N的01串\( S_i \)表示第i步由 \( S_i \) 号选手进行操作。第i人可以将当前变量\( x \)变成\( x \text{ XOR } A_i \),也可以什么都不做放弃这个\(A_i \)。这N个\( A_i \)都用完之后如果变量x为0,则0胜,否则1胜。
假定两人对战时都会出最优的策略,请判断0能否取胜。

\( 1 \leq N \leq 200 \)
\( 1\leq A_i \leq 10^{18} \)
\( |S| = N \)

B. 01 Unbalanced

给出一个仅由'0', '1''?'构成的字符串\( S\)。将S中的'?'替换为'0''1'(各个'?'互不影响相互独立)之后得到新字符串\( S’ \)。
定义\( S’\)的不平衡度为:\(S’ \)中第\( l\)个字符到第\(r\)个字符中0与1的个数之差的绝对值的最大值,\(1 \leq l \leq r \leq N \)。
给定一个\( S \),试求一个最小\( S’ \)的不平衡度 。

\( 1\leq |S| \leq 10^6 \)

C. Range Set

有一长为N的字符串,初始全为0。Alice可以对这个字符串做这样的操作:

  • 选择连续的A个字符置为0
  • 选择连续的B个字符置为1

不限制Alice执行的次数和顺序,计算Alice可以得到多少种不同字符串。结果较大,输出时结果对 \( 10^9+7 \)取余。

\( 1\leq N \leq 5000 \)
\( 1\leq A,B \leq N \)

发表评论

电子邮件地址不会被公开。 必填项已用*标注