Contestant~. Rank 1909. Rating -24.
A. Channel
题意
定义每个人上线都会阅读所有帖子。
现在，\(A\) 发布了一篇文章，发布的时候。
给定由 "+", "-" 组成的字符串，分别代表该时刻有一个人上线/下线，按照下面的方式输出答案：
所有人都阅读过该文章，输出 \(YES\)；
有可能所有人都阅读过该文章，输出 \(MAYBE\)；
所有人都不可能阅读过该文章，输出 \(NO\)
思路
所有人都阅读过的条件是假设下线后上线的是同一个人，有可能所有人都阅读过的条件是假设下线后上线的是不同的人。
否则就是不可能。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m, q;
cin >> n >> m >> q;
string s;
cin >> s;
int cur1 = 0, cur2 = 0;
for(int i=0;i<q;i++){
if(m + cur1 == n) {
cout << "YES\n";
return;
}
if(s[i] == '-') cur1 --;
else{
cur1 ++, cur2 ++;
}
}
if(m + cur1 == n) {
cout << "YES\n";
return;
}
cout << (m + cur2 >= n ? "MAYBE\n" : "NO\n");
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}但是很抽象（
B. Split Sort
题意
给定一个排列 \(p\)，定义一次操作为：
选定一个数 \(x \in [2, n]\)；
在不改变顺序的条件下，将小于 \(x\) 的元素放在左边，将剩余的元素放在右边
输出最小操作数，使对于所有 \(i \in [1, n]\)，有 \(p_i = i\)。
思路
显然，对于 \(a_i = k, a_j = k + 1\)，如果 \(i > j\)，那么我们就得选择 \(x = k + 1\) 并执行一次操作。
观察可得，上面的操作方案即可让方案数最小。
具体来说，我们令 \(a_{p_i} = i\)，然后统计 \(a_i > a_{i + 1}\) 的个数即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), pos(n + 1);
for(int i=1;i<=n;i++){
cin >> a[i];
pos[a[i]] = i;
}
int ans = 0;
for(int i=1;i<=n;i++){
if(pos[i] > pos[i - 1]) continue;
ans ++;
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}思维题（
C. MEX Repetition
题意
给定一个序列，定义一次操作如下：
遍历 \(i \in [1, n]\)；
对于 \(a_i\)，将其替换为 \(MEX(a_1, a_2, \ldots , a_{i - 1}, a_{i + 1}, \ldots, a_n)\)。
输出 \(k\) 次操作后的序列。
思路
观察可得，执行一次操作后等价于将其变为 \(\{MEX(a_2, a_3, \ldots , a_n), a_1, a_2, \ldots, a_{n - 1}\}\)。
如果我们将 \(MEX(a_2, a_3, \ldots , a_n)\) 放到序列的最后，整道题就等价于：将这个序列循环右移 \(k\) 位后，输出前 \(n\) 个数。
显然，循环右移是的周期是 \(n + 1\)，那么我们只需将 \(k \ \% = (n + 1)\)。
我们可以将 \([1, n + 1]\) 复制一份到 \([n + 2, 2n + 2]\)，最后输出 \([n - k + 2, 2n - k + 1]\) 内的数即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(2 * n + 4);
vector<bool> st(n + 1);
for(int i=1;i<=n;i++){
cin >> a[i];
st[a[i]] = true;
}
int p = 0;
for(int i=1;i<=n;i++){
if(st[i]) continue;
p = i;
break;
}
a[n + 1] = p;
for(int i=1;i<=n + 1;i++) a[n + i + 1] = a[i];
k %= (n + 1);
for(int i=1;i<=n;i++){
cout << a[n - k + i + 1] << ' ';
}
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}找规律题（
D. Two-Colored Dominoes
题意
给定由若干个两格长的多米诺骨牌拼成的图形，该图形位于一个点阵中。
骨牌可以横向放置，也可以竖向放置，分别如下所示：
.... ...
.LR. .U.
.... .D.
.... ...现在，给定点阵，按下面的要求涂色：
每个骨牌有白色方块和黑色；
每行黑白方块个数相等；
每列黑白方块个数相等
若无法涂色，输出 \(-1\)。
思路
如果我们单独考虑 "LR" 和 "UD"，不难发现两者是互相不影响的。
换句话说，"LR" 的多少不影响当前行的黑白配对，"UD" 的多少不影响当前列的黑白配对。
因而，我们只需单独对两者进行操作，且操作是随意的，对于 \(j\) 列，我们将所有的 "L" 交叉插入黑白，对于 \(i\) 行，我们将所有 "U" 交叉插入黑白。
自然，如果某一列可以涂色的方块个数为奇数，或者某一行可以涂色的方块个数为奇数，那么就是无解。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
vector<string> s(n);
for(int i=0;i<n;i++) {
cin >> s[i];
}
for(int i=0;i<n;i++){
int cnt = 0;
for(int j=0;j<m;j++){
if(s[i][j] != '.') cnt ++;
}
if(cnt % 2 == 1){
cout << -1 << '\n';
return;
}
}
for(int j=0;j<m;j++){
int cnt = 0;
for(int i=0;i<n;i++){
if(s[i][j] != '.') cnt ++;
}
if(cnt % 2 == 1){
cout << -1 << '\n';
return;
}
}
auto res = s;
for(int j = 0;j < m;j++) {
bool f = true;
for (int k = 0; k < n; k++) {
if (res[k][j] == 'L') {
if (f) {
res[k][j] = 'W', res[k][j + 1] = 'B';
} else {
res[k][j] = 'B', res[k][j + 1] = 'W';
}
f = !f;
}
}
}
for(int i = 0;i < n;i++) {
bool f = true;
for (int k = 0; k < m; k++) {
if (res[i][k] == 'U') {
if (f) {
res[i][k] = 'W', res[i + 1][k] = 'B';
} else {
res[i][k] = 'B', res[i + 1][k] = 'W';
}
f = !f;
}
}
}
for(auto e : res) cout << e << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}一起涂就寄咯
E. Speedrun
题意
给定 \(n\) 个任务，每个任务 \(i\) 必须在每一个 游戏日 的 \(h_i\) 小时时刻完成，且每个人物只需完成一次。
上述 游戏日 为给定的 \(k\) 小时。
现在，给定 \(n\) 个限制 \((a_i, b_i)\)，每个限制代表任务 \(b_i\) 必须在任务 \(a_i\) 完成后才能完成。保证没有环。
输出 最后一个任务完成的时刻 与 第一个任务完成的时刻 的 差值 的最小值。
思路
首先，任务之间的依赖性，不难让我们想到拓扑序，我们可以以 \(a_i \rightarrow b_i\) 的建图方式，先跑一遍拓扑排序，得到拓扑序 \(q\)。
那么显然，后面的任务依赖于前面的任务。
那么如果我们定义 \(dp[i]\) 为 \(i\) 任务及其所有子任务完成的总时间，就有 \(dp[x] = \max(dp[x], dp[y] + (h[y] - h[x] + k) \bmod k):x \to y\)。
如果我们只要求最后一个任务完成的时刻，那么此时问题已经解决了，也就是 \(\max(dp[x])\)。
但我们需要求的是差值，也就是说，可能存在某两个依赖的任务的相差时间大于 \(k\) 的情况，导致第一个任务完成时间偏小，造成答案偏大。
不难发现，我们只需从小到大枚举 \(h_i\)，并将其加上 \(k\) 即可，因为相差时间不会超过 \(2k\)。
那么，我们只需维护当前 \(dp_{max}\) 以及第一个任务完成的时刻即可。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
vector<vector<int>> e(n);
vector<int> in(n);
while(m --){
int u, v;
cin >> u >> v;
u --, v --;
e[u].pb(v);
in[v] ++;
}
vector<int> q;
for(int i=0;i<n;i++){
if(in[i] == 0) q.pb(i);
}
for(int i=0;i<n;i++){
int x = q[i];
for(auto y : e[x]){
if(-- in[y] == 0) q.pb(y);
}
}
vector<int> dp(n);
for(int i=n-1;i>=0;i--){
int x = q[i];
for(auto y : e[x]){
dp[x] = max(dp[x], dp[y] + (a[y] - a[x] + k) % k);
}
}
for(int i=0;i<n;i++) dp[i] += a[i];
int res = *max_element(all(dp));
vector<int> p(n);
iota(all(p), 0);
sort(all(p), [&](int o1, int o2) -> bool{
return a[o1] < a[o2];
});
int ans = inf;
for(auto i : p){
ans = min(ans, res - a[i]);
res = max(res, dp[i] + k);
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}为什么我会去反向拓扑呢，为什么嘞(x