abc 339 D

这道题的关键条件是，两个点同时向一个方向移动
也用bfs，但是表示的是两个点的位置
当两个点位置相同的时候，直接输出就可以了

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int dp[61][61][61][61];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i ++) cin >> s[i];

    int a, b, c, d;

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (s[i][j] == 'P') {
                c = a, d = b;
                a = i, b = j;
            }
        }
    }

    queue<PII> q;
    q.push({a * n + b, c * n + d});

    for (int i = 0; i <= 60; i ++) 
        for (int j = 0; j <= 60; j ++) 
            for (int k = 0; k <= 60; k ++) 
                for (int o = 0; o <= 60; o ++) 
                    dp[i][j][k][o] = -1;

    dp[a][b][c][d] = 0;

    while (q.size()) {
        auto [e, f] = q.front();
        q.pop();

        int v = e / n, u = e % n, l = f / n, r = f % n;

        if (e == f) {
            cout << dp[v][u][l][r] << endl;
            return 0;
        }

        for (int i = 0; i < 4; i ++) {
            int sv = v + dx[i], su = u + dy[i], sl = l + dx[i], sr = r + dy[i];
            if (sv < 0 || sv >= n || su >= n || su < 0 || s[sv][su] == '#') sv = v, su = u;
            if (sl < 0 || sl >= n || sr >= n || sr < 0 || s[sl][sr] == '#') sl = l, sr = r;
            if (dp[sv][su][sl][sr] == -1) {
                dp[sv][su][sl][sr] = dp[v][u][l][r] + 1;
                q.push({sv * n + su, sl * n + sr});
            }
        }
    }

    cout << -1 << endl;

    return 0;
}

abc 338 D

差分，酷似 Round 974(Div.3) D，差分也要开long long

abc 337 D

单调队列
这里要注意给的条件是 max(h, w) >= k

abc 336 D

计得以当前点为山峰，左边需要削掉的点数和右边需要削掉的点数
得到每个点左翼和右翼的点数，答案是二者最小值的最大值
jls的做法是记录每个点可能达到的最大高度，从左往右处理一边，从右往左处理一遍
这样，其中的最大值是可能的最大高度
这道题有点像dp，如果左边是那么高，那么最多比它大 1，同时也不能大于自身的高度

#include <bits/stdc++.h>

using namespace std;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i ++) cin >> a[i];
    vector<int> p(n, 0), q(n, 0);

    int ans = 1;
    int l = 0, r = 0;
    for (int i = 1; i < n; i ++) {
        if (a[i] <= i) {
            p[i] = max(p[i - 1], i - a[i] + 1);
        } else {
            p[i] = p[i - 1];
        }
    }

    for (int i = n - 2; i >= 0; i --) {
        if (a[i] < n - i) {
            q[i] = max(q[i + 1], n - i - a[i]);
        } else {
            q[i] = q[i + 1];
        }
    }


    for (int i = 0; i < n; i ++) {
        ans = max(ans, min(i - p[i], n - i - 1 - q[i]) * 2 + 1);
    }

    cout << (ans + 1) / 2 << endl;

    return 0;
}

abc 335 D

语法题，没有夸张，语法基础里有。。。

abc 334 D

二分

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<ll> r(n);
    for (int i = 0; i < n; i ++) {
        cin >> r[i];
    }

    sort(r.begin(), r.end());
    for (int i = 1; i < n; i ++) r[i] = r[i - 1] + r[i];

    while (q --) {
        ll x;
        cin >> x;

        auto t = upper_bound(r.begin(), r.end(), x) - r.begin() - 1;

        cout << t + 1 << endl;
    }

    return 0;
}

abc 333 D

并查集，把所有 1 的枝干合并，想要删掉 1，就要让 1 只剩一个枝干，这样 1 也是叶子节点，可以被删除

#include <bits/stdc++.h>

using namespace std;

struct DSU {
    vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1) {iota(f.begin(), f.end(), 0); }
    int leader(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool same(int x, int y) {return leader(x) == leader(y); }
    bool merge(int x, int y) {
        x = leader(x), y = leader(y);
        if (x == y) return false;
        f[x] = y;
        siz[y] += siz[x];
        return true;
    }
    int size(int x) {return siz[leader(x)]; }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    DSU dsu(n);
    set<int> s;

    for (int i = 0; i < n - 1; i ++) {
        int u, v;
        cin >> u >> v;
        u --, v --;
        if (u == 0) s.insert(v);
        else {
            dsu.merge(u, v);
        }
    }

    if (s.size() == 1) cout << 1 << endl;
    else {
        int ans = 1e9;
        for (auto i : s) ans = min(ans, n - 1 - dsu.size(i));
        //for (auto i : s) cout << dsu.size(i) << ' ';
        cout << ans + 1 << endl;
    }

    return 0;
}