4/8上午考试

4/8上午考试

四月 08, 2022

　　4月8日上午考试

　　考了三道做过的题，所以写起来比较顺畅，但是考试的时候脑子抽了写了个 inf = 0x3f3f3f3f3f3f3f3f 导致挂了 $30pts$ ，痛失 AK 。（爆%机房AK巨佬 brAKzero 和 logfk OTZ）

T1

来源：[CERC2014]Virus synthesis

题意：

　　初始给定一个空串，有 2 种操作：

　　　　1.在串开头或者末尾添加一个字母。

　　　　2.将当前串复制一份并反接在后面。（AAAB $\rightarrow $ AAABBAAA）

　　多次询问给定一个字符串，最少能用多少次操作得到这个字符串。

题解：

　　PAM 的板题， 首先可以发现操作 2 越多越好，但是发现操作 2 只能得到长度为偶数的回文串，所以答案其实就是 在一个长度为偶数的回文串的基础上暴力添加字符 。

　　于是我们对于每次询问的串建立 PAM，设 $dp_x$ 表示得到节点 $x$ 所代表的回文串的最小操作次数，$Len_x$ 为节点 $x$ 所代表的的回文串的长度，$n$ 为询问串的长度，那么答案其实就是 $min\left \{ dp_x + n -Len_x\right\}$ 。

　　首先对于 $dp$ 数组的转移，有：

　　　　设 $S_x$ 为 $x$ 节点代表的回文串。

　　　　若在 PAM 上存在一条 $u \rightarrow v$ 的转移边（即在 $S_x $ 开头和末尾添加一个相同字符能得到 $S_v$），那么就有转移： $dp_v = min(dp_v , dp_u+1)$ 。

　　　　证明：先构造 $S_u$ 的一半，再在开头添加一个对应字符，在通过操作 2 得到 $Sv$ ，操作次数： $dp_u - 1 + 1 + 1= dp_u + 1$

　　　　我们发现回文串可能由自己的一半转移过来，因此我们在PAM上面利用 $fail$ 维护一个 $tran$ 指针， 表示长度不超过当前回文串一半的最长回文串对应的节点。（具体看代码）

　　我们设 $y = tran_x​$ 那么可以得到转移：$ dp_x = min(dp_x , dp_y + \frac{Len_x} {2} - Len_y + 1)​$ 。

　　直接从根开始 BFS 转移就行了，复杂度 $O(\sum|S|)$。

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
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
/* Written by Rikka__  */
/* 锟斤拷 */
#include<bits/stdc++.h>
using namespace std;
#define _ =read()
inline int read(){
    int r = 0 , w = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') w = -1; ch = getchar();} 
    while(ch >='0' && ch <='9') {r = r * 10 + ch -'0'; ch = getchar();}
    return r * w;
}
namespace FileIO{
    string InFile;
    string OutFile;
    void File(string s){
        InFile = s + ".in";
        OutFile = s + ".out";
        freopen(InFile.data() , "r" , stdin);
        freopen(OutFile.data() , "w" , stdout);
    }
}
const int Maxn = 500010;
char str[Maxn];
int n;
int L;
int ans;
int a[5]={0,'G'-'A','C'-'A','T'-'A'};
namespace PAM{
    int tot = 1;
    int cur = 0;
    int Len[Maxn];
    int fail[Maxn];
    int ch[Maxn][26];
    int num[Maxn];
    int tran[Maxn];
    int dp[Maxn];
    inline int Get(int x , int i){
        while(str[i - Len[x] - 1] != str[i]) x = fail[x];
        return x;
    }
    void extend(int i){
        int pos = Get(cur , i);
        if(ch[pos][str[i] - 'A'] == 0){
            fail[++tot] = ch[Get(fail[pos] , i)][str[i] - 'A'];
            ch[pos][str[i] - 'A'] = tot;
            Len[tot] = Len[pos] + 2;
            if(Len[tot] <= 2) tran[tot] = fail[tot];
            else{
                int now = tran[pos];
                while(str[i - Len[now] - 1] != str[i] || (Len[now] + 2) * 2 > Len[tot]) now = fail[now];
                tran[tot] = ch[now][str[i] - 'A'];
            }
	    }
        cur = ch[pos][str[i] - 'A'];
        num[cur]++;
    }
    void init(){
        for(int i = 0 ; i <= tot ; i++){
            for(int j = 0 ; j < 4 ; j++){
                ch[i][a[j]] = 0;    
            }
        }
        tot = 1;
        cur = 0;
        Len[1] = -1;
        fail[0] = 1 , fail[1] = 1;
    }
}
signed main(){
    // FileIO::File("dna");
    using namespace PAM;
    n _;
    while(n --> 0){
        scanf("%s" , str + 1);
        L = strlen(str + 1);
        ans = L;
        init();
        for(int i = 1 ; i <= L ; i++) extend(i);
        for(int i = 2 ; i <= tot ; i++) dp[i] = Len[i];
        queue<int> q;
        q.push(0);
        dp[0] = 1;
        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(int i = 0 ; i <= 3 ; i++){
                int son = ch[now][a[i]];
                if(son == 0) continue;
                dp[son] = dp[now] + 1;
                dp[son] = min(dp[son] , dp[tran[son]] + 1 + Len[son] / 2 - Len[tran[son]]);
                ans = min(ans , dp[son] + L - Len[son]);
                q.push(son);
			}
		}
        cout << ans << "\n";
    }
	return 0;
}
T2

