2020 ICPC Universidad Nacional de Colombia Programming Contest

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

比赛链接

solved by Tryna. (-)

题意 ：给出四个点，前两个点确定一条直线，后面两个点确定另外一条直线。有两个人，分别从两条直线的起点以同样的速度出发，当一个人到达终点时，另外一个人继续前进，问两个人移动过程中的最短距离。

题解 ：这两个人前进过程中的距离函数是一个有极值的凹函数，所以只需要三分一下时间，求出该时间下两点的坐标，然后在求出距离。需要注意一个人到达终点后，另外一个人继续前进，所以需要分成两段，第一段为0 - min(d1,d2)，第二段为min(d1,d2) - max(d1,d2) 。还有个难点就是求出该时间下各个点的坐标。需要预先用反正切求出直线与x轴的夹角，然后配合正弦函数和余弦函数求出点的坐标，最后在计算两点距离。注意这题卡精度，要限定三分的次数。

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;    
const double pi = acos(-1);
#define inf 0x3f3f3f3f
#define ll long long
const int maxn = 20010;
const int mod = 1e9 + 7;
double X1,X2,X3,X4,Y1,Y2,Y3,Y4,angle1,angle2,d1,d2,midl,midr;
double getDist(double ax, double ay, double bx, double by){
    return sqrt((ax - bx)*(ax - bx) + (ay - by)*(ay - by));
}
double f(double t){
    double t1 = min(d1, t);
    double t2 = min(d2, t);
    double xt1 = t1*cos(angle1);
    double yt1 = t1*sin(angle1);
    double xt2 = t2*cos(angle2);
    double yt2 = t2*sin(angle2);
    double _x1 = X1 + xt1;
    double _y1 = Y1 + yt1;
    double _x2 = X3 + xt2;
    double _y2 = Y3 + yt2;
    return getDist(_x1, _y1, _x2, _y2);
}
double sf(double l, double r){
    for(int i = 1;i <= 10000; i++){
        midl = (l + r)/2;
        midr = (midl + r)/2;
        if(f(midl) > f(midr)) l = midl;
        else r = midr;
    }
    return f(midr);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>X1>>Y1>>X2>>Y2;
    cin>>X3>>Y3>>X4>>Y4;

    angle1 = atan2(Y2 - Y1, X2 - X1);
    angle2 = atan2(Y4 - Y3, X4 - X3);
    
    d1 = getDist(X1,Y1,X2,Y2);
    d2 = getDist(X3,Y3,X4,Y4);
    
    double mn = min(d1,d2);
    double mx = max(d1,d2);
    double result = min(sf(0, mn), sf(mn, mx));
    cout<<fixed<<setprecision(12)<<result<<endl;
    return 0;
}

B. Baby name

solved by Sstee1XD. 03:03(+3)

题意 ：给你父亲和母亲的名字，各取父亲和母亲名字的一个字串，将它们拼在一起成为子代的名字，问最大字典序的名字。

题解：分别把父母亲名字中最大的字母的下标记录下来，最后再比较各个下标开始的字串字典序大小。这里注意一下连续相同的字母只用取第一位，比较连续的字母是没有意义的。得到两个字符串的下标之后，先输出父亲的第一个字母，再一个个比较，最后输出母亲的字串。

P.S：刚开始没想清楚直接冲了一发，后来想出来写代码没写完整，但是以为会RE，报了WA，考虑了很久才交最后一发。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
 
#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...);
}
const int maxn = 2e5 + 7;
 
char s1[maxn], s2[maxn];
 
int m1 = 0, m2 = 0;
int n1 = 0, n2 = 0;
 
int G1[maxn >> 1], G2[maxn >> 1];
 
int gao(int G[], int n, int len, char s[]) {
	int ans = G[0];
	for (int i = 1; i <= n; ++i) {
		int tmp = G[i];
		int a = ans;
		while (tmp < len && s[a] == s[tmp]) {
			a++;
			tmp++;
		}
		if (tmp < len && s[a] < s[tmp]) ans = G[i];
	}
	return ans;
}
 
