清明时节,细雨纷纷。

年年岁岁花相似,岁岁年年人不同。

——不对,wxh、mcfx、yfz 都还在,再一次毫无悬念屠杀 uestc 校赛。

当然,我不在了。

一头天天喊着我名字当傻逼的李斯猪,一只菜到变形还自暴自弃的妹狗狗,——希望省选不是你们 OI 的终点。

还有 Yonda 和 €,有机会当然是最好的;再不济,也能感受一下 T1 选手的实力,明年再战也无妨。

不管怎么说,加油吧。

永远相信,汗水是不会骗人的。

Now the old king is dead, long live the king.

那传说 忘却了我的寂寞
英雄名不堪得
何必较我混沌徒费口沫
这人间 毕竟我真正走过
一途平九百波 九千错
凌云渡成正果
但我 有九九八十一种不舍


Day -1

和 QWsin、wxh 还有一位绵阳小哥住在一间寝室里,还是比较 Excited 的。

七中爷爷们还有南山爷爷们都在左右隔壁,栋栋也不远。

食堂好评。

晚上和 Menci、zyz、Qizy(ZYQN)、Sengxian 等等打炸弹小分队。我好菜啊.jpg

Day 0

上午开幕式,蜜汁校长讲话,“泥萌都是 CCF NOI 的孩子!”。dzd 先生骚话连篇。

Qizy 真牛逼,这么快就撩到 chrt 了。

下午笔试 AK,试机只有传统题,感觉药丸。

晚上心态不太好,开了一道 splay,一道 fft,一道树上前缀和,只能瞎写。最后 fft 没写。

NOI2003 文本编辑器 30min 1A,本来是好事,但是这是我 day1 惨挂的伏笔。

做了做 wxh 的毒瘤题。真毒。

去隔壁四中爷爷们那里 gay 了一会儿,嘿嘿嘿。

晚上睡不着,突然接到初中和高中好朋友的电话,被人惦记着的感觉真幸福。

Day 1

早饭不太舒服。

T1,造计算机?

T2,卧槽,字符集很小的字符串题,怕是药丸。

T3,九老师的 DP,好难。

于是怼 T1。先写了一发暴力,然后再找了好久规律,直到发现一位加一可以看做是一个 xor 和一个区间翻转。复杂度好像超了,想了一会儿发现可以在线段树上 dfs,对 32 位做暴力,然后再区间翻转复杂度就比较对了,算了算内存开得下。

时间已经过去 2h,不过我大概 20 min 就写完了,过了编译直接 1A。退役了想想,还是挺佩服自己在考场上的代码能力的,毕竟 200+ 行代码能够完美无缺地在 20 min 内写完,也可以说挺厉害的了吧。

把对拍写完,赛程过半,心有点慌。T2 因此看题不仔细,把 K 看做了一个 1e5 级别的数,然后怎么想都不行,把脑子里出现的 hash 正解给枪毙了。于是我只能先写 24 分暴力。

这个时候,我做出了一个改变我一生的决定。因为头天晚上 splay 很顺手,我居然没有继续认真看条件,特 么 在 考 场 上 准 备 用 L C T 维 护 链!

然后 1h 过去,写挂。

这个时候是真的慌了。看 T3,本来暴力挺好想的,愣是想了 40 min。

最后当然只能交交最简单的暴力了。


100 + 32 + 10,看成绩还不算太惨,rk 100 左右,还能翻。

wxh MLE,惨惨,不过还是比我高,这才是真正的大佬.jpg。

栋栋崩崩。QWsin 崩崩崩。


发了条说说,说 day2 AK 还能翻。

其实不用 AK 就能翻,不过我是傻子。

本来他们在打 deeeep.io,wxh 在栋栋的带领下开始打东方,毒瘤。

想打三国杀,结果大家都不打,我网页版三国杀也被盗号,找回真麻烦(10 月才找回成功)。

Day 1.5

早上忘记在干嘛了。

下午三国杀。

wxh:连营,AK,杀!

身份证掉了,去办了个临时的。

晚上不想写题,想着 Day 2 需要 AK 心态就比较崩。

Day 2

比 Day 1 有了更重的心理压力。

T1 是一道被我一眼看出来的 2-SAT,但我不会。

T2 是一道看起来像网络流的题。

T3 是防 AK (假)动态凸包。

因为不会 2-SAT,所以很慌,自己 YY 出来的 2-SAT 无法正常工作,骗分也没太有正常工作的可能。

有点崩。

T2,先写暴力网络流。

然后挂大样例,发现从第 29 天开始自己的输出就错了。

