2018 ACM-ICPC, Asia Nanjing Regional

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

比赛链接

A. Adrien and Austin

solved by Sstee1XD & Tryna. 0:36(+3)

题意nn个石子，每个石子从11到nn编号，每次可以取11-kk个连续的石子，问谁先取完。

题解：我们特判nn为00和kk为11的情况，对于其余情况，先手都可以做出相应的选择达到必胜态。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int n, k;

int main() {
	scanf("%d %d", &n, &k);
	if(n == 0) puts("Austin");
	else if (k == 1 && n % 2 == 0) puts("Austin");
	else puts("Adrien");
    return 0;
}

D - Country Meow

solved by Tryna. (-)

题意： 求覆盖了所有点的最小球半径

题解： 裸题，跑一边模拟退火，代码中更新pos值的时候理解了很久。总的来说就是当前温度越高，向最远点移动的幅度越大，当前温度越低，向最远点移动的幅度越小

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
#include<bits/stdc++.h>
using namespace std;    
#define inf 0x3f3f3f3f
#define eps 1e-8
const int maxn = 110;
const double startT = 100000;
struct Point{
	double x, y, z;
}P[maxn];
double Dist(Point a, Point b){
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}
int n;
double SA(){
	double delta = 0.98, T = startT, ans = inf;
	Point pos = {0, 0, 0};
	while(T > eps){
		Point maxP = P[1];
		for(int i = 2; i <= n; i++){
			if(Dist(pos, P[i]) > Dist(pos, maxP))
				maxP = P[i];
		}
		ans = min(ans, Dist(pos, maxP));
		pos.x += (maxP.x - pos.x) * T / startT;
		pos.y += (maxP.y - pos.y) * T / startT;
		pos.z += (maxP.z - pos.z) * T / startT;
		T *= delta;
	}
	return ans;
}
 
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%lf %lf %lf", &P[i].x, &P[i].y, &P[i].z);
	printf("%.15f\n", SA());
	return 0;
}

G - Pyramid

solved by Tryna. (-)

题意: 计算等边三角形的个数

题解: 打表找规律，打表的思路就是把三角形放入坐标系中，O（n^3）暴力枚举每个顶点，如果三条边长度相同就计数。
打完表发现前几个数是这样的: 0 1 5 15 35 70 126 210
下面的方法将会用到这里的知识:差分的应用
所以我们对上面那个数列不断差分。
0 1 5 15 35 70 126 210
 1 4 10 20 35 56 84
  3 6 10 15 21 28
   3  4  5  6  7
     1  1  1  1
      0  0  0
所以前n项和

S(n)=1Cn+12+3Cn+13+3Cn+14+1Cn+15S(n) = 1C_{n+1} ^ 2 + 3C_{n+1} ^ 3 + 3C_{n+1} ^ 4 + 1C_{n+1} ^ 5

化简得

S(n)=n∗(n+1)∗(n+2)∗(n+3)∗(n+4)120S(n) = \frac{n*(n+1)*(n+2)*(n+3)*(n+4)}{120}

所以第n项$$f(n) = S(n) - S(n-1)$$
化简得:

f(n)=n∗(n+1)∗(n+2)∗(n+3)24f(n) = \frac{n*(n+1)*(n+2)*(n+3)}{24}

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
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<queue>
using namespace std;    
#define inf 0x3f3f3f3f
#define ll long long
#define eps 1e-10
#define endl "\n"
const int maxn = 1000010;
const int mod = 1e9 + 7;
const double pi = acos(-1.0);
int moven2[10][5] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}}; 
int moven1[10][5] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int quick_power(ll n, ll k){
	int ans=1;
	while(k){
		if(k&1){
			ans=(ans*n)%mod;
		}
		n=n*n%mod;
		k>>=1;
	}
	return ans%mod;
}
int t;
ll n;
int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0);
	scanf("%d", &t);
	while(t--){
		scanf("%lld", &n);
		ll ans = quick_power((ll)24, mod - 2);
		ans = ans * n % mod * (n + 1) % mod * (n + 2) % mod * (n + 3) % mod;
		printf("%lld\n", ans);
	}
	return 0;
}

I. Magic Potion

solved by lllllan. 01:26(+)

