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

普及组的题目，感觉挺适合现在的我做的。。。。
前两题可以无压力AC的，第三题想不出来了，第四题可惜没去试一试。

A 战争尾声

题意：
给一个200*200的矩形，放在平面直角坐标系中。给n个点，问能否找到一个点到所有n个点的距离相同。n的坐标要求是正整数。n<=200。
思路：
题目保证答案是正整数，那么我们暴力枚举就可以了。
复杂度O(n^3)
类型：
暴力、模拟
代码：

#include<bits/stdc++.h>
using namespace std;
int x[222],y[222],n;
double juli(int x1,int y1,int x2,int y2){
  return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
bool solve(int xx,int yy){
  double  delta=juli(xx,yy,x[1],y[1]);
  for(int i=2;i<=n;i++){
      double tmp=juli(xx,yy,x[i],y[i]);
      if(fabs(tmp-delta)>=0.0001)return false;
  }
  return true;
}
int main()
{

  cin>>n;
  for(int i=1;i<=n;i++){
      cin>>x[i]>>y[i];
  }
  int f=0;
  for(int i=1;i<=200;i++){
      for(int j=1;j<=200;j++){
          if(solve(i,j)){
              cout<<i<<' '<<j<<endl;
              f=1;
              break;
          }
      }
      if(f)break;
  }
  if(f==0)cout<<"War is cruel."<<endl;
  return 0;
}

B 签订协议

题意：
给一个环，环上一共有n个点编号为1-n并且按照顺时针排序。每个点有一个战力值，每次从1-n会转一圈传递协议，要求先传给战力值高的点。每转一圈算一个轮回，问需要转多少个轮回让所有的点都拿到协议。
思路：
纸上手模一下应该能够很快知道解法。
可以先将点按照战力值进行排序，从排序后的第一个点开始往后扫，每次比较相邻的两个点的编号大小，假设编号是a[i]和a[i+1]，如果a[i]<a[i+1]，说明这一轮可以从a[i]传给a[i+1]，如果a[i]>a[i+1]了，那么说明这一轮传不到了，只能下一轮了，而且本轮的传递结束了。
因此我们只要扫一遍，比较相邻的两个点的编号，如果遇到a[i]>a[i+1]就ans++。
```
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
  int a,idx;
}p[800005];
bool cmp(node x,node y){
  return x.a>y.a;
}
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++){
      int x;
      scanf("%d",&x);
      p[i].a=x;
      p[i].idx=i;
  }
  int ans=1;
  sort(p+1,p+1+n,cmp);
  for(int i=1;i<n;i++){
      if(p[i].idx>p[i+1].idx)ans++;
  }
  cout<<ans<<endl;
  return 0;
}
```
C 照顾小猫

数学太差，看到这种题经常一筹莫展。看了一会，感觉是容斥，但是不知道怎么做，因为我只知道有容斥这个东西，具体怎么分析不会做。。
然后瞄了一眼题解，看是看懂了，但是感觉和我理解的容斥好像用法不太一样？
首先我们考虑没有限制的时候的方案数，对于一只猫来说，长度为i的话，存在方案数26^1+26^2+26^3+...26^i种，这个用一个前缀和sum[i]可以表示出来。
此时再来一只猫，最大长度为j，假设i<j，这只猫的无限制方案数就是sum[j]，由于j猫的名字不能和i猫的名字一样，那么j猫的名字方案数就是sum[j]-1
如果再来一只猫，最大长度为k，无限制方案为sum[k]，k猫不能和前面的猫的名字相同，所以又sum[k]-2种
因此第m只猫的方案数就是sum[a[m]-m+1
答案就是全部乘起来就好了。注意要先对a[i]数组排序，保证后面的字符串一定会受到前面的影响。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=77797;
int n,a[10005],num[105],sum[105];
void init(){
    num[0]=1;
    for(int i=1;i<=10;i++)num[i]=num[i-1]*26%mod;
    for(int i=1;i<=10;i++)sum[i]=(sum[i-1]+num[i])%mod;
}
int main()
{

    cin>>n;
    init();
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    long long ans=1;
    for(int i=1;i<=n;i++){
        if(sum[a[i]]<i){
            cout<<-1<<endl;
            return 0;
        }
        ans=ans*(sum[a[i]]-i+1);
        ans=ans%mod;
    }
    cout<<ans<<endl;
    return 0;
}

D 路线规划
题意不赘述了。本题的关键在于，要使得走过的路最少，在这个前提下再让时间尽量的少。其实看到了这个条件，考虑了一下最小生成树。但是他又要走回来，觉得会不会走回来换条更短的路（因为回来不需要再访问所有的点了）。但是现在想一想，如果换更短的路，由于路尽量少的限制，他不能走新路，只能走老路。只能走老路的情况下，我走过来的已经是最短的了，所以还是原路返回时间最少。
因此，构造一颗最小生成树，答案乘2就可以了。注意开long long
类型：
最小生成树
代码：
include<bits/stdc++.h>
using namespace std;
int n,m,tot,f[200050];
struct node{
int u,v;
long long w;
bool operator < (const node & a)const {
```
  return w<a.w;
```
}
}p[2000500];
void init()
{
for(int i=0;i<200050;i++)f[i]=i;
}
int find(int x){
if(x!=f[x])return f[x]=find(f[x]);
return f[x];
}
int main()
{
init();
cin>>n>>m;
for(int i=1;i<=m;i++){
```
  int x,y;
  long long z;
  scanf("%d%d%lld",&x,&y,&z);
  p[i].u=x;
  p[i].v=y;
  p[i].w=z;
```
}
long long ans=0;
sort(p+1,p+1+m);
for(int i=1;i<=m;i++){
```
  int fx,fy;
  fx=find(p[i].u);
  fy=find(p[i].v);
  if(fx==fy)continue;
  ans+=p[i].w;
  f[fx]=fy;
```
}
cout<<ans*2<<endl;
return 0;
}

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

A 战争尾声

B 签订协议

C 照顾小猫

D 路线规划

include<bits/stdc++.h>

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