2022 RoboCom 世界机器人开发者大赛-本科组（省赛）T4, T5_2022rc大赛

RC-u4 攻略分队

题意
把 6 支队伍分成两组，把所有的可能方案按照下面的筛选方式找到最佳方案：

思路
比较简洁的一个方法是，将每一条方案中的元素都存储到结构体中，然后在结构体中重载运算符，根据给出的筛选策略将所有方案排序，排过序之后的首条方案便是最佳方案。
怎么按照筛选策略排序呢？
对于一条筛选，在结构体中申请元素表示该筛选条件满不满足，如果满足置为1，否则为0。在重载小于号时，按照该元素从大到小排序。这样满足该条件的就放到了前面，不满足的就在后面。

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;

//队伍结构体
struct node{
	int cnt;
	int tan, gong, zhi;
}dui[N];

//方案结构体
struct ST{
	int ou[7]; //第一组的所有队伍 
	int ya[7]; //第二组的所有队伍 
	int cnt1, cnt2; //两组的队伍个数 
	int zg; //指挥官和工兵都有 
	int zhi; //有指挥官 
	int cha; //两组人数之差 
	int tan; //有坦克 
	int more; //是否第一组比第二组人多 
	
	friend bool operator < (ST a, ST b)
	{
		if(a.tan != b.tan) return a.tan > b.tan; //筛选条件0 
		if(a.zg != b.zg) return a.zg > b.zg; //条件1
		if(a.zhi != b.zhi) return a.zhi > b.zhi; //2
		if(a.cha != b.cha) return a.cha < b.cha; //3
		if(a.more != b.more) return a.more > b.more; //4 
		for(int i=1;i<=min(a.cnt1, b.cnt1);i++) //5
			if(a.ou[i] != b.ou[i]) return a.ou[i] < b.ou[i];
	}
}a[N];

