发表更新ICPC/CCPC / Contests / 其他22 分钟读完 (大约3364个字)

GMCPC2020 网络赛

比赛链接 / 官方题解链接

B / C / D / G / I / J / N / O / Q

水题，不多说

A

记一个坑：$a\sim z$ 的 $\mathrm{ASCII}$ 码是 $97\sim122$，直接加上 $10$ 会爆掉 char 类型。

>folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

string s, dat;

int get(){
	int sz = dat.size();
	if(sz != 8)	return -1;
	int y = 0, m = 0, d = 0;
	for(int i = 0; i <= 3; i++)	y = y * 10 + dat[i] - '0';
	if(y < 1900 || y > 2020)	return -1;
	for(int i = 4; i <= 5; i++)	m = m * 10 + dat[i] - '0';
	if(m < 1 || m > 12)	return -1;
	for(int i = 6; i <= 7; i++)	d = d * 10 + dat[i] - '0';
	if(d < 1)	return -1;

	if(m == 2){
		if(y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)){ // leap year
			if(d > 29)	return -1;
		}
		else{
			if(d > 28)	return -1;
		}
	}
	else if((m <= 7 && m % 2 == 1) || (m >= 8 && m % 2 == 0)){ // big
		if(d > 31)	return -1;
	}
	else{ // small
		if(d > 30)	return -1;
	}

	int res = y * 10000 + m * 100 + d;
	while(res >= 10){
		int ans = 0;
		while(res){
			ans += res % 10;
			res /= 10;
		}
		res = ans;
	}
	return res;
}

int main(){
	while(getline(cin, dat)){
		LL k = get();
		getline(cin, s); int len = s.size();
		if(k == -1){ puts("none"); continue; }
		bool ok = true;
		string ans;
		for(int i = 0; i < len; i++){
			if(s[i] == ' ')	ans += '#';
			else if(s[i] >= 'A' && s[i] <= 'Z'){
				int t = s[i] - 'A' + 1;
				t += k; if(t > 26)	t %= 26;
				ans += (char)(t - 1 + 'A');
			}
			else if(s[i] >= 'a' && s[i] <= 'z'){
				int t = s[i] - 'a' + 1;
				t += k; if(t > 26)	t %= 26;
				ans += (char)(t - 1 + 'a');
			}
			else{
				ok = false;
				break;
			}
		}
		if(!ok){ puts("none"); continue; }
		cout << ans << endl;
	}
	return 0;
}

H

【参考官方题解】把原序列建成一个双向链表，然后从小到大考虑每个值作为区间第 $x$ 大的贡献，算完这个值的贡献就把它从链表中删去，这样链表中的所有值总是不小于当前值。于是欲知它是哪些区间的第 $x$ 大，就往前扫 $x-1$ 步，往后扫 $x-1$ 步，然后尺取长度为 $x$ 的区间。在往前往后扫的过程中记录一下后缀、前缀最大值，就可以在尺取过程中求得最大值。

>folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 10005;
const int X = 105;

int T, n, x;
LL ans;

struct Node{
	LL val, pos;
	bool operator < (const Node &A) const{
		return val < A.val;
	}
}a[N];

struct List{
	LL val, pre, suc;
}lis[N];
void del(int x){
	int p = lis[x].pre, s = lis[x].suc;
	if(p != 0)		lis[p].suc = s;
	if(s != n + 1)	lis[s].pre = p;
	lis[x].pre = lis[x].suc = 0;
}

LL lmx[N], rmx[N], lid, rid;
inline void solve(int i){
	lid = rid = 0;
	int l = i;
	lmx[0] = rmx[0] = lis[i].val;
	while(lis[l].pre && lid < x - 1){
		l = lis[l].pre;
		lid++;
		lmx[lid] = max(lmx[lid-1], lis[l].val);
	}
	int r = i;
	while(lis[r].suc != n + 1 && rid < x - 1){
		r = lis[r].suc;
		rid++;
		rmx[rid] = max(rmx[rid-1], lis[r].val);
	}
	if(lid + rid + 1 < x)	return;
	int now = i, cnt = 0;
	while(lid + 1 + cnt < x){
		cnt++;
		now = lis[now].suc;
	}
	for(int k = l, t = lid; k <= i && t >= 0; k = lis[k].suc, t--){
		ans += 1ll * (max(lmx[t], rmx[cnt]) ^ (lis[i].val)) * (k - lis[k].pre) * (lis[now].suc - now);
		cnt++;
		if(cnt > rid)	break;
		now = lis[now].suc;
	}
}

