2019 ACM-ICPC, Asia Xuzhou Regional

字数统计: 3.7k字   |   阅读时长: 20分
训练题解
solved A B C D E F G H I J K L M
6 / 13 O · O · Ø O · Ø · · · · Ø
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

REPLY： 在队友的提醒下，还坚决地否定了M题是树的重心。我是八嘎。——lllllan

比赛链接

A. Cat

Solved by Sstee1XD. 4:52(+)

题意： 给你一个[L,R][L, R]的区间，每个点的权值与区间值对应，现有ss元，你现在可以在这个区间内选一个连续区间，花费为这个区间所有值的异或值，问你最多购买的区间长度是多少。

思路： 写一下发现，当起始点为偶数时，每四个值的异或值为00。我们再讨论一下情况，发现只要判断一下区间头是否是奇数，如果是的话就往后移动一位，接下来再暴力判断一下左右两边怎么取就行了，并不需要管区间头向右移动更多位的情况。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long ll;

ll l, r, m, p;
ll tl;
ll a[7];

void solve() {
	ll maxx = -1;
	for (ll i = l; i <= r; ++i) {
		if (i <= m) maxx = max(maxx, 1ll);
		ll tmp = i;
		for (ll j = i + 1; j <= r; ++j) {
			tmp ^= j;
			if (tmp <= m) maxx = max(maxx, j - i + 1);
		}
	}
	printf("%lld\n", maxx);
}

