今天有点人品，T1的50pts暴力怒压正解。。这数据。。不言而喻

$\text{score: 100 + 0 + 0 = 100 rk: 7/36}$

Problem A：时间管理带师

题目描述

众所周知，罗老师是时间管理带师

因为罗老师是时间管理带师，所以他的时间是以东为单位的

具体来讲，罗老师一天有nn东的时间

现在有很多妹子想跟罗老师约会

奇特的，她们每天总会提出两段约会时间（可能相同，代表一种），并且每天提出的总是一样的。

她们提出的约会时间形式形如i,j,代表希望在[i东,(i+1)东)[i东,(i+1)东)或[j东,(j+1)东)[j东,(j+1)东)与罗老师进行约会。

当然，罗老师可以这两段时间都与这个妹子约会,只选择一段，或者伤心地抛弃。

那么，作为时间管理带师的罗老师，每天会选择尽可能多的妹子进行约会

但你一定要注意,罗老师最近并不打算进行多人运动，所以他不会在1东的时间同时与两个或多个妹子约会

罗老师并不脸盲，与一个妹子约会2次并不能算成”2”次的贡献，只能是”1”

罗老师是时间管理带师，只要满足以上条件，他就可以安排好他的时间，不用担心别的

而且,每天可能会有新的妹子向罗老师提出约会邀请

但是时间久了，一些妹子认识到罗老师是个渣男罗老师太忙了，就不再给罗老师提出约会邀请

每天要么有妹子加入，要么有妹子退出，这两种情况有且仅会发生一种，并且退出的妹子一定是当前想要和罗老师约会的妹子中时间最久的。其实，这就对应了双端队列的push和pop。我们保证，罗老师每天的妹子数量非负

现在，作为罗老师的贴身秘书，你每天要给罗老师规划好他的时间，每天告诉罗老师他今天最多可以约会多少个妹子

不过本题中，操作可以强制在线

数据范围

对 $100\%$ 的数据，$1 \le n, m \le 10^5, 0 \le type \le 1, 0 \le op, a, b \le 10^6$

其中 $a, b$ 表示妹子的约会时间为 $a, b$

题解

这神奇的题目描述，真的时间管理带师

先考虑暴力，每次替换实际上就是一个类似匈牙利算法的东西，然后它只删队首的妹子，所以我们要尽可能让队首的妹子对答案无影响，所以每次队尾加入一个妹子的时候，如果判断出可以为她凑出一个额外的位置那就直接做，加入不行则替换掉其中最早入队的妹子（实际上这整个可以看成多棵内向基环树，即假如编号为 $i$ 的妹子占了一个位置，并且占的是约会时间 $a$，那么她就连一条 $a \rightarrow b$ 的有向边，并给这个边以入队顺序的编号，那么每一次类似匈牙利算法的过程即是这个图中的一条链，那么就取编号最小的边就行了），那么在删队首妹子的时候她就只有对答案无影响或者占了一个位置而使答案减一两种情况了

这个理论复杂度显然不能过，随便出个一条链的数据就卡掉了，但我还是稍微放一下它的代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
#include <iostream>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
const int MAXN = 1e05 + 10;
const int MAXM = 1e05 + 10;
const int MAXA = 1e06 + 10;
 
int A, M, type;
int ns = 1, ne = 0;
int posi[MAXN][2]= {0};
 
bool visit[MAXA]= {false};
int who[MAXA]= {0}, use[MAXN]= {0}, in[MAXN]= {0};
pair<int, int> findpos (int u) { // pair<int, int> 分别表示找到的空座位与占位置的编号最小妹子
    if (visit[u]) return make_pair (- 1, who[u]);
    if (! who[u]) return make_pair (u, 0);
    visit[u] = true;
    pair<int, int> ret = findpos (posi[who[u]][use[who[u]] ^ 1]);
    visit[u] = false;
    return make_pair (ret.first, min (ret.second, who[u]));
}
bool select (int u, int aim) {
    if (visit[u]) return false;
    if (u == aim) {
        in[who[u]] = 0; who[u] = 0;
        return true;
    }
    visit[u] = true;
    bool suc = false;
    if ((suc = select (posi[who[u]][use[who[u]] ^ 1], aim))) {
        int p = who[u]; who[u] = 0;
        use[p] ^= 1; in[p] = posi[p][use[p]];
        who[in[p]] = p;
    }
    visit[u] = false;
    return suc;
}
int ans = 0;
void add (int p, int tp) {
    use[p] = tp, in[p] = posi[p][tp];
    who[in[p]] = p;
}
 
