A~F

A
签到题

#include<bits/stdc++.h>

using namespace std;

string s;
int main()
{
    cin >> s;
    int n = s.size();

    if(n != 3) cout << "wrong answer" << '\n';
    else 
    {
        bool flag = 1;
        for(int i = 0; i < 3; i ++)
        {
            if(i == 0 && (s[i] != 'y' && s[i] != 'Y')) 
            {
                flag = 0;
                break;
            }
            if(i == 1 && (s[i] != 'e' && s[i] != 'E'))
            {
                flag = 0;
                break;
            }
            if(i == 2 && (s[i] != 's' && s[i] != 'S'))
            {
                flag = 0;
                break;
            }
        }
        if(flag) cout << "accept" <<'\n';
        else cout << "wrong answer"<< '\n';
    } 
    return 0;
}

B
模拟

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int n;

int main()
{
    cin >> n;
    cout << n << '\n';
    for(int i = n; i > 1; i --)
    {
        if(n % i == 0)
        {
            for(int j = 1; pow(i, j) <= n; j ++)
            {
                if(pow(i, j) == n) printf("=%d^%d\n", i, j);
            }
        }
    }
    return 0;
}

C
模拟

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    ll ans = 0;
    map<int,int> mp;
    for(int i = 1; i <= n; i ++)
    {
        ll x = mp[a[i]];
        ans += x;
        mp[a[i]] ++;
        cout << ans << ' ';
    }
    return 0;
}

D
思维题（对角线无法同时减少，先取完一个对角线的，下一个就无法操作）

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int T;
int a, b, c, d;

int main()
{
    cin >> T;
    for(int i = 1;i <= T; i ++)
    {
        cin >> a >> b >> c >> d;
        int x = min(a + d, b + c);
        if(x & 1) cout << "kou" << '\n';
        else cout << "yukari" << '\n';
    }
    return 0;
}

E
构造+贪心
设字符串长度为n
根据鸽巢原理： 当一个字母出现次数大于n/2时候，必然无解

有解的话，必然有最大的字母出现的次数，设为maxx；
记录下所有出现过的字母及它们的位置，之后按照字典序排序；
之后遍历整个序列，把当前字母的出现位置 向右移动 maxx 位即可，
一定符合要求。

举个例子：s = “bbaaz”
设下标数组idx[5] = {{b,0},{b,1},{a,2},{a,3},{z,4}};

排序后：idx = {{a,2},{a,3},{b,0},{b,1},{z,4}};
这里只要 把a在2这个出现的位置 用向右第(i + maxx)%n的字母即可：
（贪心的想：因为排序后所有字母的连续长度<=maxx，因此 第(i + maxx)%n一定是当前不相同字母）

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10, inf = 0x3f3f3f3f;

string s;
int cnt[30];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    int n = s.size();

    int maxx = 0;
    for(int i = 0; i < n; i ++) 
    {
        cnt[s[i] - 'a'] ++;
        maxx = max(maxx, cnt[s[i] - 'a']);
    }
    if(maxx > n / 2) cout << -1 << '\n';
    else 
    {
        vector<pair<char,int>> idx(n);
        for(int i = 0; i < n; i ++)
        {
            idx[i] = {s[i], i};
        }
        sort(idx.begin(), idx.end());

        string ans = s;
        for(int i = 0; i < n; i ++)
        {
            auto [id, t] = idx[i];
            ans[t] = idx[(i + maxx) % n].x;
        }
        cout << ans << '\n';
    }
    return 0;
}

F
2次dfs + 1次 01 bfs

由于q只有一次，可以记录每个点到 起点st 和终点ed 的距离；
如何判断一个点是否在路径上？
一个点到起点和终点的和 等于 起点到终点的和
把所有起点（这里是所有的路径上的点）存储起来，最后跑一边01 bfs，
这里可以贪心证明：bfs先跑到的点路径一定比后跑到的点路径短

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int n, q, st, ed;
int h[N], e[N], ne[N], idx;
int dst[N], ded[N], dist[N];
bool vis[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int fa, int d[])
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int son = e[i];
        if(son == fa) continue;
        d[son] = d[u] + 1;
        dfs(son, u, d);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(h, -1, sizeof h);
    cin >> n >> q;
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    while(q --)
    {
        cin >> st >> ed;
    }

    dfs(st, -1, dst);
    dfs(ed, -1, ded);

    vector<int> start;
    ll d = dst[ed];

    for(int i = 1; i <= n; i ++)
    {
        if(dst[i] + ded[i] == d) start.push_back(i), vis[i] = 1;
    }

    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    for(int i = 0; i < start.size(); i ++) q.push(start[i]), dist[start[i]] = 0;

    while(q.size())
    {
        int t = q.front();
        q.pop();

        vis[t] = 1;
        for(int i = h[t]; ~i; i = ne[i])
        {
            int son = e[i];
            if(vis[son]) continue;
            if(dist[son] > dist[t] + 1)
            {
                dist[son] = dist[t] + 1;
                q.push(son);
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i ++) ans += dist[i];
    cout << ans << '\n';
    return 0;
}