2019 ACM-ICPC, Asia Nanjing Regional

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

REPLY 我到底会不会记忆化搜索？——Sstee1XD

比赛链接

A - A Hard Problem

solved by Sstee1XD. 0:09(+)

题意：给你11~nn的序列，求最小的k能使每个k大小的区间里都存在两个数，它们有倍数关系。

题解：最小的倍数是22，所以分下奇偶就直接开写。

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define endl "\n"
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
#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;
int n;
void run () {
	n = rd();
	if (n & 1) {
		printf("%d\n", n - 1 - (n - 1) / 2 + 2);
	}
	else printf("%d\n", n - n / 2 + 1);
}

int main () {
	int _T;
	_T = rd();
	while (_T--) run(); 
    return 0;
}

C - Digital Path

solved by Sstee1XD & lllllan. 03:22(+4)

题意：你需要在矩阵里找路径的数量。
路径应符合以下规定：

  • 每次只能上下左右扩展
  • 每次扩展到的值应比上一个值大11
  • 长度至少为44
  • 不能再继续扩展

题解：对于一个点来说，它能向大的地方扩展的数量是确定的，所以我们采用记忆化搜索来写。

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define endl "\n"
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
#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 = 1e3 + 7;
const ll mod = 1e9 + 7;
int n, m;
int maps[maxn][maxn];
ll dp[maxn * maxn][5];
int vis[maxn][maxn];
int go[][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int sx[1000007], sy[1000007];
int f;
int checkF(int x, int y) {
	int flag = 0;
	for (int i = 0; i < 4; ++i) {
		int fx = x + go[i][0], fy = y + go[i][1];
		if (fx < 1 || fx > n || fy < 1 || fy > m) continue;
		if (maps[fx][fy] == maps[x][y] - 1) return 0;
		if (maps[fx][fy] - maps[x][y] == 1) flag = 1;
	}
	return flag;
}

int check(int x, int y, int v) {
	if (x < 1 || x > n || y < 1 || y > m) return 0;
	if (maps[x][y] - v != 1) return 0;
	return 1;
}

int get(int x, int y) {
	return (x - 1) * m + y;
}

void dfs(int x, int y, int s) {
	int flag = 0;
	vis[x][y] = 1;
	for (int i = 0; i < 4; ++i) {
		int fx = x + go[i][0], fy = y + go[i][1];
		if (check(fx, fy, maps[x][y])) {
			flag = 1;
			if (!vis[fx][fy]) {
				dfs(fx, fy, s + 1);
			}
			for (int j = 1; j <= 4; ++j) {
				dp[get(x, y)][min(1 + j, 4)] += dp[get(fx, fy)][j];
				dp[get(x, y)][min(1 + j, 4)] %= mod;
			}
		}
	}
	if (!flag) dp[get(x, y)][1]++, dp[get(x, y)][1] %= mod;
}
void run () {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &maps[i][j]);
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (checkF(i, j)) sx[f] = i, sy[f++] = j;
		}
	}
	ll ans = 0;
	for (int i = 0; i < f; ++i) {
		dfs(sx[i], sy[i], 1);
		ans += dp[get(sx[i], sy[i])][4];
		ans %= mod;
	}
	printf("%lld\n", ans);
}

int main () {
	n = rd();
	m = rd();
	run();
    return 0;
}
lllllan赛后代码 
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
#include<bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 1e3 + 10;

int n, m;
int G[N][N];
int vis[N][N];
ll ans, dp[N][N][5];
int dir[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
inline int min (int a, int b) { return a < b ? a : b;}

inline void dfs (int x, int y) {
	int flag = 1;
	vis[x][y] = 1;
	_for (i, 0, 3) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if ((nx < 1 || nx > n || ny < 1 || ny > m) || G[nx][ny] != G[x][y] + 1) continue;
		flag = 0;
		if (!vis[nx][ny]) dfs(nx, ny);	//记忆化搜索 
		_for (k, 1, 4)	//继承序列中下一个点的dp值，注意＋1以及上限为4 
			dp[x][y][min(k + 1, 4)] = (dp[x][y][min(k + 1, 4)] + dp[nx][ny][k]) % mod;
	}
	if(flag) dp[x][y][1] = 1;	//flag为1表示为某个序列中的末尾，需要对dp[][][1]赋值为1 
}

