Codeforces Round #182 (Div. 2)

点击打开链接cf 182

A

/*
题目的真正意思是问能否由r-l+1个数组成和为0
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 2*100010;

int main(){
    int x , n , m;
    int num1 , num2;
    while(scanf("%d%d" , &n , &m) != EOF){
         num1 = num2 = 0;
         for(int i = 1 ; i <= n ; i++){
            scanf("%d" , &x); 
            x == 1 ? num1++ : num2++;
         }
         int l , r;
         for(int i = 0 ; i < m ; i++){
            scanf("%d%d" , &l , &r); 
            int tmp = r-l+1;
            if(tmp&1)
               puts("0");
            else{
               if(num1*2 >= tmp && num2*2 >= tmp) 
                 puts("1");            
               else
                 puts("0");
            }
         }
    }
    return 0;
}

B

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

typedef long long int64;
const int MAXN = 100010;

struct Node{
    int num;
    int64 start;
    int64 end;
};
Node node[MAXN]; 
int n , m;

int getAns(int x){
    int left , right , mid;
    left = 1 , right = n;
    while(left <= right){
         mid = (left+right)/2;
         if(node[mid].start <= x && node[mid].end >= x)
            return mid;
         else if(node[mid].start > x)
            right = mid-1;
         else
            left = mid+1;
    }
}

int main(){
    int pre;
    int x , y;
    while(scanf("%d%d" , &n , &m) != EOF){
         pre = 0;
         for(int i = 1 ; i <= n ; i++){
             scanf("%d%d", &x , &y); 
             node[i].num = i;
             node[i].start = pre+1;
             node[i].end = pre+x*y;
             pre = node[i].end;
         } 
         for(int i = 0 ; i < m ; i++){
            scanf("%d" , &x);
            printf("%d\n" , getAns(x));
         }
    }
    return 0;
}

C

/*
1 总共有2*n-1个数就是奇数个数
2 如果n为奇数，那么说明每次可以变换的个数为n，那么无论负数的个数是偶数还是奇数那么最后都是可以变成正数，所以最后的和就是所有数的绝对值之和
3 如果n为偶数，那么每次要变换的个数是偶数个，如果负数的个数是奇数个那么最后是不能全部变成呢个正数的，那么我们留下绝对值最小的那个负数，如果奇数的个数是偶数个那么最后肯定是可以把所有的数都变成正数的

代码: 
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n;
    while(scanf("%d" , &n) != EOF){
         int sum = 0;
         int minNum = 1<<30;
         int cnt = 0;
         int x;
         for(int i = 0 ; i < 2*n-1 ; i++){
             scanf("%d" , &x); 
             sum += abs(x);
             if(x < 0) 
                cnt++;
             minNum = min(minNum , abs(x)); 
         }
         if(n&1)
             printf("%d\n" , sum);
         else{
             if(cnt&1) 
                 printf("%d\n" , sum-2*minNum); 
             else
                 printf("%d\n" , sum);
         }
    }
    return 0;
}

D

/*
floyd算法求最短路
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 110;

struct Node{
    int x;
    int y;
};
Node node[MAXN];
int n , d , a[MAXN];
int dis[MAXN][MAXN];

void init(){
    for(int i = 1 ; i <= n ; i++){
       for(int j = 1 ; j <= n ; j++)
          dis[i][j] = d*(abs(node[i].x-node[j].x)+abs(node[i].y-node[j].y))-a[j]; 
       dis[i][i] = 0;
    }
}

void floyd(){
    for(int k = 1 ; k <= n ; k++){
       for(int i = 1 ; i <= n ; i++){
          for(int j = 1 ; j <= n ; j++)
             dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]); 
       }    
    }
}

int main(){
    memset(a , 0 , sizeof(a));
    while(scanf("%d%d" , &n , &d) != EOF){
        for(int i = 2 ; i <= n-1 ; i++) 
           scanf("%d" , &a[i]); 
        for(int i = 1 ; i <= n ; i++)
           scanf("%d%d" , &node[i].x , &node[i].y);
        init(); 
        floyd();
        printf("%d\n" , dis[1][n]);
    }
    return 0;
}