Codeforces Round #153 (Div. 2)

从此醉

浏览: 1040022 次
性别:
来自: US

最近访客更多访客>>

billyhhzh

u012363178

devcang

宝帅啊啊啊

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

点击打开链接cf #153

思路：暴力
分析：
1 题目给定n个数 n<=100，要求一个区间内做^能够得到的最大值
2 n最大为100，暴力枚举区间即可。

代码：

#include<iostream>
#include<cstdio>
using namespace std;

#define MAXN 110

int n;
int num[MAXN];

int main(){
   while(scanf("%d" , &n) != EOF){
      for(int i = 0 ; i < n ; i++)
         scanf("%d" , &num[i]);
      long long max = 0;

      for(int i = 0 ; i < n ; i++){
         for(int j = i ; j < n ; j++){
            long long tmp = num[i];  
            for(int k = i+1 ; k <= j ; k++)
               tmp = tmp^num[k];
            if(tmp > max)
              max = tmp;
         }
      }
      cout<<max<<endl;
   }
   return 0;
}

法一

思路：暴力
分析：
1 题目问能否找到两个不同的位置i , j.使得i 和 j交换后序列不是有序的。如果找不到输出-1
2 很明显n<=2时是不可能找到的，输出-1；还有一中特殊的情况就是num[1]=num[2]=...=num[n]，这种也是输出-1.
3 接下来就是暴力枚举i个j的值，然后找到满足的即可。
4 注意如果没有找到应该输出-1，这里不能漏了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 100010

int n;
int num[MAXN];

bool ok(){
   for(int i = 2 ; i < n ; i++){
      if(!((num[i] >= num[i-1] && num[i] <= num[i+1]) || (num[i] <= num[i-1] && num[i] >= num[i+1]))){
        return true;
      }
   }
   return false;
}

int main(){
   while(scanf("%d" , &n) != EOF){
       bool mark = true;
       scanf("%d" , &num[1]);
       for(int i = 2 ; i <= n ; i++){
          scanf("%d" , &num[i]);
          if(num[i] != num[i-1])
            mark = false;
       }
       if(mark || n <= 2)
         printf("-1\n");
       else{
         mark = false;
         for(int i = 1 ; i <= n ; i++){
            for(int j = i+1 ; j <= n ; j++){
               if(num[i] == num[j])
                 continue;
               swap(num[i] , num[j]);           
               if(ok()){
                 printf("%d %d\n" , i , j);
                 mark = true;  
                 break;
               }
               swap(num[i] , num[j]);
            }
            if(mark)
              break;
         }
         if(!mark)
           printf("-1\n");
       }
   }
   return 0;
}

法二

思路：分类模拟
分析：
1 题目要求找到两个位置交换这两个位置的数，使得序列不是单调的。如果没有输出-1
2 如果n<=2，肯定是不可能找到满足的位置的。
3 那么我们可以通过分析序列总共有几个不同的数字。
如果只有1个就是类似1 1 1...这样的肯定找不到输出-1；
如果是2个那么我们一个for循环找到num[i] != num[i-1]，然后交换它判断是否满足即可。2个的情况可能会有不满足情况，如果都不满足那么就输出-1；
如果是大于等于3个，那么我们只要找出三个不同的数然后交换。但是这三个数原先的排列情况有4种(/，/\，\，\/ 表示增减)。那么我们只要去判断最大值的位置就可以。有三个不同的数那么肯定是可以找到两个位置的。

代码：

#include<iostream>
#include<cstdio>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;

#define MAXN 100010

int n;
int num[MAXN];
set<int>s;

bool ok(){  
   for(int i = 2 ; i < n ; i++){  
      if(!((num[i] >= num[i-1] && num[i] <= num[i+1]) || (num[i] <= num[i-1] && num[i] >= num[i+1]))){  
        return true;  
      }  
   }  
   return false;  
}