int main () {
	scanf("%d%d", &n, &m);
	_for (i, 1, n) _for (j, 1, m) scanf("%d", G[i] + j);
	_for (i, 1, n) _for (j, 1, m) {
			int flag = -1;
			for (int k = 0; k < 4 && flag; k++) {
				int x = i + dir[k][0], y = j + dir[k][1];
				if (x >= 1 && x <= n && y >= 1 && y <= m) {
					if (G[x][y] == G[i][j] + 1) flag = 1;	//周围存在差值为1的数 
					if (G[x][y] == G[i][j] - 1) flag = 0;	//发现不是序列中的最小值取消搜索 
				}
			}
			if (flag == 1) {
				dfs(i, j);
				ans = (ans + dp[i][j][4]) % mod;
			}
		}
	printf("%lld\n", ans % mod);
    return 0;
}

H - Prince and Princess

solved by Sstee1XD. 04:17(+4)

题意：王子要娶公主，他要问（他并不知道他向谁提问）出席婚礼的所有人公主在哪。出席婚礼的人包括支持者（包括公主），反对者，无所谓者。支持者一定说实话，反对者和无所谓者可能说假话，问你王子最少要问几个人能知道公主在哪儿。

题解：注意支持者里包括公主自己，所以我们要特判1 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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define endl "\n"
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
#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;
int a, b, c;
void run () {
	a = rd(), b = rd(), c = rd();
	if (a <= b + c) {
		puts("NO");
	}
	else {
		puts("YES");
		if (a == 1 && b + c == 0) {
			printf("0\n");
		}
		else printf("%d\n", 2 * (b + c) + 1);
	}
}

int main () {
	run();
    return 0;
}

J - Spy

Solved by Sstee1XD. (-)

题意： 给你一个nn，接下来给你44行nn列的数字，分别代表敌方各个单位的能量，击败这个敌方单位能获得的点数，己方各个单位的能量以及己方nn个装备的能量。对于这nn个装备你可以装在任意一个己方单位上，并把能量加在对应的单位上。己方的一个单位会和一个敌方单位对上，若己方单位的能量大于敌方单位，即可获得对应的点数，但你并不知道己方单位会和哪个敌方单位对上。现在要求最终的数学期望乘上nn。

题解： 我们考虑固定己方单位的位置，然后枚举哪个装备装在这个己方单位的身上，再枚举他对上的敌方单位。这时我们发现我们可以把当前对上的敌方单位的位置也固定上，那么当前位置对整体的贡献为能获得的点数乘以(n−1)!(n - 1)!。由于答案最终要乘以nn，所以概率对答案已经没有影响了。这时我们对于装备的己方单位建边，边的权值为能获得点数，于是这道题目就变成了一道km问题。注意nn的数量过大，只能用n3n^3的板子写。

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

using namespace std;

typedef long long ll;
const int maxn = 407;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll a[maxn], b[maxn], c[maxn], d[maxn];
bool vis[maxn];
ll cap[maxn][maxn];
ll slack[maxn], l[maxn];
ll wx[maxn], wy[maxn], pre[maxn];
int n;

void bfs(int k)
{
    ll px, py = 0, yy = 0, d;
    memset(pre, 0, sizeof(pre));
    memset(slack, 0x3f, sizeof(slack));
    l[py] = k;
    while (l[py]) {
        px = l[py], d = INF, vis[py] = true;
        for(int i = 1;i <= n;i++)
            if(!vis[i])
            {
                if(slack[i] > wx[px] + wy[i] - cap[px][i])
                    slack[i] = wx[px] + wy[i] - cap[px][i], pre[i]=py;
                if(slack[i] < d) d = slack[i], yy = i;
            }
        for(int i = 0;i <= n; i++)
            if(vis[i]) wx[l[i]] -= d,wy[i] += d;
            else slack[i] -= d;
        py = yy;
    }
    while(py) l[py] = l[pre[py]], py = pre[py];
}
ll km(){
    memset(wx,0,sizeof(wx));
    memset(wy,0,sizeof(wy));
    memset(l,0,sizeof(l));
    for(int i = 1;i <= n; i++)
        memset(vis, 0, sizeof(vis)), bfs(i);

    ll ans = 0;
    for (int i = 1; i <= n; i++) ans += cap[l[i]][i];
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++) cin >> b[i];
    for (int i=1; i<=n; i++) cin >> c[i];
    for (int i=1; i<=n; i++) cin >> d[i];
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            for (int k=1; k<=n; k++){
                if (c[i] + d[j] > a[k]) cap[i][j] += b[k];
            }
        }
    }
    ll ans = km();
    cout << ans << "\n";
    return 0;
}

