A - qh与复读机I

A、每次按顺序给出$ n $个字符串，求出每个字符串是前面多少个字符串的前缀和后缀

tire树
因为题面给定数据范围$\sum |S_i| < 1e6$，也就是说如果建一棵树的话结点数是不会超过这么多的，而且遍历的时候也是，那么考虑正序和逆序建树，每次建树的同时到达最后一个结点返回当前结点已经记录的单词数量，也就分别对应了前缀和后缀
时间复杂度$O(n)$

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
#define maxn 1000007

struct Node{
	int child[26];
	int sum;

	void init(){
		for(int i = 0;i < 26;i++) child[i] = 0;
		sum = 0;
	}
}Tree[2][maxn];

int cnt1 = 0,cnt2 = 0;

int insert(bool statu,const string& s){
	int len = s.length();
	int now = 0;
	for(int i = 0;i < len;i++){
		int pos = s[i] - 'a';
		if(Tree[statu][now].child[pos] == 0){
			int nxt = (statu ? ++cnt2 : ++cnt1);
			Tree[statu][now].child[pos] = nxt;
			Tree[statu][nxt].init();
		}
		now = Tree[statu][now].child[pos];
		Tree[statu][now].sum ++;
	}
	return Tree[statu][now].sum - 1;
}

int main(){
	int n;
	string s;
	cin>>n;
	for(int i = 1;i <= n;i++){
		cin>>s;
		cout<<insert(0,s)<<" ";
		reverse(s.begin(),s.end());
		cout<<insert(1,s)<<endl;
	}
	return 0;
}
B - qh与复读机II

B、给定一个字符串$ S $，求出这个字符串的所有循环节大小

KMP fail数组
有一个结论是字符串的$ border $的 $border$还是这个字符串的$border$，那么用KMP算法求出fail数组后，对应的就是$border$，那么就依次求出$fail[n]、fail[fail[n]]…..$然后用原串长度减去就可以了
直接把以前写的KMP算法拿过来了（逃
时间复杂度$O(n)$

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
char s[1000007]; 
int nxt[1000007];
vector<int> ans;

void KMP(char *s){
    nxt[0] = 0;
    nxt[1] = 0;
    int j;
    int len = strlen(s);
    for(int i = 1;i<len;i++){
        j = nxt[i];
        while(s[i]!=s[j]&&j) j = nxt[j];
        nxt[i+1] = s[i]==s[j]?j+1:0; 
    }
}


int main(){
    cin>>s;
    KMP(s);
    int len = strlen(s);
    int x = nxt[len];
    while(x){
        ans.push_back(len - x);
        x = nxt[x];
    }
    ans.push_back(len);
    for(int i = 0;i < ans.size();i++) cout<<ans[i]<<" ";
    cout<<endl;
    return 0;
}
C - qh与复读机III

C、给出字符串$ S $和$ T $，求出$ T $在$ S $中出现的每一个位置

KMP
KMP板题，求出匹配位置即可，时间复杂度$O(n)$

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
char s1[1000007],s2[1000007]; 
int nxt[1000007];

void KMP(char *s){
    nxt[0] = 0;
    nxt[1] = 0;
    int j;
    int len = strlen(s);
    for(int i = 1;i<len;i++)
    {
        j = nxt[i];
        while(s[i]!=s[j]&&j) j = nxt[j];
        nxt[i+1] = s[i]==s[j]?j+1:0; 
    }
}

void solve(){
    int n = strlen(s1),m = strlen(s2);
    int j=0;
    for(int i = 0;i<n;i++)
    { 
        while(s1[i]!=s2[j]&&j) j = nxt[j];
        if(s1[i]==s2[j]) j++;
        if(j==m){cout<<i-j+2<<" ";}
    }
}

int main(){
    cin>>s1>>s2;
    KMP(s2);
    solve();
    return 0;
}
D - qh与复读机IV

D、给出一堆模式串$T_i$，求出每个模式串在待匹配串里面的出现次数

AC自动机
AC自动机的板题，把模式串放到AC自动机里面然后用匹配串放进去匹配求出次数输出即可，这个题没有加强数据，所以平常的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
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
int n;
char s1[1000007],s2[1000007];
int ans[100007];
int tid[100007];

struct acnode{
    acnode *child[26];
    int id;
    acnode *fail;

};

void init(acnode *root){
    for(int i = 0;i<26;i++) root->child[i] = NULL;
    root->id = 0;
    root->fail = NULL;
}

void insert(acnode *root,char *s,int id){
    int len = strlen(s);
    acnode *t = root;
    for(int i = 0;i<len;i++){
        int pos = s[i] - 'a';
        if(t->child[pos] == NULL){
            acnode *newnode = new acnode;
            init(newnode);
            t->child[pos] = newnode;
        }
        t = t->child[pos];
    }
    if(t -> id != 0) tid[id] = t -> id;
    else t -> id = id,tid[id] = t -> id;

}

void getfail(acnode *root){
    queue<acnode*> q;
    q.push(root);
    while(!q.empty()){
        acnode *now = q.front();
        q.pop();
        for(int i = 0;i<26;i++){
            if(now->child[i] != NULL){
                acnode *p;
                if(now == root){
                    now->child[i]->fail = root;
                }
                else{
                    p = now->fail;
                    while(p != NULL){
                        if(p->child[i] != NULL){
                            now->child[i]->fail = p->child[i];
                            break;
                        }
                        p = p->fail;
                    }
                    if(p == NULL) now->child[i]->fail = root;
                }
                q.push(now->child[i]);
            }
        }
    }
}

void query(acnode *root,char *s){
    acnode *p = root;
    int len = strlen(s);
    for(int i = 0;i<len;i++){
        int pos = s[i] - 'a';
        while(p->child[pos] == NULL && p!= root) p = p->fail;
        p = p->child[pos];
        if(!p) p = root;
        acnode *now = p;
        while(now != root){
            if(now->id > 0)
                ans[now->id] ++;
            now = now->fail;
        }
    }
}
acnode *root;

int main(){
	cin>>s2;
    cin>>n;
    root = new acnode;
    init(root);
    for(int i = 1;i<=n;i++){
        cin>>s1;
        insert(root,s1,i);
    }
    getfail(root);
    query(root,s2);
    for(int i = 1;i <= n;i++){
    	cout<<ans[tid[i]]<<endl;
    }
    return 0;
}
E - qh与复读机V

