Codeforces 1834 / Codeforces Round #879 (Div. 2)

• Contest Link
• Problem B Maximum Strength
• Problem C Game with Reversing
• Problem D Survey in Class
• Problem E MEX of LCM
• Problem F Typewriter

Contest Link

Codeforces Round #879 (Div. 2)

Problem B Maximum Strength

题意

给定 \(L,R\)，求两个整数 \(L \leq a,b \leq R\) 使得 \(a,b\) 的数位差之和最大。例如 \(133\) 和 \(219\) 的数位差是 \(|1-2|+|3-1|+|3-9| = 9\)，位数不足用前导零补齐。

\(1 \leq L \leq R < 10^{100}\)

题解

考场上脑子瓦特了，想的 DP：钦定 \(a \leq b\)。设 \(f(i,0/1,0/1,0/1)\) 分别表示高 \(i\) 位 \(a\) 是否一直处于下界，\(b\) 是否处于上界，是否已经选取的位有 \(a=b\)，然后枚举当前位选的数，判断是否合法。

但事实上我们发现答案最大就是找到最高的位使得 \(L,R\) 的这一位 \(l_i,r_i\) 不同，然后 \(a\) 的这一位选 \(r_i\)，\(b\) 的这一位选 \(l_i\)，之后 \(a\) 一直选 \(0\)，\(b\) 一直选 \(9\)。

例如：\(L = 558244, R = 559244\)，取 \(a=559000,b=558999\) 最优。

Problem C Game with Reversing

题意

Alice Bob 玩游戏。现在有两个长为 \(n\) 的小写字母串 \(S,T\)，从 Alice 开始轮流操作，Alice 可以选择串里的某个位置，改成另一个小写字母（可以和原来相同），Bob 可以选一个串进行翻转。

Alice 想要游戏尽快结束，Bob 想要游戏尽可能长。求游戏结束时总共操作了多少次。

\(1 \leq n \leq 10^5\)

题解

我们发现 Bob 的具体操作策略对答案没有影响，因为翻两次 \(S\) 和翻一次 \(S\)，翻一次 \(T\) 本质相同。我们只需要关心游戏结束时，Bob 究竟操作了多少次。如果操作了奇数次，Alice 必须把 \(S\) 改的和 \(T\) 的反串相同，否则必须把 \(S\) 和 \(T\) 改的相同。

我们进一步发现，Alice 的操作次数只和 \(S\) 和 \(T\)（或其反串的差异）有关。于是分类讨论 Bob 操作次数的奇偶性，然后计算 Alice 的操作次数即可。注意有可能在 Bob 操作偶数次的情况下，Alice 需要操作的次数是一个奇数（比如 \(5\)），这个时候 Alice 必须要放空一轮，等 Bob 的第 \(6\) 次操作。同理另一侧也有一些特殊情况，处理一下即可。

Problem D Survey in Class

题意

现在有 \(n\) 个学生，\(m\) 个学科，第 \(i\) 个学生只会 \([l_i,r_i]\) 的学科的问题。现在你作为老师，可以问一些学科的问题，当然，每一科最多问一次。初始每个学生的手高度为 \(0\)。如果学生会该问题，则手的高度增加 \(1\)，否则减少 \(1\)。问在所有可能的问法中，最后学生中最高的手和最低的手的高度差最大是多少。

\(2 \leq n \leq 10^5,1 \leq l_i \leq r_i \leq m \leq 10^9\)

题解

考虑钦定两个学生是最高的和最低的。发现问他们都会的和都不会的都没有意义。只需要问一个人会的，另一个人不会的，才会拉开差距。设两个人会的集合分别是 \(a,b\)，那么要求的就是最大的 \(|a|-|a \cap b|\)。

考虑 \(b\) 怎么交 \(a\)：要么和 \(a\) 的左端点交，要么和 \(a\) 的右端点交，要么完全在 \(a\) 内部。于是，我们只需要检查三条线段：右端点最小的，左端点最大的，长度最小的。如果其中某些线段和 \(a\) 没有交，那无疑是更优的。

有瓜皮考场上写了线段树。