前言

F出题人的期望解法是三元环，第一次见，内测时候交出了34发的天文数字，如果有错欢迎大家指出。

题解

A.ACM中的A题

枚举所有情况，分别给每一个木棍乘2试试。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    std::vector<i64> a;
    for (i64 i = 1; i <= 3; i++) {
        i64 x;
        std::cin >> x;
        a.push_back(x);
    }

    for (int i = 0; i < 3; i++) {
        std::vector<i64> v;
        for (int j = 0; j < 3; j++) {
            if (i == j) {
                v.push_back(a[j] * 2);
            }
            else
                v.push_back(a[j]);
        }
        std::sort (v.begin(), v.end());
        if (v[0] + v[1] > v[2]) {
            std::cout << "Yes";
            return;
        }
    }
    std::cout << "No";
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

B.ACM中的C题

如果为1无法交换则无解，否则输出除向上取整即可。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        int a;
        std::cin >> a;
    }
    if (n == 1) {
        std::cout << -1;
    }
    else {
        std::cout << (n + 1) / 2 ;
    }
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

C.ACM中的M题

此题与上一题的区别就是数组可能会属于不同的集合，那把上一题看成数组都属于同一个集合不就好了，本题的答案就是把不同的集合的答案求和，跟上一题一样，如果有某个集合的大小为，那么则无解。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        int a;
        std::cin >> a;
    }

    std::map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        int b;
        std::cin >> b;
        mp[b]++;
    }
    
    std::vector<int> v;
    for (auto [x, y] : mp) {
        v.push_back(y);
    }

    int ans = 0;
    for (auto it : v) {
        ans += (it + 1) / 2;
        if (it == 1) {
            std::cout << -1;
            return;
        }
    }

    std::cout << ans ;
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

D.ACM中的AC题

我写的史山，先预处理出来每个位置到任意一个传送门的最短距离，所有的传送门连到一个超级源点上，从超级源点开始跑就可以处理出来了，然后就是两个人从一个点开始跑bfs，我的写法是一起扔进去两个点打上编号，代表这个人正着跑，代表这个人跑反方向，然后就是一起跑，如果其中某一个找到终点了，就算看一下另一个点的位置到任意传送门的最短路，每次把目前走的距离加上另一个点还需要走的距离取个最小值即可。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

int dx1[4] = {0, 1, 0, -1};
int dy1[4] = {1, 0, -1, 0};

int dx2[4] = {0, -1, 0, 1};
int dy2[4] = {-1, 0, 1, 0};

void solve() {
    int n, m, a, b;
    std::cin >> n >> m >> a >> b;

    std::vector<std::vector<char> > mp(n + 1, std::vector<char> (m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> mp[i][j];
        }
    }

    std::queue<std::tuple<int, int> > st;
    std::vector<std::vector<int > > dist(n + 1, std::vector<int> (m + 1, -1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> mp[i][j];
            if (mp[i][j] == '@') {
                st.push({i, j});
                dist[i][j] = 0;
            }
        }
    }

    while (!st.empty()) {
        auto [x, y] = st.front();
        st.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x + dx1[i], yy = y + dy1[i];
            if (xx < 1 || xx > n || yy < 1 || yy > m || mp[xx][yy] == '#' || dist[xx][yy] != -1) continue;
            dist[xx][yy] = dist[x][y] + 1;
            st.push({xx, yy});
        }
    }
   
    std::queue<std::tuple<int, int, int> > q;
    std::vector<std::vector<std::vector<int> > > vis(n + 1, std::vector<std::vector<int> > (m + 1, std::vector<int> (2, -1)));
    q.push({a, b, 0});//0表示正常走
    q.push({a, b, 1});//1表示反着走
    vis[a][b][0] = 0;
    vis[a][b][1] = 0;
    int ans = 1e9;
    int sx = -1, sy = -1, flag = 1;

    while (!q.empty()) {
        auto [x1, y1, op1] = q.front();
        q.pop();
        auto [x2, y2, op2] = q.front();
        q.pop();

        if (mp[x1][y1] == '@') {
            ans = std::min(ans, vis[x1][y1][0] + dist[x2][y2]);
            flag = 0;
        }
        if (mp[x2][y2] == '@') {
            ans = std::min(ans, vis[x2][y2][1] + dist[x1][y1]);
            flag = 0;
        }
        for (int i = 0; i < 4; i++) {
            int xx1 = x1 + dx1[i], yy1 = y1 + dy1[i];
            if (xx1 < 1 || xx1 > n || yy1 < 1 || yy1 > m || mp[xx1][yy1] == '#' || vis[xx1][yy1][op1] != -1) continue;
            int xx2 = x2 + dx2[i], yy2 = y2 + dy2[i];
            if (xx2 < 1 || xx2 > n || yy2 < 1 || yy2 > m || mp[xx2][yy2] == '#' || vis[xx2][yy2][op2] != -1) continue;

            vis[xx1][yy1][op1] = vis[x1][y1][op1] + 1;
            vis[xx2][yy2][op2] = vis[x2][y2][op2] + 1;
            q.push({xx1, yy1, op1});
            q.push({xx2, yy2, op2});
        }
    }

    if (flag) {
        std::cout << -1;
        return;
    }
    std::cout << ans;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