来源：不知道。

题意：

　　给定一颗 $n$ 个节点的树，树的节点标号从 0 开始。每个节点可以是黑色或者白色，初始时每个节点的颜色为白色。要求实现两个操作：

　　　　1.将节点 $x$ 涂黑。

　　　　2.查询节点 $x$ 到所有黑色节点的距离和。

题解：

　　考虑题目中要求的东西，设黑色节点集合为 $B$ ，当前询问节点为 $x$ 则答案为：

　　推一下这个式子：

　　其中 $\sum dep_x $ 和 $\sum dep_y$ 是好求的，所以只需要思考如何求出 $\sum dep_{lca(x,y)}$

　　维护方式和 [LNOI2014]LCA 是一样的。

　　考虑将问题转化，每次想要将 $x$ 节点变为黑色，就将 $x$ 到根的路径上所有节点权值 +1，询问节点 $x$ 时，只需要求出 $x$ 到根的权值和，这个和就是 $\sum dep_{lca}$ 。

　　具体维护只需要树剖+线段树就行了 复杂度 $O(n\log n)$

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
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
/* Written by Rikka__  */
/* 锟斤拷 */
#include<bits/stdc++.h>
using namespace std;
#define _ =read()
#define int long long
inline int read(){
    int r = 0 , w = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') w = -1; ch = getchar();} 
    while(ch >='0' && ch <='9') {r = r * 10 + ch -'0'; ch = getchar();}
    return r * w;
}
namespace FileIO{
    string InFile;
    string OutFile;
    void File(string s){
        InFile = s + ".in";
        OutFile = s + ".out";
        freopen(InFile.data() , "r" , stdin);
        freopen(OutFile.data() , "w" , stdout);
    }
}
const int Maxn = 100005;
int head[Maxn];
int cnt = -1;
struct Vollerei{
    int to;
    int nxt;
    int w;
};
Vollerei *ed[Maxn << 1];
int fa[Maxn];
int siz[Maxn];
int dep[Maxn];
int top[Maxn];
int son[Maxn];
int dfn[Maxn];
int dis[Maxn];
int d[Maxn];
int sum[Maxn];
int col[Maxn];
int Idx;
int ans;
int now;
int n;
int q;
void add(int x , int y , int z){
    ed[++cnt] = new Vollerei;
    ed[cnt]->to = y;
    ed[cnt]->w = z;
    ed[cnt]->nxt = head[x];
    head[x] = cnt;
}
void dfs1(int x){
    dep[x] = dep[fa[x]] + 1;
    siz[x] = 1;
    for(int i = head[x] ; ~i ; i = ed[i]->nxt){
        int to = ed[i]->to;
        d[to] = ed[i]->w;
        dis[to] = dis[x] + ed[i]->w;
        dfs1(to);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
	}
}
void dfs2(int x , int tp){
    top[x] = tp;
    dfn[x] = ++Idx;
    sum[Idx] = sum[Idx - 1] + d[x];
    if(son[x]) dfs2(son[x] , tp);
    for(int i = head[x] ; ~i ; i = ed[i]->nxt){
        int to = ed[i]->to;
        if(to == tp || to == fa[x] || to == son[x]) continue;
        dfs2(to , to);
    }
}
namespace Segment_Tree{
    struct node{
        int l;
        int r;
        int sum;
        int tag;
    };
    node tr[Maxn << 2];
    void push_up(int x){
        tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum;
    }
    void build(int x , int l , int r){
        tr[x].l = l , tr[x].r = r;
        tr[x].sum = 0 , tr[x].tag = 0;
        if(l == r) return;
        int mid = l + r >> 1;
        build(x << 1 , l , mid);
        build(x << 1 | 1 , mid + 1 , r);
    }
    void push_down(int x){
        int mid = tr[x].l + tr[x].r >> 1;
        if(tr[x].tag){
            tr[x << 1].sum += tr[x].tag * (sum[mid] - sum[tr[x].l - 1]);
            tr[x << 1 | 1].sum += tr[x].tag * (sum[tr[x].r] - sum[mid]);
            tr[x << 1].tag += tr[x].tag;
            tr[x << 1 | 1].tag += tr[x].tag;
            tr[x].tag = 0;
        }
    }
    void update(int x , int l , int r){
        if(l <= tr[x].l && tr[x].r <= r){
            tr[x].sum += sum[tr[x].r] - sum[tr[x].l - 1];
            tr[x].tag++;
            return;
        }
        int mid = tr[x].l + tr[x].r >> 1;
        push_down(x);
        if(l <= mid) update(x << 1 , l , r);
        if(r >  mid) update(x << 1 | 1 , l , r);
        push_up(x);
    }
    inline int query(int x , int l , int r){
        if(l <= tr[x].l && tr[x].r <= r) return tr[x].sum;
        push_down(x);
        int mid = tr[x].l + tr[x].r >> 1;
        int res = 0;
        if(l <= mid) res += query(x << 1 , l , r);
        if(r >  mid) res += query(x << 1 | 1 , l , r);
        return res; 
    }
    inline int query(int x){
        int res = ans + dis[x] * now;
        while(x) {
            res -= query(1 ,  dfn[top[x]] , dfn[x]) * 2;
            x = fa[top[x]];
        }
        return res;
    }
    inline void update(int x){
        ans += dis[x];
        while(x){
            update(1 , dfn[top[x]] , dfn[x]);
            x = fa[top[x]];
        }
    }
}
using namespace Segment_Tree;
signed main(){
    //FileIO::File("color");
    n _;
    q _;
    memset(head , -1 , sizeof head);
    for(int i = 2 ; i <= n ; i++) fa[i] _ , fa[i]++;
    for(int i = 2 ; i <= n ; i++){
        int x _;
        add(fa[i] , i , x);
    }
    dfs1(1) , dfs2(1 , 1);
    build(1 , 1 , Idx);
    while(q --> 0){
        int opt _ , x _;
        x++;
        if(opt == 1){
            if(!col[x]){
                col[x] = 1;
                update(x);
                now++;
            }
		}
		else cout << query(x) << "\n";
    }
}
T3

