A - CAPS LOCK

题意:
将输入字母转成大写

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    string temp;
    cin >> temp;
    transform(temp.begin(), temp.end(), temp.begin(), ::toupper);
    cout << temp << endl;
    return 0;
}

总结:
如题

B - Yellow and Red Card

题意:
"1 x"是玩家x吃到黄牌, "2 x"是玩家x吃到红牌, "3 x"是询问玩家x是否被逐出游戏. 吃到2次黄牌或者一次红牌的玩家会被逐出游戏

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int n, q;
    cin >> n >> q;
    map<int, int> cnt;
    for (int i = 1; i <= q; ++i)
    {
        int n1, n2;
        cin >> n1 >> n2;
        if (n1 == 3)
        {
            cout << (cnt[n2] >= 2 ? "Yes" : "No") << endl;
        }
        else
        {
            cnt[n2] += n1;
        }
    }
    return 0;
}

总结:
如题

C - Four Variables

题意:
给一个正整数N, 求出符合 (AB+CD=N) 形式的 (A, B, C, D) 有几种

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxN = 2e5 + 10;

map<int, int> cnt;
void init()
{
    for (int i = 1; i <= maxN; ++i)
    {
        for (int j = 1; j * j <= i; ++j)
        {
            if (i % j == 0)
            {
                ++cnt[i];
                if (i / j != j)
                {
                    ++cnt[i];
                }
            }
        }
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    init();
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i < n; ++i)
    {
        ans += cnt[i] * cnt[n - i];
    }
    cout << ans << endl;
    return 0;
}

总结:
求出1到2e5每个数能分解成几对2个因数相乘, 复杂度 nlogn
从1到N-1, 累加一下相乘的结果得到答案

D - Unicyclic Components

题意:
给出一个无向图, 问无向图的每一个连通块是否是满足点数等于边数

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxN = 2e5 + 10;

vector<int> son[maxN];
map<pair<int, int>, int> cnt1;
map<int, int> cnt2;
map<int, bool> vis;
map<pair<int, int>, bool> vis2;
int num1, num2;
void dfs(int now)
{
    ++num1;
    num2 += cnt2[now];
    vis[now] = 1;
    int len = son[now].size();
    for (int i = 0; i < len; ++i)
    {
        int v = son[now][i];
        if (!vis2[make_pair(now, v)] && !vis2[make_pair(v, now)])
        {
            vis2[make_pair(now, v)] = 1;
            num2 += cnt1[make_pair(now, v)];
            num2 += cnt1[make_pair(v, now)];
        }
        if (!vis[v])
        {
            dfs(v);
        }
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        if (u == v)
        {
            ++cnt2[u];
        }
        else
        {
            son[u].push_back(v);
            son[v].push_back(u);
            ++cnt1[make_pair(u, v)];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        num1 = 0, num2 = 0;
        if (!vis[i])
        {
            dfs(i);
        }
        if (num1 != num2)
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

总结:
如题, 感觉写的不好.

E - Transitivity(补)

题意:
给出一个有向图, 问对于每三个不同的点若满足 (若顶点A指向顶点B, 顶点B指向顶点C, 则顶点A指向顶点C) 需要添加几条边.

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxN = 2010;

int n, m;
vector<int> son[maxN];
int ans;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        son[u].push_back(v);
    }
    map<int, bool> vis;
    for (int i = 1; i <= n; ++i)
    {
        vis.clear();
        vis[i] = 1;
        queue<int> q;
        q.push(i);
        while (q.size())
        {
            int now = q.front();
            q.pop();
            int len = son[now].size();
            for (int i = 0; i < len; ++i)
            {
                int v = son[now][i];
                if (vis[v])
                {
                    continue;
                }
                vis[v] = 1;
                ++ans;
                q.push(v);
            }
        }
    }
    cout << ans - m << endl;
    return 0;
}

总结:
题目条件可以转换为一个顶点和它可以去到的每一个顶点之间都要有一条边, 那这样的话就可以对每一个点跑一遍bfs, 累加每个点的边数, 最后在边的总数量中减掉一开始就有的M条边就是答案了