牛客ioi周赛22普及组题解

A.战争尾声

题意：
给定个点，第个点坐标为，现在让你在大陆上求出一个整数坐标的点，使得这个点到给定的个点的距离都相等，如果找不到则输出，相等指的是到给定个点的个距离中，任意两个差值的绝对值都小于
数据范围：
大陆是指对于任何一个点，都有的一片区域。

题解：
暴力枚举大陆上的所有点，看这个点是否满足到给定个点的距离都相等即可。

代码：

#include
using namespace std;
const double eps = 1e-4;
const int N = 210;
const int M = N * N;
struct Node {
    int x, y;
}node[N];
int vis[M];
int n;

double get(Node A, int x, int y) {
    int xx = A.x - x;
    int yy = A.y - y;
    return sqrt(xx * xx + yy * yy);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        --a, --b;
        node[i] = {a, b};
        vis[a * 200 + b] = 1;
    }

    int f = -1;
    for(int i = 0; i < 200; ++i)
        for(int j = 0; j < 200; ++j) {
            int ok = 1;
            double dis = get(node[1], i, j);
            for(int k = 2; k <= n; ++k)
                if(fabs(get(node[k], i, j) - dis) < eps);
                else ok = 0;
            if(ok) return 0 * printf("%d %d\n", i + 1, j + 1);
        }

    return 0 * printf("War is cruel.");
}

B.签订协议

题意： 给定个国家的战力，每个国家的战力各不相同，第个国家战力为，每一轮开始都选择当前还没有签订协议的战力最高的国家先签订协议，如果一个国家签订过或者一个国家并非当前还没有签订协议的国家中战力最高的国家，则跳过。由于个国家代表环坐一圈，当第个国家传递给第个国家时，代表完成了一轮传递，现在问最少传递多少轮才能让所有国家才完成协议。

数据范围：

题解：
由于战力各不相同，离散化使得战力相邻的国家更容易判断。
从战力最低的国家开始反着枚举，当战力为第小的国家所在的位置再战力为第这个国家之前时，需要额外多进行一轮，因此离散化后再判断即可。

代码：

#include
using namespace std;

const int N = 8e5 + 10;
int b[N], a[N], n, g, pa[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    for(int i = 1; i <= n; ++i) pa[a[i]] = i;

    int res = 0, pre = 0;
    for(int i = 1; i <= n; ++i) {
        if(pa[i] > pre) ++res;
        pre = pa[i];
    }

    printf("%d\n", res);

    return 0;
}

C.照看小猫

题意： 给定只小猫，第只小猫允许自己的名字最多有个小写字母，问给所有小猫取名的方案数，答案对取模。
数据范围：

题解：
考虑允许自己名字有个小写字母的猫的数量为，为可取的名字数，
则该类小猫有种取名方案数。由于越小，可取名的范围就越小，因此从小到大考虑，每次可取名字数需要减去之前已经取过考虑的小猫数。

代码：

#include
using namespace std;

typedef long long ll;
const int N = 10010;
const ll mod = 77797;
int a[N], n;
int cnt[11];
ll act[11];
ll res = 1;

void init() {
    act[0] = 1;
    for(int i = 1; i <= 10; ++i) act[i] = act[i - 1] * 26;
    act[0] = 0;
    for(int i = 1; i <= 10; ++i) act[i] += act[i - 1];
}

int main()
{

    scanf("%d", &n);
    for(int i = 1, x; i <= n; ++i)
        scanf("%d", &x), ++cnt[x];
    init();
    for(int i = 1; i <= 10; ++i) {
        if(cnt[i] != 0) {
            if(cnt[i] + cnt[i - 1] > act[i]) return 0 * printf("-1\n");
            ll a = act[i] - cnt[i - 1], b = cnt[i];
            for(ll j = a - b + 1; j <= a; ++j) res = res * (j % mod) % mod; 
        } 
        cnt[i] += cnt[i - 1];
    }

    printf("%lld\n", res);
    return 0;
}

D.路线规划

题意： 给定个点，条边，保证图连通，问从点走到每个点之后再返回点的时间，其中经过一次第条边需要的时间，求出经过所有点并且经过最少路径的条件下，返回点的最短时间。
数据范围：
保证最后的答案小于。

题解：
首先考虑经过路径最少，如果从到一个点的路径唯一，则无需考虑。如果从到一个点的路径不唯一，则必然有环，如果有环则无论从哪个点进入，经过这个环上的所有点所采取的路径一定是最短的，因此原路返回需要的时间也一定比走完这个环回到初始点需要的时间更短。因此问题变成了求解从到达剩余个点的最短单程路径，显然是需要转换为求解一个最小生成树。

代码：

#include
using namespace std;

typedef long long ll;
const int N = 2e5 + 10;
const int M = 4e6 + 10;
int p[N];
int n, m;
ll res;

struct Node {
    int a, b;
    ll c;
    bool operator < (const Node &A) const {
        return c < A.c;
    }
}e[M];

int find(int x) {
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i)
        scanf("%d%d%lld", &e[i].a, &e[i].b, &e[i].c);

    for(int i = 1; i     
    sort(e + 1, e + m + 1);
    for(int i = 1; i <= m; ++i) {
        int a = find(e[i].a), b = find(e[i].b);
        if(a != b) res += e[i].c, p[a] = b;
    }

    printf("%lld\n", res * 2);

    return 0;
}