Practice.

A. Cowardly Rooks

题意

给定 \(n\) 个点的横纵坐标，输出是否可以将任意一个点移动，使每一行每一列都只有最多一个点。

思路

我们可以先将原来的所有点对应的横坐标和纵坐标对应的行和列进行统计，之后若能找出任意一行或者任意一列没有点，那么就可以移动到那里去。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 5e3 + 10, inf = 0x3f3f3f3f3f3f, mod = 998244353;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n, m;
        cin >> n >> m;
        int r[10]{}, c[10]{};
        bool f = false;
        for(int i=0;i<m;i++) {
            int a, b;
            cin >> a >> b;
            r[a]++, c[b]++;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(r[i] == 0 || c[j] == 0){
                    f = true;
                }
            }
        cout << (f ? "YES\n" : "NO\n");
    }
}

给的代码写得略微麻烦了点（

B. Death's Blessing

题意

给定 \(n\) 个怪物的血量和能力 \(a_i, b_i\)，在干掉一个怪物的时候，该怪物将会把相邻的怪物的血量加上它的能力，怪物死亡后从序列中移除，第一个和最后一个怪物只有一个相邻的怪物。输出将所有怪物干掉需要扣除的血量最大值。

思路

首先，答案可以拆分成原来所有怪物的血量和加上外加的血量，外加的血量只和操作顺序有关，所以我们可以试试贪心：

既然两侧的怪物能附加的血量只会影响到一个怪物，那么我们可以贪心地从两侧开始打，但这不够，考虑到只剩一个怪物的时候，这个怪物无法再将自己的能力附加到其他怪物上，所以我们可以将能力值最大的怪物放到最后。

可以很容易证明上述贪心思想成立。

时间复杂度：\(O(n \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 5e3 + 10, inf = 0x3f3f3f3f3f3f, mod = 998244353;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n;
        cin >> n;
        int ans = 0;
        for(int i=0;i<n;i++) {
            int cur;
            cin >> cur;
            ans += cur;
        }
        vector<int> b(n);
        for(int i=0;i<n;i++){
            int cur;
            cin >> cur;
            b[i] = cur;
            ans += b[i];
        }
        sort(b.begin(), b.end());
        cout << ans - b[n - 1] << '\n';
    }
}

简单的贪心捏

C. Number Game

题意

给定一个数组 \(a\)，选择任意回合数 \(k\)，在第 \(i\) 个回合，\(A\) 需要找出一个小于等于 \(k - i + 1\) 的数，并将其删去，之后 \(B\) 选择任意一个数，将其加上 \(k - i + 1\)。在两个人足够聪明的条件下，输出最大的 \(k\)，满足不存在某一个回合，数组不为空但 \(A\) 无法删除。

思路

显然，既然要让 \(A\) 寄，那么 \(B\) 一定会将当前的最小值加上 \(k - i + 1\)，因为所加的值是递减的。

考虑到数据范围特别小，我们不妨在每一局结束的时候将整个新数组排个序。

对于一个回合，我们可以用二分的方法，快速找出第一个大于 \(k - i + 1\) 的数并将其前面一个数删去，也就是在每次操作时删去最大数，这样可以尽可能删除多一点的数。然后，将第一个数加上 \(k - i + 1\) 即可。

数据量太小了，可以二分答案 \(k\)，也可以直接暴力枚举。

时间复杂度：\(O(n^2 + n^2 \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f, mod = 998244353;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i=0;i<n;i++) cin >> a[i];
        for(int k=n;k>=0;k--){
            vector<int> tmp(a);
            sort(tmp.begin(), tmp.end());
            bool f = true;
            for(int i=1;i<=k;i++){
                int p = upper_bound(tmp.begin(), tmp.end(), k - i + 1) - tmp.begin();
                if(p == 0) {
                    f = false;
                    break;
                }
                tmp[p - 1] = inf;
                tmp[0] += k - i + 1;
                sort(tmp.begin(), tmp.end());
            }
            if(f){
                cout << k << '\n';
                break;
            }
        }
    }
}

无脑暴力.jpg