Codeforces - 1166E - The LCMs Must be Large
Codeforces - 1166E - The LCMs Must be Large地址http://codeforces.com/contest/1166/problem/E原文地址https://www.lucien.ink/archives/434题目Dora the explorer has decided to use her money after several years of juicy royalties to go shopping. What better place to shop than Nlogonia?There are $n$ stores numbered from $1$ to $n$ in Nlogonia. The $i$-th of these stores offers a positive integer $a_i$.Each day among the last $m$ days Dora bought a single integer from some of the stores. The same day, Swiper the fox bought a single integer from all the stores that Dora did not buy an integer from on that day.Dora considers Swiper to be her rival, and she considers that she beat Swiper on day $i$ if and only if the least common multiple of the numbers she bought on day $i$ is strictly greater than the least common multiple of the numbers that Swiper bought on day $i$.The least common multiple (LCM) of a collection of integers is the smallest positive integer that is divisible by all the integers in the collection.However, Dora forgot the values of $a_i$. Help Dora find out if there are positive integer values of $a_i$ such that she beat Swiper on every day. You don't need to find what are the possible values of $a_i$ though.Note that it is possible for some values of $a_i$ to coincide in a solution.题意有 $n$ 种石头，每个石头有一个未知的权值，有 $m$ 天，每天一个整数 $k$ 代表这一天拿了 $k$ 个石头，接下来是 $k$ 个整数，代表石头的下标。问是否存在一种分配权值的方案，使得每一天拿的所有石头权值的 $LCM$ 都严格大于补集中所有石头权值的 $LCM$ 。题解反证法，考虑某一天拿的集合为 $D_i$ ，补集为 $S_i$ ，另一天的集合为 $D_j$ ，补集为 $S_j$ ，且 $S_i$ 严格等于 $D_j$ 。假设题设成立，那么有：$$LCM(D_i) > LCM(S_i) = LCM(D_j) > LCM(S_j) = LCM(D_i)$$显然矛盾，所以不成立。考虑另一个问题，假设 $A$ 是 $B$ 的子集，那么一定存在 $LCM(B) \ge LCM(A)$ 而且 $LCM(B) \mod LCM(A) = 0$ ，假设 $D_i$ 和 $D_j$ 的交集为空，那么 $D_j$ 一定为 $S_i$ 的真子集，同理，$D_i$ 也是 $S_j$ 的真子集，那么：$$LCM(D_i) > LCM(S_i) \ge LCM(D_j) > LCM(S_j) \ge LCM(D_i)$$显然也矛盾，即：任意两天所拿的石头都必须有交集 (1)。2019年5月22日补充虽然不满足条件 (1) 一定不能赢，但满足条件 (1) 就一定可以赢吗？答案是不一定。但我们可以通过合理的构造来使得当满足条件 (1) 时是一定全胜的。如何构造出来一组解呢？根据结论 (1) ，一个显然的想法就是将权值全都集中在有交集的那部分石头上，剩下的全为 $1$ ，这样一来我方取到的石头的 LCM 一定是严格大于对面的。更详细一些，我们取出 $m$ 个互不相同的素数 ${p_1, p_2, \dots, p_{m - 1}, p_m}$ ，令 $n$ 个石头的权值为 ${a_1, a_2, a_3, \dots, a_{n - 1}, a_n}$ ，初始时 $a_i$ 均为 $1$ 。假设我们在第 $j$ 天访问了 $a_i$ ，那么我们就令 $a_i = a_i \cdot p_j$ ，这样一来 $p_j$ 就是 $a_i$ 的一个因子。下面来证明这样分配一定是必胜的。我们知道在第 $i$ 天，我们访问了一个在第 $j$ 天访问过的石头，而且这个石头的权值一定是 $p_j$ 的倍数。所以对于每一天 $i$ ，$LCM(D_i) = p_1p_2\dots p_m$ 。另一方面，$S_i$ 并不包含 $p_i$ 这个因子，因为 $p_i$ 都在 $D_i$ 里，所以 $LCM(S_i)$ 严格小于 $LCM(D_i)$ 。$m$ 的范围只有 $50$ ，所以直接 $O(nm^2)$ 暴力判断一下即可。代码https://pasteme.cn/8174#include <bits/stdc++.h> const int maxm = 57, maxn = int(1e4) + 7; int m, n; bool vis[maxm][maxn]; int main() { scanf("%d%d", &m, &n); for (int i = 1, cnt, buf; i <= m; i++) { scanf("%d", &cnt); while (cnt--) scanf("%d", &buf), vis[i][buf] = true; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { bool flag = false; for (int k = 1; k <= n && !flag; k++) { if (vis[i][k] && vis[j][k]) flag = true; } if (!flag) return 0 * puts("impossible"); } } puts("possible"); return 0; }
Codeforces - 1166D - Cute Sequences地址http://codeforces.com/contest/1166/problem/D原文地址https://www.lucien.ink/archives/433题目Given a positive integer $m$, we say that a sequence $x_1, x_2, \dots, x_n$ of positive integers is $m$-cute if for every index $i$ such that $2 \le i \le n$ it holds that $x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i$ for some positive integer $r_i$ satisfying $1 \le r_i \le m$.You will be given $q$ queries consisting of three positive integers $a$, $b$ and $m$. For each query you must determine whether or not there exists an $m$-cute sequence whose first term is $a$ and whose last term is $b$. If such a sequence exists, you must additionally find an example of it.题意定义 $x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i$ ，$1 \le r_i \le m$ ，给你 a b m ，判断是否存在一个一个序列 $x$ ，假定这个序列的长度为 $n$ ，使得 $x_1 = a$ 且 $x_n = b$ 。题解规定 $2 ^ {x} = 0$ $(x < 0)$ ，归纳一下，可以发现：$$x_{n(n \ge 2)} = 2 ^ {n - 2}a + 2 ^ {n - 3} r_2 + 2 ^ {n - 4} r_3 + \dots + 2r_{n - 2} + r_{n - 1} + r_n\ \tag{a}$$即判断是否存在一个 $x_n$ 满足 $(a)$ 式且 $x_n = b$ 。可以进一步简写一下，如果将 $b$ 代入 $(a)$ 式，且令：$$r = 2 ^ {n - 3} r_2 + 2 ^ {n - 4} r_3 + \dots + 2r_{n - 2} + r_{n - 1} + r_n \tag{b}$$ 则有：$$b = 2 ^ {n - 2}a + r$$ 可以发现忽略 $(b)$ 式中的 $r_n$ 之后，剩下的式子为 $r$ 为一个二进制表示，我们可以将 $(b)$ 整体减去一个 $k$ 从而消掉 $r_n$ ，这样一来可以表示为 $x_n = 2 ^ {n - 2}(a + k) + r$ ，令 $r$ 的二进制表示为 $d_{n - 3}d_{n - 4} \dots d_0$ ，此时 $r_{i(i < n)} = k + d_{n - i - 1}$ ，$r_n = k$ 。然后暴力输出 $x$ 序列即可。代码https://pasteme.cn/8173#include <bits/stdc++.h> const int maxn = 54; typedef long long ll; ll __pow[maxn] = {1}, r[maxn], a, b, m; int solve() { if (a == b) return 1; for (int n = 2; __pow[n - 2] <= b; n++) { ll div = b / __pow[n - 2], mod = b % __pow[n - 2]; if (div > a && (div - a < m || (mod == 0 && div - a <= m)) && __pow[n - 2] - 1 >= mod) { for (int i = 2, bit = n - 3; bit >= 0; i++, bit--) r[i] = (mod >> bit & 1) + div - a; return n; } } return -1; } ll calc(int x, int n) { if (x > 1 && x < n) { ll ret = __pow[x - 2] * a; for (int i = 2; i < x; i++) ret = ret + __pow[x - i - 1] * r[i]; return ret + r[x]; } else return x == 1 ? a : b; } int main() { int q, n; for (int i = 1; i < maxn; i++) __pow[i] = __pow[i - 1] << 1; for (scanf("%d", &q); q; q--) { scanf("%lld%lld%lld", &a, &b, &m); if (~(n = solve())) { printf("%d ", n); for (int i = 1; i <= n; i++) printf("%lld%c", calc(i, n), i == n ? '\n' : ' '); } else puts("-1"); } return 0; }
题目链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=6022原文地址https://www.lucien.ink/archives/427/题意一维坐标轴上有 $n$ 条线段，你可以在每个线段的整点上放任意多个标记，但是任意两个标记不能重合，问最多有多少条线段可以拥有标记。题解思路最原始的想法是二分图，但看了眼范围放弃了，考虑贪心。简单的贪心想法就是按照左右端点的升序进行二级排序，然后贪心地依次靠左放点，这种思路显然不对，提供一组 hack：1 3 1 2 2 2 1 3还有一种想法是按照长度升序和左端点升序进行二级排序，然后扫一遍，每次给当前线段分配一个坐标最小的标记，这种思路也是错的，提供一组 hack：1 4 1 3 1 3 1 3 3 4仔细思考一下，对于一个标记 $x$ ，如果一个线段集合 $s$ 中的所有线段都可以被这个标记所覆盖，可以被发现其实是要优先将 $x$ 分配给 $s$ 中右端点最小的线段，可以证明这样一定是最优的，证明过程待系统地学习一下贪心之后再补上吧。代码https://pasteme.cn/7981#include <bits/stdc++.h> const int maxn = int(1e5) + 7; struct Seg { int l, r; bool operator < (const Seg &tmp) const { return r > tmp.r; } } seg[maxn]; int t, n; int main() { for (scanf("%d", &t); t; t--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &seg[i].l, &seg[i].r); std::sort(seg, seg + n, [](Seg x, Seg y){ return x.l < y.l; }); std::priority_queue<Seg> que; int cur = seg[0].l, ans = 0; seg[n].l = 1000000001; for (int i = 0; i <= n; i++) { if (seg[i].l != cur) { while (!que.empty() && cur < seg[i].l) { if (cur <= que.top().r) cur++, ans++; que.pop(); } cur = seg[i].l; } que.push(seg[i]); } printf("%d\n", ans); } return 0; }
Codeforces - 1152B - Neko Performs Cat Furrier Transform
地址https://codeforces.com/contest/1152/problem/B原文地址https://www.lucien.ink/archives/422/题意给你一个 $x$ ，让你在 $40$ 步之内把它变成 $2 ^ n - 1$ 的形式，你一定会在奇数步将其异或上一个值 $2 ^ k - 1$ ，在偶数步将其自增 $1$ ，让你输出你需要花多少步，以及每次奇数步时的 $k$ 值。题解观察可得，每次将最高位的 $0$ 置为 $1$ 之后一定是最优的。代码https://pasteme.cn/6826#include <bits/stdc++.h> int x, ans[107], len; bool check(int x) { x++; return (x & -x) == x; } int main() { scanf("%d", &x); int h = 28, step = 0; while (!(x >> h)) h--; while (!check(x)) { step++; if (step & 1) { for (int i = h; i >= 0; i--) { if (!((x >> i) & 1)) { x ^= ((1 << (i + 1)) - 1); ans[++len] = i + 1; break; } } } else x++; } printf("%d\n", step); for (int i = 1; i <= len; i++) printf("%d%c", ans[i], i == len ? '\n' : ' '); return 0; }
地址https://codeforces.com/contest/1152/problem/A原文地址https://www.lucien.ink/archives/421/题意有 $n$ 把锁 $m$ 把钥匙，如果锁 $A$ 和钥匙 $B$ 的权值加起来是一个奇数，那么 $A$ 和 $B$ 就可以配对，问最多能配多少对。代码https://pasteme.cn/6825#include <bits/stdc++.h> int lock[2], key[2], n, m; int main() { scanf("%d%d", &n, &m); for (int i = 1, buf; i <= n; i++) { scanf("%d", &buf); lock[buf & 1]++; } for (int i = 1, buf; i <= m; i++) { scanf("%d", &buf); key[buf & 1]++; } printf("%d\n", std::min(lock[0], key[1]) + std::min(lock[1], key[0])); return 0; }
Codeforces - 1155C - Alarm Clocks Everywhere
地址https://codeforces.com/contest/1155/problem/C原文地址https://www.lucien.ink/archives/419/题意你有 $n$ 个事件，第 $i$ 个事件需要在第 $x_i$ 时刻去做，你是一个机器人，你只能选定任意一个起始时间 $y$ ，然后从给定的 $m$ 个数字中选出一个 $p_i$ ，然后你从第 $y$ 时刻起，每隔 $p_i$ 个时刻有做事的权利（包括第 $y$ 个时刻），问能否做完掉所有的事，能的话输出 y i。题解起始时间肯定是第一个时间发生的时刻，然后对所有事件的间隔求一下 $gcd$ ，判断一下是否存在一个 $p_i$ 满足 $gcd \mod\ p_i = 0$ 即可。代码https://pasteme.cn/6689#include <bits/stdc++.h> typedef long long ll; const int maxn = int(3e5) + 7; ll gcd(ll p, ll q) { return q ? gcd(q, p % q) : p; } int n, m; ll x[maxn], p[maxn]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%lld", x + i); for (int i = 1; i <= m; i++) scanf("%lld", p + i); ll d = 0; for (int i = 2; i <= n; i++) d = gcd(d, x[i] - x[i - 1]); for (int i = 1; i <= m; i++) { if (d % p[i] == 0) { return 0 * printf("YES\n%lld %d\n", x[1], i); } } return 0 * puts("NO"); }
Codeforces - 1155B - Game with Telephone Numbers
地址https://codeforces.com/contest/1155/problem/B原文地址https://www.lucien.ink/archives/418/题意如果一个纯数字的串长度为 $11$ 且以数字 $8$ 开头，那么这个串就是一个好串，给你一个纯数字的串 $s$ ，你和另一个人轮流从中任意删掉一个数字，你先手，直到这个串的长度变为 $11$ ，如果最后的串是一个好串，那么你赢，问能否必胜。题解首先必败和必胜态和两人的取数顺序无关，只和次数和串本身有关。对方每次肯定尽可能地拿走最靠左的 $8$ ，那么看一下对方用完所有的操作之后我方能否将其变为一个好串即可。代码https://pasteme.cn/6688#include <bits/stdc++.h> const int maxn = int(1e5) + 7; int n, cnt; char str[maxn], buf[maxn]; bool judge() { int len = 0; int b = (n - 11) / 2, a = n - 11 - b; for (int i = 0; i < n; i++) { if (str[i] == '8' && b > 0) b--; else buf[len++] = str[i]; } for (int i = 0; i <= a; i++) { if (buf[i] == '8') return true; } return false; } int main() { scanf("%d%s", &n, str); puts(judge() ? "YES" : "NO"); return 0; }
Codeforces - 1155A - Reverse a Substring
地址https://codeforces.com/contest/1155/problem/A原文地址https://www.lucien.ink/archives/417/题意给你一个串 $s$ ，问能否翻转一个区间使得它的字典序变小。题解先 sort 一下判断是否可以，可以的话枚举一下。代码https://pasteme.cn/6687#include <bits/stdc++.h> const int maxn = int(3e5) + 7; char str[maxn], buf[maxn]; int n; int main() { scanf("%d%s", &n, str); strcpy(buf, str); std::sort(buf, buf + n); if (strcmp(str, buf) == 0) return 0 * puts("NO"); puts("YES"); for (int i = 0; i < n; i++) { if (str[i] > buf[i]) { for (int j = n - 1; j > i; j--) { if (str[j] == buf[i]) { return 0 * printf("%d %d\n", i + 1, j + 1); } } } } return 0; }
Codeforces - 1153C - Serval and Parenthesis Sequence
地址https://codeforces.com/contest/1153/problem/C原文地址https://www.lucien.ink/archives/415代码https://pasteme.cn/6250#include <bits/stdc++.h> const int maxn = int(1e6) + 7; int len, left, right; char str[maxn]; bool check() { std::stack<char> stack; if (len % 2 != 0) return false; left = right = len / 2; for (int i = 1; i <= len; i++) { if (str[i] == '(') left--; } for (int i = 1; i <= len; i++) { if (str[i] == '?') { if (left > 0) { str[i] = '('; left--; } else { str[i] = ')'; right--; } } else { if (str[i] == ')') right--; } } if (left != 0 || right != 0) return false; for (int i = 1; i <= len; i++) { if (str[i] == '(') stack.push('('); else { if (stack.empty()) return false; if (stack.top() == '(') stack.pop(); } if (i != len && stack.empty()) return false; } return stack.empty(); } int main() { scanf("%d%s", &len, str + 1); if (check()) puts(str + 1); else puts(":("); return 0; }
Codeforces - 1153B - Serval and Toy Bricks
地址https://codeforces.com/contest/1153/problem/B原文地址https://www.lucien.ink/archives/414代码https://pasteme.cn/6248#include <bits/stdc++.h> const int maxn = 1007; int N, M, H, m[maxn], n[maxn], h[maxn][maxn], ans[maxn][maxn]; int main() { scanf("%d%d%d", &N, &M, &H); for (int i = 1; i <= M; i++) scanf("%d", m + i); for (int i = 1; i <= N; i++) scanf("%d", n + i); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { scanf("%d", h[i] + j); } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (h[i][j]) ans[i][j] = std::min(n[i], m[j]); else ans[i][j] = 0; } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { printf("%d%c", ans[i][j], j == M ? '\n' : ' '); } } return 0; }