K - Triangle

solved by Tryna 03:59(+7)

题意： 给出三角形的三个顶点和一条线段的一个端点，问是否存在另外一个点和之前的端点构成一条线段，满足落在三角形边上，并且把三角形分成面积相等的两部分，起始点也需要在三角形边上。

题解： 赛后看了一下大家的bolg，基本上都是用二分写的，我觉得我的写法还挺好的。首先如果起始点不在三角形边上，直接输出 -1，如果起始点在边上，那么就一定能够找到另外一个点也在三角形边上把这个三角形分为面积相等的两部分，接下来我们就需要去找到这个点，这里我用到了高中时常用的求三角形面积公式$$S = \frac{1}{2} * \sin\theta * a * b $$

以上面这张图举例，A B C是给出的三角形的三个顶点， P也是给出的，我们想要找到Q，我的方法是：首先找到P所在的直线，然后找到在这条直线上找到离P远的顶点，以这个点为公共角去寻找Q，我们可以通过下面的方程找到BQ的长度$$\frac{1}{2} * \sin\ B * BC * BA = 2 * \frac{1}{2} * \sin\ B * BP * BQ$$
可以直接化简到$$BC * BA = 2 * BP * BQ $$
因为只有BQ是未知的所以可以容易得到BQ的值，进而就可以根据BA向量的方向来确定Q的坐标了。

代码

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
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
int sgn(double x){
	if(fabs(x) < eps) return 0;
	else return x < 0 ? -1 : 1;
}
struct Point{
	double x, y;
	Point(){}
	Point(double x, double y):x(x),y(y){}
	Point operator - (Point B){
		return Point(x - B.x, y - B.y);
	}
}P[5], pos[5];

struct Line{
	Point p1, p2;
	Line(){}
	Line(Point p1, Point p2):p1(p1),p2(p2){}
}L[5];

double Dist(Point A, Point B){
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double Dot(Point A, Point B){
	return A.x * B.x + A.y * B.y;
}

double Cross(Point A, Point B){
	return A.x * B.y - A.y * B.x;
}

bool Point_on_seg(Point p, Line v){
	return sgn(Cross(p - v.p1, v.p2 - v.p1)) == 0 &&
	sgn(Dot(p - v.p1, p - v.p2)) <= 0;
}

int t;
int main () {
	scanf("%d", &t);
	while(t--){
		for(int i = 1; i <= 4; i++) scanf("%lf %lf", &P[i].x, &P[i].y);
		L[1] = Line(P[1], P[2]);
		L[2] = Line(P[2], P[3]);
		L[3] = Line(P[3], P[1]);
		if(Point_on_seg(P[4], L[1]) == 0 && Point_on_seg(P[4], L[2]) == 0 && Point_on_seg(P[4], L[3]) == 0){
			printf("-1\n");
			continue;
		}
		int p = 0;
		for(int i = 1; i <= 3; i++){
			if(Point_on_seg(P[4], L[i]) == 1){
				p = i;
				break;
			}
		}
		if(p == 1)	pos[1] = P[3];	
		else if(p == 2) pos[1] = P[1];
		else pos[1] = P[2];
		if(Dist(P[4], L[p].p1) > Dist(P[4], L[p].p2)){
			pos[2] = L[p].p1;
			pos[3] = L[p].p2;
		} 
		else{
			pos[2] = L[p].p2;	
			pos[3] = L[p].p1;
		} 
		double cnt = Dist(P[4], pos[2]) / Dist(pos[2], pos[3]);
		cnt = 0.5 / cnt;
		double resultX = cnt * (pos[1].x - pos[2].x) + pos[2].x;
		double resultY = cnt * (pos[1].y - pos[2].y) + pos[2].y;
		printf("%.12f %.12f\n", resultX, resultY);
	}
    return 0;
}
文章目录
  1. A - A Hard Problem
  2. C - Digital Path
  3. H - Prince and Princess
  4. J - Spy
  5. K - Triangle
|