碎碎念
前些天和一位博导教授聊了一个多小时,了解到游戏制作也挺看重算法的,跌跌撞撞又回到了算法竞赛。
不过这一年还是以专业必修课和英语六级为主,算法竞赛相对花的时间更少。
比赛
A.Maxmina (0:06)
题意
数组 由 0
和 1
组成,有两种操作:
- 相邻两个数字替换为这两个数字中较小的那个
- 连续 个数字替换为这 个数字中最大的那个
求能否通过一定的操作,让数组 只有一个数字 1
。
分析
- 考虑数组大小 :也就是只有操作一。这种情况下只要存在
0
就没有解。
- 考虑数组大小 :显然,使用操作二一定不劣于使用 次操作一。这种情况下只要存在
1
就有解。
- 考虑数组大小 :尝试让 ,不断使用操作一,尽可能保留
1
。又因为只要存在 1
就可以,那可以随便取一个长度为 的区间,这个区间包含至少一个 1
,区间外的全用操作一去掉就可以了。
综合考虑,只需要判断 与 的大小关系即可。
Code
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
| void solve() { int n,k; bool flag; std::cin >> n >> k; if(n >= k) { flag = false; for(int i = 1; i <= n; i++) { int x; std::cin >> x; if(x) flag = true; } } else { flag = true; for(int i = 1; i <= n; i++) { int x; std::cin >> x; if(!x) flag = false; } } std::cout << (flag ? "YES\n" : "NO\n"); }
|
B. Rebellion (0:12)
题意
数组 由 0
和 1
组成,进行若干次操作:
- 选择两个下标
- 删去
要求最终的数组单调不下降,求最少操作次数。
分析
不难发现,最终的数组形式一定是若干个 0
+ 若干个 1
。若出现某个数字 ,一定能证明出有更优的解法。
于是可以使用两个指针,分别从前往后和从后往前。当找到一对 时,交换这两个数字
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| void solve() { int n; std::cin >> n; std::vector<int> a(n); for(int i = 0; i < n; i++) std::cin >> a[i]; int l = 0, r = n - 1, ans = 0; while(l < r) { while(l < r && a[l] != 1) l++; while(l < r && a[r] != 0) r--; if(l < r) { ans++; l++; r--; } } std::cout << ans << '\n'; }
|
C. Permutation Operations (0:25)
题意
数组 是一个 的排列,进行 次操作,第 次操作:
- 选择一个下标
- 将区间 上的数字都加上
要求进行 次操作后,排列中的逆序对数最少,输出每一次操作的下标 (多种方案时任意输出一种)
分析
看到题的第一反应是,有没有一种通用的算法,能够让逆序对数变成0
。
然后手画了几个图,发现对于某一个较大的数字 ,如果要减少关于这个数字的逆序对(以这个数字为数对的第一个),那么就要让后边的数字增加一个值 。
不难发现,当 时,以 为第一变量的逆序对数一定会变成 0
。
再从 考虑,那么 是这合理的。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| void solve() { int n; std::cin >> n; std::vector<int> a(n); for(int i = 0; i < n; i++) std::cin >> a[i]; int l = 0, r = n - 1, ans = 0; while(l < r) { while(l < r && a[l] != 1) l++; while(l < r && a[r] != 0) r--; if(l < r) { ans++; l++; r--; } } std::cout << ans << '\n'; }
|
D. Paths on the Tree (1:25)
题意
给一棵有根数树,节点有权值 。
画 条从根开始的简单路径,令 表示经过点 的路径数量,要求对于所有兄弟节点 有 。
求 的最大值。
分析
首先考虑恰好均分的情况。
记 表示有 条路径经过了 , 表示节点 有 个子节点。
当 不是叶子节点时,有 成立,此时路径方案是唯一确定的。
再考虑对于多的路径如何分配。
对于 ,令 ,因为兄弟节点 有 ,那么对于这 条边必须分给 个儿子,问题转化为如何找到最优子节点。
从叶子节点的父亲那一层开始考虑:对于这个父亲节点 ,其最优的 个方案就是其子节点 的前 个值。
那么对于父亲节点的父亲节点,也就是叶子节点的祖先节点那一层,对于祖先节点 ,其最优的 个方案是【其子节点 + 那个子节点的第 个最优子节点 】的前 个值
依次从叶子结点向上传递信息。
Code
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
| std::vector<int> f,s; std::vector<std::vector<int>> To; long long ans; void dfs(int u,int time) { ans += 1ll * time * s[u]; if(To[u].size() == 0) { f[u] = s[u]; return; } int Mod = time % To[u].size(); int cnt = time / To[u].size(); std::priority_queue<int> q; for(int v : To[u]) { dfs(v, cnt); q.push(f[v]); } while(Mod--) { ans += q.top(); q.pop(); } f[u] = s[u] + q.top(); } void solve() { int n,k; std::cin >> n >> k; To.clear();To.resize(n + 1); for(int i = 2; i <= n; i++) { int fa; std::cin >> fa; To[fa].push_back(i); } s.clear();s.resize(n + 1); for(int i = 1; i <= n; i++) std::cin >> s[i]; f.clear();f.resize(n + 1); ans = 0; dfs(1, k); std::cout << ans << '\n'; }
|
E1. Joking (Easy Version) (TLE)
题意
交互题。在 中猜一个数字。
每次提问时,给一个集合,返回 YES/NO
。
存在一些回答是假信息,保证相邻两个回答至少有一个回答是真信息。
有两次机会确定答案。
分析
对于这道题的简单模型,最多只需要 次提问。
考虑如何判断假消息,尝试从两次确定答案的机会入手。
开始直接确定答案是否为1,得到一个确定的信息,即答案不是1。
之后不停提问,给出集合{1},当回答为 YES
时,我们可以判断这是一条假消息,那么下一条消息为真,回归简单模型。
问题在于,假消息的出现频率是任意的,当假消息出现频率极低时,我们可能不停询问集合{1}。
总结
最近打 Codeforces
的次数真的很低,当时是不太想搞竞赛,打算去一次 ICPC
就退役的。
不过也还好,大二这一年把专业课学好,尽量多读点黑皮书,实现一下书里提到的内容。
无论是竞赛、大创还是美赛,都等到大三去好了。
目前计划一周打一次 CF VP,周六有 CF 就加一场比赛。
坚持一下咯,和博导聊天真的感觉到就业危机感了。