A.P1103 书本整理

显然的dp，dp[i][j]代表前i本书留下j本的最优答案，答案为dp[n][n - k]。

#include <bits/stdc++.h>
#define fu(a, b, c) for (ll a = b; a <= c; a++)
#define fd(a, b, c) for (ll a = b; a >= c; a--)
#define dbg(x) cout << #x << '=' << x << ' '
#define mx(a, b) a = max(a, b)
#define mn(a, b) a = min(a, b)
#define f first
#define s second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll N = 1e7;
ll t, n, m, k, ans = N;
ll x[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    pair<ll, ll> p[n + 1];
    fu(i, 1, n) cin >> p[i].f >> p[i].s;
    sort(p + 1, p + n + 1);
    ll dp[n + 1][n - k + 1];
    memset(dp, 60, sizeof dp), dp[0][0] = 0;
    fu(i, 1, n) fu(j, 1, n - k) {
        fd(i1, i - 1, max(i - k - 1, 0ll)) {
            t = i1 ? abs(p[i].s - p[i1].s) : 0;
            mn(dp[i][j], dp[i1][j - 1] + t);
        }
        mn(ans, dp[i][n - k]);
    }
    cout << ans;
}

B.P4389 付公主的背包

这题的前置知识是生成函数与多项式，这里简单写一下，不详细推。

对体积为V的物品构建生成函数\(f(x) = 1 + x^v + x^{2v} + ... = \frac{1}{1 - x^v}\)，
将所有的多项式相乘，次数对应的系数就是体积等于次数时的方案数。
直接做卷积显然会T，考虑取对数有\(\ln(\frac{1}{1 - x^v}) = \sum_{i >= 1} \frac{x^{vi}}{i}\)
那么我们就可以在\(mlogm\)时间内得到答案的对数，再多项式exp即可，套一个多项式模板就可以过，
代码等我整理完多项式模板再放。

C.CF1436E Complicated Computations

思考如何快速判断某个MEX值x能否被构造出来，只需要遍历所有
被x分隔的区间，数据结构加速一下，如果所有小于a[i]的数最后一次
出现的位置都大于a[i]上一次出现的位置，那么MEX值a[i]可以被构造。

#include <bits/stdc++.h>
#define fu(a, b, c) for (ll a = b; a <= c; a++)
#define fd(a, b, c) for (ll a = b; a >= c; a--)
#define mx(a, b) a = max(a, b)
#define mn(a, b) a = min(a, b)
#define lb(x) (x & -x)
typedef long long ll;
using namespace std;
const ll N = 1e5 + 1;
ll t, n, m, a;
ll T[N], lst[N], f[N];

void upd(ll p, ll x) {
    for (; p <= n; p += lb(p)) {
        T[p] = x;
        for (ll i = 1; i < lb(p); i <<= 1)
            mn(T[p], T[p - i]);
    }
}

ll qry(ll l, ll r) {
    ll res = 1e9;
    while (r >= l) {
        mn(res, lst[r]);
        for (--r; r - lb(r) >= l; r -= lb(r))
            mn(res, T[r]);
    }
    return res;
}

signed main() {
    cin >> n;
    fu(i, 1, n) {
        cin >> a;
        if (a ^ 1) {
            f[1] = 1;
            if (qry(1, a - 1) > lst[a])
                f[a] = 1;
        }
        upd(a, i), lst[a] = i;
    }
    fu(i, 1, n + 1) if (!f[i] && (i == 1 || qry(1, i - 1) <= lst[i])) {
        cout << i;
        return 0;
    }
    cout << n + 2;
}

D.P2491 消防

