A. MEX Destruction
题意：给你一个数组，每次操作选择一个区间使这个区间变为区间mex，问最少操作使得数组全为0.
容易发现，对任意一个区间，最多两次操作这个区间就会全变成0，于是我们想尽可能操作大的区间。
但并不是直接操作整个数组一定更好，如果我们选择的区间里没有0，那么只需要一次操作，于是判断除去两端连续之后，中间的数里面有没有0，有0则操作两次，没有操作1次。特别的，全0数组不需要操作。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
int zero = 0;
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
int l = 0, r = n - 1;
while (l < n && a[l] == 0) {
++ l;
}
while (r >= 0 && a[r] == 0) {
-- r;
}
for (int i = l; i <= r; ++ i) {
zero += a[i] == 0;
}
if (l > r) {
std::cout << 0 << "\n";
} else {
std::cout << (zero > 0 ? 2 : 1) << "\n";
}
}
B. pspspsps
题意：给你一个长度为n只由'p', 's', '.'构成的字符串，判断有没有一个长度为n的排列a满足下列条件：
- 每个是p的位置i，都有a1~ai是一个排列。
- 每个是s的位置i，都有ai~an是一个排列。
是点的位置没有要求。
由于整个数组是一个排列，那么任何一个p不能出现在任何一个s的前面，因为每个数只有一个。
对于任意一对i和j(i < j)，满足si是s，sj是p，那么他们可以共享j - i + 1个数字，那么i和j之中至少有一个他的需要的排列长度小于等于j - i + 1，否则就是NO,双层循环枚举即可。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
for (int i = 0; i < n; ++ i) {
for (int j = i + 1; j < n; ++ j) {
if (s[i] == 'p' && s[j] == 's') {
std::cout << "NO\n";
return;
} else if (s[i] == 's' && s[j] == 'p' && j + 1 > j - i + 1 && n - i > j - i + 1) {
std::cout << "NO\n";
return;
}
}
}
std::cout << "YES\n";
}
C. MEX Cycle
题意：一个长度为n的数组a要满足他和他的所有“朋友"的mex等于ai，数组是第一个元素和最后一个元素相邻，每个元素的朋友为他的左右邻居。
题目会多给出一组朋友关系。
让你构造一个满足条件的长度为n的数组。
这题差不多写了应该小时，人麻了。
我的写法感觉有点麻烦了，看官方题解就几行代码。
我的解法是第x个为1，第y个为2，这样他们两边应该都是0，考虑x往右走距离y还有几个没填，如果是奇数个，则直接10101...填满，如果是偶数个则x+2位置填2，然后依旧10101...
考虑特殊情况，中间没有数，并且第x+1个和第y-1个相邻，则可以让第x+1个为2，这样就是...012020...，如果他们是一个位置，则不用管，然后同样道理考虑x往左走。特殊情况让y+1填1.
点击查看代码
void solve() {
int n, x, y;
std::cin >> n >> x >> y;
-- x, -- y;
std::vector<int> ans(n);
if (std::abs(x - y) == 1 || std::abs(x - y) == n - 1) {
if (n & 1) {
ans[0] = 2;
for (int i = 1; i < n; ++ i) {
ans[i] = i & 1;
}
} else {
for (int i = 0; i < n; ++ i) {
ans[i] = i & 1;
}
}
} else {
ans[x] = 1; ans[y] = 2;
int len1 = y - 1 - (x + 1) - 1;
if (len1 == 0) {
ans[(x + 1) % n] = 2;
} else if (len1 > 0 && len1 % 2 == 0) {
ans[x + 2] = 2;
for (int i = x + 3; i < y - 1; ++ i) {
ans[i] = i - (x + 3) + 1 & 1;
}
} else if (len1 > 0 && len1 % 2 == 1) {
for (int i = x + 2; i < y - 1; ++ i) {
ans[i] = i - (x + 2) + 1 & 1;
}
}
int len2 = -1;
int l = (x - 1 + n) % n, r = (y + 1) % n;
while (l != r) {
++ len2;
l = (l - 1 + n) % n;
}
if (len2 == 0) {
ans[(y + 1) % n] = 1;
} else if (len2 > 0 && len2 % 2 == 0) {
l = (x - 2 + n) % n;
ans[l] = 2;
int k = 1;
for (int i = (l - 1 + n) % n; i != r; i = (i - 1 + n) % n, k ^= 1) {
ans[i] = k;
}
} else if (len2 > 0 && len2 % 2 == 1) {
l = (x - 2 + n) % n;
int k = 1;
for (int i = l; i != r; i = (i - 1 + n) % n, k ^= 1) {
ans[i] = k;
}
}
}
for (int i = 0; i < n; ++ i) {
std::cout << ans[i] << " \n"[i == n - 1];
}
}
D. Shift + Esc
题意：一个nm的数组，你要从(1, 1)走到(n, m)，只能往下或往右，但在走之前，对每个行你可以左移任意次，最后花费为k左移次数+路径值总和。
是个经典dp加了个状态，还是挺好想的。
我们套用f[i][j]的定义，发现无法处理左移情况，怎么办? 发现n和m才200，还可以再开一维，正好补上这个状态!
f[i][j][cnt]表示走到(i, j)且第i行左移了cnt次的最小花费，那么对于同一行可以有f[i][j - 1][cnt]转移过来，但对于上一行，他的任意左移次数状态都可以转移过来，我们可以存个min[i][j]，表示(i, j)这个位置滚了任意次中的最小值，那么可以由min[i - 1][j]转移过来。
第三维最多开m - 1，因为多转就转回来了。
点击查看代码
void solve() {
int n, m, k;
std::cin >> n >> m >> k;
std::vector a(n, std::vector<i64>(m));
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
std::cin >> a[i][j];
}
}
std::vector f(n + 1, std::vector(m + 1, std::vector<i64>(m, 1e18)));
std::vector min(n + 1, std::vector<i64>(m + 1, 1e18));
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
for (int cnt = 0; cnt < m; ++ cnt) {
i64 w = (i64)k * cnt;
if (i == 1 && j == 1) {
f[i][j][cnt] = a[0][cnt];
}
if (i > 1) {
f[i][j][cnt] = std::min(f[i][j][cnt], min[i - 1][j] + a[i - 1][(j - 1 + cnt) % m]);
}
if (j > 1) {
f[i][j][cnt] = std::min(f[i][j][cnt], f[i][j - 1][cnt] + a[i - 1][(j - 1 + cnt) % m]);
}
min[i][j] = std::min(min[i][j], f[i][j][cnt] + w);
}
// std::cout << min[i][j] << " \n"[j == m];
}
}
std::cout << min[n][m] << "\n";
}
E. Broken Queries
赛后补的
题意：有一个长度为2的幂的01字符串，和一个k，这个字符串只有一个1。每次你可以询问一个区间，假设这个区间和为s，那么当区间长度小于k时，返回s，否则返回1-s。
我们可以通过询问(1, n / 4) 和 (n / 4 + 1, n / 2)来获取1所在的区间位置，因为如果1在(1, n / 2)，不管k怎么样，这两个回答一定时不同的，否则1在(n / 2 + 1, n)。
确定1的位置就可以确定k的大小，假设1在左边，那么先询问(1, n / 2), 如果k > n / 2, 那么就会得到0，我们可以二分n / 2 + 1到n的长度，看(1, mid)的值来找第一个回到0的位置，因为他一定是000...1111这样的，满足二段性。
如果k <= n / 2, 一样的二分，只不过我们要利用另一半，因为我们知道1不在另一半，他的区间和都是0，所有可以求(mid, n)来找最后一个1的位置。
点击查看代码
int ask(int l, int r) {
std::cout << "? " << l << " " << r << std::endl;
int res;
std::cin >> res;
return res;
}
void solve() {
int n;
std::cin >> n;
if (ask(1, n / 4) != ask(n / 4 + 1, n / 2)) {
if (ask(1, n / 2)) {
int l = n / 2 + 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (ask(1, mid) == 0) {
r = mid;
} else {
l = mid + 1;
}
}
std::cout << "! " << l << std::endl;
} else {
int l = 1, r = n / 2;
while (l < r) {
int mid = l + r >> 1;
if (ask(n / 2 + 1, n / 2 + mid)) {
r = mid;
} else {
l = mid + 1;
}
}
std::cout << "! " << l << std::endl;
}
} else {
if (ask(n / 2 + 1, n)) {
int l = n / 2 + 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (ask(n - mid + 1, n) == 0) {
r = mid;
} else {
l = mid + 1;
}
}
std::cout << "! " << l << std::endl;
} else {
int l = 1, r = n / 2;
while (l < r) {
int mid = l + r >> 1;
if (ask(1, mid)) {
r = mid;
} else {
l = mid + 1;
}
}
std::cout << "! " << l << std::endl;
}
}
}