知道是建图挂了,但检查不出来。

心态崩了。

这时去把 T3 暴力写了,发现自己可能对向量排序不太熟练,希望有分。

调 T2。
调 T2。
调 T2。
看 T1,没啥好想到的。
调 T2。
调 T2。
调 T2。

时间一分一秒过去。

我终于知道,我要退役了。

看见时间,每跳一次心凉一次。

写了个大家都看不见的 AFO。

游戏结束了。

哭得有点累。


55 + 40 + 20。

下午讲题时,因为分低,连题都听不完,就被叫出去填面试表。

身不由己。

之前的成绩还可以,所以拿到了 sjtu 一本。

尬笑拍了个照,尬笑和张老师握了个手,和进了队的凯爷以及让我潜入四中听课,愿意替我背锅的文老师尬打招呼。

啊,然后在一个少有人看见的地方哭了一会儿。

天真蓝。阳光挺刺眼的,不过过一会儿太阳就落山了。

没去和爸妈老师吃饭,丢脸。

QWsin 似乎比我惨,好像没有签到约。


下午晚上三国杀,吼了一声,只有我不是 THU,全场沉默。

这可是八人局啊。

Day 3

上午错过早饭,和 QWsin 去下象棋。

Qizy 在和 Chrt 下跳棋,哼。

下午拿了个惨白色的牌子,提前回去了。

机场办临时身份证真麻烦。

金中 yylidiw 爷爷告诉我我的图怎么挂了。哦,原来我的“优化”这么厉害。


就这么退役了啊。

day1 如果 T2 没挂,我就 Au 了呀。

或者,day2 我能写出一个 O(nm) 的 2-SAT,并且不“优化”建图,也行呀。

或者,我 day1 没挂,day2 哪怕写不出 2-SAT,只要写对网络流,就能进队啊。

或者,我 day1 被卡常,day2 不失误,也能进队啊。

……

哪有那么多如果,可笑。

wxh 挂了两天 T1,照样能够在 Au 线边上。

栋栋 day1 雪崩,day2 还不是能翻回来。

人家 yql 还不是 day2 翻回了集训队。

哪有那么多如果,实力不济才是最大原因;发挥失常才是常态。

毕竟靠着运气走到现在,也比大多数人好运了吧。

不过,我可能与 thu 无缘了啊。

在二月对自己实力高估后,现在与 pku 也无缘啦。

也罢,这些都不重要,至少还有大学上。退役才是真的不甘心。

该怪谁呢?

怪学校辣鸡,支持竞赛非常晚,比别人少 x >= 1 年学习时间,进队后没有队友?

不吧,人家 LCA 还不是一年集训队。

只能说自己努力不够吧,省选后因为各种原因太水了。

太水了。

没有再来一年的机会,为什么我还要水呢?

后悔,没用啊。你高二了,没有重来的机会了。

你说 Never say die,也只能呐喊到游戏的最后一刻呀。现在,游戏结束了。

那就在这止步吧,永远不要再给自己留下这种尴尬的局面。

那一年我们望着星空
有那么多的灿烂的梦
以为快乐会永久
像不变星空陪着我

退役记坑了好久了……但还是不想写

然后这几天想玩RNN,于是预处理了一下自己BZOJ上的AC代码:

  1. 删去除 C/C++ 的其他语言
  2. 删去多余空行
  3. 将题目名称变为注释

于是,你可以点这里下载我的BZOJ AC代码。

题目描述

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

输入格式

两行,两个字符串 \(s_1,s_2\),长度分别为\(n_1, n_2\)。字符串中只有小写字母。

输出格式

输出一个整数表示答案

样例

样例输入

aabb
bbaa

样例输出

10

数据范围与提示

\(1 \leq n_1, n_2 \leq 200000\)

内存限制: 256 MiB 时间限制: 1000 ms


传送门:

https://loj.ac/problem/2064 或 http://www.lydsy.com/JudgeOnline/problem.php?id=4566


网上大部分题解都是关于SAM的……

然而我又用SA水过了QAQ

从两个串中分别取出一个后缀,对答案的贡献是他们的\(\mathrm{LCP}\)的长度;并且枚举所有后缀就是枚举了所有情况,因为实质上我们枚举的是相同子串的开头。

这样,如果将两个串加入位置在\(\mathrm{split}\)的分隔符拼接在一起变为\(S\),答案变为了$$
\sum_{i = 1} ^ {\mathrm{split} – 1} \sum_{j = \mathrm{split} + 1}^{|S|} \mathrm{LCP}(i, j)
$$转化问题到后缀数组上,那么问题就转化为分别统计对于每个\(h_i\),当他作为最小值即\(\mathrm{LCP}\)时,对答案做贡献的次数\(\mathrm{cnt}_i\)。