signed main(){
	Ios;
	for(int i=1;i<=6;i++) cin >> dui[i].cnt;
	
	for(int i=1;i<=6;i++)
	{
		string s; cin >> s;
		if(s[0] == '1') dui[i].tan = 1;
		if(s[1] == '1') dui[i].gong = 1;
		if(s[2] == '1') dui[i].zhi = 1;
	}
	
	for(int i=0;i<64;i++) //二进制枚举所有分配方案
	{
		int cnt1=0, cnt2=0;
		int sum1 = 0, sum2 = 0;
		for(int j=1;j<=6;j++) //每一位的01对应分配
		{
			if((i >> j-1) & 1){
				if(dui[j].cnt) a[i].ou[++cnt1] = j, sum1 += dui[j].cnt;
			}
			else{
				if(dui[j].cnt) a[i].ya[++cnt2] = j, sum2 += dui[j].cnt;
			}
		}
		a[i].cnt1 = cnt1;
		a[i].cnt2 = cnt2;
		
		int tan1 = 0, tan2 = 0, zhi1 = 0, zhi2 = 0, gong1 = 0, gong2 = 0;
		for(int j=1;j<=cnt1;j++)
		{
			int x = a[i].ou[j];
			if(dui[x].tan) tan1 = 1;
			if(dui[x].zhi) zhi1 = 1;
			if(dui[x].gong) gong1 = 1;
		}
		for(int j=1;j<=cnt2;j++)
		{
			int x = a[i].ya[j];
			if(dui[x].tan) tan2 = 1;
			if(dui[x].zhi) zhi2 = 1;
			if(dui[x].gong) gong2 = 1;
		}
		
		if(tan1 && tan2) a[i].tan = 1;
		if(zhi1 && zhi2 && gong1 && gong2) a[i].zg = 1;
		if(zhi1 && zhi2) a[i].zhi = 1;
		a[i].cha = abs(sum1 - sum2);
		if(sum1 > sum2) a[i].more = 1;
	}
	
	sort(a, a+64); //将所有方案按照给定的筛选条件排序
	
	ST ans = a[0]; //首个元素便是最优方案 
	if(!ans.tan){
		cout << "GG";
		return 0;
	}
	for(int i=1;i<=ans.cnt1;i++){
		cout << ans.ou[i];
		if(i!=ans.cnt1) cout << " ";
	}
	cout << endl;
	for(int i=1;i<=ans.cnt2;i++){
		cout << ans.ya[i];
		if(i!=ans.cnt2) cout << " ";
	}
	
	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
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

然后还有一个方法就是，一点一点循环判断，如果方案唯一就退出，否则就执行下一条筛选…
写的比较多，比较烦。
而且还不知道为什么有一个点过不去。

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m;
struct node{
	int cnt;
	int mt, bing, zhihui;
}a[N];
int x[N], y[N];
int cntx, cnty;
int cnt;
vector<int> ans[N][2];
int f[N];

void pd()
{
	int flag = 0;
	for(int i=1;i<=cntx;i++)
	{
		int idx = x[i];
		if(a[idx].mt) flag = 1;
	}
	if(!flag) return;
	
	flag = 0;
	for(int i=1;i<=cnty;i++)
	{
		int idx = y[i];
		if(a[idx].mt) flag = 1;
	}
	if(!flag) return;
	
	cnt++;
	for(int i=1;i<=cntx;i++) ans[cnt][0].push_back(x[i]);
	for(int i=1;i<=cnty;i++) ans[cnt][1].push_back(y[i]);
}

void dfs(int u)
{
	if(u==7)
	{
		pd();
		return;
	}
	
	x[++cntx] = u;
	dfs(u+1);
	cntx--;
	
	y[++cnty] = u;
	dfs(u+1);
	cnty--;
}

bool Less(vector<int> v1, vector<int> v2)
{
	int m = min(v1.size(), v2.size());
	
	for(int i=0;i<m;i++)
	{
		if(v1[i] < v2[i]) return 1;
		else if(v1[i] > v2[i]) return 0;
	}
}

int main()
{
	for(int i=1;i<=6;i++) cin >> a[i].cnt;
	
	for(int i=1;i<=6;i++)
	{
		string s; cin >> s;
		if(s[0]=='1') a[i].mt = 1;
		if(s[1]=='1') a[i].bing = 1;
		if(s[2]=='1') a[i].zhihui = 1;
	}
	
	dfs(1);
	
	//1 
	int sum = 0, ansi = 0;
	for(int i=1;i<=cnt;i++)
	{
		vector<int> v1 = ans[i][0];
		vector<int> v2 = ans[i][1];
		
		int flag1 = 0, flag2 = 0;
		for(int x : v1)
		{
			if(a[x].zhihui) flag1 = 1;
			if(a[x].bing) flag2 = 1;
		}
		if(!flag1 || !flag2){
			f[i] = 1;
			continue;
		}
		
		flag1 = 0, flag2 = 0;
		for(int x : v2)
		{
			if(a[x].zhihui) flag1 = 1;
			if(a[x].bing) flag2 = 1;
		}
		if(!flag1 || !flag2){
			f[i] = 1;
			continue;
		}
		
		sum ++;
		ansi = i;
	}
	if(sum == 1)
	{
		vector<int> v1 = ans[ansi][0];
		vector<int> v2 = ans[ansi][1], res1, res2;
		
		for(int i=0;i<v1.size();i++){
			int x = v1[i];
			if(a[x].cnt) res1.push_back(x);
		}
		for(int i=0;i<v2.size();i++){
			int x = v2[i];
			if(a[x].cnt) res2.push_back(x);
		}
		
		for(int i=0;i<res1.size();i++){
			cout << res1[i];
			if(i!=res1.size()-1) cout << " ";
		}
		cout << endl;
		for(int i=0;i<res2.size();i++){
			cout << res2[i];
			if(i!=res2.size()-1) cout << " ";
		}
		
		return 0;
	}
	
	if(sum == 0)
	{
		for(int i=1;i<=cnt;i++) f[i] = 0;
		
		//2
		sum = 0;
		for(int i=1;i<=cnt;i++)
		{
			vector<int> v1 = ans[i][0];
			vector<int> v2 = ans[i][1];
			
			int flag1 = 0, flag2 = 0;
			for(int x : v1)
			{
				if(a[x].zhihui) flag1 = 1;
			}
			if(!flag1){
				f[i] = 1;
				continue;
			}
			
			flag1 = 0, flag2 = 0;
			for(int x : v2)
			{
				if(a[x].zhihui) flag1 = 1;
			}
			if(!flag1){
				f[i] = 1;
				continue;
			}
			
			sum ++;
			ansi = i;
		}
		if(sum == 1)
		{
			vector<int> v1 = ans[ansi][0];
			vector<int> v2 = ans[ansi][1], res1, res2;
			
			for(int i=0;i<v1.size();i++){
				int x = v1[i];
				if(a[x].cnt) res1.push_back(x);
			}
			for(int i=0;i<v2.size();i++){
				int x = v2[i];
				if(a[x].cnt) res2.push_back(x);
			}
			
			for(int i=0;i<res1.size();i++){
				cout << res1[i];
				if(i!=res1.size()-1) cout << " ";
			}
			cout << endl;
			for(int i=0;i<res2.size();i++){
				cout << res2[i];
				if(i!=res2.size()-1) cout << " ";
			}
			
			return 0;
		}
		
		if(sum == 0){
			for(int i=1;i<=cnt;i++)
				f[i] = 0;
		}
	}
	
	//3
	sum = 0, ansi = 0;
	int maxa = 1e9;
	for(int i=1;i<=cnt;i++)
	{
		if(f[i]) continue;
		vector<int> v1 = ans[i][0];
		vector<int> v2 = ans[i][1];
		
		int sum1 = 0, sum2 = 0;
		for(int x : v1)
		{
			sum1 += a[x].cnt;
		}
		
		for(int x : v2)
		{
			sum2 += a[x].cnt;
		}
		
		if(abs(sum1 - sum2) < maxa){
			maxa = abs(sum1 - sum2);
			ansi = i;
			sum = 1;
		}
		else if(abs(sum1 - sum2) == maxa){
			sum ++;
		}
	}
	
	if(sum == 1)
	{
		vector<int> v1 = ans[ansi][0];
		vector<int> v2 = ans[ansi][1], res1, res2;
		
		for(int i=0;i<v1.size();i++){
			int x = v1[i];
			if(a[x].cnt) res1.push_back(x);
		}
		for(int i=0;i<v2.size();i++){
			int x = v2[i];
			if(a[x].cnt) res2.push_back(x);
		}
		
		for(int i=0;i<res1.size();i++){
			cout << res1[i];
			if(i!=res1.size()-1) cout << " ";
		}
		cout << endl;
		for(int i=0;i<res2.size();i++){
			cout << res2[i];
			if(i!=res2.size()-1) cout << " ";
		}
		
		return 0;
	}
	
	sum = 0, ansi = 0;
	for(int i=1;i<=cnt;i++)
	{
		if(f[i]) continue;
		vector<int> v1 = ans[i][0];
		vector<int> v2 = ans[i][1];
		
		int sum1 = 0, sum2 = 0;
		for(int x : v1)
		{
			sum1 += a[x].cnt;
		}
		
		for(int x : v2)
		{
			sum2 += a[x].cnt;
		}
		
		if(abs(sum1 - sum2) != maxa) f[i] = 1;
	}
	
	//4
	sum = 0, ansi = 0, maxa = 1e9;
	for(int i=1;i<=cnt;i++)
	{
		if(f[i]) continue;
		vector<int> v1 = ans[i][0];
		vector<int> v2 = ans[i][1];
		
		int sum1 = 0, sum2 = 0;
		for(int x : v1)
		{
			sum1 += a[x].cnt;
		}
		
		for(int x : v2)
		{
			sum2 += a[x].cnt;
		}
		
		if(sum1 <= sum2) f[i] = 1;
		else{
			sum++;
			ansi = i;
		}
	}
	if(sum == 1)
	{
		vector<int> v1 = ans[ansi][0];
		vector<int> v2 = ans[ansi][1], res1, res2;
		
		for(int i=0;i<v1.size();i++){
			int x = v1[i];
			if(a[x].cnt) res1.push_back(x);
		}
		for(int i=0;i<v2.size();i++){
			int x = v2[i];
			if(a[x].cnt) res2.push_back(x);
		}
		
		for(int i=0;i<res1.size();i++){
			cout << res1[i];
			if(i!=res1.size()-1) cout << " ";
		}
		cout << endl;
		for(int i=0;i<res2.size();i++){
			cout << res2[i];
			if(i!=res2.size()-1) cout << " ";
		}
		
		return 0;
	}
	
	vector<int> t;
	for(int i=1;i<=10;i++) t.push_back(1e9);
	
	sum = 0, ansi = 0, maxa = 1e9;
	for(int i=1;i<=cnt;i++)
	{
		if(f[i]) continue;
		vector<int> v1 = ans[i][0];
		if(Less(v1, t)){
			t = v1;
			sum = 1;
			ansi = i;
		}
	}
	
	if(sum == 1)
	{
		vector<int> v1 = ans[ansi][0];
		vector<int> v2 = ans[ansi][1], res1, res2;
		
		for(int i=0;i<v1.size();i++){
			int x = v1[i];
			if(a[x].cnt) res1.push_back(x);
		}
		for(int i=0;i<v2.size();i++){
			int x = v2[i];
			if(a[x].cnt) res2.push_back(x);
		}
		
		for(int i=0;i<res1.size();i++){
			cout << res1[i];
			if(i!=res1.size()-1) cout << " ";
		}
		cout << endl;
		for(int i=0;i<res2.size();i++){
			cout << res2[i];
			if(i!=res2.size()-1) cout << " ";
		}
		
		return 0;
	}
	
	cout << "GG";
	
	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
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382

经验
场上dfs搜出所有方案之后，一步一步循环判断，如果找到唯一解就退出，否则进入下一条继续判断…写了半个多钟头没写完，发现样例都没跑出来，然后就没有勇气往下接写了，直接去看下一题了。。
加上存储所有方案用vector存的，后面判断也写的有点烦。
应该想清楚后面应该怎么接着处理，再选择合适的方式来存放数据。免得后面就很麻烦。

---

RC-u5 树与二分图

题意
给定一个 $n$ 节点的树，问有多少个点对 $(i,j)$ 满足：

• 树中节点 $i$ 和 $j$ 之间没有边直接相连；
• 将无向边 $(i,j)$ 加上之后整个树能构成二分图。

$2\le N\le 10^6$

思路
要知道，一棵树本来就是一个二分图：根节点确定之后，深度为奇数的点在一个集合，深度为偶数的点在另一集合。

那么现在要连接两个节点，连接之后还要满足二分图，那肯定是深度为奇数的点向深度为偶数的点连边，或者深度为偶数的点向深度为奇数的点连边。

那么就可以从上到下遍历每一个节点，其和之前遍历过的深度奇偶性不同的所有点连边。因为要满足连边前两节点不直接相连，所以其父节点要去掉，点数-1。

或者记录每一层有多少节点，对于每一层来说，这一层的节点数 *（之前奇偶性不同层数的节点数-1）便是这一层的节点和上面节点连边的方案数。每一层这样的方案数相加便是总的方案数。

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 1000010;
int n, m;
int a[N];
vector<int> e[N];
int f[N], flor[N];

void bfs()
{
	queue<int> que;
	que.push(1);
	f[1] = 1;
	a[1] = 1;
	
	while(que.size())
	{
		int x = que.front(); que.pop();
		for(int tx : e[x])
		{
			if(f[tx]) continue;
			f[tx] = 1;
			
			flor[tx] = flor[x] + 1;
			a[flor[tx]] ++;
			que.push(tx);
		}
	}
}

int main(){
	cin >> n;
	for(int i=1;i<n;i++)
	{
		int x, y;cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	flor[1] = 1;
	bfs();
	
	long long cnt0 = 0, cnt1 = 0;
	long long ans = 0;
	for(int i=1;i<=n;i++)
	{
		if(i%2) cnt1 += a[i];
		else cnt0 += a[i];
		
		if(i%2)
		{
			if(a[i] && cnt0) ans += a[i]*(cnt0-1);
		}
		else if(a[i] && cnt1) ans += a[i]*(cnt1-1);
	}
	cout << 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

---

T4 写了半个多钟头没有结果，样例都跑不出来就没有勇气继续写了，先去看了最后一题。看到二分图，又觉得是最后一题，应该很难吧，所以就直接暴力跑了个染色法判定拿了个暴力分。。都没有继续往下想。。
回过头来看 T4 也不想写了。。

继续训练吧！