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

2024-06-02 16:44

本文主要是介绍2024年西安交通大学程序设计竞赛校赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

文章目录

  • 2024年西安交通大学程序设计竞赛校赛
    • D瑟莉姆的宴会
    • E: 雪中楼
    • I: 命令行(待补)
    • J:最后一块石头的重量(待补)
    • K: 崩坏:星穹铁道(待补)
    • M:生命游戏
    • N: 圣诞树

D瑟莉姆的宴会

解题思路:

​ 该题是一道思维题。

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

​ 起始该题可以不用考虑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>(n1)>(n2)>⋅⋅⋅>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:生命游戏

解题思路:

​ 该题是一道模拟题,但模拟起来有一些问题需要解决。_cgi-bin_mmwebwx-bin_webwxgetmsgimg__&MsgID=3291596598234462527&skey=@crypt_f94f2d13_d4d93e9d0c4c227384cec13b905af67e&mmweb_appid=wx_webfilehelper

​ 就比如这种情况,如果边删除边存个数等于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;
}

这篇关于2024年西安交通大学程序设计竞赛校赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1024524

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

免费也能高质量!2024年免费录屏软件深度对比评测

我公司因为客户覆盖面广的原因经常会开远程会议,有时候说的内容比较广需要引用多份的数据,我记录起来有一定难度,所以一般都用录屏工具来记录会议内容。这次我们来一起探索有什么免费录屏工具可以提高我们的工作效率吧。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  录屏软件录屏功能就是本职,这款录屏工具在录屏模式上提供了多种选项,可以选择屏幕录制、窗口

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

论文翻译:ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的,这引发了人们的担忧和猜测,即它们可能已

轻松录制每一刻:探索2024年免费高清录屏应用

你不会还在用一些社交工具来录屏吧?现在的市面上有不少免费录屏的软件了。别看如软件是免费的,它的功能比起社交工具的录屏功能来说全面的多。这次我就分享几款我用过的录屏工具。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  这个软件的操作方式非常简单,打开软件之后从界面设计就能看出来这个软件操作的便捷性。界面的设计简单明了基本一打眼你就会轻松驾驭啦