int main () {
	int t = 1;
	scanf("%d", &t);
	while (t--) {
		p = -1;
		a[1] = 0;
		scanf("%lld %lld %lld", &l, &r, &m);
		if (r - l + 1 <= 4) {
			solve();
			continue;
		}
		ll ans = 0;
		tl = l;
		if (tl & 1) {
			tl++;
			p = l;
		}
		ans = (r - tl + 1) / 4 * 4;
		ll go = ans + tl;
		int now = 2;
		ll tmp = 0;
		ll len = ans;
		while (go <= r) {
			tmp ^= go;
			a[now++] = tmp;
			go++;
		}
		for (int i = 1; i < now; ++i) {
			if (a[i] <= m) ans = max(ans, len + i - 1);
			if (p != -1) {
				a[i] ^= p;
				if (a[i] <= m) {
					ans = max(ans, len + i);
				}
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

C. < 3 numbers

Solved by Sstee1XD & Tryna. 0:57(+)

题意： 求给定区间内素数的个数是否严格小于其三分之一。

思路： 区间够大就一定可以。打个表，稍微取个大点的范围，小的直接暴力即可。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 10;
int a[maxn];
void run () {
	
}

bool check(int x) {
	if(x == 1 || x == 2) return true;
	if ((x & 1) == 0) return false;
	for(int i = 2; i <= sqrt(x); i++) {
		if(x % i == 0) return false;
	}
	return true;
}

int main () {
	int t, l, r;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &l, &r);
		int tn = 0, sn = 0, last = 20;
		int f = 0;
		for (int i = l; i <= r; ++i) {
			tn++;
			if (check(i)) sn++;
			if (sn * 3 < tn) f = 1;
			else f = 0;
			if (f) {
				i++;
				while (last-- && i <= r) {
					tn++;
					if (check(i)) sn++;
					if (sn * 3 < tn) f = 1;
					else f = 0;
					i++;
				}
				break;
			}
		}
		if (f) puts("Yes");
		else puts("No");
	}
	return 0;
}

E - Multiply

solved by Tryna.(-)

题意 给出nn个数aia_i,令Z=a1!+a2!+a3!+⋯+an!Z = a_1! + a_2! + a_3! +\cdots + a_n! 再给出XX 和 YY, 令bi=Z∗Xib_i = Z * X^i, 想找到一个最大的ii, 使得bib_i 是 Y!Y!的因子。

题解： 分解XX的所有素因子以及幂次，分析每个因子在Y!Z\frac{Y!}{Z}中有多少个，然后看看能拼到多少个ii。
因为题目中的数范围都很大，所以考虑大整数的质因数分解，这里用的是kuangbin模板。

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
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int S = 8;
int tol;
ll factor[110], N, X, Y, arr[maxn];
unordered_map<ll, ll>mp;

ll mult_mod(ll a, ll b, ll c) {
	a %= c;
	b %= c;
	ll ret = 0;
	ll tmp = a;
	while(b) {
		if(b & 1) {
			ret += tmp;
			if(ret > c) ret -= c;
		}
		tmp <<= 1;
		if(tmp > c) tmp -= c;
		b >>= 1;
	}
	return ret;
}

ll pow_mod(ll a, ll n, ll mod) {
	ll ret = 1;
	ll tmp = a % mod;
	while(n) {
		if(n & 1) 
			ret = mult_mod(ret, tmp, mod);
		tmp = mult_mod(tmp, tmp, mod);
		n >>= 1;
	}
	return ret;
}

bool check(ll a, ll n, ll x, ll tmp) {
	ll ret = pow_mod(a, x, n);
	ll last =ret;
	for(int i = 1; i <= tmp; i++) {
		ret = mult_mod(ret, ret, n);
		if(ret == 1 && last != 1 && last != n - 1) return true;
		last = ret;
	}
	if(ret != 1) return true;
	else return false;
}

bool Miller_Rabin(ll n) {
	if(n < 2) return false;
	if(n == 2) return true;
	if( (n & 1) == 0) return false;
	ll x = n - 1;
	ll tmp = 0;
	while( (x & 1) == 0 ) {
		x >>= 1;
		tmp++;
	}
	srand(time(NULL));
	for(int i = 0; i < S; i++) {
		ll a = rand() % (n - 1) + 1;
		if(check(a, n, x, tmp))
			return false;
	}
	return true;
}

ll gcd(ll a, ll b) {
	ll tmp;
	while(b) {
		tmp = a;
		a = b;
		b = tmp % b;
	}
	if(a >= 0) return a;
	else return -a;
}

ll pollard_rho(ll x, ll c) {
	ll i = 1, k = 2;
	srand(time(NULL));
	ll x0 = rand() % (x - 1) + 1;
	ll y = x0;
	while(1) {
		i++;
		x0 = (mult_mod(x0, x0, x) + c) % x;
		ll d = gcd(y - x0, x);
		if(d != 1 && d != x) return d;
		if(y == x0) return x;
		if(i == k) {
			y = x0;
			k += k;
		}
	}
}

void findfac(ll n, int k) {
	if(n == 1) return ;
	if(Miller_Rabin(n)) {
		factor[tol++] = n;
		return ;
	}
	ll p = n;
	int c = k;
	while(p >= n)
		p = pollard_rho(p, c--);
	findfac(p, k);
	findfac(n / p, k);
}

ll cal(ll n,ll x)
{
	ll ans = 0;
	while(n / x)
	{
		ans += n/x;
		n /= x;
	}
	return ans;
}

void solve() {
    tol = 0;
	mp.clear();
	scanf("%lld %lld %lld", &N, &X, &Y);
	for(int i = 1; i <= N; i++)
		scanf("%lld", &arr[i]);
	findfac(X, 107);
	for(int i = 0; i < tol; i++)  {
		mp[ factor[i] ]++;
	}
	ll ans = INF;
	for(auto v : mp) {
		ll num = 0;
		for(int i = 1; i <= N; i++) {
			num += cal(arr[i], v.fi);
		}
		ans = min(ans, (cal(Y, v.fi) - num) / v.se);
	}
	printf("%lld\n", ans);
}
int main() {
	int t = 1;
	scanf("%d", &t);
	while(t--)
		solve();
	return 0;
}

F - The Answer to the Ultimate Question of Life, The Universe, and Everything.

solved by Sstee1XD && Tryna. 3:51(+2)

题意 给出一个xx，找到a b ca\ b\ c满足a3+b3+c3=xa^3 + b^3 + c^3 = x

题解： xx很小，直接打表就可以了。注释部分为打表代码

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
const int maxn = 2e2 + 10;
//struct node{
//	int a, b, c;
//}ans[maxn];
//map<ll, pii> mp;
ll a[maxn] = {5000,5000,4375,4,1061109567,1061109567,644,168,5000,217,683,843,10,1061109567,1061109567,332,4118,2977,1671,91,2833,445,1061109567,1061109567,8,2357,2106,5000,2269,235,1061109567,1061109567,1061109567,1061109567,1557,1154,2731,445,25,1061109567,1061109567,1061109567,1061109567,837,8,2025,815,139,3991,1061109567,1061109567,659,1061109567,2141,3891,3131,559,982,1061109567,1061109567,1202,845,2903,146,5000,903,4,1061109567,1061109567,398,2325,443,434,344,1061109567,1061109567,1061109567,1061109567,2123,711,1366,2638,1188,3651,1061109567,1061109567,1061109567,4271,1686,2036,1798,3992,4039,253,1061109567,1061109567,20,3200,2391,984,1870,2325,229,1061109567,1061109567,8,2760,1117,1345,2924,1061109567,4966,1061109567,1061109567,1061109567,11,1945,962,4327,3789,2725,1061109567,1061109567,38,5,5000,2217,4988,3997,1801,1061109567,1061109567,5,389,3203,1395,946,801,103,1061109567,1061109567,116,8,1061109567,3342,10,376,2131,1061109567,1061109567,317,447,741,3744,2145,3721,1061109567,1061109567,1061109567,1526,3972,4980,4180,4033,79,1061109567,1061109567,1061109567,890,1521,4047,1178,1061109567,1061109567,349,1061109567,1061109567,1169,15,2691,1061109567,4861,91,4876,1061109567,1061109567,5,2000,1635,1974,4815,399,16,1061109567,1061109567,1061109567,1112,3026,3809,2199,2334};
ll b[maxn] = {0,1,-486,4,1061109567,1061109567,-205,44,2,-52,-353,-641,7,1061109567,1061109567,-262,-588,2195,-1276,47,-741,-287,1061109567,1061109567,8,1839,237,3,-249,-69,1061109567,1061109567,1061109567,1061109567,-244,-509,2358,-84,16,1061109567,1061109567,1061109567,1061109567,-307,-5,1709,-473,49,-1247,1061109567,1061109567,602,1061109567,1518,-648,1837,505,361,1061109567,1061109567,-163,668,-1561,102,4,403,1,1061109567,1061109567,134,824,401,-104,-146,1061109567,1061109567,1061109567,1061109567,-829,-196,-706,-1719,847,1315,1061109567,1061109567,1061109567,-1972,-1282,1953,365,-2912,861,-98,1061109567,1061109567,14,-991,-1638,-622,-903,319,118,1061109567,1061109567,-4,-1165,947,-948,853,1061109567,-2312,1061109567,1061109567,1061109567,8,-757,-555,383,-1673,1219,1061109567,1061109567,-16,0,5,-419,-3881,-726,-1238,1061109567,1061109567,2,167,-1766,-629,816,-428,-77,1061109567,1061109567,104,-3,1061109567,-2552,-7,-263,1528,1061109567,1061109567,260,215,486,-695,-516,-1049,1061109567,1061109567,1061109567,383,-1654,-2476,-1417,-2943,-59,1061109567,1061109567,1061109567,-574,-1012,-2149,891,1061109567,1061109567,-170,1061109567,1061109567,-160,-10,1503,1061109567,974,-29,976,1061109567,1061109567,5,-1092,318,-1403,-593,-215,16,1061109567,1061109567,1061109567,-579,-1606,-1347,508,-638};
ll c[maxn] = {-5000,-5000,-4373,-5,1061109567,1061109567,-637,-169,-5000,-216,-650,-695,-11,1061109567,1061109567,-265,-4114,-3331,-1373,-95,-2816,-401,1061109567,1061109567,-10,-2683,-2107,-5000,-2268,-233,1061109567,1061109567,1061109567,1061109567,-1555,-1120,-3223,-444,-27,1061109567,1061109567,1061109567,1061109567,-823,-7,-2369,-758,-141,-3950,1061109567,1061109567,-796,1061109567,-2370,-3885,-3329,-672,-998,1061109567,1061109567,-1201,-966,-2744,-161,-5000,-929,1,1061109567,1061109567,-403,-2359,-533,-432,-335,1061109567,1061109567,1061109567,1061109567,-2080,-706,-1300,-2368,-1317,-3707,1061109567,1061109567,1061109567,-4126,-1390,-2514,-1803,-3389,-4052,-248,1061109567,1061109567,-22,-3168,-2101,-893,-1797,-2327,-239,1061109567,1061109567,-7,-2689,-1309,-1165,-2948,1061109567,-4793,1061109567,1061109567,1061109567,-12,-1906,-896,-4328,-3677,-2804,1061109567,1061109567,-37,-1,-5000,-2212,-4034,-3989,-1580,1061109567,1061109567,-1,-399,-3013,-1351,-1116,-758,-86,1061109567,1061109567,-139,-7,1061109567,-2746,-8,-327,-2366,1061109567,1061109567,-367,-463,-805,-3736,-2135,-3693,1061109567,1061109567,1061109567,-1534,-3874,-4767,-4125,-3423,-66,1061109567,1061109567,1061109567,-802,-1354,-3834,-1328,1061109567,1061109567,-335,1061109567,1061109567,-1168,-13,-2839,1061109567,-4874,-90,-4889,1061109567,1061109567,-4,-1885,-1639,-1702,-4812,-377,-20,1061109567,1061109567,1061109567,-1057,-2867,-3752,-2208,-2318};
void solve() {
	int x;
	scanf("%d", &x);
	if(a[x] == inf)
		puts("impossible");
	else printf("%lld %lld %lld\n", a[x], b[x], c[x]);
}
int main() {
//	freopen("1.txt", "w", stdout);
//	for(ll ia = -5000; ia <= 5000; ia++) {
//		for(ll ib = -5000; ib <= 5000; ib++) {
//			mp[ia * ia * ia + ib * ib * ib] = {ia, ib};
//		}
//	}
//	int sum = 0;
//	for(ll ix = 0; ix <= 200; ix++) {
//		int f = 0;
//		for(ll ic = -5000; ic <= 5000; ic++) {
//			ll res = ix - ic * ic * ic;
//			if(mp.count(res)) {
//				ans[ix].a = mp[res].first;
//				ans[ix].b = mp[res].second;
//				ans[ix].c = ic;
//				f = 1;
//				sum++;
//				break;
//			}
//		}
//		if(!f) {
//			ans[ix].a = ans[ix].b = ans[ix].c = inf;
//		}
//	}
//	printf("%d\n", sum);
//	for(int i = 0; i <= 200; i++) printf("%d,", ans[i].a);
//	puts("");
//	for(int i = 0; i <= 200; i++) printf("%d,", ans[i].b);
//	puts("");
//	for(int i = 0; i <= 200; i++) printf("%d,", ans[i].c);
	int t;
	scanf("%d", &t);
	while(t--)
		solve();
	return 0;
}

H. Yuuki and a problem

题意：
带修改求区间mexmex

思路：

考虑对于一个区间，我们想要求得mexmex，可以对这个区间进行升序排序。当第一个数字不为11时，答案就是11。设当前前缀和为xx，那么我们前面的区间我们可以得到[1,x][1, x]之间任意一个数字，设当前数字为yy，我们将yy并入之前的区间，可以得到[y,y+x][y, y + x]之间的任意一个数字。当y≤xy \leq x时，这个前缀和就可以延展；如果y>xy > x，那么此时就可以得到mexmex为x+1x + 1。对于上述思路，我们可以用主席树来维护，一直询问更新前缀和sumsum，然后再询问区间内所有≤sum+1\leq sum + 1的数字的和。如果这个和并没有比sumsum大，那么mexmex即为sum+1sum+1。时间复杂度看似很大，但最坏情况下也是以斐波那契数列的增长速率增长的，是比较快的。

在知道要用主席树求区间mexmex之后，只需要写一个动态主席树即可。
这里用树状数组套主席树。树状数组里表示不同树的根节点，也就是说，树状数组里的每一个点都是一棵树。每次修改或者询问都按照树状数组来写。注意空间要给够。

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int n, m, q, li, ri;
int a[N], rt[N];

inline int lowbit(int x) {
    return x & -x;
}

struct Seg{
    struct Node{
        int ls, rs, cnt;
        ll sum;
        void init() {
            ls = rs = cnt = 0;
            sum = 0;
        }
    }t[N * 80];
    int tot;
    void init() {
        tot = 0;
        t[tot].init();
    }
    int newnode() {
        t[++tot].init();
        return tot;
    }
    void build(int &id, int l, int r) {
        if (!id) id = newnode();
        if (l == r) {
            return;
        }
        int mid = l + r >> 1;
        build(t[id].ls, l, mid);
        build(t[id].rs, mid + 1, r);
    }
    void modify(int &rt, int l, int r, int pos, ll v) {
        if (!rt) rt = newnode();
        t[rt].sum += v;
        if (l == r) {
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid) {
            modify(t[rt].ls, l, mid, pos, v);
        } else {
            modify(t[rt].rs, mid + 1, r, pos, v);
        }
    }
    void update(int x, int pos, ll v) {
        for (; x <= n; x += lowbit(x)) {
            modify(rt[x], 1, m, pos, v);
        }
    }
    ll query(int rt, int l, int r, ll k) {
        if (!rt) return 0;
        if (r <= k) {
//        	printf("%d %d %d %d\n", l, r, k, t[rt].sum);
            return t[rt].sum;
        }
        if (l > k) return 0;
        int mid = l + r >> 1;
        if (k <= mid) return query(t[rt].ls, l, mid, k);
        else return query(t[rt].ls, l, mid, k) + query(t[rt].rs, mid + 1, r, k);
    }

    ll query(int l, int r, ll k) {
        ll res = 0;
        for (int i = r; i > 0; i -= lowbit(i)) {
            res += query(rt[i], 1, m, k);
        }
        for (int i = l; i > 0; i -= lowbit(i)) {
            res -= query(rt[i], 1, m, k);
        }
        return res;
    }
}seg;

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    m = 2e5;
    seg.init();
    rt[0] = 0;
    seg.build(rt[0], 1, m);
    for (int i = 1; i <= n; ++i) {
        seg.update(i, a[i], a[i]);
    }
    ll pre = 0;
    for (int i = 1, op; i <= q; ++i) {
        scanf("%d%d%d", &op, &li, &ri);
        if (op == 1) {
            seg.update(li, a[li], -a[li]);
            a[li] = ri;
            seg.update(li, a[li], a[li]);
        } else {
            pre = 1;
            ll tmp = seg.query(li - 1, ri, pre);
            while (tmp >= pre) {
                pre = tmp + 1;
                tmp = seg.query(li - 1, ri, pre);
            }
            printf("%lld\n", pre);
        }
    }
    return 0;
}

M - Kill the tree

solved by lllllan. (-)

题意： 求每棵子树的重心。

题解： 常规的题目就是求一棵树的重心，这里需要利用一个性质来求解【两棵树相连接，合成的新树的重心，在原来两棵树的重心的连线上】。需要注意的是，一旦找到某棵子树的重心，及时break。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;

int sz[maxn];
int dp[maxn];
int pre[maxn];
int ans[maxn][3];

int n;
int cnt, head[maxn];
struct edge { int v, next; } e[maxn << 1];
void add (int u, int v) {
	e[++cnt] = {v, head[u]}; head[u] = cnt;
	e[++cnt] = {u, head[v]}; head[v] = cnt;
}

void dfs (int u, int fa) {
	sz[u] = 1;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (v == fa) continue;
		dfs(v, u);
		pre[v] = u;
		sz[u] += sz[v];
		dp[u] = max(dp[u], sz[v]);
	}
	
	
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (v == fa) continue;
		int tem = ans[v][ ans[v][0] ];
		while (tem != u) {
			int maxS = max(dp[tem], sz[u] - sz[tem]);
			if (maxS * 2 <= sz[u]) ans[u][ ++ans[u][0] ] = tem;
			else if (ans[u][0]) break;
			tem = pre[tem];
		}
	}
	if (dp[u] * 2 <= sz[u]) ans[u][ ++ans[u][0] ] = u;
}

int main () {
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	dfs(1, 0);
	
	for (int i = 1; i <= n; ++i) {
		if (ans[i][0] == 2) printf("%d %d\n", min(ans[i][1], ans[i][2]), max(ans[i][1], ans[i][2]));
		else printf("%d\n", ans[i][1]);
	}
	return 0;
}
文章目录
  1. A. Cat
  2. C. < 3 numbers
  3. E - Multiply
  4. F - The Answer to the Ultimate Question of Life, The Universe, and Everything.
  5. H. Yuuki and a problem
  6. M - Kill the tree
|