Contestant^. Rank 154. Rating +119 (+469 -350). 不知道有没有可能在有生之年打到 cf 第1000场（ A. How Much Does Daytona Cost? 题意 给定一个序列 \(a\)，以及一个整数 \(k\)，判断 \(k\) 是否是 \(a\) 的任意子串中出现次数最多的字符。 思路 只要子串长度是 \(1\)，那么该字符就是出现次数最多的字符。 那么，问题就转化为判断 \(k\) 是否在 \(a\) 中出现了。 时间复杂度：\(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, pii> ...
Contestant^. Rank 132. Rating +86 (+336 -250). A. Don't Try to Count 题意 给定两个字符串 \(s, t\)，定义操作为将 \(s\) 本身拼接到 \(s\) 后面，操作非独立。 输出最小的操作次数，使 \(s\) 中包含子串 \(t\)。 思路 显然，数据范围小的离谱，那么我们直接暴力。 我们暴力拼接，然后用合适的复杂度下的字符串匹配即可。 可以发现，需要拼接的次数是很少的，此处用了最多 \(10\) 次，但应该不用这么多。 至于匹配，可以用 \(\mathtt{strstr}\) 函数，底层是用 \(\mathtt{KMP}\) 算法实现的，可以跑的飞快。 时间复杂度：\(O(不大)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 using namespace std; //#define FLOATING_OCEAN ...
Contestant. Rank 728. Rating +14. 罚时爆炸 A. Jellyfish and Undertale 题意 对于一个即将引爆的炸弹，给定 \(i\) 个工具，每个工具最多使用一次，使用时将会使炸弹的计时器 \(+x_i\) 个单位时间，但如果计时器的时间大于 \(a\)，它将会复位为 \(a\)。 找出一个方案，使计时器在归 \(0\) 前，时间尽可能长，并输出这个时间。 思路 显然，为了让时间尽可能长，我们一定会在计时器为 \(1\) 时使用工具，那么工具的使用顺序是无所谓的。 那么，我们只需将每个工具的 \(x_i\) 和 \(a - 1\) 取最小值，然后累加即可。 时间复杂度：\(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 l ...
Practice. A. Goals of Victory 题意 对于 \(n\) 只队伍，存在 \(\frac{n(n - 1)}{2}\) 个任意两只队伍间的比赛。每支队伍具有一个效率值，为队伍的所有比赛中自己的进球数减去其他队伍进球数的总和。 现在，给定 \(n - 1\) 个队伍的效率，求第 \(n\) 个队伍的效率。 思路 对于一场比赛，如果 \(A\) 赢，那么 \(A\) 的效率 \(+ 1\)，\(B\) 的效率 \(-1\)。 因而，所有队伍的效率和为定值 \(0\)。 那么，第 \(n\) 个队伍的效率为前 \(n - 1\) 个队伍的效率和的相反数。 时间复杂度：\(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 ...
Contestant. Rank 263. Rating +90. A. Sum of Three 题意 给定一个整数 \(n\)，构造一种方案，使得 \(n = x + y + z\)，且 \(x \neq y \neq z; x, y, z \not \equiv 0 \pmod 3\)。 思路 分类讨论。 首先，最小的构造是 \(x = 1, y = 2, z = n - 3\)，那么显然，\(n - 3 > 2\)，即 \(n \geq 6\)。 并且，因为 \(z\) 不可以是 \(3\) 的倍数，所以 \(n\) 也不可以是 \(3\) 的倍数。 那么，如果 \(n\) 是 \(3\) 的倍数，我们考虑次小的构造：\(x = 1, y = 4, z = n - 5\)，此时 \(n - 5 > 4\)，即 \(n \geq 10\)。 此时，可以发现 \(n - 5\) 不是 \(3\) 的倍数，从而符合要求。 时间复杂度：\(O(1)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" ...
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 ...