int main(){
   while(scanf("%d" , &n) != EOF){
       s.clear();
       for(int i = 1 ; i <= n ; i++){
          scanf("%d" , &num[i]);
          s.insert(num[i]);
       }
       int size = s.size();
       /*如果只有1个不同的数*/
       if(size == 1 || n <= 2)
         printf("-1\n");
       /*大于等于3个不同数*/
       else if(size >= 3){
         int pos[3];
         int cnt = 0;
         pos[0] = 1;         
         for(int i = 2 ; i <= n ; i++){
            if(num[i] != num[pos[cnt]])
               pos[++cnt] = i;
            if(cnt == 3)
               break;
         }
        
         int MAX = max(num[pos[0]] , num[pos[1]]);
         MAX = max(MAX , num[pos[2]]);  
         /*判断最大值位置*/
         if(num[pos[0]] == MAX)
              printf("%d %d\n" , pos[0] , pos[1]);
         else if(num[pos[1]] == MAX)
              printf("%d %d\n" , pos[0] , pos[2]);
         else if(num[pos[2]] == MAX)
              printf("%d %d\n" , pos[1] , pos[2]);
       }       
       /*只有2个不同数*/
       else if(size == 2){
          bool mark = false;
          for(int i = 2 ; i <= n ; i++){
             if(num[i] != num[i-1]){
               swap(num[i] , num[i-1]);
               if(ok()){
                  printf("%d %d\n" , i , i-1);
                  mark = !mark;
                  break;  
               }
               swap(num[i] , num[i-1]);
             }
          }
          if(!mark)/*如果没有找到输出-1*/
            printf("-1\n");
       }
   }
   return 0;
}

思路：1 枚举起点，维护一个末尾指针。2 另外一种做法是把维护的指针 j 改成二分查找
分析：
1 题目给定一个n个数的有序序列，要求找到最多的方法满足题目要求。
2 我们知道一个有序的序列是很特殊的，假设现在我们的起点是num[i]，那么我们维护一个指针j，使得num[j]-num[i] > d。那么我们知道[i,j)就有j-i-1个数，所以知道了起点那么满足的个数就是C(j-i-1,2){组合公式}。那么我们接下来起点变成了num[i+1]，这个时候正常的做法是j 从 i+2开始，但是由于这个序列是有序的序列有num[i]>num[i-1]，那么肯定 j 之前的数都满足num[j-1]-num[i+1] <= d，所以 j 不用回溯这样就不是O(n^2)而是接近O(n)的复杂度。
3 注意：假设int n = 100000 ， long long ans = n*(n-1)*(n-2)；这个运算实际是得不到ans的，由于n是int,所以运算的时候超出了int范围，所以得到的ans是错误的。应该注意ans是long long 的情况下 n 也要改为 long long.
4 对于一个有序的序列进行二分的时候是可以利用STL的lower_bound() 和 upper_bound()函数的。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long int64;
#define MAXN 100010

int64 n , d;/*注意n d要为long long */
int64 num[MAXN];

int main(){
    while(cin>>n>>d){
       for(int i = 0 ; i < n ; i++)
          cin>>num[i];
       if(n == 1 || n == 2){
          printf("0\n");
          continue;
       }
       
       int64 maxDis = num[n-1]-num[0];
       int64 ans;

       if(maxDis <= d){
         ans = (n)*(n-1)*(n-2)/6;
         cout<<ans<<endl;
       }
       else{
         ans = 0;
         int j = 0;/*维护的指针j*/
         for(int i = 0 ; i < n-2 ; i++){
            if(num[i+2]-num[i] <= d){
              for(; j < n ; j++){
                 if(num[j]-num[i] > d)
                   break;
              }
              int64 tmp = j-i-1;
              ans += tmp*(tmp-1)/2;
            }
         }
         cout<<ans<<endl;
       }
    }
    return 0;
}

/*二分*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long int64;
#define MAXN 100010

int64 n , d;/*注意n d要为long long */
int64 num[MAXN];

