Educational Codeforces Round 55 (Rated for Div. 2)总结

A:这个鬼屎题，我真的没有发现x和y的大小关系是没有确定的，导致我疯狂wa，其实这道题也就是一道水题。

代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const long long maxn=1e5+9;
int main(){
	long long i,j,k,n,t;
	cin>>t;
	while(t--){
		long long x,y,d;
		cin>>n>>x>>y>>d;
		long long tmp;
		if(y>=x){
		if((y-x)%d==0){
			cout<<(y-x)/d<<endl;
		}
		else{
			long long ans=1e9+9,flag=0;
			if(y==n){
				ans=(y-x)/d+1;
			}
			else{
				if((y-1)%d==0&&(y-1)>=d){
						flag++;
						ans=(x-1)/d+1;
						ans+=(y-1)/d;
				}
				if((n-y)%d==0&&(n-y)>=d){
						flag++;
						ans=min(ans,((n-x)/d+1+(n-y)/d));
				}
				if(flag==0){
					ans=-1;
				}
			}
			cout<<ans<<endl;
		}
		}
		else{
			if((x-y)%d==0){
			cout<<(x-y)/d<<endl;
				}
			else{
			long long ans=1e9+9,flag=0;
			if(y==1){
				ans=(x-y)/d+1;
			}
			else{
				if((n-y)%d==0&&(n-y)>=d){
						flag++;
						ans=(n-x)/d+1;
						ans+=(n-y)/d;
				}
				if((y-1)%d==0&&(y-1)>=d){
						flag++;
						ans=min(ans,((x-1)/d+1+(y-1)/d));
				}
				if(flag==0){
					ans=-1;
				}
			}
			cout<<ans<<endl;
		}
		}
	}
}

B题:这道题我们遍历一遍就行了，开两个变量分别储存相邻的连续'G’段就行了，然后通过判断连个连续'G'段中间'S'的个数来看能不能合在一起。

代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e5+9;
int main(){
	int i,j,k,n;
	cin>>n;
	string s;
	cin>>s;
	int total=0,s_num=0,num1=0,num2=0,flag=0,mx=0;
	for(i=0;i<n;i++){
		if(s[i]=='G')total++;
	}
	for(i=0;i<n;i++){
		if(s[i]=='G'&&flag==0){
			num1++;
		}
		else if(s[i]=='G'&&flag==1){
			num2++;
		}
		else if(s[i]=='S'){
			//cout<<"woshigda"<<endl;
			s_num++;
			if(flag==0){flag++;
				mx=max(mx,num1);
			}
			else if(flag==1){flag++;
				mx=max(mx,num2);
			}
			if(flag==2) {
				flag=1;
				if(s_num>=3){
					mx=max(mx,max(num1,num2));
				}
				else{
					if(total-(num1+num2)>0)
					mx=max(mx,num1+num2+1);
					else{
						mx=max(mx,num1+num2);
					}
				}
				//cout<<num1<<' '<<num2<<endl;
				num1=num2;
				num2=0;
				s_num=1;
			}
		}
	}
	mx=max(mx,max(num1,num2));
	if(total-(num1+num2)>0){
		mx=max(mx,num1+num2+1);
	}
	else{
		mx=max(mx,num1+num2);
	}
	cout<<mx<<endl;
}

C题:这道题刚开始愚蠢的没有考虑完负数的情况wa了，考虑完了之后就tle，然后自己想了一下可能是因为循环了一些题目没给出的subject，于是又弄了个set容器，然后由于set的效率不是特别高，还是t了，后来看了董佬代码才发现，遍历的时候对于那些已经不满足有i个人的学科可以直接从set里面删去了，这样大大提高了运行效率

代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e5+9;
#define ll long long
vector<int>a[maxn];
set<int>p;
struct node{
    int x,y;
}t[maxn];
int cnt[maxn];
bool cmp(node a,node b){
    if(a.x!=b.x)return a.x<b.x;
    return a.y>b.y;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int i,j,k,n,m;
    cin>>n>>m;
    int mx=0;
    for(i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        t[i].x=x;
        t[i].y=y;
        p.insert(x);
        cnt[x]++;
        if(cnt[x]>mx)mx=cnt[x];
    }
    sort(t,t+n,cmp);
    for(i=0;i<n;i++){
        if(a[t[i].x].size()==0)a[t[i].x].push_back(t[i].y);
        else{
            a[t[i].x].push_back(a[t[i].x][a[t[i].x].size()-1]+t[i].y);
        }
    }
    long long sum=0,mx_sum=0;
    vector<int>e;
    for(i=0;i<mx;i++){
        sum=0;
        for(auto it:p){
            if(a[it].size()>i&&a[it][i]>0){
                sum+=a[it][i];
            }
            if(a[it].size()==i+1)e.push_back(it);
        }
        for(auto iter:e){
            p.erase(iter);
        }
        e.clear();
        if(sum>mx_sum)mx_sum=sum;
    }
    cout<<mx_sum<<endl;
}

D题:这个题水的呀，简直就不像是D题。刚开始看他这题目我以为是个图什么的，结果仔细分析一下发现就构建一颗树就完了。

我们就先构建一条链，最后往这条链上加边就行了

代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e3+9;
struct node{
    int mx_d,pos;
} a[maxn];
bool cmp(node a,node b){
    return a.mx_d>b.mx_d;
}
vector<int>edge[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int i,j,k,n;
    int cnt=0;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i].mx_d;
        a[i].pos=i;
    }
    sort(a+1,a+n+1,cmp);
    edge[a[1].pos].push_back(a[2].pos);
    cnt++;
    for(i=3;i<=n;i++){
        if(a[i].mx_d>=2)edge[a[i-1].pos].push_back(a[i].pos),cnt++;
        else{
            if(a[i-1].mx_d>=2){
            edge[a[i-1].pos].push_back(a[i].pos);
            cnt++;}
            break;
        }
    }
    int tot_vd=cnt+1,flag=0;
    for(i=1;i<=n;i++){
        int num;
        if(i==1)num=a[i].mx_d-1;
        else num=a[i].mx_d-2;
        int t=1;
        while(t<=num){
            if(tot_vd==n)break;
            if(i==1&&!flag){cnt++;flag=1;}
            edge[a[i].pos].push_back(a[++tot_vd].pos);
            t++;
        }
    }
    if(tot_vd!=n){
        cout<<"NO"<<endl;
    }
    else{
        cout<<"YES"<<' '<<cnt<<endl;
        cout<<n-1<<endl;
        for(i=1;i<=n;i++){
            for(j=0;j<edge[i].size();j++){
                cout<<i<<' '<<edge[i][j]<<endl;
            }
        }
    }
}

E题:待会再搞，容我先去复习一下概率论