A. Divisibility Problem
找到大于等于 $a$ 的最小的一个整数 $x$，使满足 $b \mid x$.
不难发现答案可以由下述公式计算：
$$
\lceil \frac{a}{b} \rceil \cdot b - a = \lfloor \frac{a + b - 1}{b} \rfloor \cdot b - a
$$
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int a, b;
cin >> a >> b;
cout << (a + b - 1) / b * b - a << endl;
}
return 0;
}
B. K-th Beautiful String
当两个 $b$ 分别在 $n - 1, n$ 这两个位置的时候，字典序最小。
当两个 $b$ 分别在 $n - 2, n$ 这两个位置的时候，字典序第二小。
当两个 $b$ 分别在 $n - 2, n - 1$ 这两个位置的时候，字典序第三小。
......
以此类推，不难发现，当第一个 $b$ 位于 $n - i$ 这一位置时，第二个 $b$ 可以在第 $n$ 个位置到第 $n - i + 1$ 个位置中，这 $i$ 种情况的字典序递增；而当两个 $b$ 分别位于第 $n - i, n - i + 1$ 个位置时，这个字符串的字典序是第 $\frac{(1 + i) \cdot i}{2}$ 小的。
因此，我们可以通过二分找到一个最大的一个 $i$，使得 $\frac{(1 + i) \cdot i}{2} < k$ 成立，说明第一个 $b$ 的位置在 $n - i - 1$ 上，此时距离目标的字典序还差 $k - \frac{(1 + i) \cdot i}{2}$ 个，设这个差值为 $d$，则说明第二个 $b$ 只需要放置在第 $ n - d + 1$ 位置上即可。
找到两个 $b$ 的位置之后，只需要输出字符串就能 $AC$ 此题。
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (1ll * (1 + mid) * mid / 2 < k)
l = mid;
else
r = mid - 1;
}
r = k - 1ll * (1 + l) * l / 2;
for (int i = 1; i <= n; i++)
if (i == n - l - 1 || i == n - r + 1)
cout << 'b';
else
cout << 'a';
cout << endl;
}
return 0;
}
C. Ternary XOR
贪心着拆数，$0$ 拆成 $0 + 0$，$2$ 拆成 $1 + 1$，$1$ 拆成 $1 + 0$，这个策略可以一直拆到原字符串第一个 $1$ 的出现，假设这个 $1$ 拆成的 $1$ 填在 $a$ 字符串中，$0$ 填在 $b$ 字符串中，那么这个时候 $a$ 的字典序一定大于 $b$ 的字典序。
因此，在后续的拆数过程中，要使填在 $a$ 上的尽可能小，即：不论后续的原字符串中的字符是什么，$a$ 上只填 $0$，而在 $b$ 上填与原字符串相应的字符。这样就能使两个字符串满足题意，最后输出即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int n;
char str[N], a[N], b[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n >> str + 1;
int bound = 1;
while (bound <= n && str[bound] != '1')
bound++;
for (int i = 1; i < bound; i++)
if (str[i] == '0')
a[i] = b[i] = '0';
else if (str[i] == '1')
a[i] = '1', b[i] = '0';
else
a[i] = b[i] = '1';
if (bound <= n) {
a[bound] = '1';
b[bound] = '0';
while (++bound <= n)
a[bound] = '0', b[bound] = str[bound];
}
for (int i = 1; i <= n; i++)
cout << a[i];
cout << endl;
for (int i = 1; i <= n; i++)
cout << b[i];
cout << endl;
}
return 0;
}
D. Carousel
贪心着填数，首先第一只动物可以画上颜色 $1$，从第二只动物开始枚举，如果当前枚举到的动物与前面一只动物相同，则画上同样的颜色，否则画上颜色 $2$，特殊的是最后一只动物，它的颜色限制不仅关系到第 $n - 1$ 只动物，同时也关系的到第 $1$ 只动物，所以，第 $n$ 只动物的颜色需要 if else 分类讨论。
不难发现，用上述方法填色，如果需要用到颜色 $3$，则颜色 $3$ 必定是被画在第 $n$ 只动物上，同时，还需要满足的条件为：第 $n - 1$ 只动物、第 $n$ 只动物、第 $1$ 只动物的种类都不互相同，且第 $n - 1$ 只动物与第 $1$ 只动物的颜色不同。否则，第 $n$ 只动物就可以改成颜色 $1\ or\ 2$.
这种情况下，能否将第 $n - 1$ 只动物的颜色更改为第 $1$ 只动物的颜色？
如果更改第 $n - 1$ 只动物的颜色，则其前面的一连串动物的颜色都需要更改，那么能否找到一个点，使其更改完颜色之后不影响之前的填色？
显然，按照上述方法填色过程中，相邻的同种动物的颜色填了相同的颜色，而相邻的同种动物的颜色是可以填不同颜色的。
所以，只需要找一个区间 $[l, r], l < r$ 同时这个区间的动物种类相同。那么，在更改了 $r$ 这个位置的动物颜色后，与前面的所有动物的颜色都不会产生影响，而且，其后的直到第 $n - 1$ 只动物的颜色都会产生翻转，即：从颜色 $1$ 变为颜色 $2$，从颜色 $2$ 变为颜色 $1$。此时，第 $n - 1$ 只动物的颜色会与第 $1$ 只动物的颜色相同，那么第 $n$ 只动物的颜色也就不需要 $3$，只需要与其相邻的颜色不同即可。
当然，如果找不到这个区间，则需要 $3$ 种颜色涂色。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
int t[N], c[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> t[i];
int color = 1;
c[1] = 1;
for (int i = 2; i < n; i++)
if (t[i] == t[i - 1])
c[i] = c[i - 1];
else {
c[i] = 3 - c[i - 1];
color = max(color, c[i]);
}
if (t[n] == t[n - 1] && t[n] == t[1])
c[n] = 1;
else if (t[n] == t[n - 1])
if (c[n - 1] == c[1]) {
c[n] = 3 - c[1];
color = max(color, c[n]);
} else
c[n] = c[n - 1];
else if (t[n] == t[1])
if (c[n - 1] == c[1]) {
c[n] = 3 - c[1];
color = max(color, c[n]);
} else
c[n] = c[1];
else {
if (c[n - 1] == c[1]) {
c[n] = 3 - c[1];
color = max(color, c[n]);
} else {
c[n] = 3;
color = 3;
}
}
if (color == 3) {
int st = -1;
for (int i = 1; i < n; i++)
if (t[i] == t[i + 1]) {
st = i;
break;
}
if (st != -1) {
color = 2;
int ed = st;
while (t[st] == t[ed])
ed++;
ed--;
while (ed < n) {
c[ed] = 3 - c[ed];
ed++;
}
c[n] = 3 - c[1];
}
}
cout << color << endl;
for (int i = 1; i <= n; i++)
cout << c[i] << ' ';
cout << endl;
}
return 0;
}
E. Tree Queries
根节点一定会选择，因此，第二层的节点一定会满足题意要求。
我们直接讨论层数大于二的情况，假设给出的 $k$ 个数中在第 $p(p > 2)$ 层的数有 $c$ 个，则这 $c$ 个数必须拥有同一个父亲节点，否则一定不会满足题意限制（还是比较容易说明这一点的吧，可以自行画个图看看~
即：该公共的父亲节点必须作为最终的路径中的节点。
通过上述操作我们可以得到若干个节点，这些结点必须都在最终路径上，剩下的问题就是如何快速判断这一点。
不难发现，如果两个点都在以根节点为起点的一条链上的话，那么这两个点的 $LCA$ 就是这两个点中深度较浅的那个点，而题中所给出的 $k$ 的总和不超过 $2 \cdot 10^5$，那么就说明这个 $LCA$ 的查询过程顶多也就 $2 \cdot 10^5$ 次，而一次查询的时间复杂度为 $log$，因此，这题可以用 $LCA$ 来做。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 4e5 + 5;
int n, m, path[N];
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][18];
void add(int u, int v)
{
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
bool mycmp(int a, int b)
{
return depth[a] < depth[b];
}
void bfs()
{
queue<int> q;
q.push(1);
depth[1] = 1;
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (depth[j])
continue;
q.push(j);
depth[j] = depth[t] + 1;
fa[j][0] = t;
for (int i = 1; i < 18; i++)
fa[j][i] = fa[fa[j][i - 1]][i - 1];
}
}
return;
}
int LCA(int a, int b)
{
if (depth[a] < depth[b])
swap(a, b);
for (int i = 17; ~i; i--)
if (depth[fa[a][i]] >= depth[b])
a = fa[a][i];
if (a == b)
return a;
for (int i = 17; ~i; i--)
if (fa[a][i] != fa[b][i]) {
a = fa[a][i];
b = fa[b][i];
}
return fa[a][0];
}
int main()
{
scanf("%d %d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
add(u, v);
add(v, u);
}
bfs();
while (m--) {
int k;
scanf("%d", &k);
for (int i = 1; i <= k; i++)
scanf("%d", path + i);
sort(path + 1, path + k + 1, mycmp);
int st = 1;
while (st <= k && depth[path[st]] <= 2)
st++;
if (st > k) {
printf("YES\n");
continue;
}
bool success = true;
vector<int> points;
do {
points.push_back(fa[path[st]][0]);
int ed = st;
while (ed <= k && depth[path[st]] == depth[path[ed]])
ed++;
for (int i = st; i < ed; i++)
if (fa[path[i]][0] != fa[path[st]][0]) {
success = false;
break;
}
st = ed;
} while (st <= k && success);
if (success)
for (int i = 0; i < points.size() - 1; i++)
if (LCA(points[i], points[i + 1]) != points[i]) {
success = false;
break;
}
printf("%s\n", success ? "YES" : "NO");
}
return 0;
}
F. Make k Equal
我们先来考虑最终使满足至少 $k$ 个数相等的数有没有可能是原数组中不存在的数。
首先，如果最终的这个数小于最小值的话，显然不如选择最小值的更改次数少；如果最终的这个数大于最大值的话，同理，也不如选择最大值的更改次数少；那么，如果原数组中存在两个数 $x, y(x < y)$，最终的这个数是否有可能是 $z(x < z < y\ \wedge\ z \notin 原数组)? $
假设 $x$ 与 $z$ 相差了 $a$，从小于 $z$ 的数变成 $z$ 的个数有 $c_1$ 个；$z$ 与 $y$ 相差了 $b$，从大于 $z$ 的数变成 $z$ 的个数有 $c_2$ 个，分情况讨论一下：
- 将最终的数更改为 $y$，那么操作数就会变化 $c_1 \cdot b - c_2 \cdot b$，若 $c_1 - c_2 = 0$，则操作数量不变，而当 $c_1 - c_2 < 0$ 时，操作数量就会减少。
- 将最终的数更改为 $x$，那么操作数就会变化 $c_2 \cdot a - c_1 \cdot a$，若 $c_2 - c_1 = 0$，则操作数量不变，而当 $c_2 - c_1 < 0$ 时，操作数量就会减少。
可以发现，无论 $c_1, c_2$ 的大小关系如何，我们都可以选择将 $z$ 更改为 $x$ 或 $y$，而且答案数量不会变差，甚至更优。
因此，我们就可以确定，这题需要计算的答案为：根据题意变化数组，使数组中本就存在的某个数的个数至少为 $k$ 个的最小操作次数。
那么如何计算这个数量？
由于操作次数跟数组中数的排列并没有关系，所以可以先排个序。
在此基础上，如果确定了目标数 $z$，那么，通过预处理一遍前缀和，就可以快速计算出所有比 $z$ 小的数操作成 $z - 1$ 时所需要的操作次数，同理，也可以快速计算出所有比 $z$ 大的数操作成 $z + 1$ 时所需要的操作次数。
此时，就可以用个简单的 if else 来计算，先从左边转移成 $z$ 还是先从右边转移成 $z$，计算出将 $z$ 的个数变为 $k$ 个之后次数，再跟全局最优解取个最小值。
由于目标数 $z$ 只可能是原数组中存在的数，所以只需要 $O(n)$ 枚举一遍哪个数作为目标数，再利用前缀和直接计算出操作数量，当然，如果原数组中某个数的个数已经超过了 $k$ 个，那么直接输出 $0$ 即可。
有一说一，这题纯贪心，感觉比 $E$ 好想好写很多，为啥过的人数却比 $E$ 少，还成为了最后一题
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
int n, k;
int nums[N];
LL sum[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> nums[i];
sort(nums + 1, nums + n + 1);
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + nums[i];
LL res = 1e18;
for (int l = 1; l <= n;) {
int r = l;
while (r <= n && nums[l] == nums[r])
r++;
if (r - l >= k) {
res = 0;
break;
}
LL L = 1ll * (nums[l] - 1) * (l - 1) - sum[l - 1];
LL R = (sum[n] - sum[r - 1]) - 1ll * (nums[l] + 1) * (n - r + 1);
LL cnt;
if (l - 1 >= k - (r - l))
cnt = L + k - (r - l);
else
cnt = L + l - 1 + R + k - (r - l) - (l - 1);
res = min(res, cnt);
if (n - r + 1 >= k - (r - l))
cnt = R + k - (r - l);
else
cnt = R + n - r + 1 + L + k - (r - l) - (n - r + 1);
res = min(res, cnt);
l = r;
}
cout << res << endl;
return 0;
}