void run(){
	int len1 = strlen(s1), len2 = strlen(s2);
	G1[0] = 0, G2[0] = 0;
	for (int i = 1; i < len1; ++i) {
		if (s1[i] > s1[m1]) {
			m1 = i;
			n1 = 0;
			G1[n1] = i;
			while (i < len1 && s1[i + 1] == s1[i]) ++i;
		}
		else if(s1[i] == s1[m1]) {
			G1[++n1] = i;
			while (i < len1 && s1[i + 1] == s1[i]) ++i;
		}
	}
	for (int i = 1; i < len2; ++i) {
		if (s2[i] > s2[m2]) {
			m2 = i;
			n2 = 0;
			G2[n2] = i;
			while (i < len2 && s2[i + 1] == s2[i]) ++i;
		}
		else if(s2[i] == s2[m2]) {
			G2[++n2] = i;
			while (i < len2 && s2[i + 1] == s2[i]) ++i;
		}
	}
	m1 = gao(G1, n1, len1, s1);
	m2 = gao(G2, n2, len2, s2);
	printf("%c", s1[m1]);
	m1++;
	while (m1 < len1 && s1[m1] >= s2[m2]) {
		printf("%c", s1[m1++]);
	}
	for (int i = m2; i < len2; ++i) printf("%c", s2[i]);
}
 
int main(){
	scanf("%s %s", s1, s2);
	run();
	return 0;
}

E. Enter to the best problem of this contest!

solved by Sstee1XD. 01:37(+1)

题意 : 一个人藏在一个最多2929层的二叉树里，你最多可以询问29次，每次询问一个节点，它会返回人藏在的节点和你询问的节点的距离，最后输出人所在的节点。

题解：这题运用到二叉树的性质。我们第一次询问点11，即可得到点所在的深度。然后每次询问最左边的节点，设得到的距离为dd，当前节点的层数减去d2\frac{d}{2}即可得到它和目标节点的LCALCA，就能确定目标节点在另一边的子树上。重复这个操作就能得到目标节点的位置。在极端情况下，每次询问只能让子树的层数减少11，由于第一次询问并不能减少子树的层数，所以为了保证2929次能找完，最后询问到d<=2d <= 2即停止。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define endl "\n"
 
#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...);
}
 
int qpow(int a, int b) {
	int res = 1;
	for(; b; b >>= 1) {
		if (b & 1) res *= a;
		a *= a;
	}
	return res;
}
 
int n;
 
void gao(int d) {
	int now = qpow(2, d);
	d = 10;
	while (d > 2) {
		cout << endl << now << endl;
		cout.flush();
		cin >> d;
		if (d == 0) break;
		now /= qpow(2, d / 2);
		now = now * 2 + 1;
		now *= qpow(2, d / 2 - 1);
	}
	cout << endl << "! " << now;
	cout.flush(); 
}
 
void run(){
	int d;
	cout << 1 << endl;
	cout.flush();
	cin >> d;
	if (d == 0) {
		cout << endl << "! 1" << endl;
		return;
	}
	gao(d);
}
 
int main(){
//	freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	run();
	return 0;
}

G. Great dinner

solved by Tryna .1:04(+1)

题解 ：n！除 m^2

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
 
#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...);
}
const ll mod = 1e9 + 7;
const int maxn = 100010;
int n , m;
ll ans = 1;
int main() {
	cin >> n >> m;
	for(int i = 1, u, v; i <= m; i++) cin >> u >> v;
	for(int i = 2; i <= n ; i++) {
		ans = ans * i;
		if(ans % 2 == 0 && m) {
			m--;
			ans /= 2;
		}
		if(ans >= mod)	ans %= mod;
	}
	cout << ans << endl;
	return 0;
}

I. Incredible photography

solved by Sstee1XD.(-)

题意 ：给你一段序列，以某点为起点，你的移动规则是找到一个你能看到的高度严格大于你的点，然后你可以移动到那个点，之后又可以以相同的规则进行移动。求出以每个点为起点时能移动的最长距离。

题解 ：每个点都要找，很像一道记忆化搜索，又看到了视野中严格大于，就想到了单调栈，所以就用单调栈去维护左右要去的点就行了。当视野中有相同高度的点时，我们要想移动的距离最长，就要选择能看到的最远的点，同时也要注意到，相同高度的点可能是不连续的，比如5 3 5 3 5这个例子。最后debug的时候也是过了这个例子A的，但是感觉写得有点麻烦。

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

#define endl "\n"

typedef long long ll;

const int maxn = 1e5 + 7;
ll l[maxn], r[maxn], n, h[maxn], ans[maxn];
ll sta[maxn], top;

vector<ll> G[maxn];

ll dfs(int u) {
    if (ans[u] != -1) return ans[u];
    ll tl = 0, tr = 0;
    if (l[u] != 0) tl = max(u - l[u] + dfs(l[u]), tl);
    if (r[u] != 0) tr = max(r[u] - u + dfs(r[u]), tr);
    ans[u] = max(tl, tr);
    return ans[u];
}