题意： n个英雄和m个怪兽，每个英雄都有对应的可以击败的怪兽并且只能选择其中一只。现有k瓶药水，每个英雄最多喝一瓶然后可以多击败一只怪兽。问最多可以击败多少只怪兽。

题解： 相比最经典的匹配问题，一个男朋友对应一个女朋友，现在可以一夫多妻了【不是】。又不像多重匹配那么麻烦，每个英雄最多也只能击败两只怪兽而已。所以就是简单跑两次匹配就可以了。 然后注意有K瓶药水的限制。

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
#include<bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)

const int N = 510;
int sum;
int n, m, k, t, x;
int vis[N], match[N];
vector<int> G[N];

bool dfs (int u) {
	for(auto v : G[u]) {
		if(match[v] == u) continue;
		if(!vis[v]) {
			vis[v] = 1;
			if(!match[v] || dfs(match[v])) {
				match[v] = u;
				return true;
			}
		}
	}
	return false;
}

void solve () {
	memset(match, 0, sizeof match);
	_for(i, 1, n) {
		memset(vis, 0, sizeof vis);
		if(dfs(i)) sum++;
	}
	for(int i = 1; i <= n && k; i++) {
		memset(vis, 0, sizeof vis);
		if(dfs(i)) sum++, k--;
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	_for(i, 1, n) {
		scanf("%d", &t);
		while(t--) {
			scanf("%d", &x);
			G[i].push_back(x);
		}
	}
	solve();
	printf("%d\n", sum);
    return 0;
}

J. Prime Game

solved by Sstee1XD. 1:11(+)

题意：给定序列a，定义

  • mul(l,r)=∏i=lraimul(l, r) = \prod_{i = l}^ra_i
  • fac(l,r)fac(l, r)为mul(l,r)mul(l, r)的不同质因子的数量

让你计算∑i=1n∑j=infac(i,j)\sum_{i = 1}^n\sum_{j = i}^nfac(i, j)。

题解：我们设 prevpre_v 为vv最后出现的位置。对于aia_i的质因子vv，它对于答案的贡献为对前面的贡献加上对后面的贡献，即 (n−i+1)∗(i−prev−1)+n−i+1(n - i +1)*(i-pre_v-1)+n-i+1 。

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

#define endl "\n"
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err() {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);}

