「NOI2017」题目整理

开一个大坑,决定作死做一下去年的 $6$ 道神仙题,顺便学习一波新的东西,像我这样面向题目学习算法怕是也没谁了。。。

整数

0x00 题意

维护一个长度为 $3\times 10^7$ 级别的二进制数,支持加/减一个 $a\times 2^b$ 的数,查询第 $k$ 位的值,操作数 $n$ 为 $10^6$ 级别

0x01 我会暴力!

考虑这么一个事情,如果只有加法操作,那么位置 $k$ 间接改变的次数是位置 $k - 1$ 改变次数的一半,证明显然,二进制进位嘛。
考虑到每次增加的数 $a\times 2 ^ b$ 最多直接影响 $log_2(MAXINT) = 32$ 个位置,所以,这部分的复杂度是 $O(32n)$
结合上面被间接修改的数,是
$$
f(n)=f(n/2) + O(n) = O(n)
$$
所以,先忽略 $32$ 的常数不管,暴力进位的复杂度仅为 $O(n)$!

0x02 我会$a = 1$的部分分

由于有了减法操作,以上的分析不管用了。。。
比如一个数 $100\cdots00$,减一就变成了 $011\cdots11$,相当于修改了 $n$ 个位置,然后再加一,就又变成了 $100\cdots00$,又修改了 $n$ 个位置,这样单次操作复杂度就炸成 $O(n)$ 了,而且均摊分析在这里也失效了。

我们需要用到数据结构保证每次操作的复杂度是严格的!

观察以下可以发现

  • 对于 $+1(s)$ 操作,其实就是找到从这个位置开始的连续的一段 $1$,改成 $0$,然后再把第一个不是 $1$ 的数改成 $1$。
  • 对于 $-1(s)$ 操作,其实就是找到从这个位置开始的连续的一段 $0$,改成 $1$,然后再把第一个不是 $0$ 的数改成 $0$。

结束,线段树维护区间复制标记,单点修改,单点查询。

然后。。。你将得到 $24$ 分的好成绩,$QwQ$

0x03 我会拆修改!

将算法二稍稍修改一下,如果 $a != 1$,就把 $a$ 二进制拆分成等于 $1$ 的情况处理,复杂度提升一个 $log$,加上线段树自带的一个 $log$,你将得到一个复杂度为 $O(nlog^2n)$ 的优秀做法,不过对于 $n = 10^6$。。。$O(wys)$

0x04 我会高级的暴力!

发现算法$3$再加一个二进制压位可以去掉那一个$log$,但是好难写啊,我不会写怎么办呐。。。
继续考虑暴力算法
现在已经确定,暴力算法对于只有加法的情况是成立的

如何把减法去掉?

再开一个数组记录减了多少不就行了!
维护两个数组 $Inc$ 和 $Dec$ 分别表示在加法和减法上贡献,暴力加就可以了,这一部分的复杂度仅为 $O(n)$,外加 $32$ 的常数

现在,有了两个整数 $Inc$ 和 $Dec$, 我们如何确定整数 $Inc - Dec$ 在二进制表示下第 $k$ 位是什么呢?
显然,进位是不用考虑的,因为高于第 $k$ 位的值是什么对于答案没有任何影响。

考虑没有低位借位的情况。

$0 - 0 = 0~mod~2$
$0 - 1 = 1~mod~2$
$1 - 0 = 1~mod~2$
$1 - 1 = 0~mod~2$

异或?

然后如果有借位。。。再减一个 1 ?

同或?

解决了!只用判断第 $k - 1$ 个位置要不要向前借位即可。
显然如果要借位,那么在 $Inc[0,~k-1]$ 的字典序肯定小于 $Dec[0,~k-1]$。
然后比较两个字符串的字典序是可以用后缀数组O(1)查询的。。。。。。

全完了。。。不会了。。。

线段树?考虑这么一个问题,如果我们知道了区间 $[l,~mid]$ 和区间 $[mid+1,r]$ 的字典序大小关系,是可以合并出区间 $[l,r]$ 的字典序大小关系的,这也就是后缀数组的倍增思想,所以维护这么一个奇怪的字典序大小关系,就可以完美解决借位问题辣!

然后复杂度。。。$O(32nlogn)$。。。不就是$O(nlog^2n)$ 么,实测可以 $AC$,需要一点点卡常数的技巧。
但是代码短啊!

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
#include <bits/stdc++.h>
using namespace std;

inline int read(int u = 0, char c = getchar(), bool f = false) {
for (;!isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) u = u * 10 + c - '0';
return f ? -u : u;
}

const int maxn = 4e7 + 100;
int n, m;
bool Inc[maxn], Dec[maxn];
struct {
bool fst, snd;
} T[maxn << 1];

inline void upd(register int p) {
T[p + m].fst = Inc[p] & !Dec[p];
T[p + m].snd = !Inc[p] & Dec[p];
register int q;
for (p = p + m >> 1, q = p << 1 | 1; p; q = p | 1, p >>= 1) {
T[p].fst = T[q].fst | (!T[q].snd & T[q ^ 1].fst);
T[p].snd = T[q].snd | (!T[q].fst & T[q ^ 1].snd);
}
}