int main(){
	int CASES = 0;
	for(read(T); T; T--){
		read(n, x);
		memset(lis, 0, sizeof lis);
		memset(lmx, 0, sizeof lmx);
		memset(rmx, 0, sizeof rmx);
		ans = 0;
		lis[0].val = lis[n+1].val = -1;
		for(int i = 1; i <= n; i++){
			read(a[i].val);
			a[i].pos = i;
			lis[i].val = a[i].val;
			lis[i].pre = i - 1;
			lis[i].suc = i + 1;
			lis[i - 1].suc = i;
			lis[i + 1].pre = i;
		}
		sort(a+1, a+n+1);
		for(int i = 1; i <= n; i++){
			solve(a[i].pos);
			del(a[i].pos);
		}
		printf("Case #%d: %lld\n", ++CASES, ans);
	}
	return 0;
}

K

按照贪心顺序排序：如果 $i$ 在 $j$ 前比 $j$ 在 $i$ 前优，则 $a_i+\max(a_j+b_j,b_i)\leq a_j+\max(a_i+b_i,b_j)$.

另外：其实按照 $b$ 排序就够了，证明见蓝书第二题。

>folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 1005;

int n;
struct Node{
	int a, b;
	bool operator < (const Node &A) const{
		int t1 = max(a + b, a + A.a + A.b);
		int t2 = max(A.a + A.b, A.a + a + b);
		if(t1 == t2){
			if(a == A.a)	return b < A.b;
			return a < A.a;
		}
		return t1 < t2;
	}
}a[N];

int main(){
	read(n);
	for(int i = 1; i <= n; i++)	read(a[i].a, a[i].b);
	sort(a+1, a+n+1);
	int tot = 0, sum = 0;
	for(int i = 1; i <= n; i++){
		sum += a[i].a;
		tot = max(tot, sum + a[i].b);
	}
	printf("Project %d: %d\n", n, tot);
	return 0;
}

L

首先把价值为负的鱼剔掉。设 $dp[j]$ 表示选出的颜值最大为 $j$ 的最大价值，那么 $dp[a[i]]=\max(dp[a[i]],dp[k]+w[i]),k\leq a[i]$.

然后考虑优化，发现转移方程是求前缀最大值，我们只需要对 $dp[]$ 数组进行单点修改、求前缀最大，所以树状数组维护。

>folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 10005;

int T, n, mnface = 1e9, mxface = -1e9;
struct Node{
	int face, val;
}a[N];

int c[100005];
inline int lowbit(int x){ return x & -x; }
inline void upd(int x, int val){
	while(x <= mxface){
		c[x] = max(c[x], val);
		x += lowbit(x);
	}
}
inline int getMax(int x){
	int res = -1e9;
	while(x){
		res = max(res, c[x]);
		x -= lowbit(x);
	}
	return res;
}

int main(){
	int CASES = 0;
	for(read(T); T; T--){
		read(n);
		mnface = 1e9, mxface = -1e9;
		for(int i = 1; i <= n; i++){
			int x; read(x);
			a[i].val = x / 10000;
			a[i].face = x % 10000;
		}
		int id = 0;
		for(int i = 1; i <= n; i++)
			if(a[i].val > 0)
				a[++id] = a[i];
		n = id;
		if(n == 0){
			printf("Case #%d: %d\n", ++CASES, 0);
			continue;
		}
		for(int i = 1; i <= n; i++)
			mnface = min(mnface, a[i].face);
		for(int i = 1; i <= n; i++){
			a[i].face -= mnface - 1;
			mxface = max(mxface, a[i].face);
		}
		int ans = 0;

		// from 1 to n
		memset(c, 0, sizeof c);
		for(int i = 1; i <= n; i++){
			int mx = getMax(a[i].face);
			upd(a[i].face, mx + a[i].val);
		}
		ans = max(ans, getMax(mxface));
		
		// from n to 1
		memset(c, 0, sizeof c);
		for(int i = n; i >= 1; i--){
			int mx = getMax(a[i].face);
			upd(a[i].face, mx + a[i].val);
		}
		ans = max(ans, getMax(mxface));

		printf("Case #%d: %d\n", ++CASES, ans);
	}
	return 0;
}