E.ACM中的CM题

忽略我代码里的层循环，是我内测时候无聊就想试试最少多少层循环可以AC本题，并没有什么实际意义，直接跑n层就可以，思路也很简单，排序之后就枚举排雷能力是多少，每次就排着段区间内的雷，一直往后跳，看需要跳多少次，这个复杂度是调和级数可以做到，所以整体来说就是。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

std::vector<int> a;
int n, k;

int check(int x) {
    int ans = x;
    int pos = a[1];
    while (1) {
        ans++;
        pos = std::upper_bound(a.begin() + 1, a.end(), pos + x) - a.begin();
        if (pos == a.end() - a.begin()) break;
        pos = a[pos];
    }
    
    return ans;
}

void solve() {
    std::cin >> n;
    a.push_back(0);
    for (int i = 1; i <= n; i++) {
        int v;
        std::cin >> v;
        a.push_back(v);
    }
    std::sort(a.begin() + 1, a.end());
    int ans = 1e6;
    for (int i = 0; i <= 553; i++) {
        ans = std::min(ans, check(i));
    }
    std::cout << ans << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

F.ACM中的ACM题

三元环的模板题，在本题之前我并未见过，所以卡死了，把判出来三元环的三条边并查集合并即可，最终看看有多少个条边的祖宗是自己，如果只有一个就是否则

#include<bits/stdc++.h>
#include <bits/extc++.h>

using i64 = long long;
using u64 = unsigned long long;


void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> p(m + 1);
    
    auto find = [&] (auto self, int &x) -> int {
        if (x == p[x]) return x;
        return p[x] = self(self, p[x]);
    };

    auto merge = [&] (int &a, int &b) -> void {
        int fa = find(find, a), fb = find(find, b);
        if (fa != fb) {
            p[fb] = fa;
        }
    };

    std::vector<int> in(n + 1), u(m + 1), v(m + 1);

    for (int i = 1; i <= m; i++) {
        std::cin >> u[i] >> v[i];
        in[u[i]]++,in[v[i]]++;
        p[i] = i;
    }

    std::vector<std::vector<std::pair<int,int>> > e(n + 1);

    for (int i = 1; i <= m; i++) {
        if (in[u[i]] < in[v[i]] || (in[u[i]] == in[v[i]] && u[i] < v[i])) {
            e[v[i]].push_back({u[i],i});
        }
        else {
            e[u[i]].push_back({v[i],i});
        }
    }

    std::vector<std::pair<int,int> > vis(n + 1);

    for (int i = 1; i <= n; i++) {
        for (auto [x, j] : e[i]) vis[x] = {i, j};

        for (auto [x,j] : e[i]) {
            for (auto [y,k] : e[x]) {
                if (vis[y].first == i) {
                    merge(k, j);
                    merge(j, vis[y].second );
                }
            }
        } 
    }

    int ans=0;
    for (int i = 1; i <= m; i++) {
        if(p[i]==i) ans++;
    }

    if(ans==1)std::cout<<"Yes\n";
    else std::cout<<"No\n";
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();

    }

}