2024年西安交通大学程序设计竞赛校赛

2024年西安交通大学程序设计竞赛校赛

D瑟莉姆的宴会

解题思路：

​ 该题是一道思维题。

1. 仔细想想，只要满足非负就行了，那么如果一个点没有人支配他，那让他为根节点，其他都受他的支配这样的话
2. 如果后面的所有节点都存在的时候，那么就取前面最多的那个节点。

​ 起始该题可以不用考虑1这个状态，直接用 2 这个状态也能过。

​ 官方题解方法：

​ 该题的官方题解是构造：$1->2->3->\cdot \cdot \cdot ->n$ 的树，然后判断这个方式是不是为负的，如果为负的就翻转为：$n->(n-1)->(n-2)->\cdot \cdot \cdot ->1$

解题代码：

void solve() {
	int n,m;
	cin >> n >> m;
	int maxx =0;
	for(int i = 1; i<= m; i++){
		cin >> arr[i].fi >> arr[i].se;
		user[arr[i].se] = 1;
		user1[arr[i].fi] ++;
		maxx = max(maxx, user1[arr[i].fi]);
	}
	for(int i = 1; i <= n; i++)
		if(user[i] == 0) {
			for(int j = 1; j <= n; j++){
				if(j == i) cout << 0 << " ";
				else cout << i << " ";
			}
			return ;
		}
	for(int i = 1; i <= n; i ++)
		if(maxx == user1[i]){
			for(int j = 1; j <= n; j++){
				if(j == i) cout << 0 << " ";
				else cout << i << " ";
			}
			return ;
		}
}

E: 雪中楼

解题思路：

​ 该题是运用链表的思路：

1. 当发现 0 的时候，就直接输出，因为前面没有比他更小的数了。
2. 如果发现非0的数，那么肯定是比指定的那个数大，那么就接在指定那个数的下面。
3. 如果当前遍历到的那个数下面接的有数的话，就直接输出。因为前面没有比它更大的数了。

解题代码：

const int N = 1e6+5;
int arr[N];
void solve() {
	int n,m;
	cin >> n;
	for(int i = 1; i<= n; i++)
		cin >> arr[i];
	
	vector<vector<int> > a(n + 1);
	for(int i = n; i>= 1; i--){
		if(arr[i] == 0){
			cout << i << " ";
			for(int j = 0; j < a[i].size(); j++){
				cout << a[i][j] << " ";
			}
			a[i].clear();
		}else{
			a[arr[i]].push_back(i);
			for(int j = 0; j < a[i].size(); j++){
				a[arr[i]].push_back(a[i][j]);
			}
			a[i].clear();
		}
	}
}

I: 命令行(待补)

解题思路：

解题代码：

J：最后一块石头的重量(待补)

解题思路：

解题代码：

K: 崩坏：星穹铁道(待补)

解题思路：

解题代码：

M：生命游戏

解题思路：

​ 该题是一道模拟题，但模拟起来有一些问题需要解决。

​ 就比如这种情况，如果边删除边存个数等于k的点，那么就会把中间那个节点也给存进去，但当将当前所有的k节点都删除的时候，就不会删除中间那个节点。

​ 解决这个问题的办法就是用一个set来存删除后节点为k的点，如果中间为k，但操作之后就不为k的时候，就直接将k从set中删除。

​ 所谓的这里面所谓的删边也不是真正意义的删除那个边，而是将那个边标记一下，如果遍历到已经标记的点就不进行向下dfs了。

解题代码：

const int N = 1e6+5;
int user[N];
vector<int> g[N];
int n,k;
vector<int> vis(N);

void dfs(int x){
	vis[x] = 1;
	for(auto i : g[x]){
		if(!vis[i]) dfs(i);
	}
}


void solve() {
	cin >> n >> k;
	for(int i = 1; i < n; i++){
		int a,b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	queue<int> que;
	for(int i = 1; i <= n; i++){
		user[i] = g[i].size();
		if(g[i].size() == k){
			que.push(i);
			user[i] = -1;
		}
	}
	while(que.size()){
		set<int> st;
		while(que.size()){
			int a = que.front();
			que.pop();
			vis[a] = 1;
			for(auto i : g[a]){
				if(user[i] == -1) continue;
				user[i] --;
				if(user[i] == k){
					st.insert(i);
				}
				else {
					if(st.count(i)) st.erase(i);
				}
			}
		}
		for(auto i : st){
			que.push(i);
			user[i] = -1;
		}
	}
	int res= 0;
	for(int i = 1; i <= n; i++){
		if(!vis[i]){
			dfs(i);
			res ++;
		}
	}
	cout << res << endl;
}

N: 圣诞树

解题思路：

​ 该题和我之前写过的一道题很像，

​ 该题主要是树的遍历，当这棵树满足条件的话，那就把这个子树删除，说是删除，其实就是一遍扫描，这个树下的颜色种类全清除罢了。

​ 这题主要思路就是：

1. 先将树的结构存下来，然后进行后序遍历，遍历的过程中进行统计当前节点的颜色，因为要存颜色的种类，所以用set就行。
2. 但这样直接写的话就会导致时间超时，那就需要优化一下，用启发式合并，就可以将时间降下来。

启发式合并：

​ 将少的那一部分加到多的那一部分上。

​ 但要注意的是，直接写会导致内存超限，那么也不能直接等于，那就用swap进行交换，这样就可以将内存降下来。

解题代码：

const int N = 1e6+5;
int arr[N];
vector<int> g[N];
int res = 0;
int n,k;

set<int> dfs(int x,int father){
	set<int> st;
	st.insert(arr[x]);
	for(auto i : g[x]){
		if(i == father) continue;
		set<int> temp = dfs(i,x);
		if(temp.size() > st.size()){
			swap(temp,st);  // 启发式合并 
		}
		for(auto i : temp) st.insert(i);
	}
	if(st.size() >= k){
		res ++; st.clear();
	}
	return st;
}

void solve() {
	cin >> n >> k;
	for(int i = 1; i <= n;i++){
		cin >> arr[i];
	}
	for(int i = 1; i < n; i++){
		int a,b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	set<int> st = dfs(1,1);
	if(st.size() >= k) res++;
	cout << res << endl;
}