打这场的时候迷迷糊糊的，然后掉分了（

A Prison Break:

题面很复杂，但是题意很简单，仅需求出从这个点到四个角的最大的曼哈顿距离即可

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int times;
int n,m,r,c;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> times;
    while(times--) {
        cin >> n >> m >> r >> c;
        cout << max(max(abs(1 - r) + abs(1 - c),abs(n - r) + abs(1 - c)),max(abs(1 - r) + abs(m - c),abs(n - r) + abs(m - c))) << '\n';
    }
    return 0;
}

B Repainting Street:

限制长度的区间覆盖，要求得到最后得到相同颜色的最少操作数

颜色确定之后便可以暴力覆盖

注意到颜色的值域很小，故枚举颜色即可

\(p.s.\)这道题 \(Wa\) 了两发，原因是区间长度是固定的，该染到的一定染到

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int times;
int n,m;
int a[N];
int b[N];
int vis[101];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> times;
    while(times--) {
        memset(vis,0,sizeof vis);
        cin >> n >> m;
        for(int i = 1;i <= n;i++) {
            cin >> a[i];
        }
        int ans = 2e9;
        for(int C = 1;C <= 100;C++) {
            int tot = 0,las,k;
            for(int i = 1;i <= n;i++) b[i] = a[i];
            for(int i = 1;i <= n;i++) {
                las = k = i;
                if(b[i] != C)
                while(k - las + 1 <= m) {
                    b[k] = C;
                    k++;
                }
                else continue;
                k--;
                i = k;
                tot++;

            }
            ans = min(ans,tot);
        }
        cout << ans << '\n';
    }
    return 0;
}

C Bouncing Ball :

不难发现，删除前面一块等价于把所有的往前移动一块

并且最后的代价与删除操作和添加操作顺序无关

所以直接枚举删除操作数量即可，因为每次都跳固定的 \(k\)

所以跳到的块的下标满足 \(i\space \%\space k\space =\space p\space (i = t \times k + p)\)

从后往前开一个桶扫一遍即可

\(p.s.\) 因为 \(B\) 题卡了有点久，这题最后结束了才 \(AC\) （掉分的原因

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n,m;
char a[N];
int times,tong[N],x,y;
int p,k;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> times;
    while(times--) {
        cin >> n >> p >> k;
        cin >> (a + 1);
        cin >> x >> y;
        ll ans = 2e18;
        for(int i = n;i >= 0;i--) tong[i] = 0;
        for(int i = n;i >= p;i--) {
            if(a[i] == '0') tong[i % k] += x;
            ans = min(ans,1ll * (i - p) * y + tong[i % k]);
        }
        cout << ans << '\n';
    }
    return 0;
}

D XOR-gun :

\(Xor\) 的性质太多了

这里来做一个总结 ：

\(x \otimes y \le x + y\) 适用于任何情况，作用于限制其余变量缩小问题状态

\(x \otimes y \le 2 ^ n\) 适用于 \(x \le 2 ^ n\) 并且 \(y \le 2 ^ n\)

所以做异或的题从两方面来考虑 ：

1.二进制角度上

2.整数域计算上

这道题上，要求用 $\otimes $ 破坏非减单调序列，第一条性质做不了

当存在两个在二进制上最高位相同的数时，异或之后一定可以使得到的数减少一半

并且当此时再存在一个数在最高位上与前面两个数相同时，则一定可以一次操作完成

根据鸽子原理，那么 \(n \ge 2 \times log 10^9\) 时便直接输出 \(1\) 即可，否则直接枚举出当前想把序列破坏掉的两个数即可

复杂度 \(O(n^3)\)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N],sum[N];
int ans = 2e5 + 10;
int n;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] ^ a[i];
    }
    if(n > 60) {
        cout << "1" << '\n';
        return 0;
    }
    for(int k = 1;k < n;k++) {
        for(int i = 1;i <= k;i++) {
            for(int j = k + 1;j <= n;j++) {
                int s1 = sum[k] ^ sum[i - 1] ,s2 = sum[j] ^ sum[k];
                if(s1 > s2) {
                    ans = min(ans,j - k - 1 + k - i);
                }
            }
        }
    }
    if(ans == 2e5 + 10)
    cout << "-1" << '\n';
    else
    cout << ans << '\n';
    return 0;
} 