void solve() {
    memset(ans, -1, sizeof(ans));
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) {
        int left = i;
        int tag = 0;
        while (h[i] == h[i + 1] && i < n) i++;
        while (top && h[i] >= h[sta[top - 1]]) {
            if (h[sta[top - 1]] == h[i]) {
                tag = sta[top - 1];
                break;
            }
            r[sta[top - 1]] = i;
            G[i].push_back(sta[top - 1]);
            top--;
        }
        for (int j = left; j <= i; ++j) {
            sta[top++] = j;
        }
        if (tag) {
            for (int j = 0; j < G[tag].size(); ++j) {
                G[i].push_back(G[tag][j]);
                r[G[tag][j]] = i;
            }
        }
    }
    top = 0;
    for (int i = 1; i <= n; ++i) G[i].clear();
    for (int i = n; i >= 1; --i) {
        int tag = 0;
        int right = i;
        while (h[i] == h[i - 1] && i > 1) i--;
        while (top && h[i] >= h[sta[top - 1]]) {
            if (h[sta[top - 1]] == h[i]) {
                tag = sta[top - 1];
                break;
            }
            l[sta[top - 1]] = i;
            G[i].push_back(sta[top - 1]);
            top--;
        }
        for (int j = right; j >= i; --j) {
            sta[top++] = j;
        }
        if (tag) {
            for (int j = 0; j < G[tag].size(); ++j) {
                G[i].push_back(G[tag][j]);
                l[G[tag][j]] = i;
            }
        }
    }
    for (int i = 1; i <= n; ++i) dfs(i);
    for (int i = 1; i <= n; ++i) {
        if (i > 1) cout << ' ';
        cout << ans[i];
    }
    cout << endl;
 }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin >> n;
    solve();
    return 0;
}

K. Katastrophic sort

solved by Tryna.0:29(+)

题意 ：给定两个只含字母和数字的字符串，保证字母部分长度相等，字母和字母比较，若相同，则比较数字。

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;
typedef long long ll;
const int inf = 0x3f3f3f3f;
 
#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...);
}
const int maxn = 100010;
char a1[maxn],b2[maxn],a2[maxn],b1[maxn];
string st1,st2;
int main(){
	cin>>st1;
	cin>>st2;
	int cnt = 0;
	for(int i = 0;i<st1.size();i++){
		if(st1[i]<='z'&&st1[i]>='a'){
			cnt++;
			a1[cnt] = st1[i];
		}
		else break;
	}
	for(int i = cnt;i<st1.size();i++) a2[i-cnt+1] = st1[i];
	cnt = 0;
	for(int i = 0;i<st2.size();i++){
		if(st2[i]<='z'&&st2[i]>='a'){
			cnt++;
			b1[cnt] = st2[i];
		}
		else break;
	}
	for(int i = cnt;i<st2.size();i++) b2[i-cnt+1] = st2[i];
	if(strcmp(a1+1,b1+1)>0){
		cout<<">"<<endl;
	}
	else if(strcmp(a1+1,b1+1)<0) cout<<"<"<<endl;
	else{
		if(strlen(a2+1)<strlen(b2+1)) cout<<"<"<<endl;
		else if(strlen(a2+1)>strlen(b2+1)) cout<<">"<<endl;
		else{
			if(strcmp(a2+1,b2+1)>0) cout<<">"<<endl;
			else if(strcmp(a2+1,b2+1)<0) cout<<"<"<<endl;
			else cout<<"="<<endl;
		}
	}
	return 0;
}

L. Lonely day

solved by lllllan、Sstee1XD.04:52(+13)

题意： 给定一个n*m的图，途中的’S’为起点，‘E’为终点。每次移动只能横向或纵向地移向最近的一个干净的点’.'或终点，'X’为脏的点。如果能到达终点，则输出步数最少并且字典序最小的路径（下移为D、左移为L、右移为R、上移为U）。否则输出-1。

曲折经历： 比赛时想的没有那么周到，用BFS+DFS，结构体里携带各种参数，并且实时传递移动路径，导致空间占用比较大，加上本来算法的效率就不高，所以WA的和TLE的次数累计到达了13发。最后各种修改，卡常1980ms极限AC。又因为参加过这个比赛和做过这个题目的人很少，我甚至找不到题解可以学习。所以自己又花了一个上午的时间研究，最后得出一个时间和空间以及代码长度都最优的代码（对我的能力而言）

