Personal solution. 入门算法套思维场 A. 打牌 题意 对于一张牌，有对应的权值和点数。 对于牌上的字符，按照 A,K,Q,J,10,9,8,7,6,5,4,3,2 的顺序，权值依次减小。 对于牌上的字符，若字符为 2 ~ 9，则点数为字符对应的数字；否则，有下面的对应关系： A: 1, T: 10, J: 11, Q: 12, K: 13 现在给定 A, B 之间的博弈： 每个人有两张牌，牌上会有两个字符，我们无视第二个字符； 双方都可以看到对方的牌，从而采取最优策略； 第一局 A 先手。当 先手 所出的牌的权值 \(\geq\) 后手 所出的牌的权值，先手 获得权值最大的牌对应的点数，否则 后手 获得权值最大的牌对应的点数。 上一局获得点数的玩家在第二局为先手，规则和上一局一致。 现在，若两个人都使用最优策略，输出 A 获得的点数 \(-\) B 获得的点数 的最大值。 思路 为方便计算，我们记 B 获得的都是负点数。 首先，因为只有两轮，我们可以发现，第一局的选择总共有四种。 即，如果我们将其标一个 ...
Solution from problem setter. 简单算法场 A. Amiable Parameter 背景 福师大第20届校赛 E 题 改编。 题意 给定 \(f(x) = |x - a_1| + |x - a_2| + \ldots + |x - a_n| + b_1 + b_2 + \ldots + b_n\)，找出最小的 \(x\)，使 \(f(x)\) 最小。 思路 计算中位数。 我们可以用点到数轴上的距离来形象化式子的左半部分。 如果数轴上有 \(n\) 个点，要找到一个点 \(p\)，使 \(p\) 和这些点的距离之和最小，显然我们取这些数的中位数。 你可以发现，如果中位数有两个，一定是取最小的那个中位数，因为两个中位数的答案是一样的。 那么，我们将 \(a_i\) 读入到数组中 并 升序排序，并统计 \(b_i\) 的总和 \(sum_b\)，然后我们对中位数算一下答案即可。 最后，别忘了加上右半部分式子的结果 \(sum_b\)。 注意，本题无法使用复杂度为 \(O(n ^ 2)\) 的排序算法通过。 时间 ...
Solution from problem setter. 语法场 A. Ocean睡大觉 题意 给定一个时间段，去掉这个时间段后，给定一个结束时刻 \(E\)，确定最大的开始时刻 \(S\)，使 \(S\) 到 \(E\) 这段时间的时长至少为 \(8\) 小时。 开始时刻 \(S\) 不能超过给定时间段的开始时间。 思路 直接模拟。 因为题面给的是小时和分钟，那么如果我们将其转化为分钟，显然这就转化为数轴上的问题了（比如说，\(3:40 \rightarrow 220\)）。 那么，你可以画个图，把边界情况都列出来，然后问题自然就迎刃而解了。 当然，题面是有坑的。如果你仔细看题了，不难发现，最后答案是要和比赛开始时间取一个最小值的，不然有可能出现只需睡一个阶段的情况，从而刚好挂掉 \(1\) 个点。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long void solve() { int ...
Contestant. Rank 1335. Rating +80. A. MEXanized Array 题意 给定三个整数 \(n, k, x\)，构造一个长为 \(n\) 的数组，满足 \(MEX = k\)，最大值不超过 \(x\)。 输出数组总和的最大值。无法构造输出 \(-1\)。 思路 首先，如果 \(MEX\) 大于数组的长度，或者大于数组的最大值 \(+ 1\)，那么就无法构造。 否则，我们就只需对 \(MEX\) 和最大值的大小关系进行特判即可。 我们先依次填入 \(0, 1, 2, \ldots, k - 1\)，然后剩余的都填上最大值。如果最大值是 \(MEX\)，那么我们应该填上 最大值 $ - 1$。 时间复杂度：\(O(1)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 using namespace std; //#define FLOATING_OCEAN ...
Contestant~. Rank 313. Rating +53. 这场的 \(E\) 难度感觉很有争议，感觉放 \(C\) 都不过分（个人看法 A. green_gold_dog, array and permutation 题意 给定一个序列 \(a\)，构造一个排列 \(b\)，使所有 \(a_i - b_i\) 中不同值的个数最大，并输出方案。 思路 显然地，因为我们可以减到负数，那么我们用大数减小数的方式，一定可以构造出尽可能多的 \(a_i - b_i\)。 时间复杂度：\(O(n)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pi ...
Contestant~. Rank 257. Rating +51. A. Make It Zero 题意 给定一个序列，定义一次操作为选定一个区间，并将区间内的所有数全都替换为他们的异或总和。 输出不超过 \(8\) 次操作后，让整个序列变为 \(0\) 的一种方案。 思路 我们分奇偶性来考虑： 如果序列长度为偶数，显然偶数个相同的元素异或和为 \(0\)，那么我们只要对整个序列进行异或，然后再重复一次操作即可； 如果序列长度为奇数，那么我们同上，对前 \(n - 1\) 个元素执行两次操作。因为任何数和 \(0\) 异或都是它本身，因而我们对最后两个元素操作两次即可。 时间复杂度：\(O(1)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 using namespace std; //#define FLOATING_OCEAN #define int long long #def ...
Contestant_. Rank 344. Rating +183. A. Two Vessels 题意 给定两个水槽，初始状态下有 \(a, b\) 单位的水。现在给定一个容量为 \(c\) 的水杯，输出最少需要舀几次水，让两个水槽的水体积相等 思路 显然我们缺少 \(\frac{abs(a- b)}{2}\)，设其为 \(p\)，那么我们需要舀 \(\lceil \frac{p}{c} \rceil\) 次。 时间复杂度：\(O(1)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define tpi tuple<int, int, ...
Contestant~. Rank 881. Rating +7. A. Prime Deletion 题意 给定 \(\{0, 1, \ldots, 9\}\) 的一种排列，定义一次操作为在排列剩余元素个数 大于2 的条件下，任意删去一个数字。 任意次操作后，输出排列拼接而成的数字，并满足该数字是质数。 思路 因为 \(13, 31\) 都是质数，并且 \(1\) 一定在 \(3\) 的左边或者右边，因而判一下 \(1\) 的位置即可。 时间复杂度：\(O(n)\) 对应AC代码 #define chatgpt "bits/stdc++.h" #include chatgpt using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define tpi tuple<int, int, int> #define fs first #defi ...
Contestant~. Rank 1909. Rating -24. A. Channel 题意 定义每个人上线都会阅读所有帖子。 现在，\(A\) 发布了一篇文章，发布的时候。 给定由 "+", "-" 组成的字符串，分别代表该时刻有一个人上线/下线，按照下面的方式输出答案： 所有人都阅读过该文章，输出 \(YES\)； 有可能所有人都阅读过该文章，输出 \(MAYBE\)； 所有人都不可能阅读过该文章，输出 \(NO\) 思路 所有人都阅读过的条件是假设下线后上线的是同一个人，有可能所有人都阅读过的条件是假设下线后上线的是不同的人。 否则就是不可能。 时间复杂度：\(O(n)\) 对应AC代码 #define chatgpt "bits/stdc++.h" #include chatgpt using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair< ...