Atcoder ABC420游记

无话可说

---

题目

题目评级

$A < B < C < D < E = G$

A.What month is it?

题目描述

给你介于 $1$ 和 $12$ 之间的整数 $X$ 和 $Y$ 。

求 $X$ 月之后的 $Y$ 个月是几月（例如， $1$ 月是一月）。

思路

直接模拟即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int a, b;
    cin >> a >> b;
    a += b;
    a %= 12;
    if (a == 0)  {
        cout << 12;
    } else {
        cout << a;
    }
    return 0;
}

---

B.Most Minority

题目描述

$1,2,\dots,N$ 人（其中 $N$ 为奇数）进行了 $M$ 次投票，每个人都选择了 "0 "或 “1”。
每个人在每一轮投票中的票数是由长度为 $M$ 的 $N$ 字符串 $S_1,S_2,\dots,S_N$ 给出的，字符串由 "0 "和 "1 "组成，其中 $S_i$ 的 $j$ -th字符代表 $i$ 人在 $j$ -th投票中的投票内容。

在每次投票中，处于少数的人获得 $1$ 个点。
更确切地说，点数是根据以下规则给出的：

• 假设 $x$ 人在投票中选择了 “0”， $y$ 人选择了 “1”。
  • 如果有 $x=0$ 或 $y=0$ 人选择 “1”，则每个人都会因这一投票得到 $1$ 分。
  • 否则，如果是 x&lt;y ，只有在该投票中投了 "0 "票的人才会得到 $1$ 分。
  • 否则，只有投 "1 "票的人才能得到 $1$ 分。
  • 请注意，由于 $N$ 是奇数，所以 $x=y$ 永远不会出现。

在完成 $M$ 投票后，找出所有在这些投票中总得分最高的人。

思路

直接模拟即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> b(n, 0);
    for (int i = 0; i < m; i++) {
        int cnt1 = 0, cnt2 = 0;
        for (int j = 0; j < n; j++) {
            if (a[j][i] == '0') {
                cnt1++;
            } else {
                cnt2++;
            }
        }
        if (cnt1 == 0 || cnt2 == 0) {
            for (int j = 0; j < n; j++) {
                b[j]++;
            }
        } else if (cnt1 < cnt2) {
            for (int j = 0; j < n; j++) {
                if (a[j][i] == '0') {
                    b[j]++;
                }
            }
        } else {
            for (int j = 0; j < n; j++) {
                if (a[j][i] == '1') {
                    b[j]++;
                }
            }
        }
    }
    int maxx = *max_element(b.begin(), b.end());
    for (int i = 0; i < n; i++) {
        if (b[i] == maxx) {
            cout << i + 1 << ' ';
        }
    }
    return 0;
}

---

C. Sum of Min Query

题目描述

给你一个长度为 $N$ 的整数序列： $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$ 。

您需要依次处理 $Q$ 个查询。 $i$ -th 查询 $(1\le i\le Q)$ 的描述如下：

给定字符 $c_i$ 和整数 $X_i,V_i$ 。如果 $c_i=$ A，将 $A_{X_i}$ 改为 $V_i$ ；如果是 $c_i=$ B，将 $B_{X_i}$ 改为 $V_i$ 。然后，输出 $\displaystyle \sum_{k=1}^N \min(A_k,B_k)$ 。

思路

每次改动就一个，记$\Delta$即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += min(a[i], b[i]);
    }
    for (int i = 0; i < q; i++) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'A') {
            ans -= min(a[x], b[x]);
            a[x] = y;
            ans += min(a[x], b[x]);
        } else {
            ans -= min(a[x], b[x]);
            b[x] = y;
            ans += min(a[x], b[x]);
        }
        cout << ans << '\n';
    }
    return 0;
}

---

D.Toggle Maze

题目描述

