Contestant~. Rank 1733. Rating +45(+295 -250).乱猜结论场，猜不出来坐牢场
A. Subtraction Game
题意
给定两个人之间的博弈：每个人可以选择拿走 \(a\) 或 \(b\) 个石头。
输出后手有必胜策略的石头的总数。
思路
很经典的博弈。
如果先手拿走 \(x\) 个石头后，后手都能拿走 \(n - x\) 个石头，那么后手必胜。
那么，\(n = a + b\)。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 3e5 + 10, mod = 1e9 + 9, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}怎么有人放典题啊
B. Permutations & Primes
题意
给定排列的长度 \(n\)，构造一个排列，满足所有连续子序列中 \(MEX\) 为质数的子序列最多。
\(MEX\) 代表不出现在区间中的最小正数。
思路
首先，我们希望 \(MEX\) 尽量不等于 \(1\)，那么我们就需要将 \(1\) 放在中间。
其次，比 \(1\) 大的两个质数刚好是 \(2, 3\)，也就是说，如果某个区间内包含了 \(1\)，但不包含 \(2\) 或 \(3\)，那么它的 \(MEX\) 就一定是质数。
换句话说，我们希望 \(2, 3\) 尽可能不出现在区间中，因此我们将其放在两个端点。
那么，剩下的位置，任意放置即可，因为只要不包含 \(1\)，就一定不是质数。
基于上述操作的考虑，在赛时可能会出现下面的猜测：
中间放 \(1\)，左边升序放奇数，右边降序放偶数；
中间放 \(1\)，依次在两端放上质数，剩下的填合数；
...
时间复杂度：\(O(n)\)
对应AC代码（猜测1）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 9, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
for(int i=3;i<=n;i+=2) cout << i << ' ';
cout << 1 << ' ';
for(int i=n-n%2;i>=2;i-=2) cout << i << ' ';
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}对应AC代码（正解）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 9, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> ans(n);
ans[0] = 2, ans[n - 1] = 3, ans[n / 2] = 1;
int val = 4;
for(int i=0;i<n;i++){
if(ans[i]) continue;
ans[i] = val ++;
}
for(auto e : ans) cout << e << ' ';
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}如果再胆大一点就不会卡着半小时不交题了（悲
C. Particles
题意
给定一个序列，定义一次操作如下：
选定一个元素；
将其删除；
将其左边和右边的元素合并，值变为两者之和
输出任意操作后，最后剩余的一个数的最大值。
思路
首先，我们不难发现，奇偶性不同的两个元素是不可能加在一起的。
其次，如果奇数位上出现负数，我们将其删除后，左右两者合并之后变为一个元素，那么这个元素变成偶数位上的元素，无法参与奇数位的运算了。
偶数位也是一样。
也就是说，我们只需统计奇数位和偶数位的和，遇到负数的时候，直接忽略即可。
当然，如果全都是负数，我们取负数的最大值。
很巧的是，赛时写了个连续子序列的 \(dp\)，刚好顺手用 \(0\) 和负数取了个最大值，刚好就是正解（小声
时间复杂度：\(O(n)\)
对应AC代码（dp）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 9, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a(n + 2);
for(int i=2;i<=n+1;i++) cin >> a[i];
vector<vector<int>> dp(n + 2, vector<int>(2, -inf));
for(int i=2;i<=n+1;i++){
dp[i][0] = max(dp[i - 2][0], dp[i - 2][1]);
dp[i][1] = max(0ll, dp[i][0]) + a[i];
}
cout << max(max(dp[n][0], dp[n][1]), max(dp[n + 1][0], dp[n + 1][1])) << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}对应AC代码（正解）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 9, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int ans0 = 0, ans1 = 0, mx = -inf;
for(int i=1;i<=n;i++) {
int cur;
cin >> cur;
mx = max(mx, cur);
if(cur < 0) continue;
if(i % 2 == 0) ans0 += cur;
else ans1 += cur;
}
cout << (mx < 0 ? mx : max(ans0, ans1)) << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}真就乱猜
D. Row Major
题意
给定字符串的长度 \(n\)，对于所有 \(a \times b = n\)，将字符串横向依次放入 \(a \times b\) 的矩阵中，输出一个字符串，满足所有矩阵的所有相邻字符都不相同，且字符的种数最小。
如 "tomato"：
\(\mathtt{t\ \ \ \ t\ o\ \ \ \ t\ o\ m\ \ \ \ t\ o\ m\ a\ t\ o}\)
\(\mathtt{o\ \ \ \ m\ a\ \ \ \ a\ t\ o}\)
\(\mathtt{m\ \ \ \ t\ o}\)
\(\mathtt{a}\)
\(\mathtt{t}\)
\(\mathtt{o}\)
思路
很明显，如果循环节是 \(n\) 的因数，我们就不能出现重复。
因而，我们只需枚举所有数，找出第一个不是 \(n\) 的因数的数即可，这个数就可以作为循环节。
这样，即可让字符的种数最小。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 9, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int len = 1;
while(n % len == 0) len ++;
for(int i=1;i<=n;i++) cout << (char) ('a' + ((i - 1) % len));
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}什么诈骗题啊
E. Great Grids
题意
给定一个 \(n \times m\) 的字符矩阵，矩阵满足下面的条件：
字符为 \(A, B, C\) 中的其中一个；
每个 \(2 \times 2\) 连续子矩阵中，必须同时出现 \(A, B, C\)；
相邻两个字符不能相同
现在，给定 \(k\) 个限制，每个限制给定两个坐标 \((x1, y1), (x2, y2)\)，满足两点为 \(2 \times 2\) 连续子矩阵中的对角。
对于每个限制，要求这两点字符相同。
输出是否可以构造出这个矩阵。
思路
我们设 \(A = 0, B = 1, C = 2\)。
观察/证明 1
对于下面的矩阵：
\(\mathtt{x\ \ y}\)
\(\mathtt{y\ \ z}\)
若 \((y - x)\mod 3 = p, (z - y)\mod 3 = q\)，我们进行下面的化简：
\(=> (y - (3 - y - z))\mod 3 = p\)
\(=> (2y + z)\mod 3 = p\)
\(=> ((2y + z) - (z - y))\mod 3 = p - q\)
\(=> (3y) \bmod 3 = p - q\)
\(=> 0 = p - q\)
\(=> p = q\)
\(\mathtt{x\ \ y}\)
\(\mathtt{z\ \ x}\) 同理可证得。
那么，对于所有的 \(2 \times 2\) 连续子矩阵，由于两两相邻，等式具有传递性，也就是说，每两列左右元素差值在模 \(3\) 意义下相等。
行的差值同理可证得，模 \(3\) 意义下也是相等的。
观察/证明 2
对于下面的矩阵：
\(\mathtt{x\ \ y}\)
\(\mathtt{z\ \ x}\)
若 \((y - x)\mod 3 = p, (z - x)\mod 3 = q\)，很显然 \(p \neq q\)。
也就是说，"\" 对角线上相等，行列差值不同。
而对于下面的矩阵：
\(\mathtt{x\ \ y}\)
\(\mathtt{y\ \ z}\)
显然行列差值相同。
也就是说，"/" 对角线上相等，行列差值相同。
归纳
通过上述分析，我们可以将所有限制转化为对应的 相邻行差值 和 相邻列差值 是否相等。
更具体地说，我们将 所有相邻行和所有相邻列 的差值 这一"属性" 都视为图中的点，那么所有限制等价为两个点的值是否相同。
也就是等价为 图上两个点的颜色是否相同 的限制。
这就是 二分图 问题。那么，我们只需 \(\mathtt{dfs}\)，判断涂色是否出现冲突即可。
时间复杂度：\(O(n + m + k)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 9, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<pii>> e(n + m + 1);
while(k --){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
e[min(x1, x2)].pb(n + min(y1, y2), y2 != y1 - 1);
e[n + min(y1, y2)].pb(min(x1, x2), y2 != y1 - 1);
}
vector<int> color(n + m + 1, -1);
bool f = true;
auto dfs = [&](auto dfs, int x, int c) -> void{
if(color[x] != -1 || !f) return;
color[x] = c;
for(auto [p, r] : e[x]){
if(color[p] != -1){
if((color[p] != color[x]) != r){
f = false;
cout << "NO\n";
return;
}
continue;
}
dfs(dfs, p, c ^ r);
if(!f) return;
}
};
for(int i=1;i<=n+m;i++){
if(color[i] != -1) continue;
dfs(dfs, i, 0);
if(!f) return;
}
cout << "YES\n";
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}但凡往模三上去想