海口网站制作,表格上传网站,石家庄网站系统建设,如何判断网站是用什么程序做的2024年西安交通大学程序设计竞赛校赛 文章目录 2024年西安交通大学程序设计竞赛校赛D瑟莉姆的宴会E: 雪中楼I: 命令行(待补)J#xff1a;最后一块石头的重量(待补)K: 崩坏#xff1a;星穹铁道(待补)M#xff1a;生命游戏N: 圣诞树 D瑟莉姆的宴会
解题思路#xff1a;
…2024年西安交通大学程序设计竞赛校赛 文章目录 2024年西安交通大学程序设计竞赛校赛D瑟莉姆的宴会E: 雪中楼I: 命令行(待补)J最后一块石头的重量(待补)K: 崩坏星穹铁道(待补)M生命游戏N: 圣诞树 D瑟莉姆的宴会
解题思路
该题是一道思维题。
仔细想想只要满足非负就行了那么如果一个点没有人支配他那让他为根节点其他都受他的支配这样的话如果后面的所有节点都存在的时候那么就取前面最多的那个节点。
起始该题可以不用考虑1这个状态直接用 2 这个状态也能过。
官方题解方法
该题的官方题解是构造 1 − 2 − 3 − ⋅ ⋅ ⋅ − n 1 - 2 - 3 - ··· - n 1−2−3−⋅⋅⋅−n 的树然后判断这个方式是不是为负的如果为负的就翻转为 n − ( n − 1 ) − ( n − 2 ) − ⋅ ⋅ ⋅ − 1 n - (n-1) - (n-2) - ··· - 1 n−(n−1)−(n−2)−⋅⋅⋅−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: 雪中楼
解题思路
该题是运用链表的思路
当发现 0 的时候就直接输出因为前面没有比他更小的数了。如果发现非0的数那么肯定是比指定的那个数大那么就接在指定那个数的下面。如果当前遍历到的那个数下面接的有数的话就直接输出。因为前面没有比它更大的数了。
解题代码
const int N 1e65;
int arr[N];
void solve() {int n,m;cin n;for(int i 1; i n; i)cin arr[i];vectorvectorint 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 1e65;
int user[N];
vectorint g[N];
int n,k;
vectorint 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);}queueint 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()){setint 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: 圣诞树
解题思路
该题和我之前写过的一道题很像
该题主要是树的遍历当这棵树满足条件的话那就把这个子树删除说是删除其实就是一遍扫描这个树下的颜色种类全清除罢了。
这题主要思路就是
先将树的结构存下来然后进行后序遍历遍历的过程中进行统计当前节点的颜色因为要存颜色的种类所以用set就行。但这样直接写的话就会导致时间超时那就需要优化一下用启发式合并就可以将时间降下来。
启发式合并
将少的那一部分加到多的那一部分上。
但要注意的是直接写会导致内存超限那么也不能直接等于那就用swap进行交换这样就可以将内存降下来。
解题代码
const int N 1e65;
int arr[N];
vectorint g[N];
int res 0;
int n,k;setint dfs(int x,int father){setint st;st.insert(arr[x]);for(auto i : g[x]){if(i father) continue;setint 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);}setint st dfs(1,1);if(st.size() k) res;cout res endl;
}
