2020 ACM-ICPC, Asia Nanjing Regional

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

比赛链接

A - Ah, It’s Yesterday Once More

solved by Tryna.(-)

题意： 构造一个地图去hack18hack18年南京的KK题，hackhack率达到2525%则算ACAC.

思路： 构造的原则是使路尽可能地长，也就是尽可能使11多。

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
#include<bits/stdc++.h>
using namespace std;
int main() {
    puts("20 20");
    puts("10111011111110111011");
    puts("11101100100101101101");
    puts("10110110110110110111");
    puts("01011011011011011001");
    puts("11001101101101101101");
    puts("01110110110110110110");
    puts("11011011011011011011");
    puts("01101101101101101110");
    puts("10110110110110110011");
    puts("11011011011011011010");
    puts("01001101101101101101");
    puts("01110110110110110111");
    puts("11011011011011011010");
    puts("01101101101101101111");
    puts("10110110110110110101");
    puts("10011011011011011011");
    puts("11101101101101101100");
    puts("10110110110110110111");
    puts("11011011010010011010");
    puts("01101110111111101111");
	return 0;
}

E - Evil Coordinate

solved by all. 3:21(+3)

题意： 二维整点平面，起点在(0,0)(0, 0)，给你行走路径和不能经过的点，问你能否对原行走路径进行排列，使其绕过不能经过的点。

思路： 终点或者起点与坏点重合的情况下一定不行。然后我们分类讨论一下坏点与分别与终点和起点的横纵坐标有一个重合的情况。

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

char s[N], ans[N];
int u, d, r, l, x, y, dx, dy, now;

void gaoX() {
	dx = 0;
	if (x > 0) {
		while (l) {
			putchar('L');
			l--;
			dx--;
		}
		while (r && dx < x - 1) {
			putchar('R');
			r--;
			dx++;
		}
	} else {
		while (r) {
			putchar('R');
			r--;
			dx++;
		}
		while (l && dx > x + 1) {
			putchar('L');
			l--;
			dx--;
		}
	}
}

void gaoY() {
	dy = 0;
	if (y > 0) {
		while (d) {
			putchar('D');
			d--;
			dy--;
		}
		while (u && dy < y - 1) {
			putchar('U');
			u--;
			dy++;
		}
	} else {
		while (u) {
			putchar('U');
			u--;
			dy++;
		}
		while (d && dy > y + 1) {
			putchar('D');
			d--;
			dy--;
		}
	}
}

void solve() {
	u = d = r = l = 0;
	scanf("%d %d", &x, &y);
	scanf("%s", s);
	int len = strlen(s);
	dx = 0, dy = 0;
	for (int i = 0; i < len; ++i) {
		if (s[i] == 'U') u++, dy++;
		if (s[i] == 'D') d++, dy--;
		if (s[i] == 'R') r++, dx++;
		if (s[i] == 'L') l++, dx--;
	}
	if ((dx == x && dy == y) || (x == 0 && y == 0)) {
		puts("Impossible");
		return;
	}
	if (dx == x) {
		gaoX();
		if (dx == x && ((u > d && dy > y && y >= 0) || (u < d && dy < y && y <= 0))) {
			puts("Impossible");
			return;
		}
//		gaoY();
        if (y < 0) {
        	while (u--) {
				putchar('U');
			}
			while (d--) {
				putchar('D');
			}
		} else {
			while (d--) {
				putchar('D');
			}
			while (u--) {
				putchar('U');
			}
		}
		while (l--) {
			putchar('L');
		}
		while (r--) {
			putchar('R');
		}
		puts("");
	} else if (dy == y){
		gaoY();
		if (dy == y && ((r > l && dx > x && x >= 0) || (r < l && dx < x && x <= 0))) {
			puts("Impossible");
			return;
		}
//		gaoX();
        if (x > 0) {
        	while (l--) {
				putchar('L');
			}
			while (r--) {
				putchar('R');
			}
		} else {
			while (r--) {
				putchar('R');
			}
			while (l--) {
				putchar('L');
			}
		}
		while (u--) {
			putchar('U');
		}
		while (d--) {
			putchar('D');
		}
		puts("");
	} else if (y == 0) {
		while (u--) {
			putchar('U');
		}
		while (d--) {
			putchar('D');
		}
		while (l--) {
			putchar('L');
		}
		while (r--) {
			putchar('R');
		}
		puts("");
	} else {
		while (l--) {
			putchar('L');
		}
		while (r--) {
			putchar('R');
		}
		while (u--) {
			putchar('U');
		}
		while (d--) {
			putchar('D');
		}
		puts("");
	}
}

