Codeforces Round #685 (Div. 2)/Codeforces1451 题解ABCDE

AC代码

A. Subtract or Divide

(n le 3)时特判。其余情况,若(n)为偶数,则可以直接从(2)转移,答案为(2);若(n)为奇数,则先从(2)转移到(n - 1),再转移到(n),答案为(3)

B. Non-Substring Subsequence

只要(s[1..l-1])里有(s_l)或者(s[r+1...n])里有(s_r)即可。

C. String Equality

  • 根据操作1,元素所处的位置并不影响结果,答案只和数量有关,所以先分别对两个串统计各个字符出现的次数。
  • 从小到大枚举小写字母,假设枚举到字符(c),假设(a)中有(c_1)个字符(c)(b)中有(c_2)个字符(c)
    • 如果(c_1 ge c2)
      • 那么可以令(c_1 = c_1 - c_2),表示(c_2)个字符已经匹配了。
      • 现在剩下的(c_1)是要转换成其他更大的字符的,所以如果(c_1)不能被(k)整除,则会有部分(c)无法转换成更大的字符,无解。
      • 既然要转移成更大的,不如就直接让这些(c)全都变成(c+1)
    • 否则,根据上一个步骤的第三步,没有其他更小的字符可以拿来转换了,无解。

D. Circle Game

猜结论:两人都采用最优解法是,结束时所走步数必定是最大的。

枚举向(x)轴方向走了多少步,算出此时向(y)轴最多能走多少步,记步数和的最大值为(ma)

根据(ma)的奇偶性就可以判断是先手必胜还是后手必胜。

E2. Bitwise Queries (Hard Version)

  • 首先,(forall i in [2, n]), XOR 1 i,记结果为(b_i), 花费(n - 1)次操作机会。
  • 如果存在重复元素:
    • 以下两种情况必定发生一种
      • (b_i = 0),即(a_1 = a_i)
      • (b_i = b_j),即(a_i = a_j)
    • AND i j,花费(1)次操作机会,得到(a_i), 并由此推出(a_1)
  • 否则:
    • (a)中元素两两不同。
    • (a)中存在(a_i = a_1 oplus 1)
    • (a)中存在(a_j = a_1 oplus 2)
    • AND 1 i,花费(1)次操作机会,得到(x = a_1 & (a_1 oplus 1))
    • AND 1 j,花费(1)次操作机会,得到(y = a_1 & (a_1 oplus 2))
    • (a_1 = x | y)
  • 现在(a_1)已知,(b_i oplus a_1 = a_1 oplus a_1 oplus a_i = a_i)

反思

C看错题,卡了40min。E想出来了,但是手慢了。

又掉分了,离黄名越来越远。

明年就毕业了,工作之后估计就没时间打了,希望在那之前可以实现上黄的小目标。

原文地址:https://www.cnblogs.com/zengzk/p/14018115.html