E、和上一个题一样，但是有数据加强

AC自动机 last优化
这个题我改成了用数组写，因为指针写优化容易出现空指针的问题，所以改成用数组写要稳妥一点。。。加一个last优化直接跳到对应的位置避免了重复跳位置的效率低下

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
int n,cnt = 0;
char s1[1000007],s2[1000007];
int ans[100007];
int tid[100007];
int last[1000007];

struct acnode{
    int child[26];
    int id;
    int fail;
    
    void init(){
        for(int i = 0;i < 26;i++) child[i] = 0;
        fail = 0;
        id = 0;
    }
}Node[1000007];

void insert(char *s,int id){
    int len = strlen(s);
    int now = 0;
    for(int i = 0;i < len;i++){
        if(Node[now].child[s[i] - 'a'] == 0){
            Node[now].child[s[i] - 'a'] = ++cnt;
            Node[cnt].init();
        }
        now = Node[now].child[s[i] - 'a'];
    }
    if(Node[now].id == 0) Node[now].id = id,tid[id] = id;
    else tid[id] = Node[now].id;
}

void getfail(){
    queue<int> q;
    for(int i = 0;i < 26;i++){
        if(Node[0].child[i] != 0){
            Node[Node[0].child[i]].fail = 0;
            q.push(Node[0].child[i]);
        }
    }
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i = 0;i < 26;i++){
            if(Node[now].child[i] != 0){
                int nxt = Node[now].child[i];
                Node[Node[now].child[i]].fail = Node[Node[now].fail].child[i];
                q.push(Node[now].child[i]);
                last[nxt] = Node[Node[nxt].fail].id ? Node[nxt].fail : last[Node[nxt].fail]; 
            }
            else Node[now].child[i] = Node[Node[now].fail].child[i];
        }
    }
}

void query(char *s){
    int len = strlen(s);
    int now = 0;
    for(int i = 0;i < len;i++){
        now = Node[now].child[s[i] - 'a'];
        for(int t = now;t;t = last[t]){
            if(Node[t].id > 0){
                ans[Node[t].id] ++;
            }
        }
    }
}

int main(){
    cin>>s2;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>s1;
        insert(s1,i);
    }
    getfail();
    query(s2);
    for(int i = 1;i <= n;i++){
        cout<<ans[tid[i]]<<endl;
    }
    return 0;
}
F - qh与复读机VI

F、给定一个字符串$S$，以及一个字符串$T$，要求求出所有的$S$的子串与$T$的一个前缀拼起来是回文串的情况的总数，而且要求子串长度大于前缀

exkmp manacher
一开始找字符串算法的时候发现了exkmp这个东西，可以求出一个串的所有后缀和另外一个串的最长前缀，然后感觉可以用一下，没有注意读题导致我以为是长度没有关系要找出所有的拼起来的是回文的情况有多少。。
然后我就傻逼的写了一发exkmp求出对应的extend数组就放上去了。。后面一看题目，然后看了一下样例（其实样例给的很明显了，就中间回文然后两边是相同的）
那么就是需要manacher和exkmp，exkmp的时候把原串倒过来，求出每个位置开头的回文串数量和这个位置对应的extend数组然后相乘相加即可

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
string s,t;
ll nxt[1000007],exnxt[1000007];

char s2[2000007];
ll p[2000007],id = 1,mx = 1,ans = -1;

ll pre[2000007];

void KMP()
{
	ll len = t.length(),pos,i = 0,j;
    nxt[0] = len;
    while(t[i] == t[i + 1] && i + 1 < len) i++;
    nxt[1] = i;
    pos = 1;
    for(i = 2;i < len;i++){
    	if(nxt[i - pos] + i < nxt[pos] + pos) nxt[i] = nxt[i - pos];
    	else{
    		j = nxt[pos] + pos - i;
    		if(j < 0) j = 0;
    		while(i + j < len && t[i + j] == t[j]) j++;
    		nxt[i] = j;
    		pos = i;
    	}
    }
}

void exkmp(){
	ll i = 0,j,pos = 0,len1 = s.length(),len2 = t.length();
	while(s[i] == t[i] && i < len1 && i < len2) i++;
	exnxt[0] = i;
	for(i = 1;i < len1;i++){
		if(nxt[i - pos] + i < exnxt[pos] + pos) exnxt[i] = nxt[i - pos];
		else{
			j = exnxt[pos] + pos - i;
			if(j < 0) j = 0;
			while(i + j < len1 && j < len2 && s[j + i] == t[j]) j++;
			exnxt[i] = j;
			pos = i;
		}
	}
}

ll init(){
    s2[0] = '$';
    s2[1] = '#';
    ll j = 2;
    ll len = s.length();
    for(ll i = 0;i<len;i++){
        s2[j++] = s[i];
        s2[j++] = '#';
    }
    s2[j] = '\0';
    return j;
}

void manacher(){
	ll len = init();
	for(ll i = 1;i<len;i++){
        if(i < mx) p[i] = min(p[2 * id - i],mx - i);
        else p[i] = 1;
        while(s2[i - p[i]] == s2[i + p[i]]) p[i] ++;
        if(mx < i + p[i]){
            id = i;
            mx = i + p[i];
        }
    }
}

int main(){
	cin>>s>>t;
	manacher();
	ll len = s.length();
	for(ll i = len * 2;i >= 2;i--){
		ll x = i / 2;
		pre[x]++;
		pre[x - (p[i] / 2)] --;
	}
	for(ll i = len;i >= 1;i--) pre[i] += pre[i + 1];
	reverse(s.begin(),s.end());
	KMP();
	exkmp();
	ll ans = 0;
	for(ll i = 1;i <= len;i++){
		ans += exnxt[len - i + 1] * pre[i] * 1LL;
	}
	cout<<ans<<endl;
    return 0;
}
G - qh与复读机VII

G、给出一个数字串已经一个模数，求出对应数字串的每个不同回文数相加的和在取模后的值的大小

快速幂 回文自动机
果然是个回文自动机的板题。。。每个节点对应了一个回文串，那么每次加到这个节点的时候根据上面位置的回文对应的值算出来这个回文的值再加进答案就好了。。当然要注意的是长度奇数和偶数不同情况要处理一下，取10的高次方的时候用快速幂取模

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
struct Node{
    int child[10];
    int fail,len;
    ll value;

