A. Little Artem
先填黑色，再填白色，这样以此一个一个格子填，最后如果总格子数为偶数的话，再将任意一个白格子改成黑色即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
char s[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
bool b = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++, b ^= 1)
if (b || i == 1 && j == 2 && n * m % 2 == 0)
cout << 'B';
else
cout << 'W';
cout << endl;
}
}
return 0;
}
B. Kind Anton
记录一下前缀的 $-1, 0, 1$ 出现的个数，然后从后往前遍历，比较当前的数与目标数的大小，再根据其前缀是否含有相应的 $-1\ or\ 1$ 进行判断。例如：若当前的数小于目标数，则前缀中必须含有至少一个 $1$ 才能完成转变，否则直接输出 $NO$.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
int a[N], b[N];
unordered_map<int, int> cnt;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
cnt.clear();
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
for (int i = 1; i <= n; i++)
cin >> b[i];
bool success = true;
for (int i = n; i; i--) {
cnt[a[i]]--;
if (a[i] == b[i])
continue;
if (a[i] > b[i])
if (cnt[-1])
continue;
else {
success = false;
break;
}
if (cnt[1])
continue;
else {
success = false;
break;
}
}
cout << (success ? "YES" : "NO") << endl;
}
return 0;
}
C. Eugene and an array
如果固定起点，则终点有几种取值？
若当前起点为 $l$，终点即为 $l$ 右侧离 $l$ 最近的 $r$ 使得 $\sum_{i = l}^{r + 1}{a_i} = 0$，那么以 $l$ 为起点的选法就有 $r - l + 1$ 种。
快速求一段区间的和可以用前缀和维护，那么，对于起点 $l$，就是要找一个最近的 $r$，使得 $sum_{l - 1} = sum_{r + 1}$.
如何快速求 $r?$
可以将所有的 $sum$ 将其下标存进 $set$ 中，然后二分查找 $l$ 右侧最近的点，然后将每个点作为起点，累加答案即可。
上述操作光听上去就十分繁琐（其实挺好写的）
那么此题是否有简单的解法呐？
如果我们考虑固定终点找起点，会不会实现起来简单一些？
对于终点 $r$，我们需要找的就是 $r$ 左侧离 $r$ 最近的 $l$，使得 $sum_{l - 1} = sum_r$，那么 $r - l$ 就是以 $r$ 固定为终点的选法数量。（注意边界的取值）
那么，我们就可以在从左到右遍历的时候，实时更新当前前缀和的下标，然后累加答案。
亲测，上文两种方法都能通过这题，只是这题的数据很…（一时间不知道怎么形容，它把 $unordered\_map$ 卡成 $TLE$ 了，导致这场掉了好多好多分~
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
int n, a[N];
LL res, sum[N];
map<LL, int> F;
int main()
{
scanf("%d", &n);
F[0] = 1;
for (int i = 1, p = 0; i <= n; i++) {
scanf("%d", a + i);
sum[i] = sum[i - 1] + a[i];
if (F.count(sum[i]))
p = max(p, F[sum[i]]);
res += i - p;
F[sum[i]] = i + 1;
}
printf("%lld\n", res);
return 0;
}
D. Challenges in school №41
由于转头的数量是小于 $n^2$ 的，所以我们可以在每次转头后，将转头的人记录一下，那么下一秒转头时只需要遍历这些人即可。
每一秒将能转头的人都转一遍，这样就能在最短的时间内使转头游戏达到尽头。
假设该最短时间需要 $t_{min}$ 秒，那么当 $t_{min} > k$ 时必定是无解的。那么是否有个时间的上界？显然，当每一秒只有一对人转头时，可以达到所需时间的最大值，假设该值为 $t_{max}$，那么当 $t_{max} < k$ 时必定无解。
当 $k$ 处于两者之间时，我们可以将每一秒的转头拆分，假设上述的方案中第一秒转了 $a$ 对头，那么我们最多可以用 $a$ 秒来转这 $a$ 对头，且对后续的转头不会造成影响，一直拆到时间足够 $k$ 秒为止。
唯一需要注意的就是，一开始记录的是 $1$ 秒转 $a$ 对头，最多能拆成 $a$ 秒，时间延长只有 $a - 1$（这个细节在第二天睡醒后才想到的，改完一交就过了，ε=(´ο｀*)))唉
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 5, M = 3e6 + 5;
int n, k;
char str[N];
vector<int> a, l, r;
bool vis[N];
vector<int> res[M];
int main()
{
scanf("%d %d %s", &n, &k, str + 1);
for (int i = 1; i <= n; i++)
a.push_back(i);
int t = 0, sum = 0;
do {
t++;
l.clear(), r.clear();
for (auto p : a) {
if (str[p] == 'L' && str[p - 1] == 'R' && !vis[p] && !vis[p - 1]) {
vis[p] = vis[p - 1] = true;
swap(str[p], str[p - 1]);
r.push_back(p);
l.push_back(p - 1);
} else if (str[p] == 'R' && str[p + 1] == 'L' && !vis[p] && !vis[p + 1]) {
vis[p] = vis[p + 1] = true;
swap(str[p], str[p + 1]);
l.push_back(p);
r.push_back(p + 1);
}
}
if (l.empty() && r.empty()) {
t--;
break;
}
a.clear();
res[t].push_back(l.size());
sum += l.size();
for (auto p : l) {
vis[p] = false;
a.push_back(p);
res[t].push_back(p);
}
for (auto p : r) {
vis[p] = false;
a.push_back(p);
}
} while (t <= k);
if (t == k + 1)
cout << -1 << endl;
else {
if (t == k) {
for (int i = 1; i <= k; i++) {
for (auto t : res[i])
printf("%d ", t);
printf("\n");
}
} else {
if (sum < k)
cout << -1 << endl;
else {
int need = k - t;
for (int i = 1; i <= t; i++) {
for (int j = 0; j < res[i].size(); j++) {
if (need) {
if (!j)
continue;
if (j + 1 < res[i].size())
need--;
printf("1 %d\n", res[i][j]);
} else {
if (j) {
printf("%d ", res[i].size() - j);
for (; j < res[i].size(); j++)
printf("%d%c", res[i][j], " \n"[j + 1 == res[i].size()]);
} else {
for (; j < res[i].size(); j++)
printf("%d%c", res[i][j], " \n"[j + 1 == res[i].size()]);
}
}
}
}
}
}
}
return 0;
}
E. Road to 1600
构造题。
不难发现，只需要构造出一个最小的正方形使其满足条件，而当 $n$ 大于这个正方形边长时，只要先在多余位置填上数，最后进入该正方形内即可。
假设已知一个 $4 \times 4$ 正方形满足要求，填法如样例 $2$，而现在需要你构造出一个 $6 \times 6$ 的正方形，按照上述方法应该如何构造？
- 先将左上角的 $4 \times 4$ 空出来
- 在剩余的格子中依次填入数字，且此时这能垂直着走，最终走到第三行或者第二列，即：剩余的格子中最终停留点需要与 $4 \times 4$ 的解法中 $1$ 的位置的行或列坐标相同。
- 进入事先空出来的 $4 \times 4$ 正方形，按照之前发现的解的顺序依次填入数。
按照上述方案构造出的正方形，$rook$ 与 $queen$ 的走法的花费与只走左上角的 $4 \times 4$ 的方格的花费相同，而后者是满足题意的，所以该构造方法也满足题意。
因此，只需要找到最小的满足题意的正方形，就可以用上述方法构造出任意边长的正方形，由于样例给了 $4 \times 4$ 的正解，那么，我们只需要找 $3 \times 3$ 是否存在解即可。（这里留给大家自己构造，或者直接看代码？？可以先告诉大家，最小边长是 $3$）
在找到最小正方形解之后，步骤 $1, 3$ 都好做，那么怎么填 $2$ 中的数？
由于只能走垂直方向，所以，拿起纸笔画一画就能找到一种方案吧，这里也就不再赘述，代码中的填入方案仅供参考，该步骤的填入顺序有很多解，建议自己找一个，当然，最小正方形解可能也不止一个，也可以自己试着找一找。
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, number;
int F[N][N];
int main()
{
cin >> n;
if (n < 3) {
cout << -1 << endl;
return 0;
}
for (int i = 1; i <= 3; i++)
for (int j = 4; j <= n; j++)
F[i][j] = ++number;
for (int i = 4; i <= n; i++)
for (int j = 2; j <= n; j++)
F[i][j] = ++number;
for (int i = 4; i <= n; i++)
F[i][1] = ++number;
F[1][1] = ++number;
F[2][2] = ++number;
F[2][1] = ++number;
F[3][1] = ++number;
F[2][3] = ++number;
F[3][3] = ++number;
F[1][2] = ++number;
F[3][2] = ++number;
F[1][3] = ++number;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cout << F[i][j] << ' ';
cout << endl;
}
return 0;
}
F. Kate and imperfection
如果选出的数中只有质数，那么它们两两之前的最大公约数的最大值就是 $1$，也就是说，如果 $n$ 个数中有 $k$ 个质数，那么，在选出 $\leq k + 1$ 个数时（因为 $1$ 也能选上，同时最大公约数仍然为 $1$），都可以使得答案为 $1$.
那么当选择的数量 $> k + 1$ 时呐？一个直觉上的贪心是在没选的数中从小到大依次选，比如先选了 $4$ 再选择 $6$，那么没多选一个数，答案会变成多少？假设新增的数为 $m$，小于 $m$ 的所有数都存在，大于 $m$ 的只存在质数，那么答案就是小于 $m$ 的最大的约数。
似乎上文并不难实现？写一份代码，提交，$Wrong\ Answer$.
聪明的小朋友不难发现，上述贪心是错误的，其实多往下举几个例子也能发现反例，比如当前新增加 $9$ 这个数，按上述策略答案应该为 $3$，但是其中存在 $4, 8$，使得最大公约数的最大值为 $4$，所以此时应该输出的是 $4$ 而非 $3$.
也就是说，上述贪心思路得到的答案序列并不一定是递增的，也就说明了其中某些选法并不是最优的。
再看一眼通过率，这题虽然是 $F$ 题，但是比 $E$ 题通过人数多得多，那么就大胆猜测一下，上述策略得到的序列，再排个序输出，是否就能过呢？
敢写敢过系列，比赛中其实并不需要证明这个方法是对的，只要过了就是王道
接下来我们来简单证明一下这一点，假设当前选的数为 $m$，小于 $m$ 的最大约数为 $k$，选择后的输出结果为 $res$，我们来分情况看一下：
- $res=k:$ 很完美，继续向下看。
- $res > k:$ 这种情况就说明存在一个正整数 $x$，使得 $k < res < x \cdot res < m$，且这四个数都存在在被选择的集合当中。那么，我们就可以在上一次选择时，将 $res$ 或者 $x \cdot res$ 换成 $m$，就能使得上一次的输出答案变小，也就是说，一旦存在这种情况，那么之前的选择就不是最优，而在交换这两次选择的数之后，正好可以达到我们的期望。
- $res < k:$ 也就是说 $k$ 并不在被选择的数的集合当中，那么，我们就可以在这次选择 $k$ 而不是 $m$，而在选择的数变成 $k$ 之后，又将回到这次讨论的最初，如此循环，由于最终一定会有结果，所以讨论的情况一定会有终止点。
综上，对于每一个数，我们都只需要找到小于它的最大的约数，然后将这些数排个序输出即可。
#include <bits/stdc++.h>
using namespace std;
int solve(int n)
{
int res = 1;
for (int i = 2; i <= n / i; i++)
if (n % i == 0) {
res = n / i;
break;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a;
for (int i = 2; i <= n; i++)
a.push_back(solve(i));
sort(a.begin(), a.end());
for (auto t : a)
cout << t << ' ';
cout << endl;
return 0;
}