来源：CF375C Circling Round Treasures

题意：

　　给定一个 $n \times m$ 的棋盘，有障碍、宝藏、陷阱（陷阱和宝藏的数量加起来不超过 8）。每个宝藏有一定的权值，要求用折线围成一个多边形，使得其内部不含有陷阱。对于一个多边形的价值为 围住的宝藏权值和减去多边形的周长 ，求最大价值。

题解：

　　如何判断一个点 $p$ 在多边形的内部？

　　以 $p$ 为起点画一条不经过多边形端点的射线，若和多边形的边有奇数个交点则 $p$ 在多边形内部，偶数个则在外部。

发现宝藏和陷阱的数量极少，可以考虑状压，给每个 宝藏 \ 陷阱 格子选一条射线，在转移的时候去更新有宝藏或陷阱的格子的射线与当前路径交点的奇偶性。

　　设 $f[i][j][S]$ 表示当前格子为 $(i,j)$ ，宝藏和陷阱的奇偶性的状态为 $S$ ,多边形的周长的最小值。

　　dfs 转移不太可行，我们发现每次转移只会让多边形的周长增加 1，故可以考虑BFS转移(没得选了QAQ)。

　　转移的时候枚举每个宝藏是否被包围就行了。

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
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
#include <bits/stdc++.h> 
using namespace std; 
const int Maxn = 25; 
const int Maxm = 500; 
const int Maxk = 1<<9; 
const int inf = 1e6 + 100; 
const int dx[4] = { 1, -1, 0, 0 }; 
const int dy[4] = { 0, 0, 1, -1 }; 
int n;
int m;
int s;
int t; 
int cnt;
int res; 
int val[Maxm];
int sum[Maxk]; 
int f[Maxn][Maxn][Maxk]; 
char c[Maxn][Maxn]; 
struct node {
	int x;
	int y;
	int v;
}; 
struct point {
	int x;
 	int y;
}p[Maxm]; 