inline bool qry(register int p) {
for (p = p + m + 1; p; p >>= 1) if (p & 1) {
if (T[p ^ 1].fst) return true;
if (T[p ^ 1].snd) return false;
} return true;
}

inline void pls(register int a, register int b) {
for (; a; a >>= 1, b++) if (a & 1)
a += Inc[b], Inc[b] ^= 1, upd(b);

}

inline void sub(register int a, register int b) {
for (; a; a >>= 1, b++) if (a & 1)
a += Dec[b], Dec[b] ^= 1, upd(b);
}

inline bool ask(register int p) {
return qry(p - 1) ? Inc[p] ^ Dec[p] : Inc[p] == Dec[p];
}

int main() {
n = read(); for (m = 1; m < n * 30; m <<= 1);
register int a, b, o; read(); read(); read();
for (register int i = 1; i <= n; i++) {
o = read();
if (o == 1) {
a = read(); b = read();
if (a > 0) pls(a, b);
if (a < 0) sub(-a, b);
} else puts(ask(read()) ? "1" : "0");
}
}

0x05 我会正解

还不会。。。挖坑待填

蚯蚓排队

0x00 题意

现在有一些制胡,你可以把它两个制胡窜连起来,你也可以把一个制胡窜分成两个,询问这些制胡窜中包含了多少个串 $T$。

0x01 我会暴力HASH

考虑到 $|T| \leq 50$,我们直接每一个节点下面挂上一个长度为 $50$ 的数组,存以这个位置开头,长度为 $i$ 的制胡窜的 $hash$ 值,所以每次就可以暴力合并两个制胡窜,暴力拆分两个制胡窜,单次修改复杂度是 $O(k^2)$ 的,将这些 $HASH$ 值存起来,用一个$cnt$数组表示 $HASH$ 值为这个的串有多少个,这样,知道了串 $T$ 的 $HASH$ 值,我们就可以 $O(1)$ 统计答案了,期望得分未知,部分分表太难看了

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
#include <bits/stdc++.h>
using namespace std;