    void init(){
        mst(child,0);
        fail = len = 0;
        value = 0;
    }
}node[maxn];

char s[maxn];

int last,tot = 0;
ll ans = 0,xyy;

ll QuickMod(ll a,ll b){
    ll res = 1,t = a;
    while(b){
        if(b&1) res = (res * t) % xyy;
        t = (t * t) % xyy;
        b >>= 1;
    }
    return res;
}

void insert(int c,int x){
    int p = last;
    while(s[x - node[p].len - 1] != s[x]) p = node[p].fail;
    if(!node[p].child[c]){
        int v = ++tot,k = node[p].fail;
        node[v].len = node[p].len + 2;
        while(s[x - node[k].len - 1] != s[x]) k = node[k].fail;
        node[v].fail = node[k].child[c];
        node[p].child[c] = v;
        if(p == 1){
            node[v].value = c;
            ans = (ans + c) % xyy;
        }
        else{
            ll value = (node[p].value * 10 % xyy + c * QuickMod(10,node[v].len - 1 % xyy) + c) % xyy;
            ans = (ans + value) % xyy;
            node[v].value = value;
        }
    }
    last = node[p].child[c];
}

void init(){
    node[0].init();
    node[1].init();
    node[0].fail = 1;
    node[1].len = -1;
    tot = 1;
    last = 0;
    s[0] = -1;
}

int main(){
    init();
    cin>>s + 1>>xyy;
    int len = strlen(s + 1);
    for(int i = 1;s[i];i++){
        insert(s[i] - '0',i);
    }
    cout<<ans<<endl;
    return 0;
}
H - qh与复读机VIII

H、给出一堆模式串以及对应的权重，要求组出一个字符串让其权重和最大，对应某一个模式串出现一次算一次这个模式串的权重，字符串长度限制为$L$

AC自动机 trie图
将每个模式串以及对应权重放到AC自动机里面，在AC自动机里面跑一遍动态规划求出一个最长的路径，如果动态规划的话，设$f_{i,j}$为长度为i到达AC自动机的第$j$个对应结点的时候得到的最大权重，$S_k$表示的是对应于$k$结点在trie图上的后继集合，转移方程：
$$
f_{i,j} = max \{ f_{i,k} + w_j | j \in S_k \}
$$
我写到中间的时候甚至想把图扒出来跑最长路来着。。。但是写不出来还是弃了
要从根节点开始，然后到不了的结点设置为inf，然后后面的更新状态也差不多，每次拓展的时候要当前到的结点不是inf才能往下更新

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
struct acnode{
    int child[26];
    ll val;
    int fail;
    
    void init(){
        for(int i = 0;i < 26;i++) child[i] = 0;
        fail = 0;
        val = 0;
    }
}Node[1000007];

ll cnt;
ll n,l,w;
char s[600];
ll f[2007][600];

void getfail(){
    queue<int> q;
    for(int i = 0;i < 26;i++){
        if(Node[0].child[i] != 0){
            Node[Node[0].child[i]].fail = 0;
            q.push(Node[0].child[i]);
        }
    }
    while(!q.empty()){
        int now = q.front();
        q.pop();
        if(Node[Node[now].fail].val) Node[now].val += Node[Node[now].fail].val;
        for(int i = 0;i < 26;i++){
            if(Node[now].child[i] != 0){
                int nxt = Node[now].child[i];
                Node[nxt].fail = Node[Node[now].fail].child[i];
                q.push(nxt);
            }
            else Node[now].child[i] = Node[Node[now].fail].child[i];
        }
    }
}

void insert(char *s){
    int len = strlen(s);
    int now = 0;
    for(int i = 0;i < len;i++){
        if(Node[now].child[s[i] - 'a'] == 0){
            Node[now].child[s[i] - 'a'] = ++cnt;
            Node[cnt].init();
        }
        now = Node[now].child[s[i] - 'a'];
    }
    Node[now].val += w;
}

int main(){
    cin>>n;
    for(int i = 1;i <= n;i++) {
        cin>>s>>w;
        insert(s);
    }
    cin>>l;
    getfail();
    mst(f,0);
    for(int i = 0;i <= cnt;i++){
        f[1][i] = f[2][i] = -INF;
    }
    f[1][0] = 0;
    for(int i = 1;i <= l;i++){
        for(int j = 0;j <= cnt;j++){
            if(f[1][j] == -INF) continue;
            for(int k = 0;k < 26;k++){
                int nxt = Node[j].child[k];
                f[2][nxt] = max(f[2][nxt],f[1][j] + Node[nxt].val);
            }
        }
        for(int j = 0;j <= cnt;j++) f[1][j] = f[2][j];
    }
    ll ans = 0;
    for(int i = 0;i <= cnt;i++) ans = max(ans,f[1][i]);
    cout<<ans<<endl;
    return 0;
}
I - qh与复读机IX

I、给出一堆模式串，要求求出长度小于等于$L$并且包含其中任意一个字符串为子串的字符串的总类数量

AC自动机 矩阵乘法 快速幂
和上面的类似，不过这里的话需要把一trie图中能到达的位置放在矩阵里面，将trie图建成一个邻接矩阵，在图论中一个邻接矩阵$A$，那么$A^k$表示的是路径长度为$k$的对应邻接矩阵，但是这里要求的是至少存在一个模式串的，那么反过来考虑，求出所有的不包含的，剩下的就是包含的，就把trie图上不可达的路径在矩阵中表示出来，求出$l$次幂，统计答案之后，$26^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
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
struct acnode{
    int child[26];
    int val;
    int fail;
    
    void init(){
        for(int i = 0;i < 26;i++) child[i] = 0;
        fail = 0;
        val = 0;
    }
}Node[1000007];

struct matrix{
    ll num[250][250];
    ll w,h;

    matrix operator * (const matrix& a) const{
        matrix res;
        mst(res.num,0);
        res.h = h;
        res.w = a.w;
        for(int i = 1;i <= h;i++){
            for(int j = 1;j <= a.w;j++){
                for(int k = 1;k <= w;k++){
                    res.num[i][j] = (res.num[i][j] + num[i][k] * a.num[k][j] % mod) % mod;
                }
            }
        }
        return res;
    }

    void init(ll hh,ll ww){
        h = hh;
        w = ww;
        mst(num,0);
        for(int i = 1;i <= h;i++) num[i][i] = 1;
    }
};

ll n,l,cnt = 0;
char ss[1000];
matrix f,x;
ll ans;

