ICPC#2020澳门站

C.Club Assignment

挺小清新的一个构造题。要尽量使得高位能有1，如果无法避免有的异或值高位为0的话，那么就继续递归地往下讨论，并且这一位不同的数字之间的相对位置关系对答案就不会产生影响了。

模拟赛的过程中没写完，下来花了1个多小时一遍AC了，还是挺爽的。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int mn=1e5+5;
const ll mod=998244353;
const double eps=1e-10;
int n;
int trie[mn*31][2],a[mn],cnt,siz[mn*31];
vector<pii> ad[mn*31];
void insert(int x,int cur)
{
	int pos=0;
	for(int i=30;i>=0;--i) {
		siz[pos]++;
		if(ad[pos].size()>1)ad[pos].pop_back();
		ad[pos].push_back({x,cur});
		if(!trie[pos][(x>>i)&1]) trie[pos][(x>>i)&1]=++cnt;
		pos=trie[pos][(x>>i)&1];
	}
	siz[pos]++;
	if(ad[pos].size()>1)ad[pos].pop_back();
	ad[pos].push_back({x,cur});
}

int vis[mn];
int dfs(int x,int dep)
{
	if(!dep){
		return 0;
	}
	int s0=siz[trie[x][0]],s1=siz[trie[x][1]];
	int p0=trie[x][0],p1=trie[x][1];
	if(!s0||!trie[x][0])return dfs(trie[x][1],dep-1);
	if(!s1||!trie[x][1])return dfs(trie[x][0],dep-1);
	// printf("$$%d %d\n",x,dep);
	if(s0>2){
		if(s1>2){
			return min(dfs(trie[x][0],dep-1),dfs(trie[x][1],dep-1));
		}
		else {
			for(int i=0;i<ad[p1].size();i++){
				vis[ad[p1][i].second]=i+1;
			}
			return dfs(trie[x][0],dep-1);
		}
	}
	else if(s0==2){
		if(s1>2){
			for(int i=0;i<ad[p0].size();i++){
				vis[ad[p0][i].second]=i+1;
			}
			return dfs(trie[x][1],dep-1);
		}
		else if(s1==2){
			int res0=min(ad[p0][0].first^ad[p1][0].first,ad[p0][1].first^ad[p1][1].first);
			int res1=min(ad[p0][1].first^ad[p1][0].first,ad[p0][0].first^ad[p1][1].first);
			if(res0<res1){
				vis[ad[p0][1].second]=vis[ad[p1][0].second]=1;
				vis[ad[p0][0].second]=vis[ad[p1][1].second]=2;
				return res1;
			}
			else {
				vis[ad[p0][0].second]=vis[ad[p1][0].second]=1;
				vis[ad[p0][1].second]=vis[ad[p1][1].second]=2;
				return res0;
			}
		}
		else {
			int res0=ad[p0][0].first^ad[p1][0].first;
			int res1=ad[p0][1].first^ad[p1][0].first;
			if(res0<res1){
				vis[ad[p0][1].second]=vis[ad[p1][0].second]=1;
				vis[ad[p0][0].second]=2;
				return res1;
			}
			else {
				vis[ad[p0][0].second]=vis[ad[p1][0].second]=1;
				vis[ad[p0][1].second]=2;
				return res0;
			}
		}
	}
	else {
		if(s1>2){
			vis[ad[p0][0].second]=1;
			return dfs(trie[x][1],dep-1);
		}
		else if(s1==2){
			int res0=ad[p1][0].first^ad[p0][0].first;
			int res1=ad[p1][1].first^ad[p0][0].first;
			if(res0<res1){
				vis[ad[p1][1].second]=vis[ad[p0][0].second]=1;
				vis[ad[p1][0].second]=2;
				return res1;
			}
			else {
				vis[ad[p1][0].second]=vis[ad[p0][0].second]=1;
				vis[ad[p1][1].second]=2;
				return res0;
			}
		}
		else return 0;
	}
}
void init(){
	for(int i=1;i<=n;i++){
		vis[i]=0;
	}
	for(int i=0;i<=cnt;i++){
		trie[i][0]=trie[i][1]=0;
		ad[i].clear();
		siz[i]=0;
	}
	cnt=0;
}
int main(){
	int T=1;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;++i) {
			scanf("%d",a+i);
			insert(a[i],i);
		}
		printf("%d\n",dfs(0,31));
		for(int i=1;i<=n;i++)if(!vis[i])vis[i]=1;
		for(int i=1;i<=n;i++)printf("%d",vis[i]);
		printf("\n");
		init();
	}

	return 0;
}

J.Jewel Grab

这道题使用了不太常见的线段树应用方法，正解不太好写，我现在也还是一直wa，可能有些地方没有考虑到，过两天再补一下。(第二天补充：已AC，更改了一下更新的时候的写法就过了)

