Codeforces620F Xors on Segments（位运算模拟）

February 08, 2016

题目链接

2016 年第一题献给 CF 了！

题意：n 个数，m 次询问，每次询问给出左右端点，求出区间内任意两个数 f(x,y)的最大值。其中 f（x,y）=x^(x+1)^…^y. (x<=y).

思路：预处理出 1~n 的连续异或的结果。用两重循环遍历所有两两组合，内部循环标记右侧端点最大值，内部循环结束后遍历所有询问更新结果。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int y[1000005];
int main(){
    //freopen("a.txt", "r", stdin);
    y[0]=0;
    for(int i = 1; i <= 1000002; i++)   //预处理
        y[i] = y[i-1]^i;
    int n, m;
    while(scanf("%d %d", &n, &m) != EOF){
        int a[50005], l[5005], r[5005];
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for(int i = 1; i <= m; i++)
            scanf("%d %d", &l[i], &r[i]);
        int ans[5005];
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i <= n; i++){
            int qq[50005];      //qq[j]代表i到j区间内最大值
            for(int j = i; j <= n; j++){
                int minn = min(a[i], a[j]);
                int maxx = max(a[i], a[j]);
                if(j == i) qq[j] = y[maxx]^y[minn-1];
                else qq[j] = max(qq[j-1], y[maxx]^y[minn-1]);
            }
            for(int k = 1; k <= m; k++){    //更新所有询问的答案
                if(i>=l[k] && i<=r[k]){
                    ans[k] = max(ans[k], qq[r[k]]);
                }
            }
        }
        for(int i = 1; i <= m; i++)
            cout << ans[i] << endl;
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]