inline int getnum () {
    int num = 0; char ch = getchar ();
    while (! isdigit (ch)) ch = getchar ();
    while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
    return num;
}
 
int main () {
    A = getnum (), M = getnum (), type = getnum ();
    for (int i = 1; i <= M; i ++) {
        int op, a, b;
        if (type == 0) {
            op = getnum ();
            if (op == 1) a = getnum (), b = getnum ();  
        }
        else {
            op = (getnum () + ans) % 2;
            if (op == 1) a = (getnum () + ans) % A + 1, b = (getnum () + ans) % A + 1;
        }
        if (op == 1) {
            posi[++ ne][0] = a, posi[ne][1] = b;
            pair<int, int> ret1 = findpos (a), ret2;
            if (ret1.first == - 1) {
                ret2 = findpos (b);
                if (~ ret2.first) {
                    select (b, ret2.first); add (ne, 1);
                    ans ++;
                }
                else if (ret1.second < ret2.second) {
                    select (posi[ne][0], in[ret1.second]);
                    add (ne, 0);
                }
                else {
                    select (posi[ne][1], in[ret2.second]);
                    add (ne, 1);
                }
            }
            else { select (a, ret1.first); add (ne, 0), ans ++; }
        }
        else {
            if (in[ns]) {
                ans --;
                who[in[ns]] = 0; in[ns] = 0;
            }
            ns ++;
        }
        printf ("%d\n", ans);
    }
 
    return 0;
}

那么接下来就是正解，用 $\text{LCT}$ 来维护这个最小编号妹子

现在先考虑连边整出来的连通块，设该连通块有点 $x$ 个，边 $y$ 个，那么显然若 $x > y$，则答案为 $x - 1$，若 $x \le y$，就代表有环，那么答案即为 $x$

现在考虑用 $\text{LCT}$ 来维护，首先把这个连通块里选择的节点抽成一棵树，并且边化点，那么剩下的边无法在 $\text{LCT}$ 中表示，但是只要存在其中一条就说明一定会构成环，所以我们只需统计每个点它会连多少这样的边即可

每次删 $\text{LCT}$ 中边的时候，删完边就给该边连接的两个点权值各加一，说明它们之间的边变成了使成环的边，那么就得更新答案；同理加边则把它们原来加上的权值减掉

感觉说不清楚具体还是看代码注释吧

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 2e05 + 10;
const int MAXM = 1e05 + 10;

const int INF = 0x7fffffff;

int N, M, type, n;
int posi[MAXN][2]= {0};
// n: 边化点
int ans = 0;

