2021-04-05

2019 ICPC Malaysia National

字数统计: 2.6k字 | 阅读时长: 15分

solved	A	B	C	D	E	F	G	H	I	J	K
9 / 11	O	O	O	·	O	O	·	O	O	O	O

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

比赛链接

A. Mental Rotation

Solved by Sstee1XD. 0:54(+)

思路： 按照题意模拟即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

char maps[N][N];
int n;
char s[N];
char mp[N][5];

void gaoij(int x1, int y1, int g1, int x2, int y2, int g2, int v) {
	for (int i = x1; i != y1; i += g1) {
		for (int j = x2; j != y2; j += g2) {
			if (maps[i][j] == '.') printf("%c", maps[i][j]);
			else printf("%c", mp[maps[i][j]][v]);
		}
		puts("");
	}
}

void gaoji(int x1, int y1, int g1, int x2, int y2, int g2, int v) {
	for (int j = x1; j != y1; j += g1) {
		for (int i = x2; i != y2; i += g2) {
			if (maps[i][j] == '.') printf("%c", maps[i][j]);
			else printf("%c", mp[maps[i][j]][v]);
		}
		puts("");
	}
}

void solve() {
	int tot = 0;
	scanf("%d", &n);
	scanf("%s", s);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", maps[i] + 1);
	}
	int len = strlen(s);
	for (int i = 0; i < len; ++i) {
		if (s[i] == 'R') tot++;
		else tot--;
	}
	tot = (tot + 800) % 4;
	if (tot == 0) gaoij(1, n + 1, 1, 1, n + 1, 1, tot);
	if (tot == 1) gaoji(1, n + 1, 1, n, 0, -1, tot);
	if (tot == 2) gaoij(n, 0, -1, n, 0, -1, tot);
	if (tot == 3) gaoji(n, 0, -1, 1, n + 1, 1, tot);
}

int main() {
	mp['<'][0] = '<';
	mp['<'][1] = '^';
	mp['<'][2] = '>';
	mp['<'][3] = 'v';
	mp['^'][0] = '^';
	mp['^'][1] = '>';
	mp['^'][2] = 'v';
	mp['^'][3] = '<';
	mp['>'][0] = '>';
	mp['>'][1] = 'v';
	mp['>'][2] = '<';
	mp['>'][3] = '^';
	mp['v'][0] = 'v';
	mp['v'][1] = '<';
	mp['v'][2] = '^';
	mp['v'][3] = '>';
	int t = 1;
	while(t--)
		solve();
	return 0;
}

B - SpongeBob SquarePants

solved by lllllan. 00:01(+)

题意给出矩形的长宽判断是否为正方形。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

void solve() {
	int n, m;
	scanf("%d %d", &n, &m);
	puts(n == m ? "YES" : "NO");
}

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

C. I Don’t Want To Pay For The Late Jar!

Solved by Sstee1XD. 0:31(+)

思路： 签到

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int n, s, f[N], t[N];
int cas;

void solve() {
	scanf("%d %d", &n, &s);
	for (int i = 1; i <= n; ++i) {
		scanf("%d %d", &f[i], &t[i]);
	}
	int ans = -0x3f3f3f3f;
	for (int i = 1; i <= n; ++i) {
		ans = max(ans, t[i] <= s? f[i] : f[i] - (t[i] - s));
	}
	printf("Case #%d: ", ++cas);
	printf("%d\n", ans);
}

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

E. Optimal Slots

Solved by Sstee1XD. 1:51(+)

题意： $T$ 时长， $n$ 件事情，每件事情用一定时长，要求尽量用完时长，输出方案。多种方案要求尽可能先做事情。

思路： 背包，记录路径，比较路径字典序。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

int n, m;
int w[N], dp[N];
vector<int> p[N];

