526互联

AtCoder Beginner Contest(abc) 317

发布时间 2023-11-05 17:53:29作者: mostimali



B - MissingNo.

难度: ⭐

题目大意

给定n个数, 这n个数中最小值到最大值之间缺一个数, 输出这个数;

解题思路

数据不大, 暴力即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 1e4 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int f[N];
signed main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> f[i];
    sort(f + 1, f + 1 + n);
    for (int i = 2; i <= n; i++) {
        if (f[i] != f[i - 1] + 1) {
            cout << f[i - 1] + 1;
            break;
        }
    }
    return 0;
}



C - Remembering the Days

难度: ⭐⭐

题目大意

给定n个点m条边, 每条边都有一个权值; 从任意一个点出发, 在不重复经过同一个点的情况下所能经过的边权和最大为多少;

解题思路

数据不大, 暴搜即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 1e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int g[N][N];
bool st[N];
void dfs(int u, int sum) {
    idx = max(idx, sum);
    for (int i = 1; i <= n; i++) {
        if (g[u][i]&&!st[i]) {
            st[u] = true;
            dfs(i, sum + g[u][i]);
            st[u] = false;
        }
    }
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;
    }
    for (int i = 1; i <= n; i++) {
        dfs(i,0);
    }
    cout << idx;
    return 0;
}



D - President

难度: ⭐⭐⭐

题目大意

小莫和安姐在竞选市长, 每个地区有(xi + yi)个人, 其中xi人支持小莫, yi人支持安姐, 支持人数较多的人会获得zi分, 最后分数最大的人竞选成功; 请问最少有多少人从支持安姐转向小莫可以让小莫赢得竞选;

解题思路

这道题的本质其实一个01背包dp, 对于支持安姐的地区最少有yi - xi + 1个人转向支持小莫就可以让该地方支持小莫; 设小莫需要dis=(z1 - z2 + 1) / 2价值就可以超过安姐; 把每个地区看作物品, zi是价值, yi - xi + 1是重量; 求最少需要多少重量可以得到dis价值;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int ta = 0, ao = 0;
int dp[N];
struct stu {
    int x, y;
}cre[N];
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a > b) ta += c;
        else {
            ao += c;
            int x = (b - a + 1) / 2;
            cre[++idx] = { x,c };
        }
    }
    int d = ao - ta;
    if (d < 0) {
        cout << 0;
        return 0;
    }
    d = (ao - ta + 1) / 2;
    for (int i = 1; i <= d; i++) dp[i] = 1e15;
    dp[0] = 0;
    for (int i = 1; i <= idx; i++) {
        for (int j = d; j >= 0;j--) {
            dp[j] = min(dp[j], dp[max(0ll,j- cre[i].y)] + cre[i].x);
        }
    }
    cout << dp[d];
    return 0;
}



E - Avoid Eye Contact

难度: ⭐⭐⭐

题目大意

给定一个字符矩阵, '#'表示障碍, '>', 'v', '<', '^'表示此处有监控, 并且字符的指向就是监控的方向, 该监控的范围是该方向的一条直线, 知道遇到障碍或者其他监控; 'S'为起点, 'G'是终点, 要求小莫从起点走到终点, 并且期间不被监控拍到所需要的最少步数, 保证起点和终点不在监控范围内;

解题思路

没什么好方法, 就是一个大模拟, 对于每个监控我们直接遍历它的监控范围并做标记, 最后bfs一下就行, 没啥好说的;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
PII st, ed;
struct stu {
    int x, y, d;
};
char g[N][N];
bool s[N][N];
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
int bfs() {
    queue<stu> q;
    q.push({ st.first,st.second,0 });
    while (q.size()) {
        auto t = q.front();
        q.pop();
        if (g[t.x][t.y] == 'G') {
            return t.d;
        }
        int a = t.x, b = t.y, d = t.d;
        for (int i = 0; i < 4; i++) {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] != '#' && !s[x][y]) {
                s[x][y] = true;
                q.push({ x,y,d + 1 });
            }
        }
    }
    return -1;
}
signed main() {
    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') {
                st.first = i, st.second = j;
            }
            else if (g[i][j] == 'G') {
                ed.first = i, ed.second = j;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '<') {
                s[i][j] = true;
                for (int k = j - 1; k >= 1; k--) {
                    if (g[i][k] != '.') {
                        break;
                    }
                    s[i][k] = true;
                }
            }
            else if (g[i][j] == '>') {
                s[i][j] = true;
                for (int k = j + 1; k <= m; k++) {
                    if (g[i][k] != '.') {
                        break;
                    }
                    s[i][k] = true;
                }
            }
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (g[i][j] == '^') {
                s[i][j] = true;
                for (int k = i - 1; k >= 1; k--) {
                    if (g[k][j] != '.') {
                        break;
                    }
                    s[k][j] = true;
                }
            }
            else if (g[i][j] == 'v') {
                s[i][j] = true;
                for (int k = i + 1; k <= n; k++) {
                    if (g[k][j] != '.') {
                        break;
                    }
                    s[k][j] = true;
                }
            }
        }
    }
    cout << bfs();
    return 0;
}



F - Nim

难度: ⭐⭐⭐⭐⭐