Codeforces Round #557 (Div. 2) [based on Forethought Future Cup - Final Round]

淡淡的烟草味﹌ 2022-02-05 12:53 130阅读 0赞

### A. Zoning Restrictions Again ###

暴力  每次取区间最小值

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    
    const  ll N = 5e5+100;
    ll n,h,m;
    ll l,r,s;
    ll b[N];
    ll ans;
    int main(){
    	cin>>n>>h>>m;
    	for(int i=1;i<=n;i++){
    		b[i]=h;
    	}
    	for(int i=1;i<=m;i++){
    		cin>>l>>r>>s;
    		for(int j=l;j<=r;j++){
    			b[j]=min(b[j],s);
    		}
    	}
        for(int i=1;i<=n;i++){
        	//cout<<b[i]<<endl;
        	ans+=b[i]*b[i];
    	}
    	cout<<ans<<endl;
    	return 0;
    }

### B. Double Matrix ###

一个小矩阵，一个大矩阵，然后判断

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    
    const  ll N =55;
    int a[N][N],b[N][N],c[N][N],d[N][N];
    int n,m;
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++) 
    		 cin>>a[i][j];
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++) 
    		 cin>>b[i][j];
    	}
    	int flag=0;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			c[i][j]=min(a[i][j],b[i][j]);
    			d[i][j]=max(a[i][j],b[i][j]);
    		}
    	}
    //	cout<<endl;
    //	for(int i=1;i<=n;i++){
    //		for(int j=1;j<=m;j++)
    //		cout<<c[i][j]<<" ";
    //		cout<<endl;
    //	}
    //	cout<<endl;
    //	for(int i=1;i<=n;i++){
    //		for(int j=1;j<=m;j++)
    //		cout<<d[i][j]<<" ";
    //		cout<<endl;
    //	}
    	
        if(n==1){
        	for(int i=1;i<m;i++){
        		if(c[1][i]>=c[1][i+1] || d[1][i]>=d[1][i+1]){
        			flag=1;break;
    			}
    		}
    	}
    	else if(m==1){
    		for(int i=1;i<n;i++){
    			if(c[i][1]>=c[i+1][1] || d[i][1]>=d[i+1][1]){
    				flag=1;break;
    			}
    		}
    	}
    	else{
    		for(int i=1;i<n;i++){
    		for(int j=1;j<m;j++){
    			if(c[i][j]>=c[i][j+1] || d[i][j]>=d[i][j+1] || c[i+1][j]<=c[i][j] || d[i+1][j]<=d[i][j]){
    				   flag=1;break;	
    				//else swap(a[i][j+1],b[i][j+1]);
    			} 
    		}
    	 }
    	 
    	 for(int i=1;i<m;i++){
        		if(c[n][i]>=c[n][i+1] || d[n][i]>=d[n][i+1]){
        			flag=1;break;
    			}
    		}
    		
    	for(int i=1;i<n;i++){
    			if(c[i][m]>=c[i+1][m] || d[i][m]>=d[i+1][m]){
    				flag=1;break;
    			}
    		}
    	}
    	
    	if(flag==1) cout<<"Impossible"<<endl;
    	else cout<<"Possible"<<endl;
    	return 0;
    }

### C. Hide and Seek ###

一共3\*(n-2)+4种可能区间，减去出现过的即可

#include<bits/stdc++.h>
    using namespace std;
    int n,k;
    set< pair<int,int> > s;
    int main(){
    	cin>>n>>k;
    	int a;
    	for(int i=1;i<=k;i++){
    		cin>>a;
    		s.insert({a,0});
    		if(s.count({a-1,0})==1){
    			s.insert({a-1,a});
    		}
    		if(s.count({a+1,0})==1){
    			s.insert({a+1,a});
    		}
    	}
    	int sum=3*(n-2)+4;
    	if(n==1) sum=1;
    	cout<<sum-s.size()<<endl;
    	return 0;
    }