bool check(int x, int y) {
	int len1 = p[x].size();
	int len2 = p[y].size();
	for (int i = 0 ; i < len1; ++i) {
		if (i >= len2) return false;
		if (p[x][i] < p[y][i]) return false;
		if (p[y][i] < p[x][i]) return true;
	}
	return true;
}

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &w[i]);
	}
	for (int i = 0; i <= m; ++i) {
		dp[i] = -1;
		p[i].clear();
	}
	dp[0] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int v = m; v >= w[i]; --v) {
			if (dp[v - w[i]] == -1) continue;
				if (!check(v, v - w[i])) continue;
				dp[v] = 1;
				p[v] = p[v - w[i]];
				p[v].push_back(i);
		}
	}
	for (int v = m; v >= 0; --v) {
		if (dp[v] != -1) {
			for (int i = 0; i < p[v].size(); ++i) {
				int t = p[v][i];
				if (i != 0) printf(" ");
				printf("%d", w[t]);
			}
			printf(" %d\n", v);
			return;
		}
	}
}

int main() {
	int t = 1;
	while (~scanf("%d", &m), m)
		solve();
	return 0;
}

F. Military Class

Solved by Sstee1XD. 2:58(+2)

题意： 两行，每行 $n$ 个人，要求上下一一匹配，上面第 $i$ 个人可以和下面 $[i - e, i + e]$ 之间的人匹配，然后给出 $k$ 组不可匹配的人，问匹配方案 $mod\ 10^9 + 7$ 。

思路： 考虑用 $dp$ 来计数。 $dp[i][j]$ 表示上面第 $i$ 个人匹配下面前 $j$ 个人的方案数，但是发现我们这样固定无法计入 $[i + 1, i + e]$ 之间的人。我们看到 $e$ 的范围很小，考虑进行状态压缩， $j$ 表示 $[i - e, i + e]$ 的被占用情况，用记忆化搜索就能比较容易写了。

AC代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;
const int N = 2e3 + 7;

ll dp[N][N];
int bad[N][N];
int n, e, k;
int vis[N];


ll dfs(int u) {
	if (u > n) return 1;
	int sta = 0;
	int now = 0;
	for (int i = u - e; i <= u + e; ++i) {
		if (vis[i]) sta |= 1 << now;
		now++;
	}
	if (dp[u][sta] != -1) return dp[u][sta];
	ll tmp = 0;
	for (int j = u - e; j <= u + e; ++j) {
		if (j <= 0 || j > n || bad[u][j] || vis[j]) {
			continue;
		}
		vis[j] = 1;
		tmp += dfs(u + 1);
		tmp %= mod;
		vis[j] = 0;
	}
	dp[u][sta] = tmp;
	return tmp;
}

void solve() {
	scanf("%d %d %d", &n, &e, &k);
	for (int i = 1, u, v; i <= k; ++i) {
		scanf("%d %d", &u, &v);
		bad[u][v] = 1;
	}
	memset(dp, -1, sizeof(dp));
	printf("%lld\n", dfs(1));
}

int main() {
	int t = 1;
		solve();
	return 0;
}

H - Are You Safe?

solved by Tryna.1:13(+1)

题解： 求凸包加判断点是否在多边形内，注意下换行即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
const int maxn = 1e2 + 10;
int cas;
int n, m;

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);
	}
	bool operator == (Point B) {
		return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;
	}
	bool operator < (const Point &b) const{
		if(x == b.x) return y < b.y;
		return x < b.x;
	}
}P[maxn], ch[maxn], res;

struct Line{
	Point p1, p2;
	Line(){}
	Line(Point p1, Point p2):p1(p1),p2(p2){}
};

double Cross(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}

double Dot(Point a, Point b) {
	return a.x * b.x + a.y * b.y;
}

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 Andrew(int n) {
	sort(P, P + n);
	int top = 0;
	for(int i = 0; i < n; i++) {
		while(top > 1 && Cross(ch[top - 1] - ch[top - 2], P[i] - ch[top - 2]) < 0) {
			top--;
		}
		ch[top++] = P[i];
	}
	int k = top;
	for(int i = n - 2; i >= 0; i--) {
		while(top > k && Cross(ch[top - 1] - ch[top - 2], P[i] - ch[top - 2]) < 0) {
			top--;
		}
		ch[top++] = P[i];
	}
	if(n > 1)
		top--;
	return top;
}