int father[MAXN]= {0}, son[MAXN][2]= {0};
int rev[MAXN]= {0};
int vimi[MAXN]= {0}, fic[MAXN]= {0}, vism[MAXN]= {0};
// 当前节点连的非树节点个数、当前节点虚子树vimi和、当前节点虚实子树vimi和
int mini[MAXN]= {0}; // 最早入队边
int isroot (int p) { return son[father[p]][0] != p && son[father[p]][1] != p; }
int sonbel (int p) { return son[father[p]][1] == p; }
void reverse (int p) {
	if (! p) return ;
	swap (son[p][0], son[p][1]); rev[p] ^= 1;
}
void pushup (int p) {
	vism[p] = vimi[p] + fic[p] + vism[son[p][0]] + vism[son[p][1]];
	mini[p] = min (p <= N ? INF : p, min (mini[son[p][0]], mini[son[p][1]]));
}
void pushdown (int p) {
	if (! rev[p]) return ;
	reverse (son[p][0]), reverse (son[p][1]);
	rev[p] = 0;
}
void rotate (int p) {
	int fa = father[p], anc = father[fa];
	int s = sonbel (p);
	son[fa][s] = son[p][s ^ 1];
	if (son[fa][s]) father[son[fa][s]] = fa;
	if (! isroot (fa)) son[anc][sonbel (fa)] = p;
	father[p] = anc;
	son[p][s ^ 1] = fa, father[fa] = p;
	pushup (fa), pushup (p);
}
int stack[MAXN], top;
void splay (int p) {
	top = 0; stack[++ top] = p;
	for (int tp = p; ! isroot (tp); tp = father[tp]) stack[++ top] = father[tp];
	while (top > 0) pushdown (stack[top]), top --;
	for (int fa = father[p]; ! isroot (p); rotate (p), fa = father[p])
		if (! isroot (fa))
			sonbel (p) == sonbel (fa) ? rotate (fa) : rotate (p);
}
void access (int p) {
	for (int tp = 0; p; tp = p, p = father[p]) {
		splay (p);
		fic[p] += vism[son[p][1]] - vism[tp];
		son[p][1] = tp; pushup (p);
	}
}
void makeroot (int p) { access (p), splay (p); reverse (p); }
int findroot (int p) {
	access (p), splay (p);
	while (son[p][0]) { pushdown (p); p = son[p][0]; }
	splay (p);
	return p;
}
inline int value (int p) { return vism[p] > 0; } // 判断是否成环，若成环则答案需要再点个数上加一
void hideit (int p, int delta) { // 将树上边变为使成环边
	makeroot (p); ans -= value (p);
	vimi[p] += delta, pushup (p); ans += value (p);
}
bool in[MAXN]= {false};
void link (int id, int x, int y) {
	makeroot (x), makeroot (y);
	ans -= value (x) + value (y); // 删去原来两个分开的连通块的贡献再加上新合成连通块贡献
	ans ++; father[x] = father[y] = id;
	fic[id] += vism[x] + vism[y], pushup (id);
	ans += value (id); in[id] = true;
}
void cut (int id, int x, int y) {
	makeroot (x), access (y), splay (id);
	ans --, ans -= value (id);
	father[x] = father[y] = 0; ans += value (x) + value (y);
	in[id] = false;
}
void PUSH (int id, int x, int y) {
	if (x == y) { hideit (x, 2); return ; }
	makeroot (x);
	if (findroot (y) == x) {
		access (y), splay (y); int p = mini[y];
		cut (p, posi[p][0], posi[p][1]);
		hideit (posi[p][0], 1), hideit (posi[p][1], 1);
	}
	link (id, x, y);
}
void POP (int id, int x, int y) {
	if (! in[id]) {
		hideit (x, - 1), hideit (y, - 1);
		return ;
	}
	cut (id, x, y);
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	n = N = getnum (), M = getnum (), type = getnum ();
	int st = N + 1; mini[0] = INF;
	for (int i = 1; i <= M; i ++) {
		int op, a, b;
		if (type == 0) {
			op = getnum ();
			if (op == 1) a = getnum (), b = getnum ();	
		}
		else {
			op = (getnum () + ans) % 2;
			if (op == 1) a = (getnum () + ans) % N + 1, b = (getnum () + ans) % N + 1;
		}
		if (op == 1) {
			posi[++ n][0] = a, posi[n][1] = b; // ++ n表示边化点
			PUSH (n, a, b);
		}
		else { POP (st, posi[st][0], posi[st][1]); st ++; }
		printf ("%d\n", ans);
	}

	return 0;
}

Problem B：大猫熊和他的k边形

题目描述

菜鸡zjr今天被一道幼儿园几何题打爆了，一分都拿不到。

于是他向你求助QwQ:

给定 $n,k$，求出 $i(k \le i \le n)$ 边形的所有三角剖分中, $k$ 边形的总数的和对 $1e9 + 7$ 取模的结果。

$k$ 边形指的是 $n$ 个点中的 $k$ 个点，他们在这个剖分中构成一个封闭图形。

数据范围

对于 $100\%$ 的数据，$3 \le k \le n \le 5 \times 10^6$

题解

官方题解看不懂。。看别人的题解。。

首先这个问题可以看成求所有 $n - 2$ 个节点的二叉树中大小为 $k - 2$ 的连通块的数量之和

那么现在直接令 $n, k$ 减二

单独考虑每个连通块的贡献，首先它有 $Cat_k$ 种形态，该树有 $k + 1$ 种接子树的方案（数一下就知道了，不包括该树根节点往其父亲连），那么第一部分（接儿子）方案数即为
$$
\sum\limits_{i = 0}^{n - k} Cat_k[x^i]C^{k + 1}
$$
其中 $i$ 表示接儿子子树的总大小，$C$ 表示卡特兰数列的生成函数

那么现在考虑接父亲，容易知道方案数为
$$
\sum\limits_{j = 0}^{n - k - i} Cat_j(j + 1)
$$
其中 $j$ 表示接的树的大小，$j + 1$ 也是一样表示对接的树来讲有 $j + 1$ 种接儿子的方案

现在时间复杂度的症结在于 $[x^n]C^m$ 的计算，考虑它的几何意义