inline int rd() {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 7, N = 1e3;
int prime[N + 10], cnt, flag[N + 10];
void isprime() {
	for (int i = 2; i <= N; ++i) {
		if (!flag[i]) {
			prime[++cnt] = i;
		}
		for (int j = 1; j <= cnt; ++j) {
			if (1ll * prime[j] * i > N) break;
			flag[prime[j] * i] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}
int n, pre[maxn], a[maxn];
vector<int>G[maxn];
void run() {
	for (int i = 1; i <= n; ++i) {
		a[i] = rd();
		if (G[a[i]].size() == 0 && a[i] != 1) {
			int tmp = a[i];
			for (int j = 1; j <= cnt; ++j) {
				if (tmp % prime[j] == 0) {
					G[a[i]].push_back(prime[j]);
					while (tmp % prime[j] == 0) {
						tmp /= prime[j];
					}
					if (tmp == 1) break;
				}
			}
			if (tmp > 1) G[a[i]].push_back(tmp);
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (auto v : G[a[i]]) {
			ans += (ll)(n - i + 1) * (ll)(i - pre[v] - 1) + (ll)(n - i + 1);
			pre[v] = i;
		}
	}
	printf("%lld\n", ans);
}

int main() {
	isprime();
	n = rd();
	run();
    return 0;
}

K. Kangaroo Puzzle

solved by Sstee1XD. (-)

题意：每次可以选择上下左右四个方向，一起移动所有的11，如果碰到00或者墙就不动，最后要在5000050000步内使所有11聚在一起。题目保证1不会转圈圈。

题解：因为保证的存在，所以就直接随机输出5000050000个方向就好了(为什么会这么玄学？)。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int main() {
	string s;
	int n, m;
	cin >> n >> m;
	while (n--) cin >> s;
	for (int i = 1; i <= 50000; ++i) {
		int x = rand()%4;
		if (x == 0) putchar('U');
		if (x == 1) putchar('D');
		if (x == 2) putchar('R');
		if (x == 3) putchar('L');
	}
	return 0;
}

M. Mediocre String Problem

solved by Sstee1XD. (-)

题意： 给你两个字符串ss和tt，对于tt中所有的前缀串kk，你要在ss中找到所有的子串sijs_{ij}，使得sijs_{ij}长度大于kk，并且将sijs_{ij}与kk拼接后得到的字符串为回文串。问你最终的数量和。

题解：为了让最后的字符串是回文串，对于前缀串kk，我们要先在ss中找到与前缀串kk一样的子串，再向后扩展，使得扩展的那部分字符串为回文串，即可实现。
我们先将tt进行反转，然后去遍历ss，那么现在的问题就转换成了找两个字符串的最长后缀（因为对于这部分所有的子串，他们的答案是一样的，所以最后求出来乘以最长后缀的长度就行了）。这里我们用哈希+二分来实现。
找出最长后缀后，我们假设当前遍历到sis_i，那么接下来我们要求以si+1s_{i+1}为起点的回文串数量。想到回文串就想到了马拉车。马拉车可以求以每个点为中心的最长回文半径，那么对于以这个点为终点，以ii - 最长回文半径的位置为起点，终点对于这段区间的贡献值为1。所以就转化成了区间修改，最终求每个点的权值的差分数组问题。稍微推一下就能从马拉车字符串推回到原字符串数组。

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

typedef unsigned long long ull;
typedef long long ll;

const int maxn=1e6 + 7;
const ull base = 131;
char s[maxn], t[maxn];
char ma[maxn<<1];
ll mp[maxn<<1], paw[maxn];
ull gap[maxn], hashS[maxn], hashT[maxn];

void init() {
	gap[0] = 1;
	for (int i = 1; i <= 1000000; ++i) {
		gap[i] = gap[i - 1] * base;
	}
}

void makeHash(char *s, ull *hash) {
	int len = strlen(s);
	for (int i = 0; i < len; ++i) {
		hash[i + 1] = hash[i] * base + (ull)s[i];
	}
}

ull getHash(int l, int r, ull *hash) {
	return hash[r + 1] - hash[l] * gap[r - l + 1];
}

void manacher(char *s){
	int len = strlen(s);
	int l=0;
	ma[l++]='$';
	ma[l++]='#';
	for(int i = 0;i < len; ++i){
		ma[l++] = s[i];
		ma[l++] = '#';
	}
	ma[l] = 0;
	ll mx = 0, id = 0;
	for (int i = 0; i < l; ++i){
		mp[i] = mx > i? min(mp[2 * id - i], mx - i) : 1;
		while (ma[i + mp[i]] == ma[i - mp[i]])	mp[i]++;
		if(i + mp[i] > mx){
			mx = i + mp[i];
			id = i;
		}
	}
	for (int i = 1; i < l; i++) {
		paw[(i >> 1) - (mp[i] >> 1)]++;
		paw[(i >> 1)]--;
	}
	for (int i = 1; i < len; ++i) {
		paw[i] += paw[i - 1];
	}
}

void solve() {
	int len = strlen(s);
	int lent = strlen(t);
	int l, r, mid;
	ll ans = 0;
	ll maxx;
	for (int i = 0; i < len - 1; ++i) {
		l = 1, r = i + 1;
		maxx = 0;
		while (l <= r) {
			mid = l + r >> 1;
			if (getHash(i - mid + 1, i, hashS) == getHash(lent - mid, lent - 1, hashT)) {
				maxx = mid;
				l = mid + 1;
			}
			else r = mid - 1;
		}
		ans += maxx * paw[i + 1];
	}
	printf("%lld\n", ans);
}

int main(){
	init();
	scanf("%s %s", s, t);
	reverse(t, t + strlen(t));
	manacher(s);
	makeHash(s, hashS);
	makeHash(t, hashT);
	solve();
	return 0;
}
文章目录
  1. A. Adrien and Austin
  2. D - Country Meow
  3. G - Pyramid
  4. I. Magic Potion
  5. J. Prime Game
  6. K. Kangaroo Puzzle
  7. M. Mediocre String Problem
|