ICPC网络赛#2021第二场

题解传送门

H.Set

对于这种咋一看不知从何入手的题目，可以想想能否“乱搞”，即利用某种极端的条件或者这个题目某种特殊的性质入手研究整个问题。

这里需要知道一个东西，叫做Union bound,然后我们可以计算出随机选一组解为非法解的概率的上界，结果惊人地小，于是我们可以直接使用random_shuffle构造一组答案，问题就解决了

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=1e5+5;
const ll mod=998244353;
const double eps=1e-10;
int r,k;
vector<int>vec[300];
int main(){
	int T=1;//scanf("%d",&T);
	while(T--){
		scanf("%d%d",&k,&r);
		int num=(256-1)/r+1;
		for(int i=1;i<=num;i++){
			vec[0].push_back(1);
		}
		for(int j=num+1;j<=256;j++){
			vec[0].push_back(0);
		}
		for(int i=1;i<=k;i++){
			vec[i]=vec[0];
			random_shuffle(vec[i].begin(),vec[i].end());
			for(auto x:vec[i])printf("%d",x);
			if(i!=k)puts("");
		}
	}
	return 0;
}

2016-2017 ACM-ICPC Northeastern European Regional Contest (NEERC 16)

B.Binary Code

本质是一个不太难的 trie + 2-SAT，注意总的字符数量是有上限的，以及在 trie 上同一个点结尾的字符串的数量不可以超过这个点的深度+1，即必须满足size[u]≤dep[u]+1size[u]\leq dep[u]+1 ,不然一定无解。所以可以建边的数量最多达到n(n)n\sqrt{(n)}量级，是可以接受的。

