Atcoder ABC404游记（A~D）

用G逼迫自己学会了差分约束。。。赛时过的人还是L4的是什么情况

但是代码写下来感觉G比E爽，其实习惯了，atc民间风俗好吧喜欢调换顺序

A. Not Found

题目描述

给你一个长度在 $1$ 和 $25$ 之间的字符串 $S$ ，它由小写英文字母组成。
请输出一个没有出现在 $S$ 中的小写英文字母。
如果有多个这样的字母，可以输出其中任意一个。

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
bool vis[26];
int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        vis[s[i] - 'a'] = 1;
    }
    for (int i = 0; i < 26; i++) {
        if (!vis[i]) {
            cout << (char)(i + 'a');
            return 0;
        }
    }
    return 0;
}

B.Grid Rotation

题目描述

有两个网格 $S$ 和 $T$ ，每个网格有 $N$ 行和 $N$ 列。让 $(i,j)$ 表示从上往下数第 $i$ 行和从左往上数第 $j$ 列的单元格。

网格 $S$ 和 $T$ 中的每个单元格都被涂成白色或黑色。如果 $S_{i,j}$ 为"."，则 $S$ 的单元格 $(i,j)$ 为白色；如果 $S_{i,j}$ 为 “#”，则单元格 $(i,j)$ 为黑色。同样的情况也适用于 $T$ 。

您可以按任意顺序执行以下两种类型的运算任意多次。求使网格 $S$ 与网格 $T$ 相同所需的最少运算次数。

选择网格 $S$ 中的一个单元格并改变其颜色。
顺时针旋转整个网格 $S$ $90$ 度。

思路

水…吗可能考察一点代码能力

代码

#include<bits/stdc++.h>
using namespace std;
vector<string> calc(vector<string> s) {
    int n = s.size();
    vector<string> res(n, string(n, '.'));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            res[j][n - 1 - i] = s[i][j];
        }
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    vector<string> s, t;
    for (int i = 0; i < n; i++) {
        string tp;
        cin >> tp;
        s.push_back(tp);
    }
    for (int i = 0; i < n; i++) {
        string tp;
        cin >> tp;
        t.push_back(tp);
    }
    int ans = INT_MAX;
    for (int k = 0; k < 4; k++) {
        int cnt = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < s[i].size(); j++) {
                if (s[i][j] != t[i][j]) {
                    cnt++;
                }
            }
        }
        ans = min(ans, k + cnt);
        s = calc(s);
    }
    cout << ans;
    return 0;
}

C.Cycle Graph?

问题陈述

给你一个简单的无向图，图中有 $N$ 个顶点和 $M$ 条边。顶点编号为 $1,2,\dots,N$ ，边编号为 $1,2,\dots,M$ 。边 $i$ 连接顶点 $A_i$ 和 $B_i$ 。

请判断该图是否为循环图。

简单无向图的定义：简单无向图是指不存在自循环或多条边的无向边图。

循环图的定义：如果存在 $(1,2,\dots,N)$ 的排列 $(v_1,v_2,\dots,v_N)$ ，且其顶点标记为 $1,2,\dots,N$ ，则一个 $N$ /顶点图是循环图：

对于每个 $i = 1,2,\dots,N-1$ ，顶点 $v_i$ 和 $v_{i+1}$ 之间有一条边。
顶点 $v_N$ 与 $v_1$ 之间有一条边。
不存在其他边。

思路

首先 $n=m$ 必要条件，没什么好说的

然后用bfs判图连通性，其实就完了，没错这就完了，但是仍然被卡了一下

代码

#include <bits/stdc++.h>
using namespace std;
vector<int> edges[222222];
bool vis[222222];
int deg[222222];
int main()
{
    int n, m;
    cin >> n >> m;
    if (m != n) {
        cout << "No";
        return 0;
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
        deg[a]++;
        deg[b]++;
    }
    for (int i = 1; i <= n; i++) {
        if (deg[i] != 2) {
            cout << "No";
            return 0;
        }
    }
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    int cnt = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cnt++;
        for (int i = 0; i < edges[x].size(); i++) {
            int nex = edges[x][i];
            if (!vis[nex]) {
                vis[nex] = 1;
                q.push(nex);
            }
        }
    }
    cout << (cnt == n ? "Yes" : "No");
    return 0;
}

D.Goin’ to the Zoo

题目描述

思路

等等，你们怎么都过的这么快，是不是开了

哦，学习完了，DFS就行，人麻了不必3进制十八但是我还是要讲

可能今天刷了一堆状压DP的题，一眼想到了3进制

我们枚举所有访问方案，可以从 $0$ 到 $3^{N}-1$ 来表示每种访问组合，然后根据状压的思想就可以得到动物园的访问次数

然后对每个动物统计和，然后打擂台就好了

啊啊啊啊啊啊怎么卡我这么久可能就能推出E了QAQ

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    vector<vector<int>> a(m);
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        a[i].resize(x);
        for (int j = 0; j < x; j++) {
            cin >> a[i][j];
            a[i][j] -= 1; 
        }
    }
    int ans = 1e18;
    int maxx = 1;
    for (int i = 0; i < n; i++) {
        maxx *= 3;
    }
    for (int i = 0; i < maxx; i++) {
        vector<int> tp(n, 0);
        int now = i;
        int cnt = 0;

        for (int j = 0; j < n; j++) {
            int ttp = now % 3;
            now /= 3;
            tp[j] = ttp;
            cnt += ttp * c[j];
        }
        if (cnt >= ans) {
            continue;
        }
        bool flag = true;
        for (int j = 0; j < m; j++) {
            int cnt = 0;
            for (int nex : a[j]) {
                cnt += tp[nex];
                if (cnt >= 2) {
                    break;
                }
            }
            if (cnt < 2) {
                flag = false;
                break;
            }
        }
        if (flag) {
            ans = cnt;
        }
    }
    cout << ans;
    return 0;
}