matrix MatrixQuickMod(const matrix& a,ll b){
    matrix t = a,res;
    res.init(a.h,a.w);
    if(b <= 0) return res;
    while(b){
        if(b & 1) res = res * t;
        t = t * t;
        b >>= 1;
    }
    return res;
}

void insert(char *s){
    int len = strlen(s);
    int now = 0;
    for(int i = 0;i < len;i++){
        if(Node[now].child[s[i] - 'a'] == 0){
            Node[now].child[s[i] - 'a'] = ++cnt;
            Node[cnt].init();
        }
        now = Node[now].child[s[i] - 'a'];
    }
    Node[now].val = 1;
}

void getfail(){
    queue<int> q;
    for(int i = 0;i < 26;i++){
        if(Node[0].child[i] != 0){
            Node[Node[0].child[i]].fail = 0;
            q.push(Node[0].child[i]);
        }
    }
    while(!q.empty()){
        int now = q.front();
        q.pop();
        if(Node[Node[now].fail].val == 1) Node[now].val = 1;
        for(int i = 0;i < 26;i++){
            if(Node[now].child[i] != 0){
                int nxt = Node[now].child[i];
                Node[Node[now].child[i]].fail = Node[Node[now].fail].child[i];
                q.push(Node[now].child[i]);
            }
            else Node[now].child[i] = Node[Node[now].fail].child[i];
        }
    }
}

int main(){
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>ss;
        insert(ss);
    }
    cin>>l;
    getfail();
    cnt++;
    f.w = f.h = cnt + 1;
    for(int i = 0;i < cnt;i++){
        for(int j = 0;j < 26;j++){
            if(Node[Node[i].child[j]].val == 0) f.num[i + 1][Node[i].child[j] + 1]++; 
        }
    }
    for(int i = 0;i <= cnt;i++) f.num[i + 1][cnt + 1] = 1;
    f = MatrixQuickMod(f,l);
    ans = 0;
    for(int i = 1;i <= cnt + 1;i++) ans = (ans + f.num[1][i]) % mod;
    f.num[1][1] = 26;
    f.num[2][1] = 0;
    f.num[1][2] = 1;
    f.num[2][2] = 1;
    f.w = f.h = 2;
    f = MatrixQuickMod(f,l + 1);
    ans = f.num[1][2] - ans;
    ans = (ans + mod) % mod;
    cout<<ans<<endl;
    return 0;
}
J - qh与复读机X

J、给出一堆模式串，求出每个模式串在所有的模式串中出现的次数

AC自动机 SAM
本来一开始我的想法是每个模式串中间用#号隔开然后拼接，跑一遍AC自动机，结果交上去是TLE。。。（下来之后cjj说我的string+string的那个位置复杂度可能有点大）
然后我换成了SAM，直接求出对应的right集合的大小统计一下。。然后就是答案了。。
然后复杂度的话。。。自动机的复杂度我算不来（逃
后缀自动机txdy!

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
char s1[maxn],s2[maxn];
int len2 = 0;
int len[maxn],ans[maxn],sum[maxn],tmp[maxn],ccnt[maxn];
int n;

int last = 1,cnt = 1;
int ch[maxn][27],fa[maxn<<1],l[maxn<<1];
void insert(int c){
    int p=last,np=++cnt;
    last=np,l[np]=l[p]+1;
    ccnt[np] = 1;
    for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else{
        int q=ch[p][c];
        if(l[q]==l[p]+1) fa[np]=q;
        else{
            int nq=++cnt;l[nq]=l[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q];fa[q]=fa[np]=nq;
            for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }

    }
}

void cal(){
    for(int i = 1;i <= cnt;i++) sum[l[i]]++;
    for(int i = 1;i <= cnt;i++) sum[i] += sum[i - 1];
    for(int i = 1;i <= cnt;i++) tmp[sum[l[i]]--] = i;
    for(int i = cnt;i;i--) ccnt[fa[tmp[i]]] += ccnt[tmp[i]];
}

int main(){
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>s1;
        len[i] = strlen(s1);
        for(int j  = 0;j < len[i];j++) insert(s2[++len2] = s1[j] - 'a');
        insert(s2[++len2] = 26);
    }
    cal();
    len2 = 0;
    for(int i = 1;i <= n;i++){
        int x = 1;
        for(int j = 0;j < len[i];j++)  x = ch[x][s2[++len2]];
        ans[i] = ccnt[x];
        ++len2;
    }
    for(int i = 1;i <= n;i++) cout<<ans[i]<<endl;
	return 0;
}
K - qh与复读机XI

K、给出一个字符串$S$，要求输出长度为$1到|S|$的出现次数最多的子串的数量

SAM 基数排序``right集合 Parent树
SAM的每个节点都对应了一类的子串，那么统计每个right集合的大小，right的集合大小按照parent树往上加，然后根据maxlen数组依次求出对应长度子串的大小最后输出答案即可

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
char s1[2000007];
int len = 0,ans[2000007],sum[2000007],f[2000007];
int id[2000007];

int last = 1,cnt = 1;
int ch[maxn][26],fa[maxn<<1],l[maxn<<1];
void insert(int c){
    int p=last,np=++cnt;
    last=np,l[np]=l[p]+1;
    for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else{
        int q=ch[p][c];
        if(l[q]==l[p]+1) fa[np]=q;
        else{
            int nq=++cnt;l[nq]=l[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q];fa[q]=fa[np]=nq;
            for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }

    }
    f[np]++;
}

void build(int n){
    for(int i = 1;i <= n;i++) insert(s1[i] - 'a');
}

int main(){
    cin>>s1 + 1;
    len = strlen(s1 + 1);
    build(len);
    for(int i = 1;i <= cnt;i++) sum[l[i]]++;
    for(int i = 1;i <= len;i++) sum[i] += sum[i - 1];
    for(int i = 1;i <= cnt;i++) id[sum[l[i]]--] = i;
    for(int i = cnt;i;i--) f[fa[id[i]]] += f[id[i]];
    for(int i = 1;i <= cnt;i++) ans[l[i]] = max(ans[l[i]],f[i]);
    for(int i = len;i;i--) ans[i] = max(ans[i + 1],ans[i]);
    for(int i = 1;i <= len;i++) cout<<ans[i]<<" "; 
    return 0;
}
L - qh与复读机XII

