牛客IOI周赛22-普及组题解

T1

枚举坐标，进行判断

#include<bits/stdc++.h>
using namespace std;
int x[205],y[205],n;
bool calc(int xx,int yy)
{
    int MAX=0,MIN=INT_MAX;
    for(int i=1;i<=n;i++){
        int k=(x[i]-xx)*(x[i]-xx)+(y[i]-yy)*(y[i]-yy);
        MAX=max(MAX,k);
        MIN=min(MIN,k);
    }
    return sqrt(MAX)-sqrt(MIN)<=1e-4;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=200;i++)
        for(int j=1;j<=200;j++)
            if(calc(i,j)){
                cout<<i<<" "<<j<<"\n";
                return 0;
            }
    puts("War is cruel.");
    return 0;
}

T2

先通过排序知道每个国家的战力排在多少位
然后，如果一个国家后面有排在它之后一位的国家，答案不变
如果没有，答案加一

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,ans;
pair<int,int> a[N];
int b[N],c[N],f[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].first);
        c[i]=a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        b[a[i].second]=i;
    for(int i=n;i>=1;i--){
        if(!f[b[i]-1]) ans++;
        f[b[i]]=1;
    }
    cout<<ans<<"\n";
    return 0;
}

T3

先排序
考虑让名字短的先选，名字长的选名字短选剩下的，乘法原理即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[10004];
int ans=1,mod=77797;
int p[20];
signed main()
{
    p[0]=1;
    for(int i=1;i<=10;i++)
        p[i]=p[i-1]*26%mod;
    for(int i=2;i<=10;i++)
        p[i]=(p[i]+p[i-1])%mod;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        ans=(p[a[i]]-i+1)*ans%mod;
    if(ans<=0) ans=-1;
    cout<<ans<<"\n";
    return 0;
}

T4

随便搞一个最小生成树的模板,然后答案*2

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
struct oppo{
    int a,b,s;
}rod[2000005];
bool rule(oppo a,oppo b)
{
    return a.s<b.s;
}
int fa[500004];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int ans,tot;
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&rod[i].a,&rod[i].b,&rod[i].s);
    }
    sort(rod+1,rod+m+1,rule);
    for(int i=1;i<=m;i++)
    {
        if(find(rod[i].a)!=find(rod[i].b))
        {
            ans+=rod[i].s;
            tot++;
            fa[find(rod[i].a)]=find(rod[i].b);
        }
    }
    cout<<ans*2;
    return 0;
}