Codeforces Round #416 (Div. 2)

刺骨的言语ヽ痛彻心扉 2022-05-14 02:07 90阅读 0赞

地址：[点我][Link 1]

A. Vladik and Courtesy  
模拟

#include<iostream>
    using namespace std;
    int main(){
    	int n,m;
    	scanf("%d%d",&n,&m);
    	int flag1=0,flag2=0;
    	for(int i=1;i<=1e9;i++){
    		if(i*i>n){
    			flag1=i;
    			break;
    		}
    	}
    	for(int i=1;i<=1e9;i++){
    		if(i*i+i>m){
    			flag2=i;
    			break;
    		}
    	}
    	if(flag2<flag1){
    		printf("Valera\n");
    	}
    	else{
    		puts("Vladik");
    	}
    	
    }

B. Vladik and Complicated Book  
给n个数，然后给一个区间，将区间里的数从小到大排序，问指定位置的数排序后有没有改变位置，这个把区间里的数一个一个和a\[x\]比较，看比他小的数有几个，是不是x-l个

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=1e4+20;
    int a[N];
    int main(){
    	int n,m;
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    	}
    	while(m--){
    		int l,r,x;
    		scanf("%d%d%d",&l,&r,&x);
    		int count=0;
    		for(int i=l;i<=r;i++){
    			if(a[x]>a[i]){
    				count++;
    			}
    		}
    		if(count==x-l){
    			puts("Yes");
    		}
    		else{
    			puts("No");
    		}
    	}
    }

C. Vladik and Memorable Trip  
n^2的动态规划，题意，给n个数，要你划分，如果一个序列里有x,那么这个序列必须包含所有的x. 有的数可以舍弃不用，关键是划分的子序列的异或值加起来要最大  
dp\[i\] 表示从a\[1\]到a\[i\]的最大值，  
递推：dp\[i\]=max(dp\[i-1\],dp\[j-1\]+a\[j\]a\[j+1\]…a\[i\]) 其中\[j,i\]为满足题意的区间

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int N = 5000+10, inf = 0x3f3f3f3f;
    int n, l[N], r[N], a[N], dp[N];
    bool vis[N];
    
    int main(){
    	
        scanf("%d", &n);
        memset(l, inf, sizeof(l));
        memset(r, 0, sizeof(r));
        for(int i=1; i<=n; ++i){
        	
            scanf("%d", &a[i]);
            l[a[i]] = min(l[a[i]], i);
            r[a[i]] = max(r[a[i]], i);
        }
        
        for(int i=1; i<=n; i++){
        	
          
            dp[i]= dp[i-1];
            int L = l[a[i]], R = r[a[i]], t = a[i];
            if(R>i) continue;
            memset(vis, 0, sizeof(vis));
            vis[a[i]] = 1;
            for(int j=i;j>0;j--){
            	
                if(!vis[a[j]]){
                	
                    vis[a[j]] = 1;
                    t ^= a[j];
                }
                L = min(L, l[a[j]]);
                R = max(R, r[a[j]]);
                if(L==j && R==i) dp[i] = max(dp[i], dp[L-1]+t);
                if(R>i) break;
            }
        }
       
        printf("%d\n",dp[n]);
        return 0;
    }

[Link 1]: http://codeforces.com/contest/811