Codeforces Round 884 (Div. 1 + Div. 2)
题目链接：Codeforces Round 884 (Div. 1 + Div. 2)
A. Subtraction Game
题意
给\(a\)和\(b\)两个数，两个玩家每次可以选择在总数里面减去其中一个数，需要给出一种后手必胜的总数\(n\)。
思路
\(a+b\)就能保证后手必胜。
代码
#include <bits/stdc++.h>
using namespace std;
void sol() {
int x, y;
cin >> x >> y;
cout << x + y << endl;
}
int main() {
int _;
cin >> _;
while (_--) sol();
return 0;
}
B. Permutations & Primes
题意
定义一个序列的\(MEX\)为这个序列中没有出现的第一个质数，让求能让所有连续子序列的\(MEX\)的和最大的那个排列。
思路
首先，\(1\)肯定在最中间的位置，因为需要尽可能多的子序列都包含他。由于2和3都是质数，所以两边各一个就行，这样只有\([1,n]\)的区间才会同时包含\(2和3\)，这就意味着，除了这三个数，其他数的排列顺序不会影响结果。
代码
#include <bits/stdc++.h>
using namespace std;
void sol() {
int n;
cin >> n;
if (n >= 2) cout << 2;
for (int i = 4; i <= n / 2 + 2; ++i) cout << ' ' << i;
cout << (n > 1 ? " 1" : "1");
for (int i = n / 2 + 3; i <= n; ++i) cout << ' ' << i;
if (n >= 3) cout << ' ' << 3;
cout << endl;
}
int main() {
int _;
cin >> _;
while (_--) sol();
return 0;
}
C. Particles
题意
给出\(n\)个数，每次可以删除一个数，然后相邻的两个数会求和合并成一个数，删除两端的数时，不会有合并操作，问最后合成一个数后最大的结果。
思路
首先，很容易注意到一件事，奇数下标的数只能跟奇数下标的数和到一块，偶数也一样，这意味着我们可以把原数组按下标的奇偶性分成两个数组考虑。又由于下标奇偶性相同的两个数总能够通过若干次操作合到一块，所以实际上就是让求两个数组中所有正数的和，大的那个就是结果。如果两个数组中都没正数，说明最大的那个负数就是结果。
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1e5 + 5, maxnn = 1e9 + 7;
int a[maxn], b[maxn];
void sol() {
int n, g1 = 0, g2 = 0;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> (i & 1 ? a[++g1] : b[++g2]);
int ma = -maxnn;
LL sum1 = 0, sum2 = 0, ans = -maxnn;
for (int i = 1; i <= g1; ++i) {
if (a[i] > 0) sum1 += a[i], ans = max(ans, sum1);
ma = max(ma, a[i]);
}
for (int i = 1; i <= g2; ++i) {
if (b[i] > 0) sum2 += b[i], ans = max(ans, sum2);
ma = max(ma, b[i]);
}
if (ma <= 0)
cout << ma << endl;
else
cout << ans << endl;
}
int main() {
int _;
cin >> _;
while (_--) sol();
return 0;
}
D. Row Major
题意
给一个\(n\)，要求构造一个字符串，使得对于任何满足式子\(n=a×b\)的\(a和b\)，按“行优先”规则写成\(a×b\)的形式后，任意相邻的两个字符不能相同，问最少需要的字符种类数\(x\)。
思路
考虑到一个事实：对于任意的\(a×b\)矩阵，只要\(x\)不整除\(a或b\)，那么就有一定的排列方式使得相邻的字符都互不相同。我们在这里可以缩紧条件，让\(x\)必须整除\(a\)，这样问题就转化为了：对于所有\(n\)的因子\(y_i\)，需要求最小的\(x\)，使得\(x\)不整除任何一个\(y_i\)，也就是求最小的不整除\(n\)的\(x\)。又由于\(26!\)远远大于\(1e6\)，所以对于所有的\(n\)，\(x\)肯定是小于等于\(26\)的（其实从小写字母一共就\(26\)个也能看出来...）。
代码
#include <bits/stdc++.h>
using namespace std;
void sol() {
int n, ans;
cin >> n;
ans = n;
for (int i = 1; i <= 26; ++i) {
if (n % i != 0) {
ans = i;
break;
}
}
for (int i = 1; i <= n; ++i) cout << (char)('a' + (i - 1) % ans);
cout << endl;
}
int main() {
int _;
cin >> _;
while (_--) sol();
return 0;
}
E. Great Grids
题意
对于一个只含有三种字符的矩阵，如果他的每个\(2×2\)的小矩阵都存在三种不同的字符且相邻的字符不相同，那么就称其为\(great\)。给出\(k\)个限制，每个限制都是两个点的坐标，意味着这两个点的字符相同，且满足
\((x_{i,2},y_{i,2})=(x_{i,1}+1,y_{i,1}+1)或者(x_{i,2},y_{i,2})=(x_{i,1}+1,y_{i,1}−1)\)。问是否存在\(n×m\)的\(great\)矩阵满足上述条件。
思路
对于\(great\)矩阵的每个\(2×2\)的小矩阵，例如：
AB BA
CA AC
可以发现以下事实：
\(a[i+1][j]-a[i][j]=a[i+1][j+1]-a[i][j+1]\)以及\(a[i][j+1]-a[i][j]=a[i+1][j+1]-a[i+1][j]\)。并且\(a[i+1][j]-a[i][j]\)和\(a[i][j+1]-a[i][j]\)的值在模\(3\)的意义下，只能为\(1或者2\)。
所以对\(n×m\)的矩阵可以把前\(n-1\)个行和前\(m-1个列\)，看作\(n+m-2\)个点，又由于题目上的每一个限制，是对一个行和一个列对应的值相同或不同的限制，那么每个限制实际上是对两个点是否在同一个集合进行的限制。这样，这个题就转化为了一个二分图判定的题，这里可以使用并查集来快速判定。
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 2e3 + 5;
int r[maxn][2], c[maxn][2], f[4 * maxn];
int find(int x) {
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
void merge(int x, int y) { f[find(x)] = find(y); }
void sol() {
int n, m, k;
cin >> n >> m >> k;
int tmp = 0;
for (int i = 1; i <= n; ++i) r[i][0] = tmp++, r[i][1] = tmp++;
for (int i = 1; i <= m; ++i) c[i][0] = tmp++, c[i][1] = tmp++;
for (int i = 0; i < tmp; ++i) f[i] = i;
for (int i = 1; i <= k; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (y1 > y2) {
merge(r[x1][0], c[y2][0]);
merge(r[x1][1], c[y2][1]);
} else {
merge(r[x1][0], c[y1][1]);
merge(r[x1][1], c[y1][0]);
}
}
for (int i = 0; i < tmp; ++i)
if (find(i) == find(i ^ 1)) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
}
int main() {
int _;
cin >> _;
while (_--) sol();
return 0;
}