2022 robocom world robot developer competition - undergraduate group (provincial competition) T4, T5

RC-u4 Strategic team

The question
hold 6 The detachment is divided into two groups , Find the best solution according to the following screening method ：

Ideas
A simpler method is , Store the elements in each scheme in the structure , Then overload the operator in the structure , Sort all schemes according to the given screening strategy , The first plan after ranking is the best plan .
How to sort according to the screening strategy ？
For a filter , Applying for elements in the structure indicates whether the filtering conditions are satisfied , If the satisfaction is set to 1, Otherwise 0. When reloading the less than sign , Sort the elements from large to small . In this way, those who meet this condition are put in front , Dissatisfied is behind .

#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;

// Team structure 
struct node{
    
	int cnt;
	int tan, gong, zhi;
}dui[N];

// Scheme structure 
struct ST{
    
	int ou[7]; // All teams in the first group  
	int ya[7]; // All teams in the second group  
	int cnt1, cnt2; // The number of teams in the two groups  
	int zg; // Commanders and engineers have  
	int zhi; // There's a commander  
	int cha; // The difference between the two groups  
	int tan; // There are tanks  
	int more; // Whether the first group has more people than the second group  
	
	friend bool operator < (ST a, ST b)
	{
    
		if(a.tan != b.tan) return a.tan > b.tan; // filter 0 
		if(a.zg != b.zg) return a.zg > b.zg; // Conditions 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++) // Binary enumeration of all allocation schemes 
	{
    
		int cnt1=0, cnt2=0;
		int sum1 = 0, sum2 = 0;
		for(int j=1;j<=6;j++) // Everyone 's 01 Corresponding allocation 
		{
    
			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); // Sort all schemes according to the given filter conditions 
	
	ST ans = a[0]; // The first element is the optimal solution  
	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;
}

Then there is another way , Little by little cyclic judgment , If the plan is unique, exit , Otherwise, perform the next filter …
More writing , It's annoying .
And I don't know why there is a point that can't pass .

#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;
}

Experience
On the field dfs After searching all the schemes , Judge step by step , If you find the only solution, exit , Otherwise, go to the next item and continue to judge … I haven't finished writing for more than half an hour , I found that none of the samples came out , Then I don't have the courage to write down , Go straight to the next question ..
Add storage for all schemes vector Deposited , The latter judgment is also a little annoying .
You should figure out how to deal with it later , Then choose a suitable way to store data . Lest it be troublesome later .

RC-u5 Tree and bipartite graph

The question
Given a $n$ The tree of nodes , Ask how many points are right $(i,j)$ Satisfy ：

• Nodes in the tree $i$ and $j$ There are no edges directly connected ;
• Set undirected edge $(i,j)$ After adding, the whole tree can form a bipartite graph .

$2\le N\le 10^6$

Ideas
Need to know , A tree is a bipartite graph ： After the root node is determined , Points with odd depth are in a set , Points with an even depth are in another set .

Now connect the two nodes , After connection, the bipartite graph must be satisfied , It must be a point with an odd depth to a point with an even depth , Or points with even depth are connected to points with odd depth .

Then you can traverse each node from top to bottom , All points with edges that are different from the depth parity traversed before . Because the first two nodes are not directly connected , So its parent node should be removed , points -1.

Or record how many nodes there are in each layer , For each floor , Number of nodes in this layer *（ The number of nodes with different levels of parity -1） This is the number of schemes connecting the nodes of this layer and the nodes above . The sum of such schemes on each layer is the total number of schemes .

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;
}

T4 After writing for more than half an hour, there was no result , If you can't get the samples out, you won't have the courage to continue writing , I went to the last question first . See the bipartite graph , I think it's the last question , It should be difficult , So I ran a staining method directly and got a violence score .. Did not continue to think ..
Looking back T4 I don't want to write ..

Keep training ！