cf真的好久没进前1千了，这次状态还算不错，怒涨90分，总算把今年跌的分涨回来了，感动涕零
A. False Alarm
思路：有n个门，部分门开部分门关，每经过一个门耗时一秒，现在有个按钮可以让所有门关的门打开k秒，问人能否顺利通过。水题，直接判断第一个关门和最后一个关门之间的距离，若小于k，则可以直接通过
/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {int n, x;cin >> n >> x;int st = -1, en = -1;for (int i = 0; i < n; i++) {int a;cin >> a;if (a == 1) {if (st == -1) {st = i;}en = i;}}if (en - st >= x) {cout << "NO" << '\n';} else {cout << "YES" << '\n';}}return 0;
}
B. Shrink
思路：要求构造一个金字塔型数组，即中间的数一定比两边的数高，那么直接从左右往中间放数即可
/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int MAXN = 2e5 + 5;int a[MAXN];int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {int n;cin >> n;for (int i = 1; i <= n; i++) {if (i % 2 == 1) {a[i >> 1] = i;} else {a[n - (i >> 1)] = i;}}for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;}return 0;
}
C. Cool Partition
思路：将数组分割成几个连续的子集，要求后面的子集一定包含前面的子集。
这就是一个贪心的策略，从后往前遍历，每一轮要求遍历所有现有的元素，即为完整的一个集合。为了方便起见，可以用一个标记单独标一下每个数字是出现在奇数轮还是偶数轮。由于每个数字消失前每一轮都必须出现，这样即可实现每一轮的独立标记
/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int MAXN = 2e5 + 5;int a[MAXN];
int b[MAXN];
int c[MAXN];int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {memset(b, 0, sizeof b);memset(c, -1, sizeof c);int n;cin >> n;int count = 0;for (int i = 0; i < n; i++) {cin >> a[i];b[a[i]]++;if (b[a[i]] == 1) {count++;}}int re = 0;int currentCount = count;for (int i = n - 1; i >= 0; i--) {b[a[i]]--;if (b[a[i]] == 0) {count--;}if (c[a[i]] != re % 2) {c[a[i]] = re % 2;currentCount--;}if (currentCount == 0) {re++;currentCount = count;}}cout << re << endl;}return 0;
}
D. Retaliation
思路：给定一个数组，判断该数组能否仅经过多次正向加操作（给数组中的数分别加1,2……n）和逆向加操作（给数组中的依次加n，n-1……1）完成。
其实简化来说只需要进行两步判断
1.这个数组是否为等差数列
2.数组中最小的数减去公差后剩余的数后能否被n-1整除
注意一下判断等差数列的时候处理公差的场景
/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int MAXN = 2e5 + 5;int a[MAXN];int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {int n;cin >> n;int diff = 0;bool yes = true;for (int i = 0; i < n; i++) {cin >> a[i];if (i == 1) {diff = a[i] - a[i - 1];}if (i > 1 && yes) {if (a[i] - a[i - 1] != diff) {yes = false;// cout << i << "*" << a[i] << "**" << a[i - 1] << "**" << diff << endl;}diff = a[i] - a[i - 1];}}int a0 = a[0] - diff;if (diff < 0) {a0 = a[n - 1] + diff;}// cout << diff << "*" << a0 << "*" << (a0 % (n + 1)) << "*" << yes << endl;if (yes && a0 >= 0 && (a0 % (n + 1)) == 0) {cout << "YES" << endl;} else {cout << "NO" << endl;}}return 0;
}
E. Lost Soul
思路：给定两个数组，给定一个常规操作和一个限定操作。常规操作就是将某个数组中的第i位设置为第二个数组中的第i+1位，该操作可以进行无数次。限定操作即为同时删除两个数组中的第k位，这个操作只能进行一次。现在要求最多可以让两个数组有多少相同的数。
其实这题的思路也是个策略。不难发现，一旦找到了某个位置两个数组相同，那么就可以利用常规操作将前方所有的数字都变成这个数。那么题目就简化为了，寻找最靠后的相同位数的数。接下来看一下构造方案。
方案0：若两数组中某个位置两个数相同，则该位置即可以为答案
方案1：如果某个数组中连续两个数相同，则另一个数组中前一个位置一定也能变成这个数，即前方的位置即可以为答案
方案2：如果数组中某个位置k，其数在任意数组的第k+1位（不包含）之后出现过，则位置k也可以为答案
针对方案2，我们不难发现我们反复执行方案1，或者砍掉第k+1位后再反复执行方案1即可得到
/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int MAXN = 2e5 + 5;int a[MAXN];
int b[MAXN];
bool c[MAXN];int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while (t--) {memset(c, false, sizeof c);int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {cin >> b[i];}int re = 0;if (a[n] == b[n]) {re = n;} else {c[a[n]] = true;c[b[n]] = true;if (a[n] == a[n - 1] || b[n] == b[n - 1] || a[n - 1] == b[n - 1]) {re = n - 1;} else {for (int i = n - 2; i > 0; i--) {if (c[a[i]] || c[b[i]] || a[i] == b[i] || a[i] == a[i + 1] || b[i] == b[i + 1]) {re = i;break;}c[a[i + 1]] = true;c[b[i + 1]] = true;}}}cout << re << endl;}return 0;
}
