专栏文章

AT_385比赛

ssea_water
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqokwdq
此快照首次捕获于
2025/12/04 08:11
3 个月前
此快照最后确认于
2025/12/04 08:11
3 个月前
查看原文

UNIQUE VISION Programming Contest 2024 Christmas (AtCoder Beginner Contest 385)

建议绑定AT账号之后再提交

警告：题解仅供参考，不许抄！！！

[ABC385A] Equally

AT 链接
洛谷 链接
一道简单的不得了的基础题,按题意特判即可。
CPP
#include <bits/stdc++.h>
using namespace std;
int a, b, c;

int main() {
	cin >> a >> b >> c;
	if (a == b && b == c && a == c) {
		cout << "Yes";
		return 0;
	}
	if (a + b == c || b + c == a || a + c == b) {
		cout << "Yes";
		return 0;
	}
	cout << "No";
	return 0;
}

[ABC385B] Santa Claus 1

AT 链接
洛谷
记录每一个点被走过了，注意判断是否可以走到那个点。
CPP
if (s[i] == 'L') {
  if (c[sx][sy - 1] == '.' || c[sx][sy - 1] == '@') {
    sy -= 1;
    b[sx][sy] = 1;
  }
}
截取向左走的操作
最后记录有几个到达的点为房屋。
CPP
for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (b[i][j] && c[i][j] == '@') {
				sum++;
			}
		}
	}

注意：只算经过过，如果再经过不会让不会让答案增加！！！

代码

CPP
#include <bits/stdc++.h>
using namespace std;
int n, m, sx, sy, sum = 0;
char c[105][105];
string s;
bool b[105][105];

int main() {
	cin >> n >> m >> sx >> sy;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> c[i][j];
		}
	}
	b[sx][sy] = 1;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'L') {
			if (c[sx][sy - 1] == '.' || c[sx][sy - 1] == '@') {
				sy -= 1;
				b[sx][sy] = 1;
			}
		} else if (s[i] == 'R') {
			if (c[sx][sy + 1] == '.' || c[sx][sy + 1] == '@') {
				sy += 1;
				b[sx][sy] = 1;
			}
		} else if (s[i] == 'U') {
			if (c[sx - 1][sy] == '.' || c[sx - 1][sy] == '@') {
				sx -= 1;
				b[sx][sy] = 1;
			}
		} else if (s[i] == 'D') {
			if (c[sx + 1][sy] == '.' || c[sx + 1][sy] == '@') {
				sx += 1;
				b[sx][sy] = 1;
			}
		}
	}
	cout << sx << ' ' << sy << ' ';
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (b[i][j] && c[i][j] == '@') {
				sum++;
			}
		}
	}
	cout << sum;
	return 0;
}

[ABC385C] Illuminate Buildings

AT 链接
洛谷
这道题可以用dp解决
设dp[j][i]dp[j][i]表示与第i座楼高度一样间隔为j的连续楼数。
dp方程有两个可能：
  • 若h[i]=h[i−j]h[i] = h[i - j] ,易得dp[j][i]=dp[j][i−j]+1 dp[j][i] = dp[j][i - j] + 1.
  • 否则，可知dp[j][i]dp[j][i]不能从dp[j][i−j]dp[j][i-j]转移，易得dp[i][j]=1 dp[i][j] = 1。
答案为dpdp 数组中的最大值。
时间复杂度为 O(N2)O(N^2) 。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
int n, h[3005], sum = 0;
int a[3005][3005];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> h[i];
	}
	for (int i = 1; i <= n; i++) {
		a[0][i] = 1;
		for (int j = 1; j <= n; j++) {
			if (j < i && h[i] == h[i - j]) {
				a[j][i] = a[j][i - j] + 1;
			} else {
				a[j][i] = 1;
			}
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			sum = max(a[j][i], sum);
		}
	}
	cout << sum;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...