template <typename Type>
inline Type read(Type u = 0, char c = getchar(), bool f = false) {
for (;!isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
return f ? -u : u;
}

typedef unsigned long long ull;
typedef long long ll;
const int maxn = 2e5 + 10;
const int maxk = 50 + 1;
const int maxm = 3e5 + 10;

const ull P = 1000007;
const ull B = 17;
ull str[maxn][maxk], Pow[maxk];
int cnt[P][maxk];

struct { int Len, Last, Next; } q[maxn];

void Link(register int x, register int y) {
q[y].Last = x; q[x].Next = y;
while (x) {
if (q[x].Len >= maxk - 1) return;
for (register int i = min(maxk - 1, q[y].Len + 1); i > q[x].Len; i--)
++cnt[str[x][i] = (str[y][i - 1] * B + str[x][1]) % P][i];
q[x].Len = q[y].Len + 1; y = x; x = q[x].Last;
}
}

void Cut(register int x) {
register int tmp = 1;
q[q[x].Next].Last = 0; q[x].Next = 0;
while (x) {
if (tmp >= maxk - 1) return;
for (register int i = q[x].Len; i > tmp; i--) --cnt[str[x][i]][i];
q[x].Len = ++tmp; x = q[x].Last;
}
}

char s[int(1e7+10)];
const int Mod = 998244353;
ll Ask(register int k) {
int n = strlen(s); reverse(s, s + n); ll ans = 1; ull Hash = 0;
for (int i = 0; i < n; i++) {
if (i >= k) Hash = Hash + P - Pow[k - 1] * (s[i - k] - '0') % P;
Hash = Hash * B + s[i] - '0';
Hash %= P;
if (i + 1 >= k) ans = ans * cnt[Hash][k] % Mod;
} return ans;
}

int main() {
int n = read<int>(), m = read<int>();
Pow[0] = 1; for (register int i = 1; i <= 50; i++) Pow[i] = Pow[i - 1] * B % P;
for (register int i = 1; i <= n; i++) str[i][1] = read<int>(), q[i].Len = 1, cnt[str[i][1]][1]++;
while (m--) {
register int o = read<int>(), x, y;
if (o == 1) x = read<int>(), y = read<int>(), Link(x, y);
else if (o == 2) x = read<int>(), Cut(x);
else scanf("%s", s), printf("%lld\n", Ask(read<int>()));
}
}

实测可以拿到 $32$ 分的好成绩。。。目前的问题便是这样直接按照$hash$值统计太不靠谱了,估计有 $O(nk)$ 级别的$hash$值,想要不冲突,模数得取到 $O(n^2k^2)$ 的级别,空间肯定开不下,然后上面的代码似乎还有别的问题。。。

0x02 我会正确的HASH!

从之前的代码不难看出,每次最多需要重新计算 $O(k^2)$ 个 $hash$ 值,有 $m(3\times 10^5)$ 个操作,所以复杂度是 $O(k^2m)$ 的。。。

等等。。。

复杂度真的有这么高么?
我们来从另一个角度来看这个问题

  • 对于 link 操作
    假定只有拼接操作,我们可以发现,最终算得的 $hash$ 值只有 $O(nk)$ 个,因为每一个节点下面挂 $k$ 个 $hash$ 值,一共 $n$ 个节点。
    对于每一个节点,我们记一个 $Len$ 值,表示从这个节点开始的 $hash$ 值存了多少个,在只有拼接操作的前提下,$Len$ 单调不减,这样就不会有任何一个 $hash$ 值需要被计算两次,所以复杂度 $O(nk)$。
  • 对于 cut 操作
    分割操作会破坏以上 $O(nk)$ 的性质,但是题目里面还有一个隐含条件,分割操作的次数 $c$ 不超过 $3\times 10^3$,这就好办啦,显然一个分割操作可以由一个拼接操作抵消,所以相当于这一步什么都不干,那么复杂度呢?最坏情况显然是 $O(k^2)$ 的吧,不过不要紧,$O(k^2c+nk)$ 的复杂度是可以承受的。

至此,我们已经证明了暴力求解 $hash$ 值的复杂度,但还有一个重要的地方需要去改进。。。

0x03 我会hash表

看来还是要掌握正确的 $hash$ 姿势啊,$hash$ 值有多大,我就开了多大的数组,然后发现不是 MLE,就是 hash冲突,现在才掌握了一种名叫挂链的东西。。。
具体来说,就是先搞一个很大的 $hash$ 值,保证基本不会冲突的那一种,然后再把这些 $hash$ 值对一个数取模,变成值域较小但可能冲突的 $hash$ 值,然后再采取挂链的方法,冲突了就在下面挂一条链,建议模数取19260817

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 <bits/stdc++.h>
using namespace std;

inline int read(int u = 0, char c = getchar(), bool f = false) {
for (;!isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
return f ? -u : u;
}

typedef unsigned long long ull;

const int maxn = 2e5 + 10;
const int maxk = 50;


namespace HashTable {
const int mod = 1926817;
struct { int cnt, nxt; ull val; int len; } data[int(2e7)];
int head[mod], dataCnt = 0;
void insert(register ull val, int len) {
for (register int i = head[val % mod]; i; i = data[i].nxt)
if (val == data[i].val && len == data[i].len) return void(data[i].cnt++);
int u = val % mod;
data[++dataCnt] = { 1, head[u], val, len }; head[u] = dataCnt;
}
void erase(register ull val, int len) {
for (register int i = head[val % mod]; i; i = data[i].nxt)
if (val == data[i].val && len == data[i].len) return void(data[i].cnt--);
cerr << "ERROR!" << endl; while (1);
}
int count(register ull val, int len) {
for (register int i = head[val % mod]; i; i = data[i].nxt)
if (val == data[i].val && len == data[i].len) return data[i].cnt;
return 0;
}
}


const ull P = 998244353;
const ull B = 17;
ull str[maxn][maxk + 1], Pow[maxk + 1];

struct { int Len, Last, Next; } q[maxn];

void Link(register int x, register int y) {
//cerr << "link" << endl;
q[x].Next = y; q[y].Last = x;
//assert(q[x].Len == 1);
while (x) {
if (q[x].Len == maxk) return;
for (int i = min(maxk, q[y].Len + 1); i > q[x].Len; i--)
HashTable::insert(str[x][i] = str[y][i - 1] * B + str[x][1], i);
q[x].Len = min(q[y].Len + 1, maxk);
y = x; x = q[x].Last;
}
}

void Cut(register int x) {
//cerr << "cut" << endl;
q[q[x].Next].Last = 0; q[x].Next = 0; register int Len = 1;
while (x) {
//cerr << q[x].Len << endl;
for (int i = Len + 1; i <= q[x].Len; i++) {
//cerr << str[x][i] << endl;
HashTable::erase(str[x][i], i);
}
q[x].Len = Len++;
if (Len >= maxk) break;
x = q[x].Last;
}
}

char s[int(2e7)];

int Ask(register int k) {
//cerr << "ask" << endl;
int n = strlen(s); reverse(s, s + n); ull ans = 1, Hash = 0;
for (register int i = 0; i < n; i++) {
Hash = Hash * B + s[i] - '0';
if (i >= k) Hash -= (s[i - k] - '0') * Pow[k];
if (i >= k - 1) ans = ans * HashTable::count(Hash, k) % P;
} return ans;
}

int main() {
//freopen("ex_queue3.in", "r", stdin);
//freopen("ex_queue3.out", "w", stdout);
Pow[0] = 1; for (register int i = 1; i <= maxk; i++) Pow[i] = Pow[i - 1] * B;
register int n = read(), m = read(), o, x, y;
for (register int i = 1; i <= n; i++) HashTable::insert(str[i][1] = read(), q[i].Len = 1);
while (m--) {
//cerr << "ok" << m << endl;
o = read();
if (o == 1) x = read(), y = read(), Link(x, y);
else if (o == 2) x = read(), Cut(x);
else scanf("%s", s), printf("%d\n", Ask(read()));
}
}