https://codeforces.com/contest/1294/problem/A
简要题意
\(\bullet\) 给出 \(a, b, c, n\), 判断是否存在 \(A, B, C\) 满足 \((A + B + C = n\) 且 \(a + A = b + B = c + C)\) .
\(\bullet\) 多组数据,\(1 \leq t \leq 10 ^ 4\),\(1 \leq a, b, c, n \leq 10 ^ 8\) 且 \((a, b, c, n)\) 均为正整数,\((A, B, C)\) 均为非负整数.
做法
- \(\because\) \(a + A = b + B = c +C\)
- \(\therefore\) \(a + A + b + B + c + C = 3 \cdot (a + A) = 3 \cdot (b + B) = 3 \cdot (c + C)\)
又 \(\because A + B + C == n\)
- \(\therefore a + A + b + B + c + C = a + b + c + n\)
- \(\therefore a + b + c + n = 3 \cdot (a + A) = 3 \cdot (b + B) = 3 \cdot (c + C)\)
即 \(\frac{a + b + c+ n}{3} = a + A = b + B = c + C\)
\(\because (A, B, C )\) 均为非负整数
- $\therefore $ \(A, B, C \geq 0\)
- \[\therefore \left\{
- \begin{
- aligned
- } \frac{
- a + b + c + n
- }{
- 3
- } - a \geq 0 \\frac{
- a + b + c + n
- }{
- 3
- } - b \geq 0 \\frac{
- a + b + c + n
- }{
- 3
- } - c \geq 0 \end{
- aligned
- } \right.\]
- \[\therefore 1 \left\{
- \begin{
- aligned
- } \frac{
- a + b + c + n
- }{
- 3
- } \geq a \\frac{
- a + b + c + n
- }{
- 3
- } \geq b \\frac{
- a + b + c + n
- }{
- 3
- } \geq c \end{
- aligned
- } \right.\]
故我们只需判断 \((a + b + c + n) \equiv 0 \mod 3\) 且 满足 1 .
- \(Code:\)
- #include <bits/stdc++.h>
- using namespace std;
- inline int read() {
- int cnt = 0, opt = 1;
- char ch = getchar();
- for (; ! isalnum(ch); ch = getchar())
- if (ch == '-') opt = 0;
- for (; isalnum(ch); ch = getchar())
- cnt = cnt * 10 + ch - 48;
- return opt ? cnt : -cnt;
- }
- int T;
- int main() {
- T = read();
- while (T --) {
- int a, b, c, n;
- a = read(), b = read(), c = read(), n = read();
- int sum = a + b + c + n;
- if (sum % 3 != 0) {
- puts("NO");
- continue;
- }
- sum /= 3;
- if (a> sum || b> sum || c> sum)
- puts("NO");
- else puts("YES");
- }
- }
- https://codeforces.com/contest/1294/problem/B
简要题意
\(\bullet\) 给出 \(n\) 与 \(n\) 个特殊点的坐标 \((x_i, y_i)\) .
\(\bullet\) 从 \((0, 0)\) 出发, 只能向上'U'和向右'R'移动, 求最优路径, 或告知无解.
\(\bullet\) 多组数据,\(1 \leq t \leq 100\),\(1 \leq n \leq 1000\),\(0 \leq x_i, y_i \leq 1000\).
做法
傻逼模拟
显然,\((0, 0)\) 经过每个点的最优路径, 一定是从坐标小的点往坐标大的点移动, 故我们把 \((x_i, y_i)\) 按照 \(x_i\) 为第一关键字, \(y_i\) 为第二次关键字, 按从小到大排序时.
若存在 \(y_i> y_{i + 1}\), 那么必然无解.
我们再考虑路径, 显然, 从 \((x_1, y_1)\) -> \((x_2, y_2)\) , 路径必然可以为: 先向右走 \(x_2 - x_1\) 步, 再向上走 \(y_2 - y_1\) 步.
故, 对于每 \(2\) 个坐标 \((x_i, y_i)\) -> \((x_{i + 1}, y_{i + 1})\) 我们只需要输出 \(x_{i + 1} - x_{i}\) 个 R,\(y_{i + 1} - y_{i}\) 个 U .
- #include <bits/stdc++.h>
- const int MaxN = 1000 + 10;
- using namespace std;
- inline int read() {
- int cnt = 0, opt = 1;
- char ch = getchar();
- for (; ! isalnum(ch); ch = getchar())
- if (ch == '-') opt = 0;
- for (; isalnum(ch); ch = getchar())
- cnt = cnt * 10 + ch - 48;
- return opt ? cnt : -cnt;
- }
- int T;
- struct point {
- int a, b;
- } edge[MaxN];
- inline int cmp(point x, point y) {
- return x.a == y.a ? x.b <y.b : x.a < y.a;
- }
- int main() {
- T = read();
- while (T --) {
- int n, opt = 1;
- n = read();
- for (int i = 1; i <= n; ++ i)
- edge[i].a = read(), edge[i].b = read();
- sort(edge + 1, edge + 1 + n, cmp);
- for (int i = 1; i < n; ++ i)
- if (edge[i].b> edge[i + 1].b) {
- puts("NO");
- opt = 0;
- break;
- }
- if (opt == 1)
- puts("YES");
- else continue;
- int x = 0, y = 0;
- for (int i = 1; i <= n; ++ i) {
- for (int j = 1; j <= abs(x - edge[i].a); ++ j)
- printf("R");
- for (int j = 1; j <= abs(y - edge[i].b); ++ j)
- printf("U");
- x = edge[i].a, y = edge[i].b;
- }
- puts("");
- }
- }
- https://codeforces.com/contest/1294/problem/C
简要题意
\(\bullet\) 给出一个 \(n\), 求 \(x, y, z\) 满足 \((x \cdot y \cdot z = n\) 且 \(x, y, z \geq 2\) 且 \(x \not= y \not= z)\), 或者告知无解.
\(\bullet\) 多组数据,\(1 \leq t \leq 100\),\(2 \leq n \leq 10 ^ 9\).
\(\bullet\) 给出 \(n\) 与 \(n\) 个特殊点的坐标 \((x_i, y_i)\) .
\(\bullet\) 从 \((0, 0)\) 出发, 只能向上'U'和向右'R'移动, 问是否可以经过每个特殊点, 可以则输出路径.
做法
考虑把 \(n\) 分解质因数.
设 \(n = \prod\limits_{i = 1}^{m} p_{i} ^ {a_i}\)
分类讨论:
当 \(m \geq 3\) 时, 必存在 \((p_1, p_2, n / p_1 / p_2)\) 符合条件.
当 \(m = 2\) 时, 可能存在 \((p_1, p_2, n / p_1 / p_2)\), 其中 \((n / p_1 / p_2 \geq 2\) 且 \(n / p_1 / p_2 \not= p_1 \not= p_2)\).
考虑到 \(m = 2\),\(n / p_1 / p_2 = p_1 ^ {a_1 - 1} \cdot p_2 ^ {a_2 - 1}\).
显然, 满足条件的只有 \(a_1 - 1 + a_2 - 1\geq 2\), 即 \(a_1 + a_2 \geq 4\) 时满足条件.
当 \(m = 1\) 时, 最小的分法也就是 \((p_1 ^ 1, p_1 ^ 2, p_1 ^ 3)\)
也就是说,\(a_1 \geq 1 + 2 + 3\), 即 \(a_1 \geq 6\) 时满足条件, 满足条件的也就是 \((p_1 ^ 1, p_1 ^ 2, p_1 ^ {a_i - 3})\).
- #include <bits/stdc++.h>
- const int MaxN = 1000000 + 10;
- using namespace std;
- inline int read() {
- int cnt = 0, opt = 1;
- char ch = getchar();
- for (; ! isalnum(ch); ch = getchar())
- if (ch == '-') opt = 0;
- for (; isalnum(ch); ch = getchar())
- cnt = cnt * 10 + ch - 48;
- return opt ? cnt : -cnt;
- }
- int T;
- int t, w[MaxN], c[MaxN];
- inline void solve(int x) {
- for (int i = 2; i <= sqrt(x); ++ i) {
- if (x % i == 0)
- t ++;
- while (x % i == 0) {
- w[t] = i;
- c[t] ++;
- x /= i;
- }
- }
- if (x> 1)
- w[++ t] = x, c[t] = 1;
- }
- inline int POW(int x, int y) {
- int cnt = 1;
- while (y) {
- if (y & 1)
- cnt = cnt * x;
- x = x * x;
- y>>= 1;
- }
- return cnt;
- }
- int main() {
- T = read();
- while (T --) {
- memset(w, 0, sizeof(w));
- memset(c, 0, sizeof(c));
- t = 0;
- int x;
- x = read();
- solve(x);
- if (t>= 3)
- printf("YES\n%d %d %d\n", POW(w[1], c[1]), POW(w[2], c[2]), x / POW(w[1], c[1]) / POW(w[2], c[2]));
- if (t == 2) {
- if (c[1] + c[2] <= 3) puts("NO");
- else printf("YES\n%d %d %d\n", w[1], w[2], x / w[1] / w[2]);
- }
- if (t == 1) {
- if (c[1] <6) puts("NO");
- else printf("YES\n%d %d %d\n", POW(w[1], 1), POW(w[1], 2), x / POW(w[1], 1) / POW(w[1], 2));
- }
- }
- }
- https://codeforces.com/contest/1294/problem/D
简要题意
\(\bullet\) 定义数组中的 \(MEX\) 表示不属于该数组的最小非负整数,\(example:[0, 0, 1, 0, 2]\) 的 \(MEX\) 就是 \(3\).
\(\bullet\) 给出 \(q, x\), 您拥有一个空数组 \(a[](\) 即数组中没有元素 \()\).
\(\bullet\) 您还得到 \(q\) 次询问, 第 \(j\) 个询问由一个整数 \(y_j\) 组成, 意味着数组将多一个元素 \(y_j\), 查询后长度增加 \(1\).
\(\bullet\) 你可以选择任意元素 \(a_i\) 并让 \(a_i += x\) 或 \(a_i -= x\), 且可以操作任意次.
\(\bullet\) 您需要进行以上操作, 并且最大化 \(a\) 数组的 \(MEX\), 并输出.
做法
我们发现答案 \(ans\) 会修改, 一定是存在 \(y_j\) 通过操作后可以变为 \(ans\), 此时, \(ans\) 就要加 \(1\).
我们考虑把 \(ans\) 与 \(y_j\) 都修改为最小值, 即把 \(ans, y_j \mod x\) .
每次把 \(y_j \mod x\) 存入数组.
若存在 \(y_j \equiv ans \mod x\), 则表示 \(y_j\) 通过操作后可以变为 \(ans\), 此时,\(num[ans \mod x] --, ans ++\).
- #include <bits/stdc++.h>
- const int MaxN = 4 * (100000 + 10);
- using namespace std;
- inline int read() {
- int cnt = 0, opt = 1;
- char ch = getchar();
- for (; ! isalnum(ch); ch = getchar())
- if (ch == '-') opt = 0;
- for (; isalnum(ch); ch = getchar())
- cnt = cnt * 10 + ch - 48;
- return opt ? cnt : -cnt;
- }
- int q, x, ans;
- int num[MaxN];
- int main() {
- q = read(), x = read();
- for (int i = 1; i <= q; ++ i) {
- int m = read();
- num[m % x] ++;
- while (num[ans % x]) {
- -- num[ans % x];
- ans ++;
- }
- printf("%d\n", ans);
- }
- }
- https://codeforces.com/contest/1294/problem/E
咕咕咕
https://codeforces.com/contest/1294/problem/F
咕咕咕
[题解][Codeforces] Round_615_Div. 3 简要题解
来源: http://www.bubuko.com/infodetail-3393709.html