M

把不同的化学元素看做不同的点，那么每一个化学物品就是一条边，要求不能出现环，所以并查集维护。

>folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int fa[N];
inline int findfa(int x){ return x == fa[x] ? x : fa[x] = findfa(fa[x]); }
inline void unionn(int x, int y){ fa[findfa(y)] = findfa(x); }

int main(){
	for(int i = 1; i <= 100000; i++)	fa[i] = i;
	int x, y, cnt = 0;
	while(1){
		read(x);
		if(x == -1)	break;
		read(y);
		if(findfa(x) == findfa(y))	cnt++;
		else	unionn(x, y);
	}
	printf("%d\n", cnt);
	return 0;
}

P

设 $dp[i][0\sim4]$ 表示前 $i$ 天、最后一天在 $0\sim4$ 地点的去图书馆最多天数，转移很好写。

>folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int n, dp[N][10], a[N][10];

int main(){
	read(n);
	for(int i = 1; i <= n; i++){
		read(a[i][1], a[i][2], a[i][3], a[i][4]);
		for(int j = 0; j <= 4; j++){
			if(j == 0){
				for(int k = 0; k <= 4; k++)
					dp[i][j] = max(dp[i][j], dp[i-1][k]);
			}
			else{
				if(a[i][j]){
					for(int k = 0; k <= 4; k++){
						if(j == k)	dp[i][j] = max(dp[i][j], dp[i-1][k]);
						else	dp[i][j] = max(dp[i][j], dp[i-1][k] + 1);
					}
				}
			}
		}
	}
	int ans = 0;
	for(int k = 0; k <= 4; k++)
		ans = max(ans, dp[n][k]);
	printf("%d\n", ans);
	return 0;
}

R

考虑反面，如何求出长度为 $n$ 的不孤独的串的个数。

设 $dp[j]$ 表示最后一个 $b$ 的位置在 $j$ 的不孤独串的个数。从 $1$ 到 $n$ 依次考虑，设当前位置为 $i$，那么 $dp[i]=\sum\limits_{0\leq j<i且j\neq i-2}dp[j]$，也即如果要在 $i$ 处放置 $b$，那么最后一个 $b$ 可以在除了 $i-2$ 以外的其余位置。此时，长度为 $i$ 的不孤独串的个数就是 $\sum\limits_{0\leq j\leq i且j\neq i-1}dp[j]$，于是孤独串的个数就是 $2^i-\sum\limits_{0\leq j\leq i且j\neq i-1}dp[j]$.

然后发现答案会爆 long long，所以要上高精度（或者写 Python）。

>folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

struct BigNum{
    vector<int> a; // a[n-1]...a[1]a[0]
    int neg;

    BigNum(){ a.clear(); neg = 1; }

    BigNum operator = (LL num){
        a.clear();
        do{
            a.pb(num % 10);
            num /= 10;
        }while(num);
        return *this;
    }
    BigNum operator = (const string &s){
        a.clear();
        int len = s.length();
        for(int i = 0; i < len; i++)
            a.pb(s[len-i-1] - '0');
        return *this;
    }

    bool operator < (const BigNum &b) const{
        if(a.size() != b.a.size())	return a.size() < b.a.size();
        for(int i = a.size() - 1; i >= 0; i--)
            if(a[i] != b.a[i])
                return a[i] < b.a[i];
        return false;
    }
    bool operator > (const BigNum &b) const{ return b < *this; }
    bool operator <= (const BigNum &b) const{ return !(*this > b); }
    bool operator >= (const BigNum &b) const{ return !(*this < b); }
    bool operator != (const BigNum &b) const{ return (*this > b) || (*this < b); }
    bool operator == (const BigNum &b) const{ return !(*this < b) && !(*this > b); }

