A、战争尾声

暴力枚举棋盘中全部的格点，再去判断是不是全部的国家到这个点距离一样。注意一下枚举顺序找到退出即可。
最坏情况下时间复杂度 $O(200^2*n)$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<double,double>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const int N = 200 + 7;

ll n, m;
pai a[N];
#define x first
#define y second
double k, b;

double dis(pai A, pai B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
bool check(pai tmp) {
    double len = dis(tmp, a[1]);
    rep(i, 2, n) {
        double p = dis(tmp, a[i]);
        if (fabs(p - len) > eps)    return 0;
    }
    return 1;
}

void solve() {
    n = read();
    rep(i, 1, n) {
        a[i].x = read();
        a[i].y = read();
    }
    rep(i, 1, 200) {
        rep(j, 1, 200) {
            if (check({ i, j })) {
                printf("%d %d\n", i, j);
                return;
            }
        }
    }
    puts("War is cruel.");
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

B、签订协议

就拿样例举例子了。

10
11 8 5 7 1 6 2 3 4 10

显然第一次我们要找到最大的 11 接下来再要找到 10 ，并且 10 的坐标在 11 后面说明不需要额外增加一次操作，但是下一次找到 8 的时候，会发现 8 的下标在 10 之前，说明找到 8 需要额外增加一次操作。那么就这这个思路，我们记录原数组的值以及之前所在位置，对结构体按照数组的值降序排序，顺序遍历有几个点跑到当前正在遍历的点前面去了即可。第一次进入前可以看作起始位置为无穷大。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;

ll n, m;
struct Node {
    int val, pos;
    bool operator < (const Node& opt) const {
        return val > opt.val;
    }
}a[N];

void solve() {
    n = read();
    rep(i, 1, n)
        a[i].val = read(), a[i].pos = i;
    sort(a + 1, a + 1 + n);
    int ans = 0, now = INF;
    rep(i, 1, n) {
        if (a[i].pos < now)    ++ans;
        now = a[i].pos;
    }
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

C、照看小猫

组合数学。很显然如果只有 1 只猫咪的时候，他的答案就是一个类比 26 进制的值。
现在我有很多只猫咪，那么我把猫咪名字需求按照升序排序，优先处理名字较短的猫咪。这样我们写个样例看看。可以看到第一只猫取名字有 26 种取法，但是第二只同为 1 的猫咪名字取值有 26 - 1 种取法，因为它不能和前一只猫名字相同，那么再看第三只猫，他的名字要求是 2 ，那么在没有限制的情况下他的取法是 $(26*26+26)-2$ 前面的括号部分是不带限制的取法，但是它又要保证和前 2 只猫咪名字不同，所以取值就有上面写的那么多，那么枚举下去你会发现，每个位置的取法都是可以 $O(1)$ 计算出来的，我们预处理一下 26 进制的前缀和，就可以 $O(n)$ 解决这个问题了。
图片说明

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 77797;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;

ll n, m;
ll a[N], bs[N];
void solve() {
    n = read();
    rep(i, 1, n)    a[i] = read();
    bs[1] = 26;
    rep(i, 2, 10)    bs[i] = bs[i - 1] * 26 % MOD;
    rep(i, 2, 10)    bs[i] = (bs[i] + bs[i - 1]) % MOD;

    sort(a + 1, a + 1 + n);
    ll ans = 1;
    rep(i, 1, n) {
        m = bs[a[i]] - i + 1;
        if (m <= 0) { print(-1); return; } // 注意有等号
        ans = ans * m % MOD;
    }
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

D、路线规划

最小生成树。前言：其实题目已经暗示的很明显了，但是我竟然没有看出来，在树形 dp 上走死了。
题目给出一个图，并且要求在走过的路径最少的情况下，去到全部的点，并且需要路径和最少。这里就和最小生成树的定义一样了，但是它稍微添加了一个条件，就是它最后要回到起点，那么我们可以找到一个涵盖起点的最小生成树，从这个最小生成树上去到每一个点路径一定是最少的，但是我们需要考虑回退操作，这里我们想，我们已经找到这个图的最小生成树了，我们可能存在一条更优的边回到之前的位置吗？显然是不存在的，如果存在这条边就变成我们最小生成树的边了，所以我们一定是沿着路径返回，再接着往下探，直到我们去到了最深的一个点这个时候我们就可以一路沿着之前来的路径回到起点。距离就是最小生成树路径和的两倍，因为每一条最小生成树上的边都要经历进入和回退两个操作。并且只进行这样两次。最小生成树的求法就用 $kruskal$ 就行了。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 7;
const int M = 2e6 + 7;

ll n, m;
int head[N], tot, fa[N];
struct Node {
    int u, v;
    ll w;
    bool operator < (const Node& opt) const {
        return w < opt.w;
    }
}edge[M];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void solve() {
    n = read(), m = read();
    rep(i, 1, n)    fa[i] = i;
    rep(i, 1, m) {
        edge[i].u = read();
        edge[i].v = read();
        edge[i].w = read();
    }
    sort(edge + 1, edge + 1 + m);
    ll ans = 0;
    rep(i, 1, m) {
        int fu = find(edge[i].u), fv = find(edge[i].v);
        if (fu != fv) {
            fa[fv] = fu;
            ans += edge[i].w;
        }
    }
    print(ans << 1);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

牛客IOI周赛22-普及组

A、战争尾声

B、签订协议

C、照看小猫

D、路线规划