The 16th Zhejiang Provincial Collegiate Programming Contest

àì夳堔傛蜴生んèń 2022-04-24 15:56 161阅读 0赞

本次和队友总共出了五题（E，F，G，H，I）。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    int a[maxn],b[maxn];
    
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		int n;
    		scanf("%d",&n);
    		for(int i=0;i<n;i++){
    			scanf("%d",&a[i]);
    			b[i]=a[i];
    		}
    		sort(a,a+n);
    		int cnt=0,r=n-1;
    		for(int i=n-1;i>=0;i--){
    			while(b[r]!=a[i]&&r>0) r--;
    			if(a[i]==b[r]){
    				cnt++;
    				r--;
    			} 
    			else break;
    		}
    		printf("%d\n",n-cnt);
    	}
    	
    	
    	return 0;
    }

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=110;
    char s[maxn],ans[maxn];
    
    
    int main()
    {
        int T;
        string t="aeiouy";
        scanf("%d",&T);
        while(T--){
            string ans="";
            scanf("%s",s);
            int len=strlen(s);
            ans+=s[0];
            for(int i=1;i<len;i++){
                bool flag=true;
                for(int j=0;j<6;j++){
                    if(s[i]==t[j]){
                        flag=false;
                        break;
                    }
                }
                if(flag) ans+=s[i];
            }
            cout<<ans<<endl;
        }
        return 0;
    }

#include<bits/stdc++.h>
    using namespace std;
    int main(){
    	int T,n;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d",&n);
    		for(int i=n;;i++){
    			if(i%7==0&&i%4!=0){
    				printf("%d\n",i);
    				break;
    			}
    		}
    	}
    	return 0;
    }

H.WA

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    ll a[maxn];
    int vis[maxn];
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		memset(vis,0,sizeof(vis));
    		int n,res=0;
    		scanf("%d",&n);
    		if(n>=1) scanf("%lld",&a[1]);
    		if(n>=2) scanf("%lld",&a[2]);
    		if(n>=3){
    			bool flag=false,tag=false;
    			scanf("%lld",&a[3]);
    			if(a[2]>a[1]&&a[2]>a[3]){
    				res++;
    				if(a[1]==a[3]){
    					flag=true;
    					vis[2]=1;
    				} 
    			}
    			for(int i=4;i<=n;i++){
    				scanf("%lld",&a[i]);
    				if(a[i-1]>a[i]&&a[i-1]>a[i-2]){
    					res++;
    					vis[i-1]=1;
    					if(a[i-2]==a[i]) flag=true;
    				}
    				if(a[i-1]==a[i-3]&&vis[i-1]&&vis[i-3]) tag=true;
    			}
    			if(tag) res-=2;
    			else if(flag) res--; 
    		}
    		printf("%d\n",res);
    	}
    	
    	
    	return 0;
    }

import java.math.BigInteger;
    import java.util.Scanner;
    
    public class Main {
    
    	public static void main(String[] args) {
    		Scanner sc=new Scanner(System.in);
    		int T;
    		T=sc.nextInt();
    		while(true){
    			T--;
    			
    			if(T<0) break;
    			BigInteger a,b;
    			a=sc.nextBigInteger();
    			a=a.subtract(BigInteger.valueOf(1));
    			b=sc.nextBigInteger();
    			a=a.mod(BigInteger.valueOf(3));
    			b=b.mod(BigInteger.valueOf(3));   
    			int A=Integer.valueOf(a.toString());
    			int B=Integer.valueOf(b.toString());
    			int ra=0,rb=0;
    			if(A==1) ra=1;
    			if(B==1) rb=1;
    			System.out.println((ra+rb)%2);
    		} 
    
    	}
    
    }

[J.Welcome Party][] (zoj4109)

我用并查集和优先队列处理的，结果超时（详情见代码1）。

**代码1（超时代码）：**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    int par[maxn],n,m,vis[maxn];
    
    void Init(){
    	for(int i=1;i<=n;i++){
    		par[i]=i;
    	}
    	
    }
    
    int fi(int x){
    	if(par[x]==x) return x;
    	return par[x]=fi(par[x]);
    }
    
    void join(int x,int y){
    	int fx=fi(x),fy=fi(y);
    	if(fx!=fy){
    		par[fx]=fy;
    	}
    }
    
    
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		Init();
    		vector<vector<int> > v;
    		v.resize(n+1);
    		int a,b;
    		while(m--){
    			scanf("%d%d",&a,&b);
    			join(a,b);
    			v[a].push_back(b);
    			v[b].push_back(a);
    		}
    		int cnt=0;
    		for(int i=1;i<=n;i++){
    			if(par[i]==i) cnt++;
    		}
    		printf("%d\n",cnt);
    		memset(vis,0,sizeof(vis));
    		priority_queue<int,vector<int>,greater<int> > pq;
    		pq.push(1);
    		vis[1]=1;
    		
    		int x=fi(1),y;
    		for(int i=1;i<=n;i++){
    			if(fi(i)!=x){
    				join(i,1);
    				pq.push(i);
    				vis[i]=1;
    			}
    		}
    		bool flag=false;
    		while(!pq.empty()){
    			x=pq.top();
    			pq.pop();
    			if(!flag){
    				printf("%d",x);	
    				flag=true;
    			} 
    			else printf(" %d",x);
    			int len=v[x].size();
    			for(int i=0;i<len;i++){
    				y=v[x][i];
    				if(!vis[y]){
    					vis[y]=1;
    					pq.push(y);
    				}
    			}
    		}
    		printf("\n");
    		
    	}
    	
    	
    	return 0;
    }

**代码2（修改后AC）：**

**注意：1.并查集注意让序号小的为根，不然找根的时候爆栈导致段错误；**

**2.不要用memset初始化，不然超时。**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    int par[maxn],n,m,vis[maxn];
     
    void Init(){
    	for(int i=1;i<=n;i++){
    		par[i]=i;
    	}
    	
    }
     
    int fi(int x){
    	if(par[x]==x) return x;
    	return par[x]=fi(par[x]);
    }
     
    void join(int x,int y){
    	int fx=fi(x),fy=fi(y);
    	if(fx!=fy){
    		if(fx>fy) par[fx]=fy;
    		else par[fy]=fx;
    	}
    }
     
     
     
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		Init();
    		vector<vector<int> > v;
    		v.resize(n+1);
    		int a,b;
    		while(m--){
    			scanf("%d%d",&a,&b);
    			join(a,b);
    			v[a].push_back(b);
    			v[b].push_back(a);
    		}
    		int cnt=0;
    		for(int i=1;i<=n;i++){
    			vis[i]=0;
    			if(par[i]==i) cnt++;
    		}
    		printf("%d\n",cnt);
    		priority_queue<int,vector<int>,greater<int> > pq;
    		
    		int x,y;
    		for(int i=1;i<=n;i++){
    			if(fi(i)==i){
    				pq.push(i);
    				vis[i]=1;
    			}
    		}
    		bool flag=false;
    		while(!pq.empty()){
    			x=pq.top();
    			pq.pop();
    			if(!flag){
    				printf("%d",x);	
    				flag=true;
    			} 
    			else printf(" %d",x);
    			int len=v[x].size();
    			for(int i=0;i<len;i++){
    				y=v[x][i];
    				if(!vis[y]){
    					vis[y]=1;
    					pq.push(y);
    				}
    			}
    		}
    		printf("\n");
    		
    	}
    	
    	
    	return 0;
    }

[J.Welcome Party]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4109