【集训队互测2015】最大异或和

正文索引 [隐藏]

描述
输入格式
输出格式
样例一
input
output
限制与约定
来源
下载
题解

描述

我有一个数列 a1,a2,…,an，每个 ai 都是小于 2m 的非负整数。
现在请您实现三种操作，格式说明如下：

1 x y w：对于所有 x≤i≤y，将 ai 修改为 aixorw。其中 w 是一个小于 2m 的非负整数。
2 x y w：对于所有 x≤i≤y，将 ai 修改为 w。其中 w 是一个小于 2m 的非负整数。
3：从 a1,a2,…,an 中选出若干个数，使得选出的数异或和最大。请输出这个最大值。

这里 xor 表示按位异或运算，x1,x2,…,xl 的异或和是指 x1xorx2xor…xorxl。

输入格式

第一行三个正整数 n,m,q。
接下来 n 行为初始时 a1,a2,…,an 的值。
接下来 q 行，每行表示一个操作。操作的格式如前所述。保证 1≤x≤y≤n。
a1,…,an 和 w 均用恰好 m 位的 01 串表示这个数的二进制表示。左边是最高位，右边是最低位，不足 m 位的在左边补 0。

输出格式

对于每个 3 号操作，输出一个 m 位 01 串表示答案的二进制表示。

样例一

input

3 4 7

0000

0011

0110

1 2 3 0010

2 1 2 0010

2 1 3 0000

output

0110

0101

0110

0000

限制与约定

测试点编号	n	m	q	特殊限制
1	=10	=10	=1000	无
2	=500	=500	=10
3	=120	=120	=120
4	=2000	=2000	=10
5	=1800	=1800	=1800	1,2 操作中 x=y
6				只有 1,3 操作
7				只有 2,3 操作
8	=1500	=1500	=1500	无
9	=1800	=1800	=1800
10	=2000	=2000	=2000

时间限制：2s
空间限制：256MB

来源

中国国家集训队互测2015 – By 金策

下载

样例数据下载

题解

我只会写40分、、、高斯消元变成一个三角矩阵、然后顺着高位贪心、、

#include<cstdio>
#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;
const int Maxn=2005;
const int Maxm=2005;
bitset<Maxm> num[Maxn];
bitset<Maxn> tmp;
bitset<Maxn> b[Maxn];
bitset<Maxm> ans;
int w,x,y;
int n,m,q;
inline void swap(bitset<Maxm> &a,bitset<Maxm> &b){
    bitset<Maxm> t=a;
    a=b;
    b=t;
}
inline void guass(){
    int now=1;
    memcpy(b,num,sizeof(num));
    for (int i=m;i>=0;i--){
        if (!b[now][i]){
            for (int j=now+1;j<=n;j++){
                if (b[j][i]){
                    swap(b[now],b[j]);
                    break;
                }
            }
            if (!b[now][i]) continue;
        }
        for (int j=now+1;j<=n;j++)
            if (b[j][i]) b[j]^=b[now];
        now++;
    }
    ans.reset();
    int p=1;
    for (int i=m;i>=0;i--){
        for (int j=p;j<=now;j++){
            if (b[j][i]){
                if (!ans[i]) ans^=b[j];
                p=j+1;
                break;
            }
        }
    }
}
int last=0;
int main(){
    scanf("%d%d%d",&n,&m,&q);
    m--;
    for (int i=1;i<=n;i++)cin>>num[i];
    for (int i=1;i<=q;i++){
        scanf("%d",&w);
        if (w==1 || w==2) scanf("%d%d",&x,&y);
        if (w==1){
            cin>>tmp;
            for (int j=x;j<=y;j++) num[j]^=tmp;
        }
        if (w==2){
            cin>>tmp;
            for (int j=x;j<=y;j++) num[j]=tmp;
        }
        if (w==3){
            if (last!=w) guass();
            for (int j=m;j>=0;j--){
                cout<<ans[j];
            }
            cout<<endl;
        }
        last=w;
    }
    return 0;
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<bitset>

using namespace std;

const int Maxn=2005;

const int Maxm=2005;

bitset<Maxm> num[Maxn];

bitset<Maxn> tmp;

bitset<Maxn> b[Maxn];

bitset<Maxm> ans;

int w,x,y;

int n,m,q;

inline void swap(bitset<Maxm> &a,bitset<Maxm> &b){

bitset<Maxm> t=a;

a=b;

b=t;

}

inline void guass(){

int now=1;

memcpy(b,num,sizeof(num));

for (int i=m;i>=0;i--){

if (!b[now][i]){

for (int j=now+1;j<=n;j++){

if (b[j][i]){

swap(b[now],b[j]);

break;

}

if (!b[now][i]) continue;

}

for (int j=now+1;j<=n;j++)

if (b[j][i]) b[j]^=b[now];

now++;

}

ans.reset();

int p=1;

for (int i=m;i>=0;i--){

for (int j=p;j<=now;j++){

if (b[j][i]){

if (!ans[i]) ans^=b[j];

p=j+1;

break;

}

int last=0;

int main(){

scanf("%d%d%d",&n,&m,&q);

m--;

for (int i=1;i<=n;i++)cin>>num[i];

for (int i=1;i<=q;i++){

scanf("%d",&w);

if (w==1 || w==2) scanf("%d%d",&x,&y);

if (w==1){

cin>>tmp;

for (int j=x;j<=y;j++) num[j]^=tmp;

}

if (w==2){

cin>>tmp;

for (int j=x;j<=y;j++) num[j]=tmp;

}

if (w==3){

if (last!=w) guass();

for (int j=m;j>=0;j--){

cout<<ans[j];

}

cout<<endl;

}

last=w;

}

return 0;

}

[remind]真正的题解：sol.pdf[/remind]

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