【题解】[JOI Open 2021] Crossing

7KByte · 2021-08-23 22:49:18 · 题解

有删减，原文见我的博客。

很有意思的一道题。

不难发觉得关键还是在变化上。

我们用 1,2,3 表示分别表示三个字母，那么如果 c_1\neq c_2，则 c_3 = c_1 \oplus c_2，直接异或就行。

但是如果 c_1=c_2 根本表示不了，后面也没法做（罚坐了半个小时

考虑用 0,1,2 分别表示三个字母，那么我们可以发现 c_3\equiv-c_1-c_2\pmod{3}。

所以杂交后得到的串 S 一定可以表示为 aS_A+bS_B+cS_C，由于每一位都是模 3 意义下的，所以杂交所得的串不会超过 27 个。

我们直接写个程序爆算所有可能的 (a,b,c)，发现只有 9 种可能。

那么我们只用预处理这 9 个串的哈希值，然后用线段树维护 T 的哈希值，这道题就做完了。