E New Game Plus!:

如果这题的 \(k\) 很小，也许可以用 \(dp\) 解决

所以这里考虑其他算法，因为求得最值，所以考虑贪心

首先考虑 \(k = 0\) 的情况，容易发现，一个 \(boss\) 的贡献是他所处的位置离结尾还有多少个乘上 \(C_i\)

所以考虑使用经典贪心微调法来证明此时应满足 \(C_i >= C_{i + 1} (i < n),i \in Z\) 时结果最优

再考虑 \(k != 0\) 的情况，容易发现，一旦使用一次 \(reset\) 游戏将会被重置为新游戏，所以游戏分为了 \(k + 1\) 个游戏。

在每一个独立的游戏中，每打一个 \(boss\) 的贡献可以写作 \(p \times C_i\) ，也就是说，当我们发现如果存在 \(p_i > p_j\) 但 \(C_i < C_j\) 的时候，一定存在更优解

那么也就是说，为了让 \(C_i > 0\) 的 \(p\) 尽量大，我们考虑将第一个正数放进来的过程，这第一个正数必然会放在此时可以令它的 \(p\) 最大的一个游戏之中

那么接下来的正数依旧会放在这个正数的后面，所以我们可以把所有的正数放在一个游戏中

同样的，我们来考虑负数的 \(p\)，我们想让 \(p\) 尽量小，所以一旦发现存在两个游戏中的第一个元素是负数，并且 \(p_1 - p_2 \ge 2\) 时，可以将 \(p_1\) 放在 \(p_2\) 的后面，以得到更优解

我们来考虑如何实现这个贪心的过程

(注：这里不证明为什么必须用完 \(k\) 次 \(reset\))

首先，对于第一条，正数都将在一个游戏之中，那么，我么考虑维护一个大根堆，这样可以满足。

考虑处理负数，那么一次 \(reset\) 相当于在单调队列中插入 \(k + 1\) 个 \(0\) ，如果此时正数的游戏中 \(sum > 0\) 则此时放在 \(sum > 0\) 依然是最优的

当正数游戏中 \(sum < 0\) 时，此时再插入会得到更差解，插入 \(0\) 即可。

这样，通过大根堆的维护，我们保证了第一条性质，并且如果我们将初始序列 \(sort\) 从大到小排一遍之后我们可以维护剩下两条性质

(简短证明一下：如果有一个有两个游戏个数分别为 \(i + 1\) 与 \(i\)，那么有\(C_i\) 大，\(p\) 也大的这条性质，可以得到 \(sum_1 < sum_2\) ，所以一定会将新数插入大小为 \(i\) 的游戏之中)

这道题确实很妙，在官方的题解之中将一个游戏看成一个一个栈，那么这里的 \(p\) 便是这个元素在栈中的 \(h\) ，会更好理解

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 5e5 + 10;

priority_queue<ll> p;
ll a[N];
int n,m;
ll ans = 0;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m + 1;i++) p.push(0);
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    sort(a + 1,a + n + 1,[&](ll a,ll b) {return a > b;});
    for(int i = 1;i <= n;i++) {
        ll x = p.top();
        ans += x;
        p.pop();
        p.push(x + a[i]);
    }
    cout << ans << '\n';
    return 0;
}

Summary :

1. 有些 (A/B) 应该考虑简单一点根据题目/题目数据来思考算法，不要先入为主
2. 当题目用一般算法做不通的时候考虑挖掘一下性质
3. 面对较复杂的题目时，多多运用分类讨论与同状态转换(E题题解中将游戏看作栈)的思想简化题目
4. 以后多补题写题解以提升思维