[Fortuna OJ]Jul 8th – Group B 解题报告

今天这几题咋就那么毒瘤呢?

A – String

其实这道题考场上应该能做出来的,是一道很简单的计数问题。在考场上一看到字符串就懵了,不知道为什么我对字符串的字典序有阴影,现在看来就是一道傻逼题。

考虑这样计数:

  1. 枚举一个\(i\),考虑前\(i-1\)个字符与\(T\)串相同,然后第\(i\)个字符小于\(T[i]\),这样可以保证后面怎么放置字母都能满足要求。
  2. 在枚举了\(i\)的情况下,枚举字符\(ch\),范围在\([a, T[i])\),考虑以下两种情况对答案的贡献:
    1. 如果\(ch = S[i]\),那么后面需要变动的字符个数为\(k\)个,对答案的贡献:\[ {n – i \choose k} 25^{k} \]
    2. 如果不等于,那么后面需要变动的字符个数为\(k-1\)个,因为本位占了一个;对答案的贡献:\[ {n – i \choose k – 1} 25^{k – 1} \]
  3. 贡献之后,如果本位\(T[i] \neq S[i]\),那么把\(k–\),代表多固定了一个不同的字符。

继续阅读[Fortuna OJ]Jul 8th – Group B 解题报告

Codeforces Round #539 (Div. 2) 解题报告 (CF1113)

C – Sasha and a Bit of Relax

其实这道题是一道大水题。我们知道成立条件为\(x_l \text{ xor } x_{l+1} \dots x_{mid} = x_{mid+1} \text{ xor } x_{mid+2} \dots x_{r}\),然而这个运算可以直接移项:因为\(xor\)是自己本身的逆运算。然后为了保证\(r-l+1\)为偶数,我们只需要在 Trie 树末端维护奇偶计数即可。

继续阅读Codeforces Round #539 (Div. 2) 解题报告 (CF1113)