Codeforces Round 957 (Div.3)_业界新闻

发布时间:2024-07-13 23:07

阅读量: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 ( $1 \le t \le 1000$ )，表示测试用例的数量。每个测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含三个整数 a、b 和 c ( $1 \le a, b, c \le 10$ )，表示Kmes 的整数。

输出格式

对于每个测试用例，输出一个整数，表示Noobish_Monk 可以获得的香蕉的最大数量。

样例输入

$2\\ 2 \hspace{0.5em}3\hspace{0.5em} 4\\ 10\hspace{0.5em} 1\hspace{0.5em} 10$

样例输出

$100\\ 600$

思路

每次都选取最小的数进行操作，最后就会得到最大的结果。

代码

#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 块，长度分别为 $a_1, a_2, \ldots, a_k$ 米。

k1o0n 不太喜欢这样。幸运的是，一切都可以修复。为此，k1o0n 可以进行以下操作之一：

1. 选择一个长度为 $a_i \ge 2$ 的块，并将其分成两个长度分别为 1 和的块。结果，块的数量将增加 1；
2. 选择一个长度为的块和另一个长度为的块 ( $i \not= j$ )，并将它们合并成一个长度为 $a_i + 1$ 的块。结果，块的数量将减少 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 ( $1 \le t \le 10^4$ )，表示测试用例的数量。

每个测试用例的描述由两行组成。第一行包含两个整数 n 和 k ( $1 \le n \le 10^9, 2 \le k \le 10^5$ )，砂锅的长度和块的数量。

第二行包含 k 个整数 $a_1, a_2, \ldots, a_k$ ( $1 \le a_i \le n - 1, \sum a_i = n$ )，分别表示 Noobish_Monk 切成的块的长度。

保证所有测试用例中 k 的总和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出 K1o0n 在 Noobish_Monk 的破坏后恢复他的砂锅所需的最小操作次数。

样例输入

$4\\ 5 \hspace{0.5em}3\\ 3\hspace{0.5em} 1\hspace{0.5em} 1\\ 5\hspace{0.5em} 2\\ 3\hspace{0.5em} 2\\ 11\hspace{0.5em} 4\\ 2\hspace{0.5em} 3\hspace{0.5em} 1\hspace{0.5em} 5\\ 16\hspace{0.5em} 6\\ 1 \hspace{0.5em}6\hspace{0.5em} 1\hspace{0.5em} 1\hspace{0.5em} 1\hspace{0.5em} 6$

样例输出

$2\\ 3\\ 9\\ 15$

思路

对于所有的块，可以直接与最大的块合并，每次合并需要进行 1 次操作。

对于剩下的 $a_i \ge 2$ 的块，除了最大的块以外，每一个块可以先分成个长度为 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。

帮助他们找到一个排列，使得 ( $\sum_{i = 1}^{n}f(i) - \sum_{i = 1}^{n} g(i)$ ) 的值最大化。

一个长度为 n 的排列是由 1 到 n 的 n 个不同整数以任意顺序组成的数组。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是排列（因为 2 出现了两次），而 [1,3,4] 也不是排列（因为 n = 3，但数组中出现了 4）。

输入格式

第一行包含一个整数 t ( $1 \le t \le 10^4$ )，表示测试用例的数量。

每个测试用例的唯一一行包含三个整数 n, m 和 k ( $2 \le n \le 10^5, 1\le m \le k \le n$ )，表示要构造的排列的大小和另外两个整数。

保证所有测试用例中 n 的总和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出一个排列，表示满足问题条件的一组数字。如果有多个解决方案，输出其中任何一个。

样例输入

$3\\ 5\hspace{0.5em} 2\hspace{0.5em} 5\\ 3 \hspace{0.5em}1\hspace{0.5em} 3\\ 10 \hspace{0.5em}3 \hspace{0.5em}8$

样例输出

$5\hspace{0.5em} 3\hspace{0.5em} 4\hspace{0.5em} 1\hspace{0.5em} 2\\ 3 \hspace{0.5em}2 \hspace{0.5em}1\\ 10\hspace{0.5em} 9\hspace{0.5em} 8\hspace{0.5em} 4\hspace{0.5em} 7\hspace{0.5em} 5\hspace{0.5em} 6\hspace{0.5em} 1\hspace{0.5em} 2\hspace{0.5em} 3$

注释

在第一个例子中， $(\sum_{i = 1}^{n}f(i) - \sum_{i = 1}^{n} g(i)) = 5 \cdot 5 - (0 \cdot 3 + 1 + 3) = 25 - 4 = 21$ 。