    BigNum operator + (const BigNum &b) const{
        BigNum C;
        int x = 0;
        for(int i = 0, g = 0; ; i++){
            if(g == 0 && i >= a.size() && i >= b.a.size())	break;
            x = g;
            if(i < a.size())	x += a[i];
            if(i < b.a.size())	x += b.a[i];
            C.a.pb(x % 10);
            g = x / 10;
        }
        return C;
    }
    BigNum operator - (const BigNum &b) const{
        BigNum C;
        BigNum A = *this;
        BigNum B = b;
        if(A < B)	C.neg = -1, swap(A, B);
        C.a.resize(A.a.size());
        for(int i = 0; ; i++){
            if(i >= A.a.size() && i >= B.a.size())	break;
            if(i >= B.a.size())	C.a[i] = A.a[i];
            else	C.a[i] = A.a[i] - B.a[i];
        }
        for(int i = 0; ; i++){
            if(i >= C.a.size())	break;
            if(C.a[i] < 0){
                C.a[i] += 10;
                C.a[i+1]--;
            }
        }
        while(C.a.size() > 1 && C.a.back() == 0)	C.a.pop_back();
        return C;
    }
    BigNum operator * (const BigNum &b) const{
        BigNum C;
        C.a.resize(a.size() + b.a.size());
        for(int i = 0; i < a.size(); i++){
            int g = 0;
            for(int j = 0; j < b.a.size(); j++){
                C.a[i+j] += a[i] * b.a[j] + g;
                g = C.a[i+j] / 10;
                C.a[i+j] %= 10;
            }
            C.a[i+b.a.size()] = g;
        }
        while(C.a.size() > 1 && C.a.back() == 0)	C.a.pop_back();
        return C;
    }
    BigNum operator / (const LL &b) const{
        BigNum C;
        C = *this;
        for(int i = C.a.size() - 1; i >= 0; i--){
            if(i)	C.a[i-1] += C.a[i] % b * 10;
            C.a[i] /= b;
        }
        while(C.a.size() > 1 && C.a.back() == 0)
            C.a.pop_back();
        return C;
    }
    BigNum operator / (const BigNum &b) const{
        BigNum L, R, ans, t;
        L = 0ll;
        R = *this;
        ans = 0ll;
        t = 1ll;
        while(L <= R){
            BigNum mid = (L + R) / 2;
            if((mid * b) > (*this))
                R = mid - t;
            else
                L = mid + t, ans = mid;
        }
        return ans;
    }
    BigNum operator % (const LL &b) const{
        BigNum B; B = b;
        return (*this) - (*this) / b * B;
    }
    BigNum operator % (const BigNum &b) const{
        return (*this) - (*this) / b * b;
    }
    BigNum operator += (const BigNum &b){ *this = *this + b; return *this; }
    BigNum operator -= (const BigNum &b){ *this = *this - b; return *this; }
    BigNum operator *= (const BigNum &b){ *this = *this * b; return *this; }
    BigNum operator /= (const LL &b){ *this = *this / b; return *this; }
    BigNum operator /= (const BigNum &b){ *this = *this / b; return *this; }

    void println(){
        if(neg == -1)	putchar('-');
        for(int i = a.size() - 1; i >= 0; i--)
            printf("%d", a[i]);
        putchar(10);
    }
};

const int N = 105;

int T, n;
BigNum dp[N], f[N];
BigNum power[N], two;

int main(){
	two = "2";
	power[0] = "1";
	for(int i = 0; i <= 100; i++){
		dp[i] = "0";
		f[i] = "0";
		if(i)	power[i] = power[i-1] * two;
	}
	dp[0] = "1";
    for(int i = 1; i <= 100; i++){
        for(int j = 0; j < i; j++)
            if(j != i - 2)
                dp[i] += dp[j];
        BigNum sum;
        sum = "0";
        for(int j = 0; j <= i; j++) sum += dp[j];
        sum -= dp[i-1];
        f[i] = power[i] - sum;
    }
	for(read(T); T; T--){
		read(n);
		f[n].println();
	}
    return 0;
}