int Point_in_polygon(Point pt, Point *p, int n) {
	for(int i = 0; i < n; i++) {
		if(p[i] == pt) return 3;
	}
	for(int i = 0; i < n; i++) {
		Line v = Line(P[i], P[(i + 1) % n]);
		if(Point_on_seg(pt, v)) return 2;
	}
	int num = 0;
	for(int i = 0; i < n; i++) {
		int j = (i + 1) % n;
		int c = sgn(Cross(pt - p[j], p[i] - p[j]));
		int u = sgn(p[i].y - pt.y);
		int v = sgn(p[j].y - pt.y);
		if(c > 0 && u < 0 && v >= 0) num++;
		if(c < 0 && u >= 0 && v < 0) num--;
	}
	return num != 0;
}

void solve() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++) {
		scanf("%lf %lf", &P[i].x, &P[i].y);
	}
	int len = Andrew(n);
	if(cas >= 1) 
		puts("");
	printf("Case %d\n", ++cas);
	for(int i = 0; i <= len; i++) {
		printf("%.0f %.0f\n", ch[i].x, ch[i].y);
	}
	for(int i = 0; i < m; i++) {
		scanf("%lf %lf", &res.x, &res.y);
		if(Point_in_polygon(res, ch, len) == 1) {
			printf("%.0f %.0f is unsafe!\n", res.x, res.y);
		}
		else printf("%.0f %.0f is safe!\n", res.x, res.y);
	}
}

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

I - To Crash Or Not To Crash

solved by Tryna.0:12(+)

题解： 签到

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
string s[5];

void solve() {
	for(int i = 1; i <= 3; i++)
		cin>>s[i];
	int x = 0, y = 0;
	for(int i = 1; i <= 3; i++) {
		for(int j = 0; j <= s[i].size(); j++) {
			if(s[i][j] == '=') {
				x = i;
				y = j;
				break;
			}
		}
	}
//	printf("%d %d\n", x, y);
	for(int i = y + 1; i < s[x].size(); i++) {
		if(s[x][i] != '.') {
			printf("%c\n", s[x][i]);
			return ;
		}	
	}
	puts("You shall pass!!!");
}

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

J - Kitchen Plates

solved by lllllan. 00:20(+)

题意： 究极迷你版拓扑排序

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int G[6][6];
int deg[6];
char s[10];

int ans[10];
void run () {
	queue<int> Q;
	for (int i = 0; i < 5; ++i) {
		if (deg[i] == 0) Q.push(i);
	}
	
	while (Q.size()) {
		int u = Q.front(); Q.pop();
		ans[ ++ans[0] ] = u;
		for (int i = 0; i < 5; ++i) {
			if (G[u][i] && deg[i]) {
				deg[i]--;
				if (deg[i] == 0) Q.push(i);
			}
		}
	}
	
	if (ans[0] == 5) for (int i = 1; i <= 5; ++i) printf("%c", ans[i] + 'A');
	else printf("impossible\n");
}

void solve() {
	for (int i = 1; i <= 5; ++i) {
		scanf("%ss", s + 1);
		int u = s[1] - 'A';
		int v = s[3] - 'A';
		if (s[2] == '<') {
			G[u][v] = 1;
			deg[v]++;
		} else {
			G[v][u] = 1;
			deg[u]++;
		}
	}
	
	int flag = 0;
	for (int i = 0; i < 5; ++i) {
		if (deg[i] == 0) flag = 1;
	}
	if (flag) run();
	else printf("impossible\n");
}

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

K - Help The Support Lady

solved by Tryna.0:28(+1)

题解： 注意一下如果做这个任务必定超过截止日期就别去做它了。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
int cas, n;
ll a[maxn], sum[maxn];
void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		sum[i] = 0;
		scanf("%lld", &a[i]);
	}
	sort(a + 1, a + 1 + n);
	int res = 0;
	printf("Case #%d: ", ++cas);
	for(int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + a[i];
		if(a[i] * (ll)2 >= sum[i]) res++;
		else {
			sum[i] = sum[i] - a[i];
		}
	}
	printf("%d\n", res);
}

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