L、给出一个字符串$ S $，然后给出$ q $个询问，每个询问对应输出$S[l_1,r_1]$在$S[l_2,r_2]$中的出现次数

后缀自动机 线段树合并 倍增 right集合 Parent树
什么好(po)题想了我三天时间
后缀自动机的构造过程我其实是比较懵的×
但是了解后缀自动机的性质的话这个题实际上就是一个数据结构题了。。。
首先要考虑的是找到$S[l_1,r_1]$在后缀自动机上对应的结点的位置，如果暴力的话就是$O(n^2)$了。。
然后去康了康倍增算法，先把$S[1,i]$能到达的结点位置预处理出来，实际上就是标记一下last的位置。。
然后$O(nlogn)$倍增找到$S[l_1,r_1]$的位置，那么剩下的事情就是要查询这个结点位置对应的$right集合$
$right$集合是需要从$parent$树自底向上合并集合得到，集合的合并？
用set的insert暴力搞？复杂度太大，启发式合并也救不了。。。。
那么用pb_ds的红黑树join？不行，区间不能相交（事后xyy给我说可以启发式合并一个一个插入是能保证复杂度的
然后我找到了一个神奇的东西——线段树合并
线段树合并的时候，如果某个子节点是空的，那么就不需要合并下去了，这里用启发式合并的话保证了合并的复杂度是$O(nlog^2n)$
于是就可以做这个题了
最开始每个集合对应了一个$endpos$，那么先把它对应在线段树上的位置$+1$，那么查询在某个区间的子串出现次数的时候就只需要查询区间和即可，也就是用线段树维护一个区间和
令$len = r_1 - l_1 + 1$,每次查询的区间就是$[ l_2 + len - 1, r_2]$，返回的区间和就是答案

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
char s1[maxn];
int len = 0;
int last = 1,cnt = 1;

int ch[maxn][26],fa[maxn],l[maxn];
int id[maxn];
int f[maxn][20];

int n,q,l1,r1,l2,r2;
queue<int> Q;

int lchild[maxn<<3],rchild[maxn<<3],rt[maxn<<3],sum[maxn<<3];
int c[maxn],a[maxn],in[maxn];
int tot = 0;

void modify(int &root,int lp,int rp,int x){
    if(!root) root = ++tot;
    if(lp == rp) {
        sum[root] = 1;
        return ;
    }
    int mid = (lp + rp)>>1;
    if(x <= mid) modify(lchild[root],lp,mid,x);
    else modify(rchild[root],mid + 1,rp,x);
    sum[root] = sum[lchild[root]] + sum[rchild[root]];
}

int merge(int x,int y){
    if(!x || !y) return x^y;
    int p = ++tot;
    lchild[p] = merge(lchild[x],lchild[y]);
    rchild[p] = merge(rchild[x],rchild[y]);
    sum[p] = sum[x] + sum[y];
    return p;
}

int query(int root,int lp,int rp,int L,int R){
    if(L <= lp && rp <= R) return sum[root];
    int mid = (lp + rp) >> 1;
    if(R <= mid) return query(lchild[root],lp,mid,L,R);
    else if(L > mid) return query(rchild[root],mid + 1,rp,L,R);
    else return (query(lchild[root],lp,mid,L,R) + query(rchild[root],mid + 1,rp,L,R));
}

int insert(int c){
    int p=last,np=++cnt;
    last=np,l[np]=l[p]+1;
    in[np] = 1;
    for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else{
        int q=ch[p][c];
        if(l[q]==l[p]+1) fa[np]=q;
        else{
            int nq=++cnt;l[nq]=l[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q];fa[q]=fa[np]=nq;
            for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }

    }
    return last;
}

void build(int n){
    for(int i = 1;i <= n;i++) id[i] = insert(s1[i] - 'a');
}

