AtCoder Beginner Contest 424 • santisify Site

A Isosceles#

题目描述#

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

参考代码#

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

cpp

B Perfect#

B Perfect

题目描述#

$n$ 个人， $m$ 个题，总共 $k$ 次提交，每次提交都是第 $A_{i}$ 人完成第 $B_{i}$ 题。
输出完成所有题的人的编号，有多个按最后一个题的完成顺序输出。

解题思路#

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

参考代码#

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

cpp

C New Skill Acquired#

C New Skill Acquired

题目描述#

$n$ 个数对，数对 ${A_{i}, B_{i}}$ 表示到达点 $A_{i}$ 或者 $B_{i}$ 才可到达点 $i$ （即 $A_{i} \rightarrow i，B_{i} \rightarrow i$ ）, $A_{i} = 0$ $B_{i} = 0$ 表示 $i$ 点可直接到达.
问：最多能到达多少个点。

解题思路#

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

参考代码#

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();
}

cpp

D 2x2 Erasing 2#

D 2x2 Erasing 2

题目描述#

给定 $n * m$ 的矩阵，要求修改矩阵，使得不出现 $2 * 2$ 的 ’#’ 的矩阵。
输出最小操作数。

解题思路#

可以发现数据最大为 $100$ 组 $7 * 7$ 的矩阵，可以直接暴力 $dfs$ .

参考代码#

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

cpp