int main() {
	int t = 1;
	scanf("%d", &t);
	while (t--) solve();
	return 0;
}
/*
1
1 0
RRD
*/

F - Fireworks

solved by Tryna.(-)

题意： 做每个烟花要花nn的时间，放掉所有的烟花要花mm的时间，每个烟花有p∗1e−4p * 1e^{-4}的概率perfectperfect，只有当出现了perfectperfect的烟花才会去休息。问花费的最少期望时间是多少。

思路： 每次放掉所有烟花可以看成是一个事件，所以这个问题可以转化为一直重复这个事件，直到某次事件出现了perfectperfect的烟花。所以这就变成了一个几何分布，所以假设每次事件一共做了kk个烟花，那么至少有一个烟花perfectperfect概率就是1−(1−p∗1e−4)k1 - (1 - p * 1e^{-4})^k, 那么期望就是11−(1−p∗1e−4)k\frac{1}{1 - (1 - p * 1e^{-4})^k}，那么再乘上每次花费的时间，就是期望时间k∗n+m1−(1−p∗1e−4)k\frac{k*n + m}{1 - (1 - p * 1e^{-4})^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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int t;
double n, m, p;
double f(int k) {
	return (k * n + m) / (1 - pow(1 - p, k));
}
void solve() {
	scanf("%lf %lf %lf", &n, &m, &p);
	p = p * 0.0001;
	int l = 1, r = 1000000000, midr, midl;
	while(l < r) {
		midl = l + (r - l) / 3;
		midr = r - (r - l) / 3;
		if(f(midl) > f(midr))
			l = midl + 1;
		else
			r = midr - 1;
	}
	printf("%.10f\n", f(r));
}
int main() {
	scanf("%d", &t);
	while(t--)
		solve();
	return 0;
}

H - Harmonious Rectangle

solved by Tryna.(-)

题意： 定义完美矩形为相邻的两个顶点为一样的颜色，同时另外两个相邻的点也为一样的颜色。一共有三种颜色可以染，给出xx和yy的范围，求存在完美矩形的方案数。

题解： 先这么想，比如这两列

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10
我们一共有三种颜色，那么只有9种染法
1 1 1 2 2 2 3 3 3
1 2 3 1 2 3 1 2 3
所以对于上面两列，根据抽屉原理，必定存在完美矩形
根据这个结论我们就可以将结果分为两类，

  • nn或mm大于9，答案就是3n+m3^{n + m}
  • 对于其他情况我们可以暴搜打表求出答案。
打表 
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
#include<bits/stdc++.h>
// #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-4
#define endl "\n"
const int maxn = 1e1 + 10;
const int mod = 1e9 + 7;
const double startT = 100;
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 t, a[maxn][maxn];
ll n, m, res;
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;
}
bool check(int x1, int x2, int y1, int y2) {
    if(a[y1][x1] == a[y2][x1] && a[y2][x2] == a[y1][x2]) return true;
    if(a[y1][x1] == a[y1][x2] && a[y2][x2] == a[y2][x1]) return true;
    return false;
}
void dfs(int x, int y) {
    for(int color = 0; color < 3; color++) {
        int x2 = x, y2 = y;
        a[y2][x2] = color;
        int f = 1;
        for(int y1 = 1; y1 < y2&&f; y1++) {
            for(int x1 = 1; x1 < x2&&f; x1++) {
                if(check(x1, x2, y1, y2)) {
                    f = 0;
                    res += quick_power(3, (n - y2) * m + (m - x2));
                    res %= mod;
                }
            }
        }
        // if(n == 2 && m == 3) printf("*%d\n", res);
        if(f) {
            x2++;
            if(x2 > m) {
                x2 = 1;
                y2++;
                if(y2 > n)
                    continue;
            }
            dfs(x2, y2);
        }
    }
}
ll res_dfs() {
    res = 0;
    dfs(1, 1);
    return res;
}
void solve() {
    for(n = 1; n <= 9; n++) {
        for(m = 1; m <= 9; m++) {
            memset(a, 0, sizeof(a));
            if(n == 1 || m == 1) printf("0, ");
            else printf("%lld, ", res_dfs());
        }
        puts("");
    }
}
int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0);
    // scanf("%d", &t);
    // while(t--)
    freopen("1.txt", "w", stdout);
    solve();
    // system("pause");
	return 0;
}

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
int t;
ll n, m;
ll quick_power(ll n, ll k){
	ll ans=1;
	while(k){
		if(k&1){
			ans=(ans*n)%mod;
		}
		n=n*n%mod;
		k>>=1;
	}
	return ans%mod;
}
ll res[9][9] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 15, 339, 4761, 52929, 517761, 4767849, 43046721, 387420489, 
    0, 339, 16485, 518265, 14321907, 387406809, 460338013, 429534507, 597431612, 
    0, 4761, 518265, 43022385, 486780060, 429534507, 792294829, 175880701, 246336683, 
    0, 52929, 14321907, 486780060, 288599194, 130653412, 748778899, 953271190, 644897553, 
    0, 517761, 387406809, 429534507, 130653412, 246336683, 579440654, 412233812, 518446848, 
    0, 4767849, 460338013, 792294829, 748778899, 579440654, 236701429, 666021604, 589237756, 
    0, 43046721, 429534507, 175880701, 953271190, 412233812, 666021604, 767713261, 966670169, 
    0, 387420489, 597431612, 246336683, 644897553, 518446848, 589237756, 966670169, 968803245
};
void solve() {
    scanf("%lld%lld", &n, &m);
    if(n == 1 || m == 1) puts("0");
    else if(m > 9 || n > 9) printf("%lld\n", quick_power(3, n * m));
    else printf("%lld\n", res[n - 1][m - 1]);
}
int main() {
    scanf("%d", &t);
    while(t--)
        solve();
	return 0;
}

