日记

昨天晚上打 CF 去了，没写日记。

CF1400 的题都做不对的 OIer 有什么用？

Wonderful Lightbulbs# Link to

我们有结论：设最初的灯泡在 $(x,y)$，那么第 $x$ 行一定有奇数个灯泡在亮，它所在的对角线也一定有奇数个灯泡在亮。

Wonderful Teddy Bears# Link to

首先我们把字符映射一下：$\texttt{B} \to 0,\texttt{P} \to 1$。考虑 $4$ 种操作：

1. $\{0,1,0\} \to \{0,0,1\}$
2. $\{1,0,0\} \to \{0,0,1\}$
3. $\{1,0,1\} \to \{0,1,1\}$
4. $\{1,1,0\} \to \{0,1,1\}$

让我们从逆序对的角度考虑：对于第 $1,3$ 种操作，只会减少 $1$ 个逆序对，对于第 $2,4$ 个操作，会减少 $2$ 个逆序对。显然我们应该贪心的先做 $2,4$ 操作直到做不动为止。

我们看何时 $2,4$ 操作做不动了。当且仅当 $a$ 变成形如 $\{0,0,0,\dots ,0,1,0,1,\dots,0,1,0,1,1,1,\dots,1\}$，也就是说，$a$ 可以被分成一个全为 $0$ 的前缀和一个全为 $1$ 的后缀，和一个 $0,1$ 交替出现的字串。

因为 $0,1$ 交替出现，我们考虑记录 $a$ 表示总的 $0$ 的个数，$b$ 表示在偶数位置上的 $0$ 的个数。依然考虑这 $4$ 种操作：$2,4$ 操作不会改变 $b$，$1,3$ 操作会使 $b$ 变化（增加或减少）$1$。考虑 $b$ 的最终形态是什么。因为 $0$ 会全聚在 $a$ 的前面，所以 $b$ 的目标是 $\lfloor \frac{a}{2} \rfloor$。于是我们可以这样：设总共有 $x$ 逆序对，先做 $|b - \lfloor \frac{a}{2} \rfloor|$ 次 $1,3$ 操作。$x$ 减少 $|b - \lfloor \frac{a}{2} \rfloor|$，然后再做 $\frac{x}{2}$ 次 $2,4$ 操作。

Unpleasant Strings# Link to

看到 $\sum|t_i| \le 1 \times 10^6$，看能不能搞出一种 $O(\sum|t_i|)$ 的算法。

我们想到预处理 $s$ 串上每个下标 $i$ 的 $ans_i$，表示以 $i$ 结尾的子序列最少还要加多少个字符才能不再成为悦耳字符串。

考虑如何预处理。$i$ 从后往前枚举，记录一个 $lst_i$ 表示字符 $i$ 最后出现的地方。我们枚举每个字符。有显然的转移：$ans_i = \min\{ans_{lst_i} + 1\}$，表示在这个点后面接每个字符的方案。$lst$ 初始全为 $n + 1$，且 $ans_{n + 1} = 0$。再记录一个 $son_{i,j}$，每次都把 $lst$ 给 memcpy 进 $son_i$。转移完了再更新 $lst$。最后把 $lst$ memcpy 进 $son_0$。

考虑如何处理询问。就像字典树一样，我们记录一个 $rt$ 表示当前跳到了 $rt$ 这个点。枚举 $t$ 里每个字符 $t_i$，每次跳到 $son_{rt,t_i}$。如果说跳着跳着直接跳到 $n + 1$ 了，就说明它本就不是悦耳字符串，$ans$ 置为 $0$ 并 break。反之如果跳到了 $t$ 的结尾了都没跳出去，就说明这是一个悦耳字符串，答案即为 $ans_{rt}$。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include<bits/extc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e6 + 5;
int n,k,q;
char t[maxn],s[maxn];
int son[maxn][26],ans[maxn];
signed main()
{
    scanf("%d%d%s",&n,&k,t + 1);
    fill(son[0],son[0] + k,n + 1);// 这里直接把 son[0] 当 lst 用了
    fill(ans + 1,ans + n + 1,inf);// ans 初始化 inf
    for (int i = n; i >= 1; i--)
    {
        memcpy(son[i],son[0],sizeof(int) * k);// 把 lst memcpy 进 son[i]
        for (int j = 0; j < k; j++)
            ans[i] = min(ans[i],ans[son[0][j]] + 1);// 转移
        son[0][t[i] - 'a'] = i;// 更新 lst
    }
    scanf("%d",&q);
    while (q--)
    {
        scanf("%s",s + 1);
        int rt = 0,len = strlen(s + 1);
        for (int i = 1; i <= len && rt <= n; i++)
            rt = son[rt][s[i] - 'a'];// 每次跳，如果跳出去了就说明本就不是悦耳字符串。
        printf("%d\n",ans[rt]);
    }
    return 0;
}

Bermuda Triangle# Link to

式子推推推推到厌倦

后日谈 # Link to 后日谈

去开拓把，即使前方道路未卜。