【比赛题解】[Codeforces] Round_615_Div. 3 简要题解
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)\)
即 \(\dfrac{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} \dfrac{a + b + c + n}{3} - a \geq 0 \\ \dfrac{a + b + c + n}{3} - b \geq 0 \\ \dfrac{a + b + c + n}{3} - c \geq 0 \end{aligned} \right.\)
\(\therefore ① \left\{ \begin{aligned} \dfrac{a + b + c + n}{3} \geq a \\ \dfrac{a + b + c + n}{3} \geq b \\ \dfrac{a + b + c + n}{3} \geq c \end{aligned} \right.\)
故我们只需判断 \((a + b + c + n) \equiv 0 \mod 3\) 且 满足 ① 。
#include
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");
}
}
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
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("");
}
}
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\)。
做法
考虑把 \(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
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));
}
}
}
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
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);
}
}
E
咕咕咕
F
咕咕咕