【bzoj4644】经典傻逼题【集训队互测2015】最大异或和

Source and Judge

bzoj4644
集训队互测2015
uoj91

Record

1h

Analysis

请先思考后再展开

这两题都要先用异或的性质转化题意
对于【经典傻逼题】,把边权异或到点权上
对于【最大异或和】,把序列异或差分一下
那么现在的目标都是一个支持删除的线性基,以【最大异或和】为例

这种看起来非常难删除的东西,有一个有趣的套路
观察操作,发现有用的数字只有n+m个
把每个数按照出现时间排序,贪心地对结束时间处理

具体而言,维护线性基并惯例地从大往小扫,如果线性基上结束比当前的完,则被替代,然后把拿出来的这个往后更新
那么如果需要删除的时候,一定没有替代方案,所以能够直接删除掉

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
#define pr pair<int,int>
#define FR first
#define SE second
int n,m,q;
const int MAX_N=2100;
#define bs bitset<MAX_N>
char str[MAX_N];
bs getstr()
{
bs ans;
scanf("%s",str);
for(int t=0;t<m;t++) ans[m-1-t]=str[t]-'0';
return ans;
}
void output(bs ans)
{
for(int i=m-1;i>=0;i--) printf("%d",(int)ans[i]);
puts("");
}
struct Num
{
int st,ed;
bs num;
}num[MAX_N*3];//已有序
struct Base
{
int bas[MAX_N];
Base(){memset(bas,0,sizeof bas);}
void insert(int id)
{
for(int i=MAX_N-1;i>=0;i--) if(num[id].num[i])
{
if(bas[i]==0)
{
bas[i]=id;
return;
}
else
{
if(num[id].ed>=num[bas[i]].ed) swap(bas[i],id);
num[id].num^=num[bas[i]].num;
//printf("id=%d bas=%d\n",id,bas[i]);
}
}
}
void del(int id)
{
for(int i=MAX_N-1;i>=0;i--) if(bas[i]==id) bas[i]=0;
}
bs ask()
{
bs ans;
for(int i=MAX_N-1;i>=0;i--) if(bas[i] and ans[i]==0) ans^=num[bas[i]].num;
return ans;
}
}bas;
int a[MAX_N];
int tot=0;
void change(int pos,int ti,bs now)
{
if(a[pos]) num[a[pos]].ed=ti;
num[a[pos]=++tot]=(Num){ti,q+1,now};
//printf("pos=%d ti=%d ->%d\n",pos,ti,(int)now.to_ulong());
}
bool isask[MAX_N];
vector<int> die[MAX_N];//死亡清单
void main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) num[a[i]=++tot]=(Num){0,q+1,getstr()};
for(int i=n;i>=1;i--) num[a[i]].num^=num[a[i-1]].num;
for(int ti=1;ti<=q;ti++)
{
int op;scanf("%d",&op);
if(op==1)
{
int x,y;scanf("%d%d",&x,&y);bs w=getstr();
change(x,ti,num[a[x]].num^w);if(y+1<=n) change(y+1,ti,num[a[y+1]].num^w);
}
else if(op==2)
{
int x,y;scanf("%d%d",&x,&y);bs w=getstr();
if(y+1<=n)//debug 先处理
{
bs nowy;for(int i=1;i<=y+1;i++) nowy^=num[a[i]].num;
change(y+1,ti,nowy^w);
}
bs nowx;for(int i=1;i<=x-1;i++) nowx^=num[a[i]].num;
change(x,ti,nowx^w);for(int i=x+1;i<=y;i++) num[a[i]].ed=ti,a[i]=0;
}
else isask[ti]=1;
}
int now=0;
for(int ti=0;ti<=q;ti++)
{
for(int t=0;t<(int)die[ti].size();t++) bas.del(die[ti][t]);
while(now+1<=tot and num[now+1].st<=ti)
{
now++;
bas.insert(now);
die[num[now].ed].push_back(now);
}
if(isask[ti]) output(bas.ask());
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a417.html
转载请注明出处,谢谢!