【10.30】【VP】Codeforces Round #735 (Div. 2)

ALL：5
AC：3
补题：1
Rank：1341

---

B. Cobb

题意：给定长度为 $n(2\le n\le 10^5)$ 和 $k(1\le k\le \min (100,n))$，输出 max ⁡ 1 ≤ i < j ≤ n { i ⋅ j − k ⋅ ( a i  OR  a j ) } \max_{1\leq imax1≤i<j≤n​{i⋅j−k⋅(ai​ OR aj​)}

思路：赛时想了半天，最后猜了暴力一下就过了。。不会严格证明。从每个 $1\le i\le n$ 向左暴力枚举 $k$ 或 $2\cdot k$ 个数字来更新就好了。

AC代码：https://codeforces.com/contest/1554/submission/178520796

---

C. Mikasa

题意：给定 $n,m(0\le n,m\le 10^9)$ ，找到最小的非负整数 $x$ 使得 x ∉ s = { n ⊕ i ∣ i ∈ [ 0 , m ] } x\notin s=\{n\oplus i|i\in [0,m] \} x∈/s={n⊕i∣i∈[0,m]} 。

思路：假设现有 $x_0\notin s$ ，由于异或的性质，即等价于 x 0 ⊕ n ∉ { i ∣ i ∈ [ 0 , m ] } x_0\oplus n\notin \{i|i\in[0,m]\} x0​⊕n∈/{i∣i∈[0,m]} ，即等价于 $x_0\oplus n\ge m+1$ 。要找到最小的 $x$ ，即等价于找最小的 $x_0$ 满足上式。

接下来思路是二进制上贪心。博客。从高位到低位贪心，如果该位相等，则跳过不考虑；否则，如果 $n^{\prime }=0,m^{\prime }=1$ ，那么 $n$ 这一位必须补 $1$ ，而且继续向下考虑；否则即 $n^{\prime }=1,m^{\prime }=0$ ，那么从这一位可以知道此时必然 $n>m$ ，直接跳出循环即可。

AC代码：https://codeforces.com/contest/1554/submission/178655723

---

D. Diane

题意：

要求您构造一个长度为 $n(1\le n\le 10^5)$ 的由小写字母构成的字符串，使得字符串内每个字串出现奇数次。

思路：手玩一下样例，可以发现，对于长度为 $i,i+1$ 的两个单字符串，本质不同子串出现次数都是奇数，那么找到最大的 $i$ 使得 $2\cdot i+1<n$ 。那么我们可以用另一个字符隔开这两个字符串，这样包含包含另一字符的子串肯定只出现一次。

这样构造出来 $n$ 为偶数，如为奇数再加一个另一字符即可。

AC代码（写过的最短 div2D 代码）：https://codeforces.com/contest/1554/submission/178523119