0%

题解 03

记错了 div 2 的时间,以为是晚上,就出去玩了。结果是下午。补题解谢罪。

CF 1469 A Regular Bracket Sequence

给定一个恰由一个左括号、一个右括号以及若干问号组成的字符串,问能否通过仅将问号替换成括号来构造一个合法的括号序列。
字符串长度不超过 $100$

一场 edu 的 A 题,当时想了非常久。很巧的一道题。显然奇数长度是不成立的。下面考虑偶数长度。

解 1

一个合法的括号序列(RBS)有这样一个性质:若一个右括号在左括号的前面,交换两者之后,仍旧是一个 RBS。

若可以构造一个 RBS,则能通过这样的交换变成前面一半左括号,后面一半右括号。我们只需要把前面一半问号换成左括号,后面一半问号换成右括号,再检查一下是不是 RBS 即可。

解 2

观察一般的括号序列判定方法可以发现,如果在某个位置加一个左括号(压栈/加一),再在后面某个位置加一个右括号(弹栈/减一),从结果来看仍然是一个 RBS。又因为题目原序列中恰有一个左括号和一个右括号,则当左括号在右括号前面时,实际上对判定没有影响,去除后仍然可以构造一个 RBS。

而当左括号在右括号后面时,分两种情况考虑:

  1. 第一个字符是右括号,或最后一个字符是左括号,不能构造 RBS
  2. 第一个字符不是右括号,且最后一个字符不是左括号,则对判定没有影响

则只需要判断头尾两个字符即可。

解 3

从经典的 RBS 判定出发,对未配对左括号和问号计数。

  1. 遇到左括号:左括号计数加一。
  2. 遇到问号:问号计数加一。
    1. 无未配对左括号:左括号计数加一。
    2. 有:先假设为右括号,消掉一个左括号。
  3. 遇到右括号
    1. 无未配对左括号:
      1. 之前有问号:一个问号由先前假设的右括号变为左括号,未配对左括号加一。由于确定了问号,问号计数减一。
      2. 之前无问号:不可构造
    2. 有:匹配,未配对左括号计数减一

CF 1476 D Journey

编号 $0$ 到 $n$ 的城市由 $n$条路连接,第 $i$ 条路连接城市 $i - 1$ 和 $i$。每条路有且仅有一个方向。
一个旅行者可以从任一个城市出发,每天必须沿路的方向去往相邻的另外一个城市。当旅行者完成一次移动后,所有的路反向。当旅行者无法完成一次移动时,旅行结束。
以仅包含字母 L 和 R 的字符串给出旅行开始前每条路的方向,求旅行者从各城市出发进行一次旅行,最多可以访问的城市数量。
$1 \leq n \leq 3\cdot 10^5$

一个解法是二分图搜索,下面介绍 dp 解法。

令 $dp_i:=从i出发可以到达的最左边的城市$,从 $i$ 开始,如果不能向左,则 $dp_i = i$,如果只能向左走一步,$dp_i = dp_{i - 1}$,两步,$dp_i = dp_{i - 2}$。由于两步过后路的状态恢复,不必要考虑后续三、四步;

同理算出最右边城市,即可得到答案。

2020 CCPC Changchun Onsite D Meaningless Sequence

给一个序列

  • $a_{0} = 0$
  • $a_{n} = c \cdot \max \{a_{i \& n} | 0\leq i < n\}$ 当 $n > 0$。

给定 $c$ 和二进制表示的 $n$,求 $\sum_{i = 0}^n a_i \mod 10^9 + 7$。

$0\leq n \leq 2^{3000}, 0\leq c\leq 10^9$

列出几项后可以发现 $a_i = c^{popcount(i)}$,其中 $popcount(i)$ 是 $i$ 的二进制 $1$ 的个数。

则对于一个 $1$ 开头的串,先只考虑后缀全部为 $0$ 的情况,和为 $\sum_{i = 0}^L C_L^i \cdot c^i$,其中 $L$ 为后缀 $0$ 的个数。

再考虑之前出现过的 $1$,每出现一次都会把加和放大一个 $c$。(前面每补上一个 $1$,$popcount$ 就会加一,且这个 $1$ 的位置不能动)扫一趟下来就是所有下标不大于 $n$ 的情况,迭代加起来即可。

CF 1492 C Maximum width

把一个字符串 $t$ 拆成子序列,匹配到另一个字符串 $s$ 中,$t$ 中各字符在 $s$ 中的新下标构成一个严格升序的数列。求数列相邻元素之差的最大值。
$2\leq |t| \leq |s| \leq 2\cdot 10^5$,保证存在可行的拆分-匹配映射。

对 $t$ 中每个字母,先贪心匹配最左边可行映射,再匹配最右边。求两个映射中差最大的即可。注意是当前字符的最左和下一个字符的最右之差。

CF 1492 D Genius’s Gambit

给定三个数 $a$,$b$,$k$,构造各长 $a + b$ 的二进制数 $x$ 和 $y$,使得两者各含 $a$ 个 $0$ 和 $b$ 个 $1$,且 $x - y$ 含有 $k$ 个 $1$。
$x$ 和 $y$ 不允许有前缀 $0$。
$0\leq a,1\leq b,0\leq k\leq a + b\leq 2\cdot 10^5$

假设 $x = y = 111\cdots 11000\cdots 00$ 形式,注意到 $y$ 的最后一个 $1$ 每向后移一位,$x - y$ 就多一个 $1$。同时剩余前缀的最后一个 $1$ 向后移一位可以使 $x - y$ 再多一个 $1$。据此可以构造最多 $b + a - 2$ 个 $1$。极端情况是 $a = 0, b = 1$,此时 $k = 0$。