bool check(int x, int y, int xx, int yy, int i) {
	if (xx == p[i].x && yy < p[i].y && x < xx) return 1; 
	if (x == p[i].x && y < p[i].y && x > xx) return 1; 
	return 0; 
}
queue<node> q; 
signed main() { 
	
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> c[i][j]; 
			if (c[i][j] == 'S') {
				s = i; 
				t = j; 
			} else if (c[i][j] != '.' && c[i][j] != '#' && c[i][j] != 'B') {
	 			p[c[i][j] - '0'].x = i; 
				p[c[i][j] - '0'].y = j; 
				++cnt; 
			}
		}
	}
	
	for (int i = 1; i <= cnt; ++i) cin>>val[i]; 
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (c[i][j] == 'B') { 
				p[++cnt].x = i; 
				p[cnt].y = j; 
				val[cnt] = -inf; 
			}
		}
	}
	
	for (int i = 1; i < (1<<cnt); ++i) {
		for (int j = 1; j <= cnt; ++j) {
			if (i & (1<<(j-1))) sum[i] += val[j]; 
		}
	}
	res = 0; 
	memset(f, -1, sizeof f); 
	q.push({s, t, 0}); 
	f[s][t][0] = 0; 
		
	while (!q.empty()) {
		node now = q.front(); 
		q.pop(); 
		int x = now.x, y = now.y, v = now.v; 
		if (x == s && y == t) {
			res = max(res, sum[v] - f[x][y][v]); 
		}
		for (int i = 0; i < 4; ++i) {
			int xx = x + dx[i], yy = y + dy[i], val = v; 
			if (xx < 1 || xx > n || yy < 1 || yy > m) continue; 
			if (c[xx][yy] != 'S' && c[xx][yy] != '.') continue; 
			for (int j = 1; j <= cnt; ++j) {
				if (check(x, y, xx, yy, j)) val ^= 1<<(j-1); 
			}
			if (f[xx][yy][val] == -1) {
				f[xx][yy][val] = f[x][y][v] + 1; 
				q.push({xx, yy, val}); 
			}
		}
	}
	cout<<res;
	return 0;
}

​