Contest Mar.5 劲题三连

发表于

%%%Sparrow…

T 1

题意是给你一个图中两两点间的最小割，要你构造出这个图

看到这个题一开始想到6号讲过的”CQOI2016不同的最小割”

然后看了一眼样例，发现一定可以构造出一个满足条件的树

然后就没往下想了。。

最后发现随便搞搞就可以过很多点。。

thh && why : 最大生成树就好啦！

sparrow :贪心选最小的边，割开就好啦！

T 2

题意是在树上选k个点，求$min(\sum_{i=1}^{k-1}dis(i,i+1))$

发现就是找一个k个点连通块，其中只有一条链权值只算一遍，其他边权值算两遍，求最小值

然后想到了“摧毁树状图”，迪屁一下就好啦！

状态：$f[i][j][k]表示i号点选了一个j个点的连通块，状态为k$

分三个状态

  • 0 : $一个链穿过i,它是闭合的，也就是端点不在i号点上$
  • 1 :$一个链吊在i上，它可以往上延伸$
  • 2 :$选的子树边权全部算两遍$

简直和摧毁树状图一模一样

然后敲了个灵车树形迪屁，GG

因为我迪屁的时候，转移全靠想象

sparrow : 把所有转移的排列枚举一下不好？

666666

发现背包时这样枚举，效率快很多！

1
2
3
4
5
6
for (j = min(size[x], m); j >= 1; j --)
			for (k = 1; k <= size[u]; k ++) {
				f[x][j + k][1] = min (f[x][j + k][1], f[x][j][1] + f[u][k][2] + Len[i] * 2);
				f[x][j + k][1] = min (f[x][j + k][1], f[x][j][2] + f[u][k][1] + Len[i]);
				f[x][j + k][1] = min (f[x][j + k][1], f[x][j][2] + f[u][k][2] + Len[i]);
			}

比枚举背包大小不知快到哪里去！

T 3

这道题非常的劲，第一眼看上去，可持久化马拉车？

想到字符串内容有一个回文树没学过，GG？

题目数据非常大，一开始毫无头绪，上了个厕所回来，可不可以hash乱搞？

于是写了两个小时，写得要吐血都不知道在写什么。。。

下午冷静想了一下，我用的hash是这样的：

$Hash(S) = \sum_{i = 0}^{|S|-1} a[i]*P^{|S|-i}$

这个$van$意，要是字符串编号变了就非常的鬼畜

换个$Hash$算法？

考虑把字符串固定在一个轴上，轴上每个点都有一个值，$hash$就求个前缀和，岂不是很爽？

轴上点的值恰可以用$p^i$形式

对于当前$hash$串，如果往后加一个字符？不影响，新字符直接递推

如果往前加一个字符？就有点鬼畜，如果硬要用标记，怕是更鬼畜

不是要算前缀和吗？往前加一个，算成负数就可以了

不能开$long long$,为了算负数不能模，自然溢出即可

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define ONLINE_JUDGE 1

char buf[1 << 20], *p1, *p2;
#ifndef GC
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
#endif

#ifndef ISDIG
#define ISDIG(CHARACTER) (CHARACTER >= '0' && CHARACTER <= '9')
#endif
inline int _R() {
	int d = 0; char t; bool ty = 1;
	while (t = GC, !ISDIG(t) && t != '-') ;
	t == '-' ? (ty = 0) : (d = t - '0');
	while (t = GC, ISDIG(t)) d = (d << 3) + (d << 1) + t - '0';
	return d;
}

#ifndef ISCHAR
#define ISCHAR(CH) (CH != ' ' && CH != '\n' && CH != '\r')
#endif

inline int _S(char *c) {
	char *t = c, ch;
	while (ch = GC, !ISCHAR(ch)) ;
	*t ++ = ch;
	while (ch = GC, ISCHAR(ch)) *t ++ = ch;
	*t = 0;
	return t - c;
}

char str[1 << 25];

#ifndef MAXN
#define MAXN 20000003
#endif

#ifndef u32
#define u32 unsigned int
#endif

#ifndef ll
#define ll long long
#endif

#ifndef MUL
#define MUL 131
#endif

#ifndef MOD
#define MOD 1000000007
#endif

