普及组的题目，感觉挺适合现在的我做的。。。。
前两题可以无压力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;
  }