思路

要让结果最大，我们很容易能想到要让 $\sum_{i = 1}^{n}f(i)$ 尽可能大，并且要让 $\sum_{i = 1}^{n}g(i)$ 尽可能小，所以只需要将所有不小于 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 ( $1 \le t \le 10^4$ )，表示测试用例的数量。

每个测试用例的第一行包含三个整数 n, m, k ( $1 \le k \le 2 \cdot 10^5, 1 \le n \le 2 \cdot 10^5, 1 \le m \le 10$ )，表示河流的长度、ErnKor 可以跳跃的距离以及 ErnKor 在不冻僵的情况下可以游泳的米数。

每个测试用例的第二行包含一个长度为 n 的字符串 a。表示第 i 米处的物体 (a[i] ∈ {'W', 'C', 'L'})。

保证所有测试用例中的 n 的总和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，如果 ErnKor 能通过测试，则输出 "YES"，否则输出 "NO"。

你可以以任何大小写输出答案。例如，字符串 "yEs", "yes", "Yes" 和 "YES" 都使正确答案。

样例输入

$6\\ 6 \hspace{0.5em} 2 \hspace{0.5em} 0\\ LWLLLW\\ 6 \hspace{0.5em} 1 \hspace{0.5em} 1\\ LWLLLL\\ 6 \hspace{0.5em} 1 \hspace{0.5em} 1\\ LWLLWL\\ 6 \hspace{0.5em} 2 \hspace{0.5em} 15\\ LWLLCC\\ 6 \hspace{0.5em} 10 \hspace{0.5em}0\\ CCCCCC\\ 6 \hspace{0.5em} 6 \hspace{0.5em} 1\\ WCCCCW$

样例输出

$YES\\ YES\\ NO\\ NO\\ 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 ( $1 \le n \le 100$ ) 个朋友。他们每个人都给了他 a ( $1 \le a \le 10000$ ) 个苹果作为生日礼物。Noobish_Monk 对这个礼物非常高兴，他把 b ( $1 \le b \le min(10000, a \cdot n)$ ) 个苹果还给了他的朋友。那么 Noobish_Monk 还剩下多少个苹果？”

K1o0n 写了一个解决方案，但不小心将 n 的值视为字符串，所以 $n \cdot a - b$ 的值被不同地计算了。具体来说：

当将字符串 n 与整数 a 相乘时，他会得到字符串 $s = n + n + \ldots + n$ （重复 a 次）。
当从字符串 s 中减去整数 b 时，最后的 b 个字符将被删除。如果 b 大于或等于字符串 s 的长度，它将变为空。

得知此事后，ErnKor 对有多少对 (a, b) 存在感兴趣，这些对满足问题的约束，使得 K1o0n 的解决方案给出正确的答案。

“解决方案给出正确答案”意味着它输出了一个非空字符串，并且该字符串在转换为整数时等于正确答案，即 $n \cdot a - b$ 的值。

输入格式

第一行包含一个整数 t ( $1 \le t \le 100$ )，表示测试用例的数量。

对于每个测试用例，输入一行包含一个整数 n ( $1 \le n \le 100$ )。

保证所有测试用例中的 n 都是不同的。

输出格式

对于每个测试用例，按以下格式输出答案：

第一行输出整数 x，表示对于给定的 n，满足条件的 (a, b) 对的数量。

接下来的 x 行中，每行输出两个整数和，表示这些整数满足 K1o0n 在测试 " $n \hspace{0.5em} a_i \hspace{0.5em} b_i$ " 上给出正确答案。

样例输入

$3\\ 2\\ 3\\ 10$

样例输出

$3\\ 20 \hspace{0.5em} 18\\ 219 \hspace{0.5em} 216\\ 2218 \hspace{0.5em} 2214\\ 1\\ 165 \hspace{0.5em} 162\\ 1\\ 1262 \hspace{0.5em} 2519$

注释

在第一个例子中，a = 20，b = 18 是合适的，因为 "22222222222222222222" ⋅ 20 - 18 = 22 = 2 ⋅ 20 - 18。

思路

从 1 到 10000 枚举 b，再把 n 当作字符串按位枚举 x，根据 x 推出对应的 a；判断 x 是否等于 n 位数字时的 $n \cdot a - b$ 。

