牛客IOI周赛22-普及组

下面的题解按照难度排序。

T1

果断枚举坐标就行了。
时间复杂度是 O $(200 * 200 * 200)$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
double dis[MAXN],x[MAXN],y[MAXN];
int n;

double calc(double X1,double Y1, double X2, double Y2) {
    return sqrt((X2 - X1) * (X2 - X1) + (Y2 - Y1) * (Y2 - Y1));
}

int main() {
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) 
        cin >> x[i] >> y[i];
    for(int i = 1 ; i <= 200 ; i ++) {
        for(int j = 1 ; j <= 200 ; j ++) {
            double X = double(i) , Y = double(j);
            for(int k = 1 ; k <= n ; k ++)
                dis[k] = calc(x[k],y[k],X,Y);
            int flag = 0;
            for(int k = 1 ; k <= n ; k ++) 
                if(abs(dis[k] - dis[1]) > 0.0001) flag = 1;
            if(flag == 0) {cout << i << " " << j << endl; return 0;}
        }
    }
    cout << "War is cruel.";
    return 0;
}

T2

观察题目后，不难想到把原数组按照战力从大到小排序。

然后映射，对于排序后的数组映射为每一个数在原数组中的下标。

假设原数组中第 $i$ 大的是在第 $i + 1$ 大的后面，那么显然答案是要 + 1的，因为这就得删去第 $i$ 大的后重新来一轮。

我们发现只需要判断映射后的数组中有多少个 $T[i].id > T[i + 1].id$ 即可。

最后的答案要 + 1，因为无论如何至少要进行一轮。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 8e5 + 50;
bool book[MAXN + MAXN / 4];
int n,A[MAXN];

struct Node {
    int data,id;
    bool operator < (const Node &Q) {
        return Q.data < data;
    }
} T[MAXN];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar() ;
    for( ; ch > '9' || ch < '0' ; ch = getchar()) ;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int main() {
    n = read();
    for(int i = 1 ; i <= n ; i ++) A[i] = read();
    for(int i = 1 ; i <= n ; i ++) T[i].data = A[i] , T[i].id = i;
    sort(T + 1 , T + 1 + n );
    int Ans = 0;
    for(int i = 1 ; i <= n ; i ++) if(T[i].id > T[i + 1].id) Ans ++;
    cout << Ans;
    return 0;
}

T4

不难发现，要求经过的边最少，那么就是一棵生成树。

要求权值最小，那么就是最小生成树。

观察到在一棵树里面能够保证每条边恰好被经过两次（根据欧拉序可知）。

所以最后的答案就是最小生成树的权值 * 2。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 50;
int n,m,cnt = 0;
int start[MAXN],f[MAXN];

struct Edge {
    int to,from,w;
} edge[MAXN * 10];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar() ;
    for( ; ch > '9' || ch < '0' ; ch = getchar()) ;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

void add(int u,int v,int w) {
    edge[++cnt].from = u;
    edge[cnt].to = v;
    edge[cnt].w = w;
    return ;
}

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

bool cmp(Edge AA, Edge BB) {
    return AA.w < BB.w;
}

int main() {
    n = read() , m = read();
    for(int i = 1 ; i <= n ; i ++) f[i] = i;
    for(int i = 1 ; i <= m ; i ++) {
        int u = read() , v = read() , w = read();
        add(u,v,w);
    }
    long long Ans = 0;
    sort(edge + 1 , edge + 1 + cnt, cmp);
    for(int i = 1 ; i <= cnt ; i ++) {
        int from = edge[i].from , to = edge[i].to;
        if(find(from) != find(to)) {
            f[find(from)] = find(to);
            Ans += edge[i].w;
        }
    }
    cout << Ans * 2;
    return 0;
}

T3

我怎么这么菜啊，这道题卡了比较久。。。。但是实际上并不难。

首先考虑，把长度限制按照从小答案排序后，前面的名字无论如何都会对后面的名字产生影响，也就是后面的名字不能与前面的相同。

不妨假装生成一个总的名字集合，不难发现，为了保证名字不重复，前面的名字如果出现了一次的话，后面的就不能再次出现这个名字，于是我们就把这个名字从这个集合里面“删去”，其实也并不是“删去”，而是说我们“假装”把它删去，后面计算答案的时候，都减去这个的贡献就行了。

// Problem: 照看小猫
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11038/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Mod = 77797,MAXN = 1e4 + 50;
int A[MAXN],M[20] = {1},book[15];
int Q[11][MAXN];
int n,sum[20];

int quickpower(int x,int k) {
    int ans = 1 , op = x;
    while(k) {
        if(k & 1ll) ans *= op;
        op = op * op;
        k >>= 1ll;
    }
    return ans;
}

signed main() {
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> A[i];
    for(int i = 1 ; i <= 10 ; i ++) M[i] = M[i - 1] * 26 % Mod;
    for(int i = 2 ; i <= 10 ; i ++) M[i] = M[i - 1] + M[i] , M[i] %= Mod;
    sort(A + 1 , A + 1 + n);
    int Ans = 1;
    for(int i = 1 ; i <= n ; i ++) {
        if(A[i] < 3 && M[A[i]] - i < 0) {cout << -1 ; return 0;} 
// 这里要注意，判断A[i] < 3 是因为如果 A[i] >= 3 的时候，M[A[i]] 就已经大于10000了，可能因为取模的缘故使得M[A[i]] < 10000。
        else Ans = (Ans * (M[A[i]] - (i - 1))) % Mod;
    }
    cout << Ans;
    return 0;
}