AtCoder Beginner Contest 424

atcoder, 题解

A Isosceles

题目描述

给出三角形的三个边, , ，判断三角形是否为等腰三角形。

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
    int a, b, c;
    std::cin >> a >> b >> c;
    if (a == b || a == c || b == c) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_ --) solve();
}

B Perfect

题目描述

个人，个题，总共次提交，每次提交都是第人完成第题。

输出完成所有题的人的编号，有多个按最后一个题的完成顺序输出。

解题思路

直接统计完成题的数目，当数目达到时，直接输出编号。

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<int> a(n + 1, 0);
    while (k --) {
        int x, y;
        std::cin >> x >> y;
        a[x] ++;
        if (a[x] == m) {
            std::cout << x << ' ';
        }
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_ --) solve();
}

C New Skill Acquired

题目描述

个数对，数对表示到达点或者才可到达点（即 $，$ ）, 表示点可直接到达.

问：最多能到达多少个点。

解题思路

题目描述很明了，直接建图，再或搜索即可.

参考代码

bfs

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
    int n;
    std::cin >> n;
    std::queue<int> q;
    std::vector<bool> vis(n + 1, false);
    std::vector g(n + 1, std::vector<int>());
    for (int i = 0, x, y; i < n; i ++) {
        std::cin >> x >> y;
        if (!x) {
            q.push(i + 1);
            vis[i + 1] = true;
        }
        g[x].push_back(i + 1), g[y].push_back(i + 1);
    }
    while (!q.empty()) {
        auto u = q.front();
        q.pop();
        for (auto v: g[u]) {
            if (!vis[v]) vis[v] = true, q.push(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        ans += vis[i];
    }

    std::cout << ans << std::endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_ --) solve();
}

D 2x2 Erasing 2

题目描述

给定的矩阵，要求修改矩阵，使得不出现的 '#' 的矩阵。

输出最小操作数。

解题思路

可以发现数据最大为组的矩阵，可以直接暴力.

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
	int n, m;
	std::cin >> n >> m;
	std::vector<std::string> s(n);
	for (int i = 0; i < n; i++) std::cin >> s[i];
	int ans = 1e9;
	std::function<void(int, int, int)> dfs = ([&](int x, int y, int res) {
		if (res >= ans) return; //实测不添加等号会TLE
		if (y == m) {
			y = 0, x++;
		}
		if (x == n) {
			ans = res;
			return;
		}

		if (s[x][y] == '.') {
			dfs(x, y + 1, res);
			return;
		} else {
			if (x == 0 || y == 0 || s[x - 1][y] == '.' || s[x][y - 1] == '.' || s[x - 1][y - 1] == '.')
				dfs(x, y + 1, res);
			s[x][y] = '.';
			dfs(x, y + 1, res + 1);
			s[x][y] = '#';
		}
	});
	dfs(0, 0, 0);
	std::cout << ans << std::endl;
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int _ = 1;
	std::cin >> _;
	while (_--) solve();
}