如果只考虑一个点,那么也就是统计经过它的符合条件的区间数。这个点左右合法区间端点必然是一个连续的区间\([L_i, R_i]\),为了避免重复我们定义\(L_i\)为最小的使得\(\mathrm{min}(h_{[L_i, i)}) \gt h_i\)的值,\(R_i\)为最小的使得\(\mathrm{min}(h_{[i, R_i]}) \geq h_i\)的值,有$$
\mathrm{cnt}_i = \sum_{l = L_i} ^ {i – 1} \sum_{r = i} ^ {R_i} h_i \cdot [(\mathrm{sa}_l < \mathrm{split} \ \mathrm{and}\ \mathrm{sa}_r > \mathrm{split}) \ \mathrm{or}\ (\mathrm{sa}_l > \mathrm{split} \ \mathrm{and}\ \mathrm{sa}_r < \mathrm{split})] $$两个\(\sum\)可以用乘法原理和前缀和\(O(1)\)求出,剩下的问题就是求\(L_i\)和\(R_i\)了,这是一个单调栈的经典问题。

所以我们就在求出后缀数组后,\(O(N)\)解决了这道题。

/* Never Say Die */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int, int> pii;
#define mp(a, b) make_pair(a, b)
#define fir first
#define sec second
inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}
int ch = 0;
template <class T> inline void read(T &a) {
	bool f = 0; a = 0;
	while (ch < '0' || ch > '9') {if (ch == '-') f = 1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {a = a * 10 + ch - '0'; ch = getchar();}
	if (f) a = -a;
}

#define MAXN 400010

void Sort(int in[], int out[], int p[], int n, int m) {
	static int P[MAXN];
	for (int i = 1; i <= m; i++) P[i] = 0;
	for (int i = 1; i <= n; i++) P[in[i]]++;
	for (int i = 2; i <= m; i++) P[i] += P[i - 1];
	for (int i = n; i; i--) out[P[in[p[i]]]--] = p[i];
}

char s[MAXN];
int sa[MAXN], rk[MAXN], h[MAXN];

int n, l1;
void getsa() {
	static int t1[MAXN], t2[MAXN], *x = t1, *y = t2;
	int m = 127;
	for (int i = 1; i <= n; i++) x[i] = s[i], y[i] = i;
	Sort(x, sa, y, n, m);
	for (int j = 1, i, k = 0; k < n; m = k, j <<= 1) {
		for (i = n - j + 1, k = 0; i <= n; i++) y[++k] = i;
		for (i = 1; i <= n; i++) if (sa[i] > j) y[++k] = sa[i] - j;
		Sort(x, sa, y, n, m);
		for (swap(x, y), i = 2, x[sa[1]] = k = 1; i <= n; i++) {
			x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k : ++k;
		}
	}
	for (int i = 1; i <= n; i++) rk[sa[i]] = i;
	for (int i = 1, k = 0; i <= n; h[rk[i++]] = k) {
		k -= !!k;
		for (int j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++);
	}
}

int sta[MAXN], p[MAXN], L[MAXN], R[MAXN], s1[MAXN], s2[MAXN];

void work() {
	int top = 0; sta[0] = -1;
	for (int i = 1; i <= n; i++) {
		while (sta[top] >= h[i]) {
			R[p[top]] = i - 1;
			top--;
		}
		L[i] = p[top] + 1;
		sta[++top] = h[i], p[top] = i;
	}
	while (top) R[p[top--]] = n;
	for (int i = 1; i <= n; i++) s1[i] = s1[i - 1] + (sa[i] < l1);
	for (int i = 1; i <= n; i++) s2[i] = s2[i - 1] + (sa[i] > l1);
	LL ans = 0;
	for (int i = 2; i <= n; i++) {
		ans += (LL)h[i] * ((s2[i - 1] - s2[L[i] - 2]) * (s1[R[i]] - s1[i - 1]) + (s1[i - 1] - s1[L[i] - 2]) * (s2[R[i]] - s2[i - 1]));
	}
	printf("%lld\n", ans);
}

int main() {
	scanf("%s", s + 1);
	n = (int)strlen(s + 1);
	s[l1 = ++n] = '|';
	scanf("%s", s + n + 1);
	n += (int)strlen(s + n + 1);
	getsa();
	work();
	return 0;
}

QAQ这么搞我什么时候才能学会SAM啊……