D. Chemical table

最开始想了一个比较复杂的解法，调整了很久依然WA5。下来看题解才发现这个题目其实十分简单，把行和列看为点，然后输出联通块的数量减一即可。

证明如下：

首先，每一个二维平面上的点(r,c)(r,c)都可以看成是点r和点c之间连的一条边。显然这是一个二分图。题意要求我们覆盖满所有的二维平面上的点，就相当于要让每一行和每一列之间都要互相连通。由于是二分图，所以我们要连接的点之间的边一定是奇数条。易知，对于任意一个连通块，其内部的行点和列点一定连通。

这里还是贴一下我的wa代码吧

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
// WA
#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,q;
ll ans;
vector<pii>seg;
vector<int>vec[maxn];
pii a[maxn];
int vis[maxn],up[maxn],mem[maxn];
bool cmp(pii x,pii y){
	return x.first==y.first?x.second>y.second:x.first<y.first;
}
int main(){
	int T=1;//scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&q);
		for(int i=1;i<=q;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			vec[y].push_back(x);
			vis[y]=1;
		}
		for(int i=1;i<=m;i++){
			if(!vec[i].size())continue;
			sort(vec[i].begin(),vec[i].end());
			int pre=vec[i][0],cur=vec[i][0];
			for(auto j:vec[i]){
				if(j==vec[i][0])continue;
				if(j==cur+1)cur++;
				else {
					seg.push_back({pre,cur});
					up[cur]=1;
					cur=j;pre=j;
				}
			}
			seg.push_back({pre,cur});
		}
		sort(seg.begin(),seg.end(),cmp);
		int pre=0;
		for(auto p:seg){
			int l=p.first,r=p.second;
			if(pre&&pre<l){
				mem[pre]=1;
			}
			for(int i=pre+1;i<l;i++)ans++;
			pre=max(r,pre);
		}
		
		for(int i=pre+1;i<=n;i++)ans++;printf("%d\n",ans);
		for(int i=1;i<=n;i++){
			if(mem[i]&&(!up[i]))ans++;
		}
		
		for(int i=1;i<=m;i++){
			if(!vis[i])ans++;
		}
		printf("%lld\n",ans);
	}


	return 0;
}
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
// AC
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=4e5+5;
const ll mod=998244353;
const double eps=1e-10;
int n,m,q;
vector<int>e[maxn];
int vis[maxn];
void dfs(int u){
	for(auto v:e[u]){
		if(vis[v])continue;
		vis[v]=vis[u];
		dfs(v);
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=q;i++){
		int r,c;
		scanf("%d%d",&r,&c);
		e[r+m].push_back(c);
		e[c].push_back(r+m);		
	}
	int ans=0;
	for(int i=1;i<=n+m;i++){
		if(vis[i])continue;
		vis[i]=++ans;
		dfs(i);
	}
	printf("%d\n",ans-1);

	return 0;
}

2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)

E. Life Transfer

这个题需要明确两点：

  1. 如果有开车的人，那么这些人一定是年龄最大的
  2. 骑摩托的人，一定是出了开车的人之外年龄最大的

训练的时候一直WA3，其实是循环的时候一个变量搞错了。结果我还以为自己想假了。。。当时还以为年龄大的人可能去当乘客，年纪小的反而可以去骑摩托…

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
#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 inf=1e18;
const ll mod=998244353;
const double eps=1e-10;
int n,k;
int lc,pc,lm,pm;
int t,d;
int a[maxn];
bool cmp(int x,int y){return x>y;}
int main(){
	scanf("%d%d",&n,&k);
	scanf("%d%d%d%d",&lc,&pc,&lm,&pm);
	scanf("%d%d",&t,&d);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	ll cnty=0,needy=0,ans=inf,res=0;
	int sgn=0;
	for(int i=1;i<=n;i++){
		res+=pm;
		if(a[i]>=lm)cnty+=min(a[i]-lm,d);
		else {
			cnty-=lm-a[i];
			if(lm-a[i]>d)sgn++;
			needy+=lm-a[i];
		}
	}
	if(!sgn&&cnty>=0)ans=min(ans,res+needy*t);
	
	int le,ri=n;
	k--;
	for(le=1;le<=ri;le++){
		res+=pc-pm;
		if(a[le]>=lc){
			cnty-=min(a[le]-lm,d);
			cnty+=min(a[le]-lc,d);
		}
		else if(a[le]>=lm){
			cnty-=min(a[le]-lm,d);
			cnty-=lc-a[le];
			needy+=lc-a[le];
			if(lc-a[le]>d)break;
		}
		else {
			cnty+=lm-a[le];
			cnty-=lc-a[le];
			needy-=lm-a[le];
			needy+=lc-a[le];
			if(lc-a[le]>d)break;
		}
		int pre=ri;
		for(;ri>max(le,pre-k);ri--){
			if(a[ri]>=lm){
				cnty-=min(a[ri]-lm,d);
				cnty+=min(a[ri]-1,d);
			}
			else {
				if(lm-a[ri]>d)sgn--;
				cnty+=lm-a[ri];
				cnty+=min(a[ri]-1,d);
				needy-=lm-a[ri];
			}
			res-=pm;
		}
		if(!sgn&&cnty>=0)ans=min(ans,res+needy*t);
	}
	if(ans==inf)ans=-1;
	printf("%lld\n",ans);
	return 0;
}