int n;
int a[MAXN], ans[MAXN], s[MAXN], now, head, tail;
u32 pow1[MAXN], pow2[MAXN], pre[MAXN], suf[MAXN], pre_lazy, suf_lazy;

bool Check(int l, int r) {
	// u32 h1 = (pre[r] - pre[l - 1] + MOD) % MOD, h2 = (suf[l] - suf[r + 1] + MOD) % MOD;
	u32 h1 = pre[r] - pre[l - 1], h2 = suf[l] - suf[r + 1];
	int l1 = l, l2 = n - r + 1;
	// if (l1 < l2) h1 = h1 * pow1[l2 - l1] % MOD;
	// else h2 = h2 * pow1[l1 - l2] % MOD;
	if (l1 < l2) h1 *= pow1[l2 - l1];
	else h2 *= pow1[l1 - l2];
	return h1 == h2;
}
void WORK(int opt, u32 num) {
	if (opt != 3) s[++ now] = opt;

	if (opt == 1) {
		++ tail;
		a[tail] = num;
		// pre[tail] = (pre[tail - 1] + num * pow1[tail] % MOD) % MOD;
		pre[tail] = pre[tail - 1] + num * pow1[tail];
		suf[tail] = -suf_lazy;
		suf_lazy += num * pow2[tail];
		// suf_lazy = (suf_lazy + num * pow2[tail] % MOD) % MOD;
		suf[tail + 1] = -suf_lazy;

		ans[now] = ans[now - 1];
		if (tail - ans[now] - 1 >= head && Check(tail - ans[now] - 1, tail)) 
			ans[now] += 2;
		else if (tail - ans[now] >= head && Check(tail - ans[now], tail)) 
			ans[now] ++;
	}
	else if (opt == 2) {
		-- head;
		a[head] = num;
		// suf[head] = (suf[head + 1] + num * pow2[head] % MOD) % MOD;
		suf[head] = suf[head + 1] + num * pow2[head];
		pre[head] = -pre_lazy;
		pre_lazy += num * pow1[head];
		// pre_lazy = (pre_lazy + num * pow1[head] % MOD) % MOD;
		pre[head - 1] = -pre_lazy;

		ans[now] = ans[now - 1];
		if (head + ans[now] + 1 <= tail && Check(head, head + ans[now] + 1)) 
			ans[now] += 2;
		else if (head + ans[now] <= tail && Check(head, head + ans[now])) 
			ans[now] ++;
	}
	else {
		for (int i = 1; i <= num; i ++, now --) {
			if (s[now] == 1) {
				pre[tail] = 0;
				// suf_lazy = (suf_lazy - a[tail] * pow2[tail] % MOD + MOD) % MOD;
				suf_lazy -= a[tail] * pow2[tail];
				tail --;
			}
			else {
				suf[head] = 0;
				// pre_lazy = (pre_lazy - a[head] * pow1[head] % MOD + MOD) % MOD;
				pre_lazy -= a[head] * pow1[head];
				head ++;
			}
			pre[head - 1] = -pre_lazy;
			suf[tail + 1] = -suf_lazy;
		}
	}
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("tower.in", "r", stdin);
#endif

	int i, j, k, opt, num;
	ll tot = 0;
	n = _R();
	_S(str);
	// scanf("%d%s", &n, str);

	pow1[0] = 1;
	for (i = 1; i <= n * 2; i ++) pow1[i] = pow1[i - 1] * MUL; //% MOD;
	pow2[n + 1] = 1;
	for (i = n; i >= 1; i --) pow2[i] = pow2[i + 1] * MUL;// % MOD;

	// head = n + 1, tail = n;
	head = 1;
	for (char *it = str; *it; it += 3) head += (*it) == '2';
	tail = head - 1;

	/*
	1 -- tail
	2 -- head
	3 -- undo
	*/

	for (char *it = str; *it; it ++) {
		opt = (*it) - '0'; it ++;
		num = (*it) - '0'; it ++;
		num = (num << 3) + (num << 1) + (*it) - '0';
		num = (num + ans[now]) % 100;
		if (opt != 3) num ++;
		WORK(opt, num);
		tot += ans[now];
		// printf("%d %d %d\n", opt, ans[now], num);
	}
	printf("%lld\n", tot);
}