K - K Co-prime Permutation

solved by all.0:16(+)

题意： 给出nn和kk，构造出一个nn的全排列a[n]a[n]使得刚好有kk个gcd(a[i],i)gcd(a[i], i)为1。

思路： 对于任意两个相邻的数它们的gcdgcd为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
#include<bits/stdc++.h>
using namespace std;
int n, k;
int main() {
    scanf("%d %d", &n, &k);
    if(k == 0)
        puts("-1");
    else{
        if(k % 2 == 1) {
            printf("1 ");
            for(int i = 2; i <= k; i += 2) {
                printf("%d %d ", i + 1, i);
            }
            for(int i = k + 1; i <= n; i++)
                printf("%d%c", i, " \n"[i == n]);
        }
        else{
            for(int i = 1; i <= k; i += 2) {
                printf("%d %d ", i + 1, i);
            }
            for(int i = k + 1; i <= n; i++)
                printf("%d%c", i, " \n"[i == n]);
        }
    }
    return 0;
}

L - Let’s Play Curling

solved by Sstee1XD & Tryna. 0:59(+1)

题意： 给出两个整点序列a,ba, b。对于一个实数点来说，这个点能获得的分数为存在多少个aia_i，使得aia_i到这个点的距离比bb中所有点到这个点的距离都要小。问最大得分是多少。

思路： 很容易想到，对aa和bb分别从小到大排序后，值在bib_i ~bi+1b_{i + 1}之间的aja_j数量，都可以记作一次的得分。我们可以通过二分求这个数量。然后注意特判首尾的情况。

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

using namespace std;

const int N = 5e5 + 7;

