牛客IOI周赛19-普及组（A,B,C)

小y的考试

思路：我们先对四个选项进行一个排序，同时我们将排好序后的要能够保留到原始的选项号，根据“三长一短选最短”，我们判断有没有最短的那个选项，有就选对应的选项，然后根据“三短一长选最长”，我们可以找出是否有最长的，同理，如果两者都没有，那么直接输出C即可。

#include<bits/stdc++.h>
using namespace std;
string s[4];
struct node{
    int len;
    char ch;
}Node[4];
bool cmp(node a,node b){
    return a.len>b.len;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        for(int i=0;i<4;i++){
            cin>>s[i];
            Node[i].len=s[i].size();
            Node[i].ch='A'+i;
        }
        sort(Node,Node+4,cmp);
        if(Node[2].len!=Node[3].len){
            cout<<Node[3].ch<<endl;
        }
       else if(Node[0].len!=Node[1].len){
            cout<<Node[0].ch<<endl;
        }
        else  cout<<"C"<<endl;
    }
    return 0;
}

小y的序列

思路：首先，我们对于这个数组里面的每一项，我们可以求出原始的数组，我们发现，原始的数组和新数组直接的每项的差值是一样的，所以，我们可以根据差值来进行一个判断，我们找到每项相对于原始项的差值，然后计算出现次数最多的那个差值的出现次数，最后用n-这个次数就是我们要求的答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010],b[100010];
ll sum=0;
int main(){
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll ans=0;
    sum=1;
    map<ll,ll> mp;
    mp[a[1]-1]++;
    for(int i=2;i<=n;i++){
        sum+=(i-1);
        //cout<<sum<<endl;
        ll tmp=a[i]-sum;
        mp[tmp]++;
        ans=max(ans,mp[tmp]);
        //cout<<ans<<endl;
    }
    cout<<n-ans<<endl;
    return 0;
}

小y的旅行

思路:这个题目我们将这些边分为两种边，一种是边上的两个端点都大于k的话，那么我们就不要管这些点的情况，但是也要用并查集维护这些点的连通性，对于只要有一个端点小于等于k的情况，我们就要将他们列入考虑删除的范围内，然后，我们考虑那些边，如果这两条边没有联通的话，我们要将他们联通，否则，我们就要删除这一条边，可以证明，我们将联通的这条边删除的话不会影响最后的结果。可以维护他们不形成环。
代码：

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
int fa[2000010];
vector<pair<int,int> > v;
int find(int x){
    if(fa[x]==x)  return x;
    return fa[x]=find(fa[x]);
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) fa[i]=i;
    while(m--){
        int x,y;
        cin>>x>>y;
        if(x<=k||y<=k) v.push_back(make_pair(x,y));
        else{
            int fx=find(x),fy=find(y);
            fa[fx]=fy;
        }
    }
    int ans=0;
    int len=v.size();
    for(int i=0;i<len;i++){
        int fx=find(v[i].first),fy=find(v[i].second);
        if(fx==fy)  ans++;
        else  fa[fx]=fy;
    }
    cout<<ans<<endl;
    return 0;
}