AT_385比赛

sea_water · 2024-12-23 22:10:15 · 个人记录

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

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

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

[ABC385A] Equally

AT 链接

洛谷 链接

一道简单的不得了的基础题,按题意特判即可。

#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 链接

洛谷

记录每一个点被走过了，注意判断是否可以走到那个点。

if (s[i] == 'L') {
  if (c[sx][sy - 1] == '.' || c[sx][sy - 1] == '@') {
    sy -= 1;
    b[sx][sy] = 1;
  }
}

截取向左走的操作

最后记录有几个到达的点为房屋。

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (b[i][j] && c[i][j] == '@') {
                sum++;
            }
        }
    }

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

代码

#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]表示与第i座楼高度一样间隔为j的连续楼数。

dp方程有两个可能：

• 若 h[i] = h[i - j] ,易得 dp[j][i] = dp[j][i - j] + 1.
• 否则，可知 dp[j][i] 不能从 dp[j][i-j] 转移，易得 dp[i][j] = 1。

答案为 dp 数组中的最大值。

时间复杂度为 O(N^2) 。

代码

#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;
}