int main(){
    cin>>n>>q;
    cin>>s1 + 1;
    build(n);
    for(int i = 1;i <= cnt;i++) c[l[i]]++;
    for(int i = 1;i <= cnt;i++) c[i] += c[i - 1];
    for(int i = 1;i <= cnt;i++) a[c[l[i]]--] = i;
    for(int i = cnt;i;i--){
        int pos = a[i];
        if(in[pos]) modify(rt[pos],1,n,l[pos]);
        rt[fa[pos]] = merge(rt[fa[pos]],rt[pos]);
        f[pos][0] = fa[pos];
    }
    for(int j = 1;j <= 18;j++){
        for(int i = 1;i <= cnt;i++){
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    for(int i = 1;i <= q;i++){
        int ans = 0;
        cin>>l1>>r1>>l2>>r2;
        int len1 = r1 - l1 + 1;
        int pos = id[r1];
        for(int j = 18;j >=0;j--) if(l[f[pos][j]] >= len1) pos = f[pos][j];
        int lp = l2 + len1 - 1,rp = r2;
        if(lp > rp) ans = 0;
        else ans = query(rt[pos],1,n,lp,rp);
        printf("%d\n",ans);
    }
    return 0;
}
M - 一切的开始,世界树的测验

M、给出$ n $个数，可以有$ k $次机会将一个数改成$\sum _{ i = 1} ^ {x} i$，求选出若干个数字可以得到$ s $的方案数

dfs meet in middle
又是您，您出的题可卡死我啰
直接交了个裸的$O(3^n)$然后被制裁了
顺着题解给的板子敲了一下$meet\ in \ middle$，zdynb
先搜索一半把可能的情况存储起来，中间有一点剪枝
然后再搜索后一半满足条件的就加到方案数里面
时间复杂度$O(3^{n/2})$

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
long long a[30];
long long b[30];
ll n,k,s,mid;
ll ans = 0;
map<ll,ll> M[30];

void dfs1(ll sum,ll cur,ll cnt){
	if(cur == mid + 1){
		if(M[cnt][sum] == 0) M[cnt][sum] = 1;
		else M[cnt][sum] ++;
		return ;
	}
	ll tmp = (a[cur] + 1) * a[cur] / 2;
	dfs1(sum,cur + 1,cnt);
	if(a[cur] + sum <= s) dfs1(sum + a[cur],cur + 1,cnt);
	if(cnt < k && tmp + sum <= s) dfs1(sum + tmp,cur + 1,cnt + 1);
}

void dfs2(ll sum,ll cur,ll cnt){
	if(cur == n + 1){
		for(int i = 0;i + cnt <= k;i++){
			if(M[i].count(s - sum)) ans += M[i][s - sum];
		}
		return ;
	}
	ll tmp = (a[cur] + 1) * a[cur] / 2;
	dfs2(sum,cur + 1,cnt);
	if(a[cur] + sum <= s) dfs2(sum + a[cur],cur + 1,cnt);
	if(cnt < k && tmp + sum <= s) dfs2(sum + tmp,cur + 1,cnt + 1);
}

int main(){
	cin>>n>>k>>s;
	for(int i = 1;i <= n;i++) cin>>a[i];
	mid = n >> 1;
    dfs1(0,1,0);
    dfs2(0,mid + 1,0);
	cout<<ans<<endl;
	return 0;
}
N - 第一个征程，噩梦的开始

N、给出一个地图以及限制条件，输出最多能到达的位置数量

BFS
一开始没读懂题。。。然后就都是等到题解下来了才写的。。
其实思路很简单，就是BFS一遍，不过要用deque维护一下优先拓展上下位置，因为花费是0

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
int n,m,x,y;
int xx,yy;

struct node{
	int x,y;
	int l,r;

	node(int posx,int posy,int posl,int posr):x(posx),y(posy),l(posl),r(posr){}
};

int ans = 1;
char mmp[2500][2500];
bool vis[2500][2500];

void bfs(){
	deque<node> Q;
	Q.push_back(node(x,y - 1,xx,yy));
	memset(vis,0,sizeof(vis));
	vis[x][y - 1] = 1;
	while(!Q.empty()){
		node cur = Q.front();
		Q.pop_front();
		if(cur.y + 1 < m && mmp[cur.x][cur.y + 1] != '*' && !vis[cur.x][cur.y + 1] && cur.r != 0){
			vis[cur.x][cur.y + 1] = 1;
			ans++;
			Q.push_back(node(cur.x,cur.y + 1,cur.l,cur.r - 1));
		}
		if(cur.y - 1 >= 0 && mmp[cur.x][cur.y - 1] != '*' && !vis[cur.x][cur.y - 1] && cur.l != 0){
			vis[cur.x][cur.y - 1] = 1;
			ans++;
			Q.push_back(node(cur.x,cur.y - 1,cur.l - 1,cur.r));
		}
		if(cur.x - 1 >= 1 && mmp[cur.x - 1][cur.y] != '*' && !vis[cur.x - 1][cur.y]){
			vis[cur.x - 1][cur.y] = 1;
			ans++;
			Q.push_front(node(cur.x - 1,cur.y,cur.l,cur.r));
		}
		if(cur.x + 1 <= n && mmp[cur.x + 1][cur.y] != '*' && !vis[cur.x + 1][cur.y]){
			vis[cur.x + 1][cur.y] = 1;
			ans++;
			Q.push_front(node(cur.x + 1,cur.y,cur.l,cur.r));
		}
	}
	cout<<ans<<endl;
}

int main(){
	cin>>n>>m>>x>>y>>xx>>yy;
	for(int i = 1;i <= n;i++){
		cin>>mmp[i];
	}
	bfs();
	return 0;
}
O - 第二个征程，拔起剪枝哀伤

O、给定$n$个数，求出一个序列使得这n个数均可以由所得序列中的数作差得到

dfs 迭代加深
用状态压缩将现在能得到的$a_i$表示出来，然后每次搜索如果在某个深度不能得到解，就向下加深。。
主要的就是状态变换的位置容易写错，而且用lower_bound的话可以优化一下时间复杂度

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))

long long n,a[60],ans[60];
int dep = 3;

bool dfs(int cur,long long statu){
	if(cur == dep){
		ans[cur] = a[n];
		for(int k = 1;k <= cur - 1;k++){
			int tmp = a[n] - ans[k];
			int pos = lower_bound(a + 1,a + n + 1,tmp) - a;
			if(a[pos] == tmp){
				statu = statu | (1ll << (pos - 1));
			}
		}
		return statu == (1ll << n) - 1;
	}
	for(int i = 1;i <= cur - 1;i++){
		for(int j = 1;j <= n - 1;j++){
			if(statu & (1ll << (j - 1))) continue;
			int tmp = ans[i] + a[j];
			if(tmp <= ans[cur - 1] || tmp >= a[n]) continue;
			ans[cur] = tmp;
			long long nxt = statu;
			for(int k = 1;k <= cur - 1;k++){
				int ttmp = tmp - ans[k];
				int pos = lower_bound(a + 1,a + n + 1,ttmp) - a;
				if(a[pos] == ttmp){
					nxt = nxt | (1ll << (pos - 1));
				}
			}
			if(dfs(cur + 1,nxt)) return true;
		}
	}
	return false;
}

int main(){
	cin>>n;
	for(int i = 1;i <= n;i++) cin>>a[i];
	sort(a + 1,a + n + 1);
	n = unique(a + 1,a + n + 1) - (a + 1);
	if(n == 1){
		cout<<2<<endl;
		cout<<0<<" "<<a[1]<<endl;
		return 0;
	}
	mst(ans,0);
	while(!dfs(2,0)){
		dep++;
		mst(ans,0);
	}
	cout<<dep<<endl;
	for(int i = 1;i <= dep;i++) cout<<ans[i]<<" ";
	return 0;
}
P - 征程的结束，吉安娜

P、先给出一个01矩阵，0表示不能移动的建筑，1表示能移动的建筑或者水晶，给出水晶坐标位置，以及两个坐标，问从一个坐标到另外一个坐标的最小时间花费

dfs spfa 最短路

先spfa预处理出可能的空白格子（就是1的位置）到某个指定位置的上下左右的时间代价
这里用$dist_{x_1,y_1,x_2,y_2,dir}$表示状态
然后用启发式搜索减小dfs经过重复路径的次数来加快dfs的效率即可

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
#define INF 1e8
#define mst(a,b) memset(a,b,sizeof(a))

struct pos{
	int x,y;

	pos(int xx,int yy):x(xx),y(yy){}
};

int mmp[40][40];
int n,m,q,ans;
int dist[40][40][40][40][5];
int vis[40][40][5];

int dirx[] = {0,1,0,-1};
int diry[] = {1,0,-1,0};
int a,b,c,d,ex,ey;

bool check(int cx,int cy){
	if(cx >= 1 && cx <= n && cy >= 1 && cy <= m && mmp[cx][cy]) return true;
	return false;
}