它相当于 $i$ 个折线图拼起来，现在考虑如何将这些折线图分段，就是将每一段折线图的结尾 $-1$，那么总共会减 $m - 1$ 次（最后一段是不需要减的），也就是说“第一次出现 $0$ 到第一次出现 $- 1$ 的位置”对应第一段折线，“第一次出现 $- 1$ 到第一次出现 $- 2$ 的位置”对应第二段折线。。。

那么现在就是给 $n$ 个 $+ 1$，$n + m - 1$ 个 $- 1$，计算其由 $(0, 0)$ 到 $(2n + m - 1, - m + 1)$，并且保证前缀和 $\ge - m + 1$ 的方案数，故显然有
$$
[x^n]C^m = \dbinom{2n + m - 1}{n} - \dbinom{2n + m - 1}{n - 1}
$$

代码

我的 $\text{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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdio>
#include <cstring>
 
#define MOD 1000000007
 
using namespace std;
 
typedef long long LL;
 
const int MAXN = 1e07 + 10;
 
const int MAX = 1e07;
 
LL inv[MAXN]= {0};
LL fact[MAXN]= {0}, invfact[MAXN]= {0};
 
LL cat[MAXN]= {0}, g[MAXN]= {0};
 
LL C (int n, int m) { return fact[n] * invfact[m] % MOD * invfact[n - m] % MOD; }
LL calc (int n, int m) { return (C (2 * n + m - 1, n) - C (2 * n + m - 1, n - 1) + MOD) % MOD; }
// [x^n]C^m
 
int main () {
    int n, k;
    cin >> n >> k;
    n -= 2, k -= 2;
    fact[0] = invfact[0] = 1;
    fact[1] = invfact[1] = inv[1] = 1;
    for (int i = 2; i <= MAX; i ++) {
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
        fact[i] = fact[i - 1] * i % MOD;
        invfact[i] = invfact[i - 1] * inv[i] % MOD;
    }
    cat[0] = g[0] = 1;
    for (int i = 1; i <= n; i ++) {
        cat[i] = cat[i - 1] * (4 * i  - 2) % MOD * inv[i + 1] % MOD;
        g[i] = (g[i - 1] + cat[i] * (i + 1) % MOD) % MOD;
    }
    LL ans = 0;
    for (int i = 0; i <= n - k; i ++)
        ans = (ans + cat[k] * calc (i, k + 1) % MOD * g[n - i - k] % MOD) % MOD;
    cout << ans << endl;
 
    return 0;
}

Problem C：SUMMER WC

题目描述

OIer是个可爱的群体，他们有很多的禁忌词汇，对此他们会有坏感度，我们表示成 $- x$ 的形式，$x$ 为正整数，越大，表示他们越讨厌，比如:

$\text{ccf}$ $-250250$ $\text{summerwc}$ $-2600$ $\text{unitedshengxuan}$ $-700$

但他们也会对一些东西有好感度，类似的，我们列出例子:

$\text{frog}$ $+1000000$（其实远远不止，但本题的权值上限 $1e6$）$\text{apiadu}$ $+3681$ $\text{txdy}$ $+3669$

类似的，我们还有很多例子

一个字符串的好感度就是里面出现过的词汇的感觉的和，一个词汇出现多次算多次

例如 $\text{frogfrog}$ 的好感度就是 $2e6$

特别的，我们考虑空串，其好感度为 $0$

现在我么给出一个大的串，同时给出所有词汇(好感度可以为负，表示有多讨厌),我们需要求出里面最大好感度子串，可以为空

数据范围

设 $n$ 个词汇的长度和为 $L$，$L_{max}$ 为其中的最大长度

对 $100\%$ 的数据，$1 \le n, m, L, L_{max} \le 10^6, ~ 1 \le x \le 10^6$

题解

完全不会。。我字符串实在太菜了。。

好像这是 $\text{GDOI2019}$ 的 $D2T3$ 的原题

主要思路就先建出一个$\text{AC}$自动机然后在上面$dp$

建出自动机后那些结尾节点都会有一个权值 $val$，那么对文本串 $[l, r]$ 的子串就是在自动机上走然后把路径上所有 $val$ 加起来即可得到它的好感度和

此时不妨设计状态 $f_{i, j}$ 表示文本串匹配到 $i$ 时，$\text{AC}$自动机上走到节点 $j$ 时的最大值，而造成这个最大值的子串即是 $1…i$ 的其中一个后缀子串

假设文本串子串 $[1, i]$ 在自动机上走到节点 $node_i$，那么现在考虑有可能被 $1…i$ 的后缀子串遍历到的 $j$，则 $j$ 一定在 $fail$ 树上是 $node_i$ 的祖先，故总状态有 $mL_{max}$ 个，此时复杂度为 $O (mL_{max})$

现在对上述 $dp$ 进行优化

在往$\text{AC}$自动机里插入的时候，建立父子关系（即$\text{trie}$树上的父子关系），用 $fa_i$ 表示

每经过自动机上某一条边，转移一定是相同的，故简化一下，令 $f_i$ 表示自动机上走到 $i$ 的答案（此时与文本串无关，因为节点 $i$ 已经确定了唯一一个后缀），考虑 $f_i$ 都从哪里转移，令字符串 $S_i$ 表示节点 $i$ 表示后缀

  • 直接等于 $f_{fail_i}$
  • 由 $fa_i$ 及其后缀再加上 $val_{fail_i}$ 转移（即不取 $S_i$ 的第一个字符，那么 $val_i$ 也不能加上了）
  • 直接取整个 $S_i$

故此时再设两个状态 $g_i, h_i$，其中 $g_i$ 表示第三种情况，$h_i$ 表示第二种情况，那么 $f_i$ 的转移就表示为
$$
f_i = \max (f_{fail_i}, \max (g_i, h_i))
$$
至于为什么还要设 $h_i$，因为假如直接从 $f_{fail_i}$ 转移的话可能 $S_i$ 的某些有贡献后缀就无法被遍历到了，举个例子

1
2
3
4
e
de
bd
abde

那么在计算 $f(abde)$ 的时候，若只取其 $fail$ 树上父亲，则只会访问到 $\text{de}$，那么 $\text{bd}$ 后面拼上一个 $e$ 的情况就遍历不到了

其中对 $h_i$ 的转移只要考虑 $S_i$ 与 $S_{fail_i}$ 的差值部分就好了，故总转移复杂度是 $O (m + L)$ 的

注意记得将文本串插入到自动机中，不然显然无法统计答案

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;

const int MAXN = 2e06 + 10;

const LL INF = 0x3f3f3f3f3f3f3f3f;

int N, M;
char str[MAXN];

int m = 0;
int father[MAXN]= {0};
int tr[MAXN][26]= {0}, fail[MAXN]= {0};
LL value[MAXN]= {0};
void insert (int x) {
	int p = 0; int n = strlen (str + 1);
	for (int i = 1; i <= n; i ++) {
		int c = str[i] - 'a';
		if (! tr[p][c]) { tr[p][c] = ++ m; father[m] = p; }
		p = tr[p][c];
	}
	value[p] += x;
}
queue<int> que;
LL f[MAXN]= {0}, g[MAXN]= {0}, h[MAXN]= {0};
void build () {
	for (int i = 0; i < 26; i ++)
		if (tr[0][i])
			que.push(tr[0][i]);
	while (! que.empty()) {
		int u = que.front(); que.pop();
		value[u] += value[fail[u]];
		g[u] = g[father[u]] + value[u];
		if (! fail[u]) h[u] = h[father[u]];
		else {
			h[u] = - INF;
			for (int j = father[u]; j != father[fail[u]]; j = fail[j])
				h[u] = max (h[u], h[j] + value[fail[u]]);
		}
		f[u] = max (f[fail[u]], max (g[u], h[u]));
		for (int i = 0; i < 26; i ++) {
			if (tr[u][i]) {
				fail[tr[u][i]] = tr[fail[u]][i];
				que.push(tr[u][i]);
			}
			else tr[u][i] = tr[fail[u]][i];
		}
	}
}
LL solve () {
	LL ans = 0;
	int p = 0, n = strlen (str + 1);
	for (int i = 1; i <= n; i ++) {
		int c = str[i] - 'a';
		p = tr[p][c];
		ans = max (ans, f[p]);
	}
	return ans;
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	bool isneg = false;
	while (! isdigit (ch)) {
		if (ch == '-') isneg = true;
		ch = getchar ();
	}
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return isneg ? - num : num;
}

int main () {
	N = getnum (), M = getnum ();
	for (int i = 1; i <= N; i ++) {
		scanf ("%s", str + 1);
		insert (getnum ());
	}
	scanf ("%s", str + 1); insert (0);
	build ();
	cout << solve () << endl;

	return 0;
}