先预处理每个颜色的前面第一个和后面第一个相同的颜色的位置。然后使用线段树一个一个地跳，因为KK比较小，所以KlognKlogn的复杂度是可以接受的。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=2e5+5;
const ll mod=998244353;
const double eps=1e-10;
int n,m;
int pre[maxn],nxt[maxn];
int c[maxn],v[maxn],pos[maxn];
set<int>st[maxn];
struct node{
	ll sum;
	int mx;
}t[maxn<<2];
void push_up(int rt){
	t[rt].mx=max(t[rt<<1].mx,t[rt<<1|1].mx);
	t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
}
void build(int rt,int l,int r){
	if(l==r){
		t[rt].sum=v[l];
		t[rt].mx=pre[l];
		return ;
	}
	int mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	push_up(rt);
}
void update(int rt,int l,int r,int xp){
	int mid=l+r>>1;
	if(l==r){
		t[rt].mx=pre[l];
		t[rt].sum=v[l];
		return ;
	}
	if(xp<=mid)update(rt<<1,l,mid,xp);
	else update(rt<<1|1,mid+1,r,xp);
	push_up(rt);
}
ll query(int rt,int l,int r,int xl,int xr){
	int mid=l+r>>1;
	ll res=0;
	if(xl==l&&xr==r){
		return t[rt].sum;
	}
	if(xl<=mid)res+=query(rt<<1,l,mid,xl,min(mid,xr));
	if(xr>mid)res+=query(rt<<1|1,mid+1,r,max(mid+1,xl),xr);
	return res;
}
int find(int rt,int l,int r,int idx,int xl,int xr){
	int mid=l+r>>1;
	int xp=0;
	if(l==r){
		if(t[rt].mx>=idx)return l;
		else return 0;
	}
	if(xl<=mid){
		if(t[rt<<1].mx>=idx)
			xp=find(rt<<1,l,mid,idx,xl,min(xr,mid));
	}
	if(!xp&&xr>mid){
		if(t[rt<<1|1].mx>=idx)
			xp=find(rt<<1|1,mid+1,r,idx,max(mid+1,xl),xr);
	}
	return xp;
}
int main(){
	int T=1;//scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d%d",&c[i],&v[i]);	
			pre[i]=pos[c[i]];
			pos[c[i]]=i;
			st[c[i]].insert(i);
		}
		for(int i=1;i<=n;i++)pos[i]=n+1;
		for(int i=n;i>=1;i--){
			nxt[i]=pos[c[i]];
			pos[c[i]]=i;
		}
		build(1,1,n);
		while(m--){
			int opt,x;
			scanf("%d",&opt);
			if(opt==1){
				scanf("%d",&x);
				if(pre[x])nxt[pre[x]]=nxt[x];
				if(nxt[x]!=n+1)pre[nxt[x]]=pre[x];
				st[c[x]].erase(x);
				if(nxt[x]&&nxt[x]!=n+1)update(1,1,n,nxt[x]);
				scanf("%d%d",&c[x],&v[x]);
				st[c[x]].insert(x);
				auto it=st[c[x]].lower_bound(x);
				pre[x]=0;nxt[x]=n+1;
				if(it!=st[c[x]].begin()){
					int cur=*(--it);
					nxt[x]=nxt[cur];
					pre[x]=cur;
					if(nxt[x]!=n+1)pre[nxt[x]]=x;
					if(pre[x])nxt[pre[x]]=x;						
				}
				else {
					++it;
					if(it!=st[c[x]].end()){
						int cur=*it;
						nxt[x]=cur;
						pre[cur]=x;
					}
				}
				update(1,1,n,x);
				if(nxt[x]&&nxt[x]!=n+1)update(1,1,n,nxt[x]);
			}
			else {
				int s,k;
				scanf("%d%d",&s,&k);
				int cur=s;
				ll skp=0;
				unordered_map<int,int>mp;
				for(int i=1;i<=k+1;i++){
					if(cur==n){cur=n+1;break;}
					cur=find(1,1,n,s,cur+1,n);
					if(!cur){cur=n+1;break;}
					if(i!=k+1){
						if(!mp.count(c[cur])){
							mp[c[cur]]=max(v[cur],v[pre[cur]]);
							skp+=min(v[cur],v[pre[cur]]);
						}
						else{
							skp+=min(v[cur],mp[c[cur]]);
							mp[c[cur]]=max(mp[c[cur]],v[cur]);
						}				
					}
				}
				printf("%lld\n",query(1,1,n,s,cur-1)-skp);
			}
		}
	}
	return 0;
}

K.Candy Ads

bitset是坏文明

这个题简直毒瘤，如果不用bitset的话感觉光是输出答案都会TLE

很正常的2-SAT建图，不过注意要用bitset来存图

然后就是解决问题了，这里需要用到Kosaraju Algorithm来求强连通分量，因为这个方法可以利用bitset来优化时间，而tarjan却做不到这一点

这里先挖个坑，代码过两天来补