void spfa(int x,int y,int nowx,int nowy,int dir){
	bool vvis[50][50];
	queue<pos> q;
	q.push(pos(x,y));
	dist[x][y][x][y][dir] = 0;
	mst(vvis,0);
	while(!q.empty()){
		pos now = q.front();
		q.pop();
		vvis[now.x][now.y] = 0;
		for(int i = 0;i < 4;i++){
			int nxtx = now.x + dirx[i],nxty = now.y + diry[i];
			if(check(nxtx,nxty) && (nxtx != nowx || nxty != nowy)){
				if(dist[x][y][nxtx][nxty][dir] > dist[x][y][now.x][now.y][dir] + 1){
					dist[x][y][nxtx][nxty][dir] = dist[x][y][now.x][now.y][dir] + 1;
					if(!vvis[nxtx][nxty]){
						q.push(pos(nxtx,nxty));
						vvis[nxtx][nxty] = 1;
					}
				}
			}
		}
	}
}

void dfs(int kx,int ky,int sx,int sy,int cnt,int k){
	if(cnt >= ans) return ;
	if(sx == ex && sy == ey) {
		ans = cnt;
		return ;
	}
	if(vis[sx][sy][k] <= cnt) return ;
    vis[sx][sy][k] = cnt;
    int used[4] = {0,0,0,0};
    int dir,len;
    for(int i = 0;i < 4;i++)
    {
        len = INF;
        for(int j = 0;j < 4;j ++)
        {
            int x = sx + dirx[j],y = sy + diry[j];
            if(check(x,y) && len > dist[x][y][kx][ky][(j+2)%4] && !used[j])
                len = dist[x][y][kx][ky][(j+2)%4],dir = j;
        }
        if(len != INF)
        {
            int x = x = sx + dirx[dir],y = sy + diry[dir];
            used[dir] = 1;
            dfs(sx,sy,x,y,cnt+dist[x][y][kx][ky][(dir+2)%4]+1,(dir+2)%4);
        }   
    }
}

int main(){
	cin>>n>>m>>q;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cin>>mmp[i][j];
		}
	}
	mst(dist,0x3f);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(!mmp[i][j]) continue;
			for(int k = 0;k < 4;k++){
				int nxtx = i + dirx[k];
				int nxty = j + diry[k];
				if(check(nxtx,nxty)){
					spfa(i,j,nxtx,nxty,k);
				}
			}
		}
	}
	for(int i = 1;i <= q;i++){
		cin>>a>>b>>c>>d>>ex>>ey;
		ans = INF;
		mst(vis,0x3f);
		dfs(a,b,c,d,0,4);
		if(ans == INF) cout<<-1<<endl;
		else cout<<ans<<endl;
	}
}
Q - 猛男24点

Q、两个人对弈，给出牌区的4张牌以及两个人的手牌，先手的获胜策略是到他的时候牌区能凑成24点，而后手的获胜条件是到他的时候牌区不能凑成24点，先手可以进行的操作是将自己的牌换到牌区里面，后手可以进行的操作是将牌区的牌与自己手中的黑牌进行交换。如果先手第一局不换牌，那么游戏会继续，反之游戏结束。

博弈 搜索 枚举
到先手的时候，如果能够凑成24点，那么当前不是第一局或者后手必败的情况下即可获胜
而到后手的时候，只要不能凑成24点，那么就可以获胜了
先枚举24点的情况将其哈希之后可以方便判断
然后每次回溯注意要写在dfs的前后。。。如果放在if后面的情况下可能没法回溯回去就直接返回了（我傻了

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#define eps 1e-6

struct statu{
	int num[4];

	statu(int a,int b,int c,int d){
		num[0] = a;
		num[1] = b;
		num[2] = c;
		num[3] = d;
	}

	bool operator == (const statu &a) const{
		for(int i = 0;i < 4;i++){
			if(num[i] == a.num[i]) continue;
			else return false;
		}
		return true;
	}

	bool operator < (const statu &a) const{
		if(num[0] == a.num[0]){
			if(num[1] == a.num[1]){
				if(num[2] == a.num[2]){
					return num[3] < a.num[3];
				}
				return num[2] < a.num[2];
			}
			return num[1] < a.num[1];
		}
		return num[0] < a.num[0];
	}
};

struct card{
	bool color;
	int num;
};

double a[4];
int nows[4];
card cards[10],card1[10],card2[10];
int T,n,m;
bool used[10];
map<int,int> M;

double cal(double a,double b,int k){
	if(k == 1) return (a + b);
	else if(k == 2) return (a - b);
	else if(k == 3) return (a * b);
	else if(k == 4) return (a / b);
}

bool check(){
	for(int i = 1;i<=4;i++){
		for(int j = 1;j <= 4;j++){
			for(int k = 1;k <= 4;k++){
				double tmp1,tmp2,tmp3;
				tmp1 = cal(a[0],a[1],i);
				tmp2 = cal(tmp1,a[2],j);
				tmp3 = cal(tmp2,a[3],k);
				if(fabs(tmp3 - 24) < eps) return true;
				tmp1 = cal(a[0],a[1],i);
				tmp2 = cal(a[2],a[3],k);
				tmp3 = cal(tmp1,tmp2,j);
				if(fabs(tmp3 - 24) < eps) return true;
				tmp1 = cal(a[1],a[2],j);
				tmp2 = cal(a[0],tmp1,i);
				tmp3 = cal(tmp2,a[3],k);
				if(fabs(tmp3 - 24) < eps) return true;
				tmp1 = cal(a[1],a[2],j);
				tmp2 = cal(tmp1,a[3],k);
				tmp3 = cal(tmp2,a[0],i);
				if(fabs(tmp3 - 24) < eps) return true;
				tmp1 = cal(a[2],a[3],k);
				tmp2 = cal(a[1],tmp1,j);
				tmp3 = cal(a[0],tmp2,i);
				if(fabs(tmp3 - 24) < eps) return true;
			}
		}
	}
	return false;
}

void init(){
	for(double i = 1.0;i <= 10.0;i += 1.0){
		a[0] = i;
		for(double j = 1.0;j <= 10.0;j += 1.0){
			a[1] = j;
			for(double k = 1.0;k <= 10.0;k += 1.0){
				a[2] = k;
				for(double l = 1.0;l <= 10.0;l += 1.0){
					a[3] = l;
					int b[4];
					if(check()){
					    for(int i = 0;i < 4;i++) b[i] = a[i];
					    sort(b,b + 4);
			            int tmp = 0;
				        for(int i = 0;i < 4;i++) tmp = tmp * 11 + b[i];
						if(M[tmp] == 1) continue;
				        M[tmp] = 1;
					}
				}
			}
		}
	}
}