A. Max or Min

题解把idea讲的很详细，这里就不多赘述了。就简单讲讲实现。

写这种题的时候先要在草稿纸上把要维护的变量列出来，然后再简单写写伪代码，理清思路后再开始。

注意到这里只有变量pre需要区间修改，其他的都可以直接索引修改，所以在结构体内只需要定义一个pre和懒标记即可。

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
#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;
struct tree{
	int tag,pre,sum;
}t[maxn<<2];
int n,m;
int a[maxn],val[maxn],len[maxn];
vector<int>e[maxn];
void push_up(int rt){
	t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
}
void push_dn(int rt){
	if(t[rt].tag){
		t[rt<<1].tag=t[rt].tag;
		t[rt<<1|1].tag=t[rt].tag;
		t[rt<<1].pre=t[rt].tag;
		t[rt<<1|1].pre=t[rt].tag;
	}
	t[rt].tag=0;
}
void build(int rt,int l,int r){
	int mid=l+r>>1;
	if(l==r){
		t[rt].pre=l;
		return;
	}
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}
int check(int rt,int l,int r,int p){
	int mid=l+r>>1;
	if(l==r){
		return t[rt].pre;
	}
	push_dn(rt);
	if(p<=mid)return check(rt<<1,l,mid,p);
	else return check(rt<<1|1,mid+1,r,p);
	push_up(rt);
}
void update_len(int rt,int l,int r,int p){
	int mid=l+r>>1;
	if(l==r){
		t[rt].sum=len[l]/2;
		// t[rt].sum=len[l];
		return;
	}
	push_dn(rt);
	if(p<=mid)update_len(rt<<1,l,mid,p);
	else update_len(rt<<1|1,mid+1,r,p);
	push_up(rt);
}
void update_pre(int rt,int l,int r,int xl,int xr,int x){
	int mid=l+r>>1;
	if(l==xl&&r==xr){
		t[rt].pre=x;
		t[rt].tag=x;
		return ;
	}
	push_dn(rt);
	if(xl<=mid)update_pre(rt<<1,l,mid,xl,min(xr,mid),x);
	if(xr>mid)update_pre(rt<<1|1,mid+1,r,max(xl,mid+1),xr,x);
	push_up(rt);
	
}
int main(){
	int T=1;//scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			e[a[i]].push_back(i);
		}
		for(int i=1;i<=n;i++){
			val[i]=1;
			len[i]=1;
		}
		build(1,1,n);
		for(int i=1;i<=m;i++){
			for(auto j:e[i]){
				int frt=check(1,1,n,j);
				int bhd=frt+len[frt]-1;
				if(frt!=j){
					len[frt]=j-frt;
					update_len(1,1,n,frt);
				}
				if(bhd!=j){
					update_pre(1,1,n,j+1,bhd,j+1);
					len[j+1]=bhd-j;
					update_len(1,1,n,j+1);
				}
				len[j]=0,val[j]=0;
				update_len(1,1,n,j);
			}
			int res=t[1].sum;
			if(val[1]*val[n]==-1){
				int frt=check(1,1,n,n);
				res-=len[1]/2+len[frt]/2;
				res+=(len[1]+len[frt])/2;
			}
			res+=n-e[i].size();
			if(!e[i].size())res=-1;
			printf("%d ",res);
			for(auto j:e[i]){
				if(j!=n&&val[j+1]==1){
					int bhd=j+1+len[j+1]-1;
					update_pre(1,1,n,j,bhd,j);
					len[j]=len[j+1]+1;
					len[j+1]=0;
					update_len(1,1,n,j);
					update_len(1,1,n,j+1);
				}
				else {
					update_pre(1,1,n,j,j,j);
					len[j]=1;
					update_len(1,1,n,j);
				}
				val[j]=-1;
				if(j!=1&&val[j-1]==1){
					int frt=check(1,1,n,j-1);
					int bhd=j+len[j]-1;
					update_pre(1,1,n,j,bhd,frt);
					len[frt]+=len[j];
					len[j]=0;
					update_len(1,1,n,frt);
					update_len(1,1,n,j);
				} 
			}

		}
	}
	return 0;
}

Diamond_Sea#Day3

E. Triple Flips

