日记 - 伊埃斯的博客站

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

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

Wonderful Lightbulbs↗

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

Wonderful Teddy Bears↗

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

$\{0,1,0\} \to \{0,0,1\}$
$\{1,0,0\} \to \{0,0,1\}$
$\{1,0,1\} \to \{0,1,1\}$
$\{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↗

看到 $\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
#include<bits/extc++.h>
2
#define inf 0x3f3f3f3f
3
using namespace std;
4
const int maxn = 1e6 + 5;
5
int n,k,q;
6
char t[maxn],s[maxn];
7
int son[maxn][26],ans[maxn];
8
signed main()
9
{
10
    scanf("%d%d%s",&n,&k,t + 1);
11
    fill(son[0],son[0] + k,n + 1);// 这里直接把 son[0] 当 lst 用了
12
    fill(ans + 1,ans + n + 1,inf);// ans 初始化 inf
13
    for (int i = n; i >= 1; i--)
14
    {
15
        memcpy(son[i],son[0],sizeof(int) * k);// 把 lst memcpy 进 son[i]
16
        for (int j = 0; j < k; j++)
17
            ans[i] = min(ans[i],ans[son[0][j]] + 1);// 转移
18
        son[0][t[i] - 'a'] = i;// 更新 lst
19
    }
20
    scanf("%d",&q);
21
    while (q--)
22
    {
23
        scanf("%s",s + 1);
24
        int rt = 0,len = strlen(s + 1);
25
        for (int i = 1; i <= len && rt <= n; i++)
26
            rt = son[rt][s[i] - 'a'];// 每次跳，如果跳出去了就说明本就不是悦耳字符串。
27
        printf("%d\n",ans[rt]);
28
    }
29
    return 0;
30
}

Bermuda Triangle↗

式子推推推推到厌倦

后日谈

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

Thanks for reading!

日记

周二 4月 29 2025

898 字 · 5 分钟

life 日记