有一个网格，网格中有 $H$ 行和 $W$ 列。让 $(i,j)$ 表示位于从上往下第 $i$ 行和从左往上第 $j$ 列的单元格。每个单元格的状态用字符 $A_{i,j}$ 表示，其含义如下：

• . ：空单元格。
• # : 障碍单元格。
• S ：起始单元格。
• G : 目标单元格。
• o : 打开的单元格。
• x : 关闭的单元格。
• ? : 开关单元。

高桥可以通过一次操作从当前单元格移动到既不是障碍物单元格也不是封闭门单元格的相邻单元格（上、下、左、右）。

此外，每当他移动到一个开关单元时，所有打开的门单元都会变成关闭的门单元，而所有关闭的门单元都会变成打开的门单元。

确定他是否能从位于起始格的初始状态移动到位于目标格的初始状态，如果可能，找出所需的最少操作次数。

思路

直接BFS然后你会发现做完了，只不过记一下走了几轮而已

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector<vector<char>> a;
int sx, sy;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
signed main()
{
    cin >> n >> m;
    a.resize(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }
    vector<vector<vector<int>>> dist(n, vector<vector<int>>(m, vector<int>(2, -1)));
    queue<vector<int>> q;  
    dist[sx][sy][0] = 0;
    q.push({sx, sy, 0});
    while (!q.empty()) {
        vector<int> tp = q.front();
        q.pop();
        int x = tp[0], y = tp[1], z = tp[2];
        for (int i = 0; i < 4; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if (dx < 0 || dx >= n || dy < 0 || dy >= m) {
                continue;
            }
            if (a[dx][dy] == '#') {
                continue;  
            }
            if (a[dx][dy] == 'x') {
                if (z % 2 == 0) {
                    continue;
                }
            }
            if (a[dx][dy] == 'o') {
                if (z % 2 == 1) {
                    continue;
                }
            }
            int tpz = z;
            if (a[dx][dy] == '?') {
                tpz = (z + 1) % 2;
            }
            if (dist[dx][dy][tpz] == -1) {
                dist[dx][dy][tpz] = dist[x][y][z] + 1;
                q.push({dx, dy, tpz});
                if (a[dx][dy] == 'G') {
                    cout << dist[x][y][z] + 1;
                    return 0;
                }
            }
        }
    }
    cout << -1;
    return 0;
}

---

E.Reachability Query

题目描述

给你一个无向图，有 $N$ 个顶点和 0 条边。
顶点编号为 $1,2,\dots,N$ ，最初所有顶点都是白色的。
请处理以下三种类型共 $Q$ 个查询：

• 类型 $1$ ：添加一条不定向边连接顶点 $u$ 和 $v$ 。
• 类型 $2$ ：如果顶点 $v$ 是白色，将其改为黑色；如果是黑色，将其改为白色。
• 类型 $3$ ：通过遍历零条或多条边，判断是否可以从顶点 $v$ 到达黑色顶点；如果可以，则报告 “是”，否则报告 “否”。

思路