bool find(statu x){
	int b[4];
	int tmp = 0;
	for(int i = 0;i < 4;i++) b[i] = nows[i];
	sort(b,b + 4);
    for(int i = 0;i < 4;i++) tmp = tmp * 11 + b[i];
    if(M[tmp] == 1) return true;
    else return false;
}

bool dfs(bool now,int dep){
	bool nowstatu = find(statu(nows[0],nows[1],nows[2],nows[3]));
	if(now == 0){
		if(nowstatu){
			if(dep != 1 || dfs(!now,dep + 1)) return true;
		}
		for(int i = 1;i <= n;i++){
			if(!used[i]){
				for(int j = 1;j <= 4;j++){
					swap(card1[i],cards[j]);
					nows[j - 1] = cards[j].num;
					used[i] = 1;
					bool flag = dfs(!now,dep + 1);
					used[i] = 0;
					swap(card1[i],cards[j]);
					nows[j - 1] = cards[j].num;
					if(flag == true) return true;
				}
			}
		}
		return false;
	}
	else{
		if(!nowstatu) return false;
		for(int i = 1;i <= m;i++){
			if(card2[i].color == 0){
				for(int j = 1;j <= 4;j++){
					swap(card2[i],cards[j]);
					nows[j - 1] = cards[j].num;
					bool flag = dfs(!now,dep + 1);
					swap(card2[i],cards[j]);
					nows[j - 1] = cards[j].num;
					if(flag == false) return false;
				}
			}
		}
		return true;
	}
}

int main(){
	init();
	cin>>T;
	for(int i = 1;i <= T;i++){
		memset(used,0,sizeof(used));
		char c;
		int num;
		for(int j = 1;j <= 4;j++){
			cin>>num>>c;
			cards[j].num = num,cards[j].color = (c == 'b' ? 0 : 1);
			nows[j - 1] = num;
		}
		cin>>n>>m;
		for(int j = 1;j <= n;j++){
			cin>>num>>c;
			card1[j].num = num,card1[j].color = (c == 'b' ? 0 : 1);
		}
		for(int j = 1;j <= m;j++){
			cin>>num>>c;
			card2[j].num = num,card2[j].color = (c == 'b' ? 0 : 1);
		}
		if(dfs(0,1)) cout<<"You are MengNan!"<<endl;
		else cout<<"Gan si 25zai!"<<endl;
	}
	return 0;
}
R - 如果早知道wf题也会被ak

R、给出一个长度为$n$的字符串，求其最长偶回文子串的长度

Manacher
马拉车板题，在板子上面改一下就可以了。。

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
char s1[30000007],s2[30000007];
int p[30000007],id = 1,mx = 1,ans = -1;

int init(){
    s2[0] = '$';
    s2[1] = '#';
    int j = 2;
    int len = strlen(s1);
    for(int i = 0;i<len;i++){
        s2[j++] = s1[i];
        s2[j++] = '#';
    }
    s2[j] = '\0';
    return j;
}

int main(){
    memset(p,0,sizeof(p));
    int n;
    cin>>n;
    cin>>s1;
    int len = init();
    for(int i = 1;i<len;i++){
        if(i < mx) p[i] = min(p[2 * id - i],mx - i);
        else p[i] = 1;
        while(s2[i - p[i]] == s2[i + p[i]]){
            p[i] ++;
        }
        if(s2[i] == '#') ans = max(ans,p[i] - 1);
        if(mx < i + p[i]){
            id = i;
            mx = i + p[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}
S - 如果早知道wf题也会被ak - DLC1

S、给出两个字符串，求这两个串的最长公共子串长度

SA SAM Height数组
也是一个求LCP的板题，一开始交了写好的SA上去结果RE了（写糊了
然后心态崩了抄了一个SAM上去。。。这里还是放一下SA的代码

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
char s1[MAX],s2[MAX];
int sa[MAX],h[MAX],x[MAX],y[MAX],r[MAX],rk[MAX],m,ans = 0;
int len1,len2;

bool cmp(int *r,int a,int b,int len){
	return r[a] == r[b] && r[a+len] == r[b+len];
}

void SA(){
	m = M;
	for(int i = 0;i<=m;i++) r[i] = 0;
	for(int i = 0;i<len1;i++) r[x[i] = s1[i]] ++;
	for(int i = 1;i<=m;i++) r[i] += r[i - 1];
	for(int i = len1 - 1;i>=0;i--) sa[--r[x[i]]] = i;
	for(int j = 1,p = 1;j<=len1;j<<=1,m = p){
		p = 0;
		for(int i = len1 - j;i<len1;i++) y[p++] = i;
		for(int i = 0;i<len1;i++) if(sa[i] >= j) y[p++] = sa[i] - j;
		for(int i = 0;i<=m;i++) r[i] = 0;
		for(int i = 0;i<len1;i++) r[x[i]] ++;
		for(int i = 0;i<=m;i++) r[i] += r[i - 1];
		for(int i = len1 - 1;i>=0;i--) sa[--r[x[y[i]]]] = y[i];
		swap(x,y);
	    p = 1;
	    x[sa[0]] = 0;
	    for(int i = 1;i<len1;i++) x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
    int j,k = 0;
    for(int i = 0;i<len1;i++) rk[sa[i]] = i;
    for(int i = 0;i<len1;h[rk[i++]] = k)
    for(k?k--:0,j = sa[rk[i] - 1];s1[i + k] == s1[j + k];k++);
}

int main(){
	cin>>s1>>s2;
	len1 = strlen(s1);
	len2 = strlen(s2);
	s1[len1] = '$';
	for(int i = 0;i<len2;i++) s1[i + len1 + 1] = s2[i];
    int tmp = len1;
	len1 = len1+len2+1;
    len2 = tmp;
    SA();
    for(int i = 0;i<len1;i++){
    	if(h[i] > 1){
    		if(min(sa[i],sa[i-1]) < len2 && max(sa[i-1],sa[i]) > len2){
    			if(ans < h[i]) ans = h[i];
    		}
    	}
    }
    cout<<ans<<endl;
    return 0;
}