阅读量:3
A. Only Pluses
时间限制：1秒 空间限制：256MB 输入：标准输入 输出：标准输出
问题描述
Kmes 写下了三个整数 a、b 和 c，以记住他要给 Noobish_Monk 的香蕉数量是 a × b × c。
Noobish_Monk 发现了这些整数，并决定最多进行 5 次以下操作：
- 选择其中一个整数；
- 将其增加 1。
例如，如果 a = 2，b = 3 和 c = 4，那么可以将 a 增加三次，将 b 增加两次。之后 a = 5，b = 5，c = 4。然后香蕉总数将是 5 × 5 × 4 = 100。
请问 Noobish_Monk 通过这些操作可以达到的 a×b×c 的最大值是多少？
输入格式
每个测试包含多个测试用例。输入的第一行包含一个整数 t (
)，表示测试用例的数量。每个测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含三个整数 a、b 和 c ()，表示Kmes 的整数。
输出格式
对于每个测试用例，输出一个整数，表示Noobish_Monk 可以获得的香蕉的最大数量。
样例输入
样例输出
思路
每次都选取最小的数进行操作，最后就会得到最大的结果。
代码
#include <bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int main() { int n = read(); while (n--) { int a = read(), b = read(), c = read(); priority_queue<int, vector<int>, greater<int>> q; q.push(a), q.push(b), q.push(c); for (int i = 1; i <= 5; i++) { int num = q.top() + 1; q.pop(); q.push(num); } int ans = 1; while (q.size()) { ans *= q.top(); q.pop(); } printf("%d\n", ans); } return 0; }B. Angry Monk
时间限制：2秒 空间限制：256MB 输入：标准输入 输出：标准输出
问题描述
为了庆祝他的康复，k1o0n 烤了一个巨大的长 n 米的土豆砂锅。
结果，Noobish_Monk 无法忍受土豆，所以他决定破坏 k1o0n 的饭菜。他将砂锅切成了 k 块，长度分别为 米。
k1o0n 不太喜欢这样。幸运的是，一切都可以修复。为此，k1o0n 可以进行以下操作之一：
1. 选择一个长度为 的块，并将其分成两个长度分别为 1 和 的块。结果，块的数量将增加 1；
2. 选择一个长度为 的块和另一个长度为 的块 ()，并将它们合并成一个长度为 的块。结果，块的数量将减少 1。
请帮助 k1o0n 找到将砂锅合并成一块长度为 n 的最小操作次数。
例如，如果 n = 5, k = 2 和 a = [3, 2]，最优操作如下：
1. 将长度为 2 的块分成两个长度分别为 2 − 1 = 1 和 1 的块，结果 a = [3, 1, 1]。
2. 将长度为 3 的块和长度为 1 的块合并，结果 a = [4, 1]。
3. 将长度为 4 的块和长度为 1 的块合并，结果 a = [5]。
输入格式
每个测试包含多个测试用例。第一行包含一个整数 t ()，表示测试用例的数量。
每个测试用例的描述由两行组成。第一行包含两个整数 n 和 k ()，砂锅的长度和块的数量。
第二行包含 k 个整数 ()，分别表示 Noobish_Monk 切成的块的长度。
保证所有测试用例中 k 的总和不超过 。
输出格式
对于每个测试用例，输出 K1o0n 在 Noobish_Monk 的破坏后恢复他的砂锅所需的最小操作次数。
样例输入
样例输出
思路
对于所有 的块，可以直接与最大的块合并，每次合并需要进行 1 次操作。
对于剩下的 的块，除了最大的块以外，每一个块可以先分成 个长度为 1 块，再分别与最大的块进行合并，分别需要进行 和 次操作。
很容易发现，以上两种情况都需要进行 次操作。
代码
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10; int t, n, k, a[N], ans; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } signed main() { t = read(); while (t--) { ans = 0; n = read(), k = read(); for (int i = 1; i <= k; i++) a[i] = read(); sort(a + 1, a + k + 1); for (int i = 1; i < k; i++) ans += (2 * a[i] - 1); printf("%lld\n", ans); } return 0; }C. Gorilla and Permutation
时间限制：2秒 空间限制：256MB 输入：标准输入 输出：标准输出
问题描述
大猩猩和 Noobish_Monk 找到了三个数字 n、m 和 k（m < k）。他们决定构造一个长度为 n 的排列。
对于这个排列，Noobish_Monk 提出了以下函数：g(i) 是排列前缀长度为 i 的所有不大于 m 的数字之和。同样，大猩猩提出了函数 f，其中 f(i) 是排列前缀长度为 i 的所有不小于 k 的数字之和。长度为 i 的前缀是由原数组的前 i 个元素组成的子数组。
例如，如果 n = 5，m = 2，k = 5，排列为 [5,3,4,1,2]，则：
f(1) = 5，因为 5 ≥ 5；g(1) = 0，因为 5 > 2；
f(2) = 5，因为 3 < 5；g(2) = 0，因为 3 > 2；
f(3) = 5，因为 4 < 5；g(3) = 0，因为 4 > 2；
f(4) = 5，因为 1 < 5；g(4) = 1，因为 1 ≤ 2；
f(5) = 5，因为 2 < 5；g(5) = 1 + 2 = 3，因为 2 ≤ 2。
帮助他们找到一个排列，使得 () 的值最大化。
一个长度为 n 的排列是由 1 到 n 的 n 个不同整数以任意顺序组成的数组。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是排列（因为 2 出现了两次），而 [1,3,4] 也不是排列（因为 n = 3，但数组中出现了 4）。
输入格式
第一行包含一个整数 t ()，表示测试用例的数量。
每个测试用例的唯一一行包含三个整数 n, m 和 k ()，表示要构造的排列的大小和另外两个整数。
保证所有测试用例中 n 的总和不超过 。
输出格式
对于每个测试用例，输出一个排列，表示满足问题条件的一组数字。如果有多个解决方案，输出其中任何一个。
样例输入
样例输出
注释
在第一个例子中，。
思路
要让结果最大，我们很容易能想到要让 尽可能大，并且要让 尽可能小，所以只需要将所有不小于 k 的数由大到小地放在排列的最前面，将所有不大于 m 地数有小到大地放在排列的最后面；中间的数字可以以任何数字排列，对结果不会产生任何影响。
代码
#include <bits/stdc++.h> using namespace std; int t, n, k, m; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int main() { t = read(); while (t--) { n = read(), k = read(), m = read(); for (int i = n; i > k; i--) printf("%d ", i); for (int i = 1; i <= k; i++) printf("%d ", i); putchar('\n'); } return 0; }D. Test of Love
问题描述
ErnKor 为了 Julen 甘愿做任何事情，甚至不惜游过鳄鱼出没的沼泽。我们决定测试这种爱。ErnKor 将不得不游过一条宽度为 1 米、长度为 n 米的河。
这条河非常寒冷。因此，在整个游程中（从 0 米到 n + 1 米），ErnKor 在水中的游程不能超过 k 米。为了人类的安全，我们不仅在河里放了鳄鱼，还放了木头供他跳跃。我们的测试如下：
起初，ErnKor 在左岸，需要到达右岸。左岸和右岸分别位于 0 米和 n + 1 米处。河流可以表示为 n 个段，每段长度为 1 米。每个段包含木头 'L'、鳄鱼 'C' 或只是水 'W'。ErnKor 可以按以下方式移动：
- 如果他在岸上（即在岸上或木头上），他可以向前跳跃不超过 m 米（1 ≤ m ≤ 10 米）（他可以跳到岸上、木头上或水里）。
- 如果他在水中，他只能游到下一个河段（或者如果他在第 n 米处，可以游到岸上）。
- ErnKor 无论如何都不能落在有鳄鱼的河段上。
判断 ErnKor 是否能到达右岸。
输入格式
第一行包含一个整数 t ()，表示测试用例的数量。
每个测试用例的第一行包含三个整数 n, m, k ()，表示河流的长度、ErnKor 可以跳跃的距离以及 ErnKor 在不冻僵的情况下可以游泳的米数。
每个测试用例的第二行包含一个长度为 n 的字符串 a。 表示第 i 米处的物体 (a[i] ∈ {'W', 'C', 'L'})。
保证所有测试用例中的 n 的总和不超过 。
输出格式
对于每个测试用例，如果 ErnKor 能通过测试，则输出 "YES"，否则输出 "NO"。
你可以以任何大小写输出答案。例如，字符串 "yEs", "yes", "Yes" 和 "YES" 都使正确答案。
样例输入
样例输出
注释
考虑以下示例：
- 第一个示例：我们从岸边跳到第一块木头（0→1），从第一块木头跳到第二块（1→3），从第二块跳到第四块（3→5），然后从最后一块木头跳到对岸（5→7）。所以，我们的路径是 0→1→3→5→7。由于我们没有遇到鳄鱼，并且游泳的距离不超过 k 米，答案是 "YES"。
- 第二个示例：0→1，我们从第一块木头跳入水中（1→2），游一个单位到木头（2⇝3），然后 3→4→5→6→7。由于我们没有遇到鳄鱼，并且游泳的距离不超过 k 米，答案是 "YES"。
- 第三个示例：ErnKor 需要游过两个 'W' 单元，但只能游一个。因此，答案是 "NO"。
- 第六个示例：我们从岸边跳入水中（0→6），然后游一个单位在水中（6⇝7）。由于我们没有遇到鳄鱼，并且游泳的距离不超过 k 米，答案是 "YES"。
思路
这题很明显是一个DP。从左到右的最少游泳距离一定是等于从右到左的最少游泳距离的，因此可以反向考虑，从最右端跳到最左端需要最少的游泳距离是多少。设 为从后往前考虑到第 i 位最少的游泳距离。
代码
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int t, n, m, k, f[N]; string s; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int main() { t = read(); while (t--) { n = read(), m = read(), k = read(); cin >> s; s = "L" + s; // 左岸与木头 'L' 性质相同，因此把左岸处理成 'L' f[n + 1] = 0; for(int i = n; i; i--) f[i] = N; f[0] = N; for(int i = n; i >= 0; i--) { if(s[i] == 'C') continue; if(s[i] == 'L') for(int j = 1; j <= m && i + j <= n + 1; j++) f[i] = min(f[i + j], f[i]); // 根据原题意理解，可以从当前位置往后跳到任何 m 以内且 s[i] != 'C' 的位置 // 由于从左往右跳跟从右往左跳必定存在相同路径 // 反向考虑之后，变成了可以从后面长度 m 以内任意 s[i] != 'C' 的位置往前跳 if (s[i] == 'W') f[i] = f[i + 1] + 1; } if(f[0] <= k) puts("YES"); else puts("NO"); } return 0; }E. Novice's Mistake
时间限制：3秒 空间限制：256MB 输入：标准输入 输出：标准输出
问题描述
K1o0n 的第一个编程问题之一是这样的：“Noobish_Monk 有 n () 个朋友。他们每个人都给了他 a () 个苹果作为生日礼物。Noobish_Monk 对这个礼物非常高兴，他把 b () 个苹果还给了他的朋友。那么 Noobish_Monk 还剩下多少个苹果？”
K1o0n 写了一个解决方案，但不小心将 n 的值视为字符串，所以 的值被不同地计算了。具体来说：
- 当将字符串 n 与整数 a 相乘时，他会得到字符串
（重复 a 次）。
- 当从字符串 s 中减去整数 b 时，最后的 b 个字符将被删除。如果 b 大于或等于字符串 s 的长度，它将变为空。
得知此事后，ErnKor 对有多少对 (a, b) 存在感兴趣，这些对满足问题的约束，使得 K1o0n 的解决方案给出正确的答案。
“解决方案给出正确答案”意味着它输出了一个非空字符串，并且该字符串在转换为整数时等于正确答案，即 的值。
输入格式
第一行包含一个整数 t ()，表示测试用例的数量。
对于每个测试用例，输入一行包含一个整数 n ()。
保证所有测试用例中的 n 都是不同的。
输出格式
对于每个测试用例，按以下格式输出答案：
第一行输出整数 x，表示对于给定的 n，满足条件的 (a, b) 对的数量。
接下来的 x 行中，每行输出两个整数 和 ，表示这些整数满足 K1o0n 在测试 "" 上给出正确答案。
样例输入
样例输出
注释
在第一个例子中，a = 20，b = 18 是合适的，因为 "22222222222222222222" ⋅ 20 - 18 = 22 = 2 ⋅ 20 - 18。
思路
从 1 到 10000 枚举 b，再把 n 当作字符串按位枚举 x，根据 x 推出对应的 a；判断 x 是否等于 n 位数字时的 。
如何得到 a：把 x 看作字符串的时候，x 是由 a 个 n（字符串）再减去最后 b 个字符得到。因此，只有 x（字符串）的长度 + b 为 n（字符串）的长度的倍数时，a 才存在。
代码
#include <bits/stdc++.h> using namespace std; #define int long long int t, n; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } signed main() { t = read(); while (t--) { n = read(); string s = to_string(n); int len = s.size(); set<pair<int, int>> ans; // 储存答案 for (int b = 1; b <= 10000; b++) { int x = n, p = 0; while (x <= 1000000) { if ((to_string(x).size() + b) % len == 0) { int a = (to_string(x).size() + b) / len; if (a * n - b == x && a <= 10000 && b <= a * n) ans.insert({a, b}); } x = x * 10 + s[p] - '0'; p = (p + 1) % len; } } printf("%lld\n", ans.size()); for (auto& val : ans) printf("%lld %lld\n", val.first, val.second); } return 0; }F. Valuable Cards
时间限制：4秒 空间限制：512MB 输入：标准输入 输出：标准输出
问题描述
Kmes 在他最喜欢的咖啡馆里再次想尝试“皮下鲱鱼”。以前，他可以轻松做到这一点，但咖啡馆最近引入了新的购买政策。
现在，为了进行购买，Kmes 需要解决以下问题：他面前放着 n 张卡片，每张卡片上有一个整数 ai，这些价格中没有一个是正整数 x。
Kmes 被要求将这些卡片分成最少数量的坏段（每张卡片必须属于一个段）。如果在一个段中不可能选择一个子集，其乘积等于 x，那么这个段被认为是坏的。Kmes 将卡片分成的所有段都必须是坏的。
正式地说，段 (l, r) 是坏的，如果不存在满足 且 的索引 。
帮助 Kmes 确定最少数量的坏段，以便他可以享受他最喜欢的菜肴。
输入格式
第一行包含一个整数 t ()—— 测试用例的数量。
每组输入数据的第一行包含两个整数 n 和 x ()，表示卡片的数量和整数 x。
每组输入数据的第二行包含 n 个整数 ai (, )，表示卡片上的价格。
保证所有测试用例中 n 的总和不超过 。
输出格式
对于每组输入数据，输出最少数量的坏段。
样例输入
样例输出
思路
要使坏的片段最少，那么要使每个坏的片段尽可能的长。从最左边的卡片开始遍历，用 set 或者 map 来存能凑出乘积为 x 的子集的因数。
- 如果 set 或者 map 中已经存有 ，那么 ans = ans + 1，并且清空 set 或者 map
- 否则，遍历 set 或者 map，将 set 或者 map的第一个元素除以 的结果分别放入 set 或者 map中；再将 放入 set 或者 map 中
（比赛时用的 unordered_map 没过.....，有没有人知道为什么用 unordered_map 过不了）
代码
用set
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int t, n, x, a[N]; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int main() { t = read(); while (t--) { set<int> s; n = read(), x = read(); int ans = 1; for (int i = 1; i <= n; i++) a[i] = read(); for (int i = 1; i <= n; i++) { if (s.count(a[i])) { ans++; s.clear(); } if (x % a[i] == 0) { for (auto& j : s) if (j % a[i] == 0) s.insert(j / a[i]); s.insert(x / a[i]); } } printf("%lld\n", ans); } return 0; }用map
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int t, n, x, a[N]; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int main() { t = read(); while (t--) { map<int, bool> mp; n = read(), x = read(); int ans = 1; for (int i = 1; i <= n; i++) a[i] = read(); for (int i = 1; i <= n; i++) { if (mp.find(a[i]) != mp.end()) { ans++; mp.clear(); } if (x % a[i] == 0) { for (auto& [j, k] : mp) if (j % a[i] == 0) mp[j / a[i]] = 1; mp[x / a[i]] = 1; } } printf("%lld\n", ans); } return 0; }