先跑个暴力，惊奇地发现当n大于等于8时，一定有解。结合小于n/3这个条件，于是可以比较自然地想到，把数组的最后六个看成一组，在两步操作内，把这六个数变成0。当数组减少到13及以下时，跑暴力求解即可。

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
#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;
map<string,int>mp;
vector<pii>opt[maxn],ans;
int n,a[maxn];
int tot;
bool check(string cur){
	for(auto x:cur){
		if(x=='1')return false;
	}
	return true;
}
void get_opt(string pre,string cur,int dep,vector<pii>vec){
	if(check(cur)){
		opt[mp[pre]]=vec;
		return;
	}
	if(dep==2)return;
	for(int i=-1;i<5;i++){
		for(int j=1;j<=5;j++){
			if(i+j>5)continue;
			vec.push_back({i,j});
			for(auto x:vector<int>({i-j,i,i+j})){
				if(x<0)continue;
				if(cur[x]=='0')cur[x]++;
				else cur[x]--;
			}
			get_opt(pre,cur,dep+1,vec);
			for(auto x:vector<int>({i-j,i,i+j})){
				if(x<0)continue;
				if(cur[x]=='0')cur[x]++;
				else cur[x]--;
			}				
			vec.pop_back();
		}
	}
}
void dfs1(string cur,int len){
	if(len==6){
		mp[cur]=++tot;
		vector<pii>vec;
		get_opt(cur,cur,0,vec);
		// cout<<cur<<"  "<<opt[mp[cur]].size()<<endl;
		// for(auto p:opt[mp[cur]]){
		// 	cout<<cur<<" "<<p.first<<" "<<p.second<<endl;
		// }
		return;
	}
	dfs1(cur+'1',len+1);
	dfs1(cur+'0',len+1);
}
int flag;
void bf(string cur){
	int cnt=0;
	map<string,int>dis,vis;
	map<string,string>fa;
	pii vec[maxn];
	memset(vec,0,sizeof(vec));
	queue<string>q;
	q.push(cur);
	vis[cur]=1;
	dis[cur]=1;
	while(!q.empty()){
		auto p=q.front();q.pop();
		if(check(p)){
			for(string s=p;s!=cur;s=fa[s]){
				if(vec[vis[s]].first)
					ans.push_back(vec[vis[s]]);
			}
			return ;
		}
		for(int i=1;i<p.size();i++){
			for(int j=1;j+i<p.size()&&i-j>=0;j++){
				string np=p;
				for(auto x:vector<int>({i-j,i,i+j})){
					if(np[x]=='0')np[x]++;
					else np[x]--;					
				}
				if(!dis[np]){
					dis[np]=dis[p]+1;
					fa[np]=p;
					vis[np]=++cnt;
					q.push(np);
					vec[vis[np]]={i+1,j};
				}
			}
		}
	}
	flag=1;
	


}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	dfs1("",0);
	for(int i=n;i>=1;i-=6){
		if(i<=14){
			string cur;
			for(int j=1;j<=i;j++)cur.push_back(a[j]+'0');
			bf(cur);
			break;
		}
		string cur;
		for(int j=i-5;j<=i;j++){
			cur.push_back(a[j]+'0');
		}
		for(auto p:opt[mp[cur]]){
			ans.push_back({p.first+i-5,p.second});
			int mid=p.first+i-5,l=p.second;
			for(auto x:vector<int>({mid-l,mid,mid+l})){
				if(a[x]==1)a[x]--;
				else a[x]++;
			}
		}
	}
	if(flag)puts("NO");
	else {
		printf("YES\n%d\n",ans.size());
		for(auto p:ans){
			int i=p.first,j=p.second;
			printf("%d %d %d\n",i-j,i,i+j);
		}
	}
	

	return 0;
}

Diamond_Sea#Day4

E. Network Safety

极其naive的题目…

因为a⊕x==ba \oplus x==b时，一定有a⊕b==xa\oplus b==x

对于每个连通的点对u,v,把边权看成是c[u]⊕c[v]c[u]\oplus c[v]，我们变量每个边权，维护仅使用当前边权的边的子图的连通性，则一个连通图内一定全被感染或者全未被感染。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=5e5+5;
const ll mod=1e9+7;
const double eps=1e-10;
int n,m,k;
vector<pii>e[maxn];
ll c[maxn];
map<ll,int>mp;
int cnt;
int fa[maxn];
ll p2[maxn];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
ll ans;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	p2[0]=1;
	for(int i=1;i<=5e5;i++)p2[i]=p2[i-1]*2,p2[i]%=mod;
	for(int i=1;i<=n;i++){
		scanf("%lld",&c[i]);
	}
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		ll cur=c[u]^c[v];
		if(!mp[cur])mp[cur]=++cnt;
		int idx=mp[cur];
		e[idx].push_back({u,v});
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=cnt;i++){
		int cur=n;
		for(auto p:e[i]){
			int x=p.first,y=p.second;
			if(find(x)!=find(y)){
				fa[find(x)]=find(y);
				cur--;
			}
		}
		ans+=p2[cur],ans%=mod;
		for(auto p:e[i]){
			int x=p.first,y=p.second;
			fa[x]=x,fa[y]=y;
		}
	}
	ans+=p2[n]*((p2[k]-cnt+mod)%mod)%mod,ans%=mod;
	cout<<ans<<endl;
	return 0;
}