Hello World.

Jason's Blog

0%

题解 03

Posted on In

记错了 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 解法。

令 $dpi:=从i出发可以到达的最左边的城市$，从 $i$ 开始，如果不能向左，则 $dp_i = i$，如果只能向左走一步，$dp_i = dp{i - 1}$，两步，$dpi = 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$。