如何得到 a：把 x 看作字符串的时候，x 是由 a 个 n（字符串）再减去最后 b 个字符得到。因此，只有 x（字符串）的长度 + b 为 n（字符串）的长度的倍数时，a 才存在。 $a = \frac{len(x) + b}{len(n)}$

代码

#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) 是坏的，如果不存在满足 $l \le i_1 < i_2 < \ldots < i_k \le r$ 且 $a_{i_1} \cdot a_{i_2} \cdot \ldots \cdot a_{i_k} = x$ 的索引 $i_1,i_2, \ldots,i_k$ 。

帮助 Kmes 确定最少数量的坏段，以便他可以享受他最喜欢的菜肴。

输入格式

第一行包含一个整数 t ( $1 \le t \le 10^3$ )—— 测试用例的数量。

每组输入数据的第一行包含两个整数 n 和 x ( $1 \le n \le 10^5, 2 \le x \le 10^5$ )，表示卡片的数量和整数 x。

每组输入数据的第二行包含 n 个整数 ai ( $1 \le a_i \le 2 \cdot 10^5$ , $a_i \not= x$ )，表示卡片上的价格。

保证所有测试用例中 n 的总和不超过。

输出格式

对于每组输入数据，输出最少数量的坏段。

样例输入

$8\\ 6 \hspace{0.5em} 4\\ 2 \hspace{0.5em} 3 \hspace{0.5em} 6 \hspace{0.5em} 2 \hspace{0.5em} 1 \hspace{0.5em} 2\\ 9 \hspace{0.5em} 100000\\ 50000 \hspace{0.5em} 25000 \hspace{0.5em} 12500 \hspace{0.5em} 6250 \hspace{0.5em} 3125 \hspace{0.5em} 2 \hspace{0.5em} 4 \hspace{0.5em} 8 \hspace{0.5em} 16\\ 5 \hspace{0.5em} 2\\ 1 \hspace{0.5em} 1 \hspace{0.5em} 1 \hspace{0.5em} 1 \hspace{0.5em} 1\\ 8 \hspace{0.5em} 6\\ 4 \hspace{0.5em} 3 \hspace{0.5em} 4 \hspace{0.5em} 3 \hspace{0.5em} 4 \hspace{0.5em} 3 \hspace{0.5em} 4 \hspace{0.5em} 3\\ 7 \hspace{0.5em} 12\\ 6 \hspace{0.5em} 11 \hspace{0.5em} 1 \hspace{0.5em} 3 \hspace{0.5em} 11 \hspace{0.5em} 10 \hspace{0.5em} 2\\ 10 \hspace{0.5em} 5\\ 2 \hspace{0.5em} 4 \hspace{0.5em} 4 \hspace{0.5em} 2 \hspace{0.5em} 4 \hspace{0.5em} 4 \hspace{0.5em} 4 \hspace{0.5em} 3 \hspace{0.5em} 1 \hspace{0.5em} 1\\ 7 \hspace{0.5em} 8\\ 4 \hspace{0.5em} 6 \hspace{0.5em} 5 \hspace{0.5em} 1 \hspace{0.5em} 2 \hspace{0.5em} 4 \hspace{0.5em} 1\\ 8 \hspace{0.5em} 27\\ 3 \hspace{0.5em} 9 \hspace{0.5em} 17 \hspace{0.5em} 26 \hspace{0.5em} 2 \hspace{0.5em} 20 \hspace{0.5em} 9 \hspace{0.5em} 3$

样例输出

$3\\ 2\\ 1\\ 1\\ 2\\ 1\\ 3\\ 3$

思路

要使坏的片段最少，那么要使每个坏的片段尽可能的长。从最左边的卡片开始遍历，用 set 或者 map 来存能凑出乘积为 x 的子集的因数。

如果 set 或者 map 中已经存有，那么 ans = ans + 1，并且清空 set 或者 map
否则，遍历 set 或者 map，将 set 或者 map的第一个元素除以的结果分别放入 set 或者 map中；再将 $\frac{x}{a_i}$ 放入 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; }

Codeforces Round 957 (Div.3)

问题描述

输入格式

输出格式

样例输入

样例输出

思路

代码

问题描述

输入格式

输出格式

样例输入

样例输出

思路

代码

问题描述

输入格式

输出格式

样例输入

样例输出

注释

思路

代码

问题描述

输入格式

输出格式

样例输入

样例输出

注释

思路

代码

问题描述

输入格式

输出格式

样例输入

样例输出

注释

思路

代码

问题描述

输入格式

输出格式

样例输入

样例输出

思路

代码

相关阅读

广告一刻