显然DSU可以秒掉连通性的问题，但是题目问的是能不能到达黑色节点，那直接对于每个点记录它在并查集内儿子的黑色节点数量即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct DSU
{
    int _n;
    vector<int> _fa, _size;
    explicit DSU(int __n) : _n(__n) {
        _fa.resize(_n + 1);
        _size.resize(_n + 1);
        for (int i = 1; i <= _n; i++) {
            _fa[i] = i;
            _size[i] = 1;
        }
    }
    int find(int _x) {
        if (_fa[_x] == _x) {
            return _x;
        }
        return _fa[_x] = find(_fa[_x]);
    }
    void merge(int _x, int _y) {
        assert(1 <= _x && _x <= _n);
        assert(1 <= _y && _y <= _n);
        _x = find(_x);
        _y = find(_y);
        if (_x == _y) {
            return;
        }
        _fa[_x] = _y;
        _size[_x] += _size[_y];
    }
    bool same(int _x, int _y) {
        assert(1 <= _x && _x <= _n);
        assert(1 <= _y && _y <= _n);
        _x = find(_x);
        _y = find(_y);
        return _x == _y;
    }
};
signed main()
{
    int n, q;
    cin >> n >> q;
    DSU dsu(n);
    vector<int> a(n + 1, 0);
    vector<int> b(n + 1, 0); 
    while (q--) {
        int ch;
        cin >> ch;
        if (ch == 1) {
            int u, v;
            cin >> u >> v;
            int rt1 = dsu.find(u);
            int rt2 = dsu.find(v);
            if (!dsu.same(u, v)) {
                dsu.merge(u, v);
                int rt = dsu.find(u);
                a[rt] = a[rt1] + a[rt2];
                }
        } else if (ch == 2) {
            int x;
            cin >> x;
            int rt = dsu.find(x);
            if (b[x] == 0) {
                b[x] = 1;
                a[rt] += 1;
            } else {
                b[x] = 0;
                a[rt] -= 1;
            }
        } else if (ch == 3) {
            int x;
            cin >> x;
            int rt = dsu.find(x);
            if (a[rt] > 0) {
                cout << "Yes" << '\n';
            } else {
                cout << "No" << '\n';
            }
        }
    }

    return 0;
}

---

G.sqrt(n²+n+X)

题目描述

给你一个整数 $X$ 。

请找出所有令 $\displaystyle \sqrt{n^2+n+X}$ 为整数的整数 $n$ 。

思路

简单数学题。

整理：

$$n^2 + n + X = m^2$$

$$n^2 + n + (X - m^2) = 0$$

求根公式：

$$n = \frac{-1 \pm \sqrt{1-4(X-m^2)}}{2} = \frac{-1 \pm \sqrt{1-4X+4m^2}}{2}$$

所以$\Delta$必须是一个完平：

$$1 - 4X + 4m^2 = k^2$$

重新整理得到： $$4m^2-k2 = 4X-1$$ $$k^2-4m2 = 1-4X$$

这可以因式分解为： $$(k-2m)(k+2m) = 1-4X$$

直接枚举$1 - 4X$的因子然后解一个方程组就好了，最后要去重+验证。

代码

#include <bits/stdc++.h>
using namespace std;
#define int __int128
signed main()
{
    long long _;
    cin >> _;
    int x = _;
    int y = 1 - 4 * x;
    int absy = y;
    if (y < 0) {
        absy *= -1;
    }
    vector<int> ans;
    for (int i = 1; i * i <= absy; i++) {
        if (y % i == 0) {
            vector<pair<int, int>> v = {{i, (y / i)}, {(y / i), i}};
            if (i != (y / i)) {
                v.push_back({-i, -(y / i)});
                v.push_back({-(y / i), -i});
            } else {
                v.push_back({-i, -(y / i)});
            }
            for (int j = 0; j < v.size(); j++) {
                if ((v[j].first + v[j].second) % 2 == 0 && (v[j].second - v[j].first) % 4 == 0) {
                    int m = (v[j].first + v[j].second) / 2;
                    int k = (v[j].second - v[j].first) / 4;
                    if (k >= 0) {
                        if (2 * (-1 + m) / 2 + 1 == -m || 2 * (-1 + m) / 2 + 1 == m) {
                            ans.push_back((-1 + m) / 2);
                        }
                        if (2 * (-1 - m) / 2 + 1 == -m || 2 * (-1 - m) / 2 + 1 == m) {
                            ans.push_back((-1 - m) / 2);
                        }
                    }
                }
            }
        }
    }
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++) {
        if (ans[i] * ans[i] + ans[i] + x >= 0) {
            cout << (long long)ans[i] << ' ';
        }
    }
    return 0;
}

复盘

赛时尝试从F倒开，结果全场最难就是F 然后E这么简单我们还没看 22分钟才切掉了E 人麻了