abc 321 D

二分(O(n * logm))或者双指针(O(n + m))，时间复杂度都足够
这道题双指针只比二分快一点点

// 二分
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

    ll ans = 0;
    sort(b.begin(), b.end());

    vector<ll> s(m + 1);
    for (int i = 1; i <= m; i ++) s[i] = s[i - 1] + b[i - 1];
    ll cnt = 0;
    for (int i = 0; i < n; i ++) {
        auto t = lower_bound(b.begin(), b.end(), p - a[i]) - b.begin();
        cnt += m - t;
        ans += s[t] + a[i] * t;
    }

    ans += cnt * p;

    cout << ans << endl;

    return 0;
}

//双指针
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

    ll ans = 0;
    sort(b.begin(), b.end());
    sort(a.begin(), a.end());

    vector<ll> s(m + 1);
    for (int i = 1; i <= m; i ++) s[i] = s[i - 1] + b[i - 1];
    ll cnt = 0;
    for (int i = n - 1, j = 0; i >= 0; i --) {
        while (j < m && b[j] + a[i] < p) j ++ ;
        ans += s[j] + a[i] * j;
        cnt += m - j;
    }

    ans += cnt * p;

    cout << ans << endl;

    return 0;
}

abc 320 D

BFS
用不着判断是否有点会得出两种坐标
并且限定所有点的坐标在一个区间内，没有必要开long long

// 用这样的方式存边更方便一点，不用开两个队列了
std::vector<std::vector<std::array<int, 3>>> adj(N);

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> PLL;

const ll inf = 1e18;
const PLL Default = {inf, inf};
const PLL un = {-inf, -inf};

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

    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    vector<vector<PLL>> val(n);
    for (int i = 0; i < m; i ++) {
        int a, b;
        cin >> a >> b;
        a --, b --;
        ll dx, dy;
        cin >> dx >> dy;
        adj[a].push_back(b), val[a].push_back({dx, dy});
        adj[b].push_back(a), val[b].push_back({-dx, -dy});
    }
    vector<PLL> coor(n, {inf, inf});
    queue<int> q;
    q.push(0);
    queue<PLL> dot;
    dot.push({0, 0});

    while (q.size()) {
        auto t = q.front();
        q.pop();
        auto [x, y] = dot.front();
        dot.pop();

        if (coor[t] != Default && coor[t] != un) continue;
        coor[t] = {x, y};
        for (int j = 0; j < adj[t].size(); j ++) {
            int i = adj[t][j];
            q.push(i);
            int dx = val[t][j].first, dy = val[t][j].second;
            dot.push({dx + x, dy + y});
        }
    }

    for (int i = 0; i < n; i ++) {
        if (coor[i] == un || coor[i] == Default) cout << "undecidable\n";
        else cout << coor[i].first << ' ' << coor[i].second << '\n';
    }

    return 0;
}

abc 319 D

二分，第一眼没看出来，看出来后又想在check中用前缀和与二分算每行的界限
结果没处理好边界，TLE了
不过如果用二分加前缀和的话，时间复杂度会更高，没有必要

abc 318 D

状态压缩DP
状态 111111 是包括状态 101111 的状态的最大值
所以状态转移时，要直接将后面的状态赋到前面的那种
然后考虑，从没有选那条边时的状态转移

其它代码都是O(2^n * n ^ 2)的，而jls的是O(2 ^ n * n)，经过了某种不知名的优化

优化和 abc 321 C 是有点像的

for (int i = 1; i < 1 << n; i ++) {
    int x = __builtin_ctz(i); // 二进制中末尾 0 的个数
    dp[i] = max(dp[i], dp[i ^ (1 << x)]);
    for (int j = x + 1; j < n; j ++ ) {
        if (i >> j & 1) {
            dp[i] = max(dp[i], dp[i ^ (1 << x) ^ (1 << j)] + adj[x][j]);
        }
    }
}

abc 317 D

背包问题
比较反直觉的是体积是席位，价值是拉票数