还有就是，没有’?'的节点，它的反点是违法的，所以我们连一条反点到该点的边，这样就增加了不能选择反点的限制

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef pair<int,string>pis;
typedef double db;
#define lowbit(x) (x&(-x))
const int maxn=1e6+7;
const ll mod=998244353;
const double eps=1e-10;
int n,tot,sz,flag=1;
int trie[maxn][2];
vector<int> ed[maxn],e[maxn];
vector<pii>vec;
void update(string s,int idx){
	int cur=0;
	for(int i=0;i<s.length();i++){
		if(s[i]=='0'){
			if(!trie[cur][0])trie[cur][0]=++sz;
			cur=trie[cur][0];
		}
		else {
			if(!trie[cur][1])trie[cur][1]=++sz;
			cur=trie[cur][1];
		}
		for(auto j:ed[cur]){
			e[idx].push_back(j^1);
			e[j].push_back(idx^1);
		}
	}
	ed[cur].push_back(idx);
	if(ed[cur].size()>s.length()+1)flag=0;
}
int dfn[maxn],low[maxn],in[maxn];
int col[maxn],cnt,vis[maxn];
vector<int>st;
void tarjan(int u){
	st.push_back(u);
	in[u]++;
	dfn[u]=low[u]=++tot;
	for(auto v:e[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(in[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		cnt++;
		while(st.back()!=u){
			col[st.back()]=cnt;
			in[st.back()]=0;
			st.pop_back();
		}
		col[st.back()]=cnt;
		in[st.back()]=0;
		st.pop_back();
	}
}
int pos[maxn];
string a[maxn];
int main(){
	freopen("binary.in","r",stdin);
	freopen("binary.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		vec.push_back({(int)a[i].length(),i});
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<n;i++){
		string str=a[vec[i].second];
		pos[i]=-1;
		for(int j=0;j<str.length();j++){
			if(str[j]=='?')pos[i]=j;
		}
		if(pos[i]!=-1){
			str[pos[i]]='0';
			update(str,i*2+1);
			str[pos[i]]='1';
			update(str,i*2);
		}
		else update(str,i*2+1),e[i*2].push_back(i*2+1);
		if(!flag){
			printf("NO\n");return 0;
		}
	}
	for(int i=0;i<n*2;i++){
		if(!dfn[i])tarjan(i);
		// printf("%d %d\n",i,col[i]);
	}
	for(int i=0;i<2*n;i+=2){		
		if(col[i]==col[i+1]){
			printf("NO\n");return 0;
		}
	}
	printf("YES\n");
	for(int i=0;i<n;i++){
		string &str=a[vec[i].second];
		if(pos[i]==-1)continue;
		int f1=col[i*2],f2=col[i*2+1];
		if(vis[f1])
			str[pos[i]]='1';
		else if(vis[f2])
			str[pos[i]]='0';
		else {
			if(f1<f2){
				str[pos[i]]='1';
				vis[f1]=1;
			}
			else {
				str[pos[i]]='0';
				vis[f2]=1;
			}
		}
	}
	for(int i=0;i<n;i++){
		cout<<a[i];
		puts("");
	}

	return 0;
}

C.Cactus Construction

这是一个结合了仙人掌树的构造题。为了方便思考，可以先考虑简单的情况，比如如果是一个树，可以怎么办呢？

如果只是一个树，即没有环的话，只用三种颜色即可，先把要连的父节点染成3，把当前子树的端点置为2，然后把两个点合到一个图内，然后连接。最后把颜色为2的置为1，颜色为3的置为2，这样就能递归地做下去。

如果有环的话，可以先跑一个dfs，这样确定环的产生都源自于返祖边。对于返祖边连到的那个“祖先”，我们可以把它和返祖边所连的那个“后代”连起来，再把这个“祖先”的颜色变为4，这样到时候就可以对它进行单独操作。注意，这样需要保证在整个操作的过程，同时存在的颜色为4的点的数量最多只有一个，所以要分类讨论一下，具体可以参见代码。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
#define lowbit(x) (x&(-x))
const int maxn=5e4+7;
const ll mod=998244353;
const double eps=1e-10;
int n,m,tot;
vector<int>e[maxn];
int fa[maxn];
int dfn[maxn],low[maxn],dep[maxn],rk[maxn];
int col[maxn],vis[maxn],in[maxn];
struct node{
	int opt,a,b,c;
};
vector<node>vec;
int find(int x){
	return in[x]==x?x:in[x]=find(in[x]);
}
void dfs(int u,int p){
	dfn[u]=low[u]=++tot;
	rk[tot]=u;
	for(auto v:e[u]){
		if(v==p)continue;
		if(!dfn[v])dep[v]=dep[u]+1,dfs(v,u);
		if(dep[v]==dep[u]+1)low[u]=min(low[u],low[v]);
		else low[u]=min(dfn[v],low[u]);
	}
}
void solve(int u){
	int son=0;
	for(auto v:e[u]){
		if(dep[v]!=dep[u]+1)continue;
		if(low[v]>=dfn[u]){
			solve(v);
			vec.push_back({2,u,col[u],3});
			if(find(u)!=find(v)){
				vec.push_back({1,u,v});
				in[find(u)]=find(v);
			}
			vec.push_back({3,u,2,3});
			vec.push_back({2,u,2,1});
			vec.push_back({2,u,3,2});			
			col[u]=2;
		}
		else son=v;
	}
	vec.push_back({2,u,col[u],3});
	if(low[u]!=dfn[u]&&!son){
		int to=rk[low[u]];
		if(col[to]!=4)
			vec.push_back({2,to,col[to],4});
		if(find(to)!=find(u)){
			vec.push_back({1,to,u});
			in[find(to)]=find(u);
		}
		vec.push_back({3,to,3,4});
		col[to]=4;
	}
	if(son){
		solve(son);
		if(find(u)!=find(son)){
			vec.push_back({1,u,son});
			in[find(u)]=find(son);
		}
		vec.push_back({3,u,2,3});
		col[u]=2;
	}
	vec.push_back({2,u,2,1});
	vec.push_back({2,u,3,2});	
}
int main(){
	freopen("cactus.in","r",stdin);
	freopen("cactus.out","w",stdout);
	// memset(col,1,sizeof(col));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)col[i]=1;
	for(int i=1;i<=n;i++)in[i]=i;
	for(int i=1;i<=m;i++){
		int cnt;
		scanf("%d",&cnt);
		int u,v;
		scanf("%d",&u);
		for(int j=2;j<=cnt;j++){
			scanf("%d",&v);
			e[u].push_back(v);
			e[v].push_back(u);
			in[find(v)]=find(u);
			u=v;
		}
	}
	for(int i=2;i<=n;i++){
		if(find(i-1)!=find(i)){
			in[find(i-1)]=find(i);
			e[i-1].push_back(i);
			e[i].push_back(i-1);
		}
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)in[i]=i;
	solve(1);
	printf("%d\n",vec.size());
	for(auto x:vec){
		if(x.opt==1)printf("j %d %d",x.a,x.b);
		else if(x.opt==2)printf("r %d %d %d",x.a,x.b,x.c);
		else printf("c %d %d %d",x.a,x.b,x.c);
		printf("\n");
	}
	return 0;
}

E.Expect to Wait

当时训练的时候居然没想出来这个题…简直太逆天了

很简单的题目，甚至可以说是签到了。

只要记录一下各个时间段的情况，然后类似于扫描线的思想，一直往上加初始车辆就行了

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
typedef pair<int,int>pii;
int n,q;
ll ans,tot;
map<int,int>mp;
set<int>st;
pii a[maxn];
int qu[maxn];
ll op[maxn];
int main(){
	freopen("expect.in","r",stdin);
	freopen("expect.out","w",stdout);
	scanf("%d%d",&n,&q);
	int cur=0,pre=0;
	for(int i=1;i<=n;i++){
		char s[10];
		int t,k;
		scanf("%s%d%d",s,&t,&k);
		if(cur<0){
			ans+=1ll*(-cur)*(t-pre);
			mp[-cur]+=t-pre;
			st.insert(-cur);
			tot+=t-pre;
		}
		pre=t;
		if(s[0]=='-')cur-=k;
		else cur+=k;
	}
	for(int i=1;i<=q;i++){
		scanf("%d",&qu[i]);
		a[i]={qu[i],i};
	}
	sort(a+1,a+q+1);
	pre=0;
	for(int i=1;i<=q;i++){
		int idx=a[i].second;
		int val=a[i].first;
		if(cur+val<0)op[idx]=-1;
		else {
			while(!st.empty()&&val>=*(st.begin())){
				int up=*(st.begin());
				st.erase(up);
				ans-=1ll*(up-pre)*tot;
				pre=up;
				tot-=mp[up];
			}			
			if(val>pre&&ans)ans-=1ll*(val-pre)*tot,pre=val;
			op[idx]=ans;
		}
	}	
	for(int i=1;i<=q;i++){
		if(op[i]<0)puts("INFINITY");
		else printf("%lld\n",op[i]);
	}
	return 0;
}

G.Game on Graph

很妙的博弈题。

最开始想了个 naive 的 dp，后来发现涉及到无穷的时候理不清逻辑…

把每个点拆成两个，分别表示起点为这个点时，轮到两个人中的第一个人或第二个人先手。

可以先考虑平局，然后第一个人肯定是想要平，第二个尽量不想平，所以可以根据这个得到哪些点是平局的，然后再考虑输赢。

注意到这里使用的是拓扑排序的方法更新节点状态的，有些点的入度可能不会变成 0，所以就不会被更新状态。但是再一想，拓扑序不为 0，不就是永远不停下来了嘛！所以这就相当于平局，但是第二个人比起输，他更不想平，所以第二个人会选择输。所以我们就要再把没有更新过状态的点（即跑完拓扑排序后入度仍不为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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
#define lowbit(x) (x&(-x))
const int maxn=2e5+10;
const ll mod=998244353;
const double eps=1e-10;
int n,m;
vector<int>e[maxn];
int in1[maxn],in2[maxn];
int inf[maxn],win[maxn];
int q[maxn];
int vis[maxn];
int main(){
	// freopen("game.in","r",stdin);
	// freopen("game.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[v].push_back(u+n);
		e[v+n].push_back(u);
		in1[u+n]++,in1[u]++;
		in2[u+n]++,in2[u]++;
	}
	int l=1,r=0;
	for(int i=1;i<=n*2;i++)inf[i]=1;
	for(int i=1;i<=2*n;i++){
		if(!in1[i])q[++r]=i,vis[i]=1,inf[i]=0;
	}
	for(;l<=r;l++){
		for(auto v:e[q[l]]){
			if(vis[v])continue;
			if(v>n){
				vis[v]=1;
				q[++r]=v;
				inf[v]=0;
			}
			else {
				in1[v]--;
				if(!in1[v]){
					inf[v]=0;
					q[++r]=v;
					vis[v]=1;
				}
			}
		}
	}
	memset(vis,0,sizeof(vis));
	l=1,r=0;
	for(int i=1;i<=2*n;i++){
		if(!in2[i]&&!inf[i])q[++r]=i,vis[i]=1,win[i]=0;
		else if(inf[i])q[++r]=i,vis[i]=1;
	}
	for(;l<=r;l++){
		for(auto v:e[q[l]]){
			if(vis[v]||inf[v])continue;
			in2[v]--;
			if((win[q[l]]||inf[q[l]])&&!in2[v]){
				vis[v]=1;
				q[++r]=v;
				win[v]=0;
			}
			else if(!win[q[l]]&&!inf[q[l]]){
				vis[v]=1;
				q[++r]=v;
				win[v]=1;
			}
		}
	}
	for(int i=1;i<=n;i++)if(!vis[i])win[i]=1;
	for(int i=1;i<=n;i++){
		if(inf[i])printf("D");
		else if(win[i])printf("W");
		else printf("L");
	}
	puts("");
	for(int i=n+1;i<=n*2;i++){
		if(inf[i])printf("D");
		else if(win[i])printf("W");
		else printf("L");
	}
	puts("");

	return 0;
}