在直径上尺取合法路径，详见[https://www.cnblogs.com/lemu/p/15510766.html]B题。

#include <bits/stdc++.h>
#define fu(a, b, c) for (ll a = b; a <= c; a++)
#define fd(a, b, c) for (ll a = b; a >= c; a--)
#define mx(a, b) a = max(a, b)
#define mn(a, b) a = min(a, b)
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll N = 3e5 + 10;
ll n, m, u, v, w, k, e, d1, d2 = 1e9;
ll fa[N], d[N], l[N];
vector<pll> g[N];

void dfs(ll u, ll f) {
    fa[u] = f, k = d[u] > d[k] ? u : k;
    for (auto [v, w] : g[u])
        if (v ^ f && !l[v])
            d[v] = d[u] + w, dfs(v, u);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    fu(i, 2, n) {
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    dfs(1, 0), d[k] = 0, dfs(k, 0), e = k;
    for (ll i = k, j = k; i; j = fa[j])
        while (i && d[j] - d[i] <= m) {
            mn(d2, max(d[e] - d[j], d[i]));
            l[i] = 1, k = i, dfs(i, fa[i]);
            mx(d1, d[k] - d[i]), i = fa[i];
        }
    cout << max(d1, d2);
}

E.P7597 猜树 加强版

暴力的做法是先得到所有节点的深度，然后从根节点开始递归询问子树。
考虑优化，选择一个大小最大的子树（重儿子），询问除它以外的所有子树，
就可以通过做差得到该子树，至于怎么选，只能想到随机，越大的子树被选择
的概率越高，复杂度我不会证。

#include <bits/stdc++.h>
#define fu(a, b, c) for (ll a = b; a <= c; a++)
#define fd(a, b, c) for (ll a = b; a >= c; a--)
#define mx(a, b) a = max(a, b)
#define mn(a, b) a = min(a, b)
typedef long long ll;
using namespace std;
const int N = 5e3 + 1, M = sqrt(N - 1);
ll t, n, m, k, a, b, c, ans;
ll d[N], fa[N];
vector<ll> g[N];

inline ll q(ll x, ll y, ll z) {
    cout << "? " << x << ' ';
    if (x == 1)
        cout << y << ' ';
    cout << z << '\n';
    cin >> m;
    return m;
}

void dfs(ll u) {
    if (!g[u].size())
        return;
    ll r = g[u][rand() % g[u].size()], s = 0;
    for (ll v : g[u])
        if (d[v] == d[u] + 1) {
            fa[v] = u;
            if (v == r || !s && d[r] - d[u] == q(1, v, r) + 1) {
                s = v;
            } else {
                ll c = q(2, 0, v);
                fu(i, 1, c) {
                    cin >> a;
                    if (a ^ v)
                        g[v].emplace_back(a);
                }
                dfs(v);
            }
        }
    for (ll v : g[u])
        if (!fa[v])
            g[s].emplace_back(v);
    dfs(s);
}

int main() {
    cin >> n;
    fu(i, 2, n) {
        d[i] = q(1, 1, i);
        g[1].emplace_back(i);
    }
    dfs(1);
    cout << "!";
    fu(i, 2, n) cout << ' ' << fa[i];
}

F.CF1436D Bandit in a City

比较容易想到一个二分贪心，因为较远的父节点拥有更多的选择,
所以叶子节点优先从距离较近的父节点得到权值。注意二分可能会爆ll，
当时济南的D题也是三分被卡int128很蛋疼。

#include <bits/stdc++.h>
#define fu(a, b, c) for (ll a = b; a <= c; a++)
#define fd(a, b, c) for (ll a = b; a >= c; a--)
#define dbg(x) cout << #x << '=' << x << ' '
#define mx(a, b) a = max(a, b)
#define mn(a, b) a = min(a, b)
using namespace std;
using ll = long long;
using LL = __int128;
const ll N = 1e6;
ll t, n, m, k, w[N];
LL x[N];
vector<ll> g[N];
ll a, ok;

void dfs(ll u = 1) {
    if (!g[u].size())
        x[u] -= m;
    for (ll v : g[u])
        dfs(v), x[u] += x[v];
    if (x[u] > 0)
        ok = 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    fu(i, 2, n) cin >> a, g[a].emplace_back(i);
    fu(i, 1, n) cin >> w[i];
    ll l = -1, r = 2e14;
    while (l < r - 1) {
        m = l + r >> 1, ok = 1;
        copy(w + 1, w + n + 1, x + 1);
        dfs(), ok ? r = m : l = m;
    }
    cout << r;
}

G.P1682 过家家

并查集处理一下得到每个女生集合对应可选的男生集合，
答案就是最小可选男生集合的大小 + k，（不超过n）。

#include <bits/stdc++.h>
#define fu(a, b, c) for (ll a = b; a <= c; a++)
#define fd(a, b, c) for (ll a = b; a >= c; a--)
#define dbg(x) cout << #x << '=' << x << ' '
#define mx(a, b) a = max(a, b)
#define mn(a, b) a = min(a, b)
using namespace std;
using ll = long long;
const ll N = 251;
ll n, m, k, f, ans;
ll x[N], y[N], fa[N], a, b;
bitset<N> g[N];

ll find(ll x) {
    return fa[x] ? fa[x] = find(fa[x]) : x;
}

void u(ll x, ll y) {
    ll fx = find(x), fy = find(y);
    if (fx ^ fy)
        fa[fx] = fy, g[fy] |= g[fx];
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k >> f;
    fu(i, n + 1, 2 * n) fa[i] = -1;
    fu(i, 1, m) cin >> a >> b, g[a][b] = 1;
    fu(i, 1, f) cin >> a >> b, u(a, b);
    ans = n;
    fu(i, 1, n) mn(ans, k + (ll)g[find(i)].count());
    cout << ans;
}

H.P2803 学校选址 II

区间dp，dp[l][r][k]代表在区间l, r内建k所小学的最小距离和，k = 1时是个带权中位数问题。

#include <bits/stdc++.h>
#define fu(a, b, c) for (ll a = b; a <= c; a++)
#define fd(a, b, c) for (ll a = b; a >= c; a--)
#define dbg(x) cout << #x << '=' << x << ' '
#define mx(a, b) a = max(a, b)
#define mn(a, b) a = min(a, b)
using namespace std;
using ll = long long;
const ll N = 101;
ll n, m, k;
ll x[N], ps[N], d[N], pd[N], dp[N][N][N];

void init() { // 双指针预处理k = 1
    fu(i, 1, n - 1) {
        ll k = i; // k记录最优位置
        fu(j, i + 1, n) {
            dis += (pd[j] - pd[k]) * x[j];
            fu(k1, k + 1, j) {
                // 这里可以画个图看一下k移动时距离和的变化
                ll nx_dis = dis + (ps[k1 - 1] - ps[i - 1] - (ps[j] - ps[k1 - 1])) * d[k1];
                if (nx_dis > dis)
                    break;
                dis = nx_dis, k = k1;
            }
            dp[i][j][1] = dis;
            dbg(dp[i][j][1]);
        }
        cout << '\n';
    }
}

ll dfs(ll l, ll r, ll k) {
    if (r - l < k) // 区间内每栋楼都有一个学校
        return 0;
    if (dp[l][r][k])
        return dp[l][r][k];
    fu(m, l, r - 1) fu(i, 1, k - 1)
        mn(dp[l][r][k], dfs(l, m, i) + dfs(m + 1, r, k - i));
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    init();
    fu(i, 1, n) cin >> x[i];
    fu(i, 2, n) cin >> d[i], pd[i] = pd[i - 1] + d[i];
    cout << dfs(1, n, k);
}