int main(){
    while(cin>>n>>d){
       for(int i = 0 ; i < n ; i++)
          cin>>num[i];
       if(n == 1 || n == 2){
          printf("0\n");
          continue;
       }
       
       int64 maxDis = num[n-1]-num[0];
       int64 ans;

       if(maxDis <= d){
         ans = (n)*(n-1)*(n-2)/6;
         cout<<ans<<endl;
       }
       else{
         ans = 0;
         int left , right , mid;
         for(int i = 0 ; i < n-2 ; i++){
            if(num[i+2]-num[i] <= d){
              /*二分查找*/
              left = i+3 , right = n;
              while(left < right){
                 mid = left+(right-left)/2;
                 if(num[mid]-num[i] > d)
                    right = mid;
                 else
                    left = mid+1;
              }
              int64 tmp = left-i-1;
              ans += tmp*(tmp-1)/2;
            }
         }
         cout<<ans<<endl;
       }
    }
    return 0;
}

分析：

1 题目的意思给定一个序列p初始为1,2,3....n。再给定一个序列q和一个序列s，做k次的变换

2 每一次的变换有两种可能，第一种是生成一个新的序列p且newp[i] = p[q[i]]，第二种是生成一个新的序列p且newp[q[i]] = p[i]

3 现在题目要问的是把初始化的序列p做k次的变换，能否前k-1次都没有出现序列s，最后一次序列正好为s

4 根据第2点，我们可以推出第一种变换和第二种变换是逆的。也就是说做一次的第一种和一次的第二种变换得到的原来的序列。

5如果我们执行m1次第一种变换可以使得序列p等于序列s，那么我们先执行(k - m1) / 2次的(第一种变换、第二种变换)组合，再执行m1次第一种变换即可。

如果我们执行m2次第二种变换可以使得序列p等于序列s，那么我们先执行(k - m2) / 2次的(第一种变换、第二种变换)组合，再执行m2次第二种变换即可。

所以只要求出其中的m1、m2再判断一下k - m1，k - m2是否是偶数就行了。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 110;

int n , k;
int p[MAXN];
int q[MAXN];
int s[MAXN];
char ans[2][4] = {"NO","YES"};

bool isEqual(){
	for(int i = 1 ; i <= n ; i++)
		if(s[i] != p[i])
			return false;
	return true;
}

void init(){
	for(int i = 1 ; i <= n ; i++)
		p[i] = i;
}

char* solve(){
	init();
	if(isEqual())
		return ans[0];
	int m1 = -1;
	int m2 = -1;
	int tmp[MAXN];
	// get m1
	for(int i = 1 ; i <= k ; i++){
		for(int j = 1 ; j <= n ; j++)
			tmp[j] = p[q[j]];
		memcpy(p , tmp , sizeof(p));
		if(isEqual()){
			m1 = i;
			break;
		}
	}
	init();
    // get m2	
	for(int i = 1 ; i <= k ; i++){
		for(int j = 1 ; j <= n ; j++)
			tmp[q[j]] = p[j];
		memcpy(p , tmp , sizeof(p));
		if(isEqual()){
			m2 = i;
			break;
		}
	}
	// judge
	if(m1 == -1 && m2 == -1)
		return ans[0];
	else if(m1 == 1 && m2 == 1 && k > 1)
		return ans[0];
	else if(m1 != -1 && (k-m1)%2 == 0)
		return ans[1];
	else if(m2 != -1 && (k-m2)%2 == 0)
		return ans[1];
	else
		return ans[0];
}

int main(){
    while(scanf("%d%d" , &n , &k) != EOF){
		for(int i = 1 ; i <= n ; i++)
			scanf("%d" , &q[i]);
		for(int i = 1 ; i <= n ; i++)
			scanf("%d" , &s[i]);
		cout<<solve()<<endl;
	}
	return 0;
}