最终思路：

  • BFS。 众所周知：一个图 + 起点到终点 + 最短路径 = BFS。定义一个结构体的队列，结构体node中只需携带某个点的坐标即可。定义vis[][] 避免重复访问。
  • pre_x[][]、pre_y[][]。 因为广搜的特性，从某个点出发，最多可能有四个可达的目标点。而因为vis避免重复访问，每个点一定只能来自于一个点。所以定义两个数组来记录某一个干净的点的前驱节点的坐标。
  • DFS。 用BFS一直搜索到终点，结束广搜。我们记录路径的方式是用两个pre数组记录前驱节点的坐标，并没有记录移动的方向。所以可以通过dfs从终点递推回起点，比较每个点与前驱节点的坐标关系，记录下移动方向。最后倒叙输出答案即可。
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;
const int N = 2e3 + 10;
int n, m;
int sx, sy, cnt;	//sx\sy记录起点坐标。cnt为路径的字符个数
int pre_x[N][N];	//记录前驱节点的坐标
int pre_y[N][N];	
int vis[N][N];		//访问标记，避免重复访问
char G[N][N];		//存图
char ans[2 * N];	//记录路径
int dir[][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char Dir[] = "DLRU";
struct node {	int x, y;};
 
int check(int x, int y) {	//检查移动后是否还在图的范围内
	if(x < 1 || x > n || y < 1 || y > m)	return 0;
	return 1;
}

void dfs(int x, int y) {	//从终点推回起点，标出移动路径
	if(x == sx && y == sy){	//回到起点，输出答案
		cout << cnt << endl;
		for(int i = cnt - 1; i >= 0; i--)	cout << ans[i];
		return;
	}
	int prex = pre_x[x][y];
	int prey = pre_y[x][y];
	if(prey == y)		//比较节点与前驱节点的关系，得出移动方向
		if(prex < x)	ans[cnt++] = Dir[0];
		else			ans[cnt++] = Dir[3];
	else
		if(prey < y)	ans[cnt++] = Dir[2];
		else			ans[cnt++] = Dir[1];
	dfs(prex, prey);
}
 
void BFS() {
	queue<node> Q;
	Q.push({sx, sy});
	vis[sx][sy] = 1;
	while(!Q.empty()) {
		node u = Q.front(); Q.pop();
		if(G[u.x][u.y] == 'E') {	//找到终点，dfs找到移动路径
			dfs(u.x, u.y);	return ;
		}
		for(int i = 0; i < 4; i++) {
			int nex = u.x + dir[i][0];
			int ney = u.y + dir[i][1];
			while(check(nex, ney)) {	
				if(vis[nex][ney])	break;
				if(G[nex][ney] == '.' || G[nex][ney] == 'E'){
					vis[nex][ney] = 1;
					pre_x[nex][ney] = u.x;
					pre_y[nex][ney] = u.y;
					Q.push({nex, ney});
					break;	//找到最近的第一个干净点，插入队列即可推出
				}
				//干净点不一定相邻，可能隔着几个'X'才能到达，所以需要不断移动查找
				nex += dir[i][0], ney += dir[i][1];
			}
		}
	}
	cout << -1 << endl;
}
 
int main() {
	ios :: sync_with_stdio(false);	cin.tie(0);	cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) 
		for(int j = 1; j <= m; j++) {
			cin >> G[i][j];
			if(G[i][j] == 'S')
				sx = i, sy = j;
		}
	BFS();
	return 0;
}

M. Magic spells

solved by Sstee1XD. 00:52(+2)

题意：给你一个主串，然后给你n个子串，询问是否存在公共子序列符合子串，输出能符合的最长的子串。

题解：用一个dpdp二维数组来记录这位之后各个字母第一次出现的位置，从后往前预处理一下，就可以开始做了。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
 
#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...);
}
 
const int maxn = 2e5 + 10;
char s[maxn];
int dp[maxn][30];
int id[maxn];
int ch(char c) {
	return c - 'a' + 1;
}
int n;
char str[maxn], ans[maxn];
void run(){
	memset(id, -1, sizeof(id));
	memset(dp, -1, sizeof(dp));
	int len = strlen(s);
	id[ch(s[len - 1])] = len - 1;
	for (int i = len - 2; i >= 0; --i) {
		for (int j = 1; j <= 26; ++j) dp[i][j] = id[j];
		id[ch(s[i])] = i;
	}
	scanf("%d", &n);
	while (n--) {
		scanf("%s", str);
		int f = id[ch(str[0])];
		int num = 1;
		if (f == -1) {
			puts("IMPOSSIBLE");
			continue;
		}
		int rear = strlen(str);
		f = dp[f][ch(str[num])];
		while (f != -1 && num < rear) {
			num++;
			f = dp[f][ch(str[num])];
		}
		str[num] = '\0';
		printf("%s", str);
		puts("");
	}
}
 
int main(){
	scanf("%s", s);
	run();
	return 0;
}
文章目录
  2. B. Baby name
  3. E. Enter to the best problem of this contest!
  4. G. Great dinner
  5. I. Incredible photography
  6. K. Katastrophic sort
  7. L. Lonely day
  8. M. Magic spells
|