int n, m;
int a[N], b[N];

void solve() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int j = 1; j <= m; ++j) scanf("%d", &b[j]);
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + m);
	int pre = 0, suf = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i] >= b[1]) break;
		pre = i;
	}
	for (int i = n; i >= 1; --i) {
		if (a[i] <= b[m]) break;
		suf++;
	}
	int ans = max(pre, suf);
	if (m == 1) {
		if (ans) printf("%d\n", ans);
		else puts("Impossible");
		return;
	}
//    int ans = 0;
	for (int i = 1; i < m; ++i) {
		int p = upper_bound(a + 1, a + 1 + n, b[i]) - a;
		if (p > n) break;
		int s = lower_bound(a + 1, a + 1 + n, b[i + 1]) - a - 1;
		if (s < p) continue;
		ans = max(ans, s - p + 1);
	}
	if (ans) printf("%d\n", ans);
	else puts("Impossible");
}

int main() {
	int t = 1;
	scanf("%d", &t);
	while (t--) solve();
	return 0;
}
/*
1
4 2
1 2 5 6
3 4
*/

M - Monster Hunter

solved by lllllan. (-)

题意： 一棵树上每个节点都有对应的权值，计算这棵树的总权值的话，如果一个节点有父节点，则该节点记两倍的权值。求分别从树上删除11到nn个节点，树上能计算到的最小权值和。

题解： 计算权值的关键点在于【存在父节点，则该节点记两倍的权值】，想要求最小的权值和，也就是说需要尽可能多地删除一些权值贡献比较大的点。

贪心？ 训练的时候的第一反应就是贪心，删除1到n个点，每次都删除当前权值贡献最大的点，删到最后，就求出全部答案。 || 选取1到n个点，每次选取当前权值贡献最小的点，选到最后即为全部答案。但是，这道题不能贪心。
【懒得画图解释为什么不能贪心了，自己思考一下好了】

既然这样，就依靠树形DP来求解。

比较容易想到定义dp[i][j]来表示以节点i为根节点的子树下选取j个节点之后获得的最小权值和。
但是在状态转移的时候，有直接父子关系的两个节点的权值贡献是会相互影响的。所以应当定义三维的dp，多一维记录该根节点是否选取。

其实确定好三维DP的定义之后，状态转移还是比较明确的，不再赘述。

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

vector<int> G[maxn];
ll dp[maxn][maxn][2];
ll w[maxn];

int sz[maxn];

void dfs (int u) {
	sz[u] = 1;
	dp[u][0][0] = 0;
	dp[u][1][1] = w[u];
	for (auto v : G[u]) {
		dfs(v);
		for (int j = sz[u]; j >= 0; --j) {
			for (int k = sz[v]; k >= 0; --k) {
				dp[u][j + k][1] = min(dp[u][j + k][1], dp[u][j][1] + min(dp[v][k][1] + w[v], dp[v][k][0]));
				dp[u][j + k][0] = min(dp[u][j + k][0], dp[u][j][0] + min(dp[v][k][1], dp[v][k][0]));
			}
		}
		sz[u] += sz[v];
	}
}

void run () {
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			dp[i][j][0] = dp[i][j][1] = INF;
	for (int i = 1; i <= n; ++i) G[i].clear();
	for (int i = 2; i <= n; ++i) {
		int u; scanf("%d", &u);
		G[u].push_back(i);
	}
	for (int i = 1; i <= n; ++i) scanf("%lld", w + i);
	
	dfs(1);
	for (int i = n; i >= 0; --i) {
		printf("%lld%c", min(dp[1][i][0], dp[1][i][1]), " \n"[i == 0]);
	}
}

int main () {
	int _; scanf("%d", &_);
	while (_--) run();
	return 0;
}
文章目录
  1. A - Ah, It’s Yesterday Once More
  2. E - Evil Coordinate
  3. F - Fireworks
  4. H - Harmonious Rectangle
  5. K - K Co-prime Permutation
  6. L - Let’s Play Curling
  7. M - Monster Hunter
|