S

把词库建成 $Trie$ 树，然后询问就在 $Trie$ 树上 $dfs$ 即可。

记一个坑：函数传参时不要传字符串！否则复制字符串会 $TLE$.

>folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

struct Trie{
	bool isEnd;
	Trie *ch[26];
	Trie(){
		isEnd = false;
		for(int i = 0; i < 26; i++)
			ch[i] = nullptr;
	}
};
Trie *rt;
void insertTrie(string s){
	int len = s.size();
	Trie *now = rt;
	for(int i = 0; i < len; i++){
		if(now -> ch[s[i]-'a'] == nullptr)
			now -> ch[s[i]-'a'] = new Trie;
		now = now -> ch[s[i]-'a'];
	}
	now -> isEnd = true;
}
Trie * insert(string s){
	int len = s.size();
	Trie *now = rt;
	for(int i = 0; i < len; i++){
		if(now -> ch[s[i]-'a'] == nullptr){
			now -> ch[s[i]-'a'] = new Trie;
			now = now -> ch[s[i]-'a'];
			if(i == len - 1)	now -> isEnd = true;
		}
		else	now = now -> ch[s[i]-'a'];
	}
	return now;
}

int n, q;
string s;

int cnt = 0;
void dfs(Trie *now){
	if(cnt == 50)	return;
	if(now -> isEnd == true)
		cout << s << endl, cnt++;
	if(cnt == 50)	return;
	for(int i = 0; i < 26; i++){
		if(cnt == 50)	return;
		if(now -> ch[i] != nullptr){
			s.push_back((char)(i + 'a'));
			dfs(now -> ch[i]);
			s.pop_back();
		}
	}
}

int main(){
	ios::sync_with_stdio(false);

	rt = new Trie;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> s;
		insertTrie(s);
	}
	cin >> q;
	while(q--){
		cin >> s;
		Trie *pt = insert(s);
		if(pt -> isEnd == false){
			cout << s << endl;
			cnt = 1;
			dfs(pt);
		}
		else{
			cnt = 0;
			dfs(pt);
		}
	}
	return 0;
}

T

【参考官方题解】把重链横着放，轻边竖着放。这样宽度不超过 $n$，高度不超过 $\lg n$，面积小于 $n\lg n$.

>folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 1005;

int n;

struct Edge{
	int nxt, to;
}edge[N<<1];
int head[N], edgeNum;
void addEdge(int from, int to){
	edge[++edgeNum] = (Edge){head[from], to};
	head[from] = edgeNum;
}

int fa[N], son[N], sz[N];
void dfs(int x, int f){
	fa[x] = f, sz[x] = 1, son[x] = 0;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == fa[x])	continue;
		dfs(edge[i].to, x);
		sz[x] += sz[edge[i].to];
		if(!son[x] || sz[edge[i].to] > sz[son[x]])
			son[x] = edge[i].to;
	}
}

int mx[N], ansx[N], ansy[N];

void solve(int x, int yy){
	ansx[x] = ++mx[yy], ansy[x] = yy;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == fa[x] || edge[i].to == son[x])	continue;
		solve(edge[i].to, yy + 1);
	}
	if(son[x])	solve(son[x], yy);
}

int main(){
	read(n);
	for(int i = 1; i < n; i++){
		int u, v; read(u, v);
		addEdge(u, v), addEdge(v, u);
	}
	dfs(1, 0);
	memset(mx, -1, sizeof mx);
	solve(1, 0);
	for(int i = 1; i <= n; i++)
		printf("%d %d\n", ansx[i], ansy[i]);
	return 0;
}

F

留坑待填……

E

标程子弹转的方向反了吧……复杂度也不对……不说了

GMCPC2020 网络赛

http://xyfjason.github.io/blog-xcpc/2020/04/26/GMCPC2020-网络赛/

作者

xyfJASON

发布于

2020-04-26

更新于

2021-08-28

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×