查看源代码：
20251118.md

---
title: 一周训练记
createTime: 2025/11/18
categories:
    - IT
tags:
    - OI
---

## 注意策略、边界情况——[P14520 【MX-S11-T1】战争游戏](https://www.luogu.com.cn/problem/P14520)

策略确实考验注意力。需要想到一个退化情况——即有时优势方可以直接固守然后取得胜利。另外，由于忘了只有大于才能吃，我忘记看边界情况是否能取等，结果第一次提交 $\color{red}{\textbf{WA 56}}$ 了。

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn=1e5+100;
int a[maxn], s[maxn];
 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        for (int i=1; i<=n; i++) {
            cin >> a[i];
            s[i] = a[i] + s[i-1];
        }
        for (int i=1; i<=n-1; i++) {
            cout << (
                s[i] > s[n] - s[i]
                || a[i]>a[i+1] && a[i]+a[i+1]>=a[i+2] && s[i+1] > s[n] - s[i+1]
            );
        }
        cout << '\n';
    }    
    
    return 0;
}
```
:::

## 拆分问题、边界情况、`lower_bound`/`upper_bound`——[P14521 【MX-S11-T2】加减乘除](https://www.luogu.com.cn/problem/P14520)

拆分问题是很重要的。例如本题，你可以感受到每个结点 $u$ 存在一个区间 $[a_i, b_i]$，$u$ 可以被访问 $\iff x \in [a_i, b_i]$，然后问题转化为离线二维数点。

另外 `lower_bound`/`upper_bound` 的运用也需要注意。你可以手动代几个例子试一试。例如：

- 恰好有一个目标
- 有多个目标
- 没有目标
- 目标比开头小
- 目标比结尾大

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=5e5+10, maxq=1e6+10, inf=0x3f3f3f3f3f3f3f3f;
int n;
int a[maxn], p[maxn], l[maxn], r[maxn];
vector<int> G[maxn];
int ans[maxq];

struct query {
    int i, x, y;
    bool operator < (const query &b) const {
        return x < b.x;
    }
} qs[maxq];

struct point {
    int x, y;
    
    bool operator < (const point &b) const {
        return x < b.x;
    }
} points[maxn] = {
//  {0,0}, {1,-1}, {2, -3}, {2, -3}, {0, -1}, {-1, -3}
};

void dfs(int u, int add) {
    points[u] = {
        max(points[p[u]].x, l[u] - add),
        max(points[p[u]].y, -(r[u] - add))
    };
    
//  printf("#%d: add %d; x in [%d, %d]\n", u, add, points[u].x, -points[u].y);
    
    for (int v: G[u]) {
        dfs(v, add + a[u]);
    }
}

int ylsh[maxn];
int *lshend;
int ilsh(int x) {
    return upper_bound(ylsh+1, lshend, x) - ylsh - 1;
}

struct BIT {
    int t[maxn];
    
    inline int lowbit(int x) {
        return x & -x;
    }
    
    inline void add(int i, int a) {
        for (; i<=n; i+=lowbit(i)) {
            t[i] += a;
        }
    }
    
    inline int query(int i) {
        int ans = 0;
        for (; i; i-=lowbit(i)) {
            ans += t[i];
        }
        return ans;
    }
} bit;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
//  freopen("calc2.in", "r", stdin);
//  freopen("calc.out", "w", stdout);
    
    int q; cin >> n >> q;
    
    l[1] = -inf; r[1] = inf;
    for (int i=2; i<=n; i++) {
        cin >> p[i] >> l[i] >> r[i];
        G[p[i]].push_back(i);
    }
    
    for (int i=1; i<=n; i++) {
        char op;
        cin >> op >> a[i];
        if (op == '-') { a[i] = -a[i]; }
    }
    
    for (int i=1; i<=q; i++) {
        cin >> qs[i].x;
        qs[i].i = i;
        qs[i].y = -qs[i].x;
    }
    
    points[0] = {-inf, -inf};
    dfs(1, 0);
    
    sort(points+1, points+n+1);
    for (int i=1; i<=n; i++) {
        ylsh[i] = points[i].y;
    }
    sort(ylsh+1, ylsh+n+1);
    lshend = unique(ylsh+1, ylsh+n+1);
    sort(qs+1, qs+q+1);
    
    int nxp = 1;
    for (int i=1; i<=q; i++) {
        while (nxp <= n && points[nxp].x <= qs[i].x) {
//          printf("add x=%d && y=%d\n", points[nxp].x, points[nxp].y);
            bit.add(ilsh(points[nxp].y), 1);
            nxp++;
        }
        
//      printf("proc x=%d\n", qs[i].x);
        
        ans[qs[i].i] = bit.query(ilsh(qs[i].y));
    }
    
    for (int i=1; i<=q; i++) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}
```
:::

## 拆分、简化问题——[P14378 【MX-S9-T1】「LAOI-16」签到](https://www.luogu.com.cn/problem/P14378)

首先拆分问题，看看不带修怎么做。显然将 $a_i$ 正序排列，加的数倒序排列即可。

然后看看带修怎么做。每次只有一处修改，则在排序后相当于局部轮换。接下来分 $3$ 种情况：没有改动的、被轮换的、被修改的点本身。显然轮换之后的值可以预处理（毕竟只有左移、右移两种），那么转换成一个 RMQ 问题。

我因为想练线段树所以写了线段树，实际上可以用 ST 表。

题解的分段过于复杂，这凸显出简化问题的重要性（事实上但凡是大分段写着都很烦）。

另外复制代码记得改好，不要复制完 `max` 忘记改成 `min` 了。

:::details Code
```cpp
// 糖：忘记排序/修改……
// 糖：分类忘分一段
// 糖：右移无视空位导致下标额外 +1 

#include <bits/stdc++.h>
using namespace std;

inline int max4(int a, int b, int c, int d) {
    return max(max(a, b), max(c, d));
}

inline int min4(int a, int b, int c, int d) {
    return min(min(a, b), min(c, d));
}

const int maxn = 5e5+10, inf = 0x3f3f3f3f;

int n, k, q;
int a[maxn], asort[maxn];

struct color {
    int b, c;
    bool operator < (const color &x) const {
        return c > x.c;
    }
} co[maxn];

int add[maxn];
int v[maxn], lsv[maxn], rsv[maxn];

struct mxst {
    int t[4*maxn];
    
    inline int md(int x, int y) { return (x+y)>>1; }
    inline int lc(int x) { return x<<1; }
    inline int rc(int x) { return (x<<1)|1; }
    
    void build(int tn, int tl, int tr, int *a){
        if (tl == tr) {
            t[tn] = a[tl];
            return;
        }
        
        int mid = md(tl, tr);
        build(lc(tn), tl, mid, a);
        build(rc(tn), mid+1, tr, a);
        t[tn] = max(t[lc(tn)], t[rc(tn)]);
    }
    
    int query(int tn, int tl, int tr, int x, int y) {
        if (tr < x || y < tl) {
            return -inf;
        }
        
        if (x <= tl && tr <= y) {
            return t[tn];
        }
        
        int mid = md(tl, tr);
        return max(
            query(lc(tn), tl, mid, x, y),
            query(rc(tn), mid+1, tr, x, y)
        );
    }
} mxv, lsmxv, rsmxv;

struct mnst {
    int t[4*maxn];
    
    inline int md(int x, int y) { return (x+y)>>1; }
    inline int lc(int x) { return x<<1; }
    inline int rc(int x) { return (x<<1)|1; }
    
    void build(int tn, int tl, int tr, int *a){
        if (tl == tr) {
            t[tn] = a[tl];
            return;
        }
        
        int mid = md(tl, tr);
        build(lc(tn), tl, mid, a);
        build(rc(tn), mid+1, tr, a);
        t[tn] = min(t[lc(tn)], t[rc(tn)]);
    }
    
    int query(int tn, int tl, int tr, int x, int y) {
        if (tr < x || y < tl) {
            return inf;
        }
        
        if (x <= tl && tr <= y) {
            return t[tn];
        }
        
        int mid = md(tl, tr);
        return min(
            query(lc(tn), tl, mid, x, y),
            query(rc(tn), mid+1, tr, x, y)
        );
    }
} mnv, lsmnv, rsmnv;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> k >> q;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        asort[i] = a[i];
    }
    sort(asort+1, asort+n+1);
    
    for (int i=1; i<=k; i++) {
        cin >> co[i].b;
    }
    for (int i=1; i<=k; i++) {
        cin >> co[i].c;
    }
    sort(co+1, co+k+1);
    
    int tot=0;
    for (int i=1; i<=k; i++) {
        while (co[i].b--) {
            tot++;
            add[tot] = co[i].c;
//          printf("+%d\n", add[i]);
        }
    }
    
    for (int i=1; i<=n; i++) {
        v[i] = asort[i] + add[i];
        lsv[i] = asort[i] + add[i-1];
        rsv[i] = asort[i] + add[i+1];
//      printf(":%d,%d,%d\n", v[i], lsv[i], rsv[i]);
    }
    
    mxv.build(1, 1, n, v);
    lsmxv.build(1, 1, n, lsv);
    rsmxv.build(1, 1, n, rsv);
    mnv.build(1, 1, n, v);
    lsmnv.build(1, 1, n, lsv);
    rsmnv.build(1, 1, n, rsv);
    
//  printf("now: %d - %d\n", mxv.query(1, 1, n, 1, n), mnv.query(1, 1, n, 1, n));
    
    while (q--) {
        int x, v; cin >> x >> v;
        int src = lower_bound(asort+1, asort+n+1, a[x]) - asort;
            
//      printf("sorted: %d->%d\n", src, dst);
        if (a[x] == v) {
            cout << mxv.query(1, 1, n, 1, n) - mnv.query(1, 1, n, 1, n) << '\n';
        } else if (a[x] > v) {
            int dst = lower_bound(asort+1, asort+n+1, v) - asort;
            int mx = max4(
                mxv.query(1, 1, n, 1, dst-1),
                rsmxv.query(1, 1, n, dst, src-1),
                v + add[dst],
                mxv.query(1, 1, n, src+1, n)
            ), mn = min4(
                mnv.query(1, 1, n, 1, dst-1),
                rsmnv.query(1, 1, n, dst, src-1),
                v + add[dst],
                mnv.query(1, 1, n, src+1, n)
            );
            cout << mx - mn << '\n';
//          printf("ans = %d - %d\n", mx, mn);
        } else {
            int dst = lower_bound(asort+1, asort+n+1, v) - asort - 1;
            int mx = max4(
                mxv.query(1, 1, n, 1, src-1),
                v + add[dst],
                lsmxv.query(1, 1, n, src+1, dst),
                mxv.query(1, 1, n, dst+1, n)
            ), mn = min4(
                mnv.query(1, 1, n, 1, src-1),
                v + add[dst],
                lsmnv.query(1, 1, n, src+1, dst),
                mnv.query(1, 1, n, dst+1, n)
            );
            cout << mx - mn << '\n';
//          printf("ans = %d - %d\n", mx, mn);
        }
    }
    
    return 0;
}
```
:::

## 贪心、`long long`——[P3545 [POI 2012] HUR-Warehouse Store](https://www.luogu.com.cn/problem/P3545)

:::details Code
```cpp
// 不开 long long 见祖宗 

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=3e5;
int a[maxn], b[maxn];

typedef pair<int, int> pii;
#define _1 first
#define _2 second

priority_queue<pii, vector<pii>, less<pii>> pq;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    for (int i=1; i<=n; i++) {
        cin >> b[i];
    }
    
    int goods = 0, ans = 0;
    for (int i=1; i<=n; i++) {
        goods += a[i];
        if (goods > b[i]) {
            goods -= b[i];
            ans++;
            pq.push({b[i], i});
        } else if (!pq.empty() && pq.top()._1 > b[i]) {
            goods += pq.top()._1 - b[i];
            pq.pop();
            pq.push({b[i], i});
        }
    }
    
    vector<int> ansv;
    while (!pq.empty()) {
        ansv.push_back(pq.top()._2);
        pq.pop();
    }
    
    sort(ansv.begin(), ansv.end());
    cout << ans << '\n';
    for (int i: ansv) {
        cout << i << ' ';
    }
    
    return 0;
}
```
:::

## 贪心、数学调整法、辨明相似变量——[P6927 [ICPC 2016 WF] Swap Space](https://www.luogu.com.cn/problem/P6927)

之前对于格式化减容量的硬盘思路错了。实际上，使用调整法（或者说邻项交换法）可以做。

假设现在剩余空间为 $s$，则先 $1$ 后 $2$，两次升级的代价分别为

$$
\begin{align*}
&\phantom{=} \Bigl( \max\{a_1 - s, 0\} \Bigr) + \Bigl( \max\{a_2 - (\max\{a_1-s, 0\} + s - (a_1-b_1)), 0 \} \Bigr) \\
&= \max\bigl\{a_2 + a_1-b_1, a_1 - s, 0 \bigr\} \\
&= a_1 + a_2 - b_1
\end{align*}
$$

同理先 $2$ 后 $1$ 的代价为 $a_1 + a_2 - b_2$，于是按照 $b_i$ 降序排列。

目前因为一个测试点不知原因输出 $0$ 所以 $\color{red}{\textbf{WA}}$。

:::details Code
```cpp
// 坑：贪心推错

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=1e6+10;

struct disk {
    int a, b;
} d1[maxn], d2[maxn];
int cnt1, cnt2;

inline bool cmp1(const disk &x, const disk &y) {
    return x.a < y.a;
}

inline bool cmp2(const disk &x, const disk &y) {
    return x.b > y.b;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    
    for (int i=1; i<=n; i++) {
        int a, b; cin >> a >> b;
        if (a <= b) {
            cnt1++;
            d1[cnt1] = {a, b};
        } else {
            cnt2++;
            d2[cnt2] = {a, b};
        }
    }
    
    sort(d1+1, d1+cnt1+1, cmp1);
    sort(d2+1, d2+cnt2+1, cmp2);
    
    int space=0, ans=0;
    for (int i=1; i<=cnt1; i++) {
        if (space < d1[i].a) {
            ans += d1[i].a - space;
            space = d1[i].a;
        }
        space += d1[i].b - d1[i].a;
    }
    
    for (int i=1; i<=cnt1; i++) {
        if (space < d2[i].a) {
            ans += d2[i].a - space;
            space = d2[i].a;
        }
        if (space < d2[i].b) {
            ans += d2[i].b - space;
            space = d2[i].b;
        }
        space -= d2[i].b;
    }
    
    cout << ans;
    
    return 0;
}
```
:::

## 贪心、简化问题、`fc`——[P8113 [Cnoi2021] 自我主义的平衡者](https://www.luogu.com.cn/problem/P8113)

:::details Code
```cpp
// 非经典田忌赛马
// 糖：多打了个空格，全 WA 了 

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 1e5+100;
int a[maxn];

signed main() {
    int n, m; cin >> n >> m;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    
    sort(a+1, a+n+1);
    int cnt1 = 0;
    for (int i=1; i<=n; i++) {
        if (a[i]*(i-1) >= cnt1*m) {
            cnt1++;
        }
    }
    
    sort(a+1, a+n+1, greater<int>());
    int cnt2 = 0;
    for (int i=1; i<=n; i++) {
        if (a[i]*(i-1) >= cnt2*m) {
            cnt2++;
        }
    }
    
    printf("%.2f %.2f", cnt1*m*1./n, cnt2*m*1./n);
    
    return 0;
}
```
:::

## 发现性质、简化做法——[P14379 【MX-S9-T2】「LAOI-16」摩天大楼](https://www.luogu.com.cn/problem/P14379?contestId=287506)

试了两种不同的做法。但是写挂了 QwQ。

## 拆分问题、化归——[P5521 [yLOI2019] 梅深不见冬](https://www.luogu.com.cn/problem/P5521)

考虑 DP，看看一个结点怎么转移。激活子结点的过程可以看作“付出代价（需要梅花）+获得回馈（余下梅花）”，设激活结点 $i$ 需要 $f(i)$，则回馈为 $g(i) = f(i) - w_i$。

由熟知结论
- $f(i) \le g(i)$ 在前，按 $f(i)$ 升序 {style="color:gray;"}
- **$f(i) > g(i)$ 在后，按 $g(i)$ 降序**

然后依题意模拟 + DP 即可，注意还需要激活当前结点、回收子结点。

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+100;
vector<int> G[maxn];
int p[maxn], w[maxn];

int f[maxn]/*放梅花*/, c[maxn]/*留多余下梅花*/, ans[maxn]; 

bool cmp(int x, int y) {
    if (c[x]>f[x] && c[y]<f[y]) {
        return true;
    } else if (c[x]<f[x] && c[y]>f[y]) {
        return false;
    } else if (c[x]>f[x]) {
        return f[x] < f[y];
    } else {
        return c[x] > c[y];
    }
}

void dp(int u) {
    for (int v: G[u]) {
        dp(v);
    }
    
    sort(G[u].begin(), G[u].end(), cmp);
    
    for (int v: G[u]) {
        if (f[v] > c[u]) {
            f[u] += f[v] - c[u];
            c[u] = c[v];
        } else {
            c[u] += c[v] - f[v];
        }
    }
    
    if (w[u] > c[u]) {
        f[u] += w[u] - c[u];
        c[u] = 0;
    } else {
        c[u] -= w[u];
    }
    
    for (int v: G[u]) {
        c[u] += w[v];
    }
    
//  printf("f(%d)=%d, c(%d)=%d\n", u, f[u], u, c[u]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    for (int i=2; i<=n; i++) {
        cin >> p[i];
        G[p[i]].push_back(i);
    }
    for (int i=1; i<=n; i++) {
        cin >> w[i];
    }
    
    dp(1);
    
    for (int i=1; i<=n; i++) {
        cout << f[i] << ' ';
    }
    
    return 0;
}
```
:::

## 双倍经验——[P4053 [JSOI2007] 建筑抢修](https://www.luogu.com.cn/problem/P4053)

时间就是金钱。把时间看成货物，实际上就是一个典中典反悔贪心。

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=15e4+10;

struct building {
    int t1, t2;
    
    bool operator < (const building &b) const {
        return t2 < b.t2;
    }
} bd[maxn];

priority_queue<int, vector<int>, less<int>> pq;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> bd[i].t1 >> bd[i].t2;
    }
    
    sort(bd+1, bd+n+1);
    
    int free=0, ans=0;
    for (int i=1; i<=n; i++) {
        free += bd[i].t2 - bd[i-1].t2;
        if (free >= bd[i].t1) {
            free -= bd[i].t1;
            pq.push(bd[i].t1);
            ans++;
        } else if (!pq.empty() && bd[i].t1 < pq.top()) {
            free += pq.top() - bd[i].t1;
            pq.pop();
            pq.push(bd[i].t1); 
        }
    }
    
    cout << ans;
    
    return 0;
}
```
:::

## 先合法再最优——[P6411 [COCI 2008/2009 #3] MATRICA](https://www.luogu.com.cn/problem/P6411)

:::details Code (90pts)
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=3e4+10, maxk=30;

int n;
int col[maxn];

struct rule {
    char c;
    int a;
    
    inline bool operator < (const rule &b) const {
        return c < b.c;
    }
} rules[maxk];

struct block {
    int l, r;
    char c;
    
    inline bool operator < (const block &b) const {
        return l < b.l;
    }
};

char diag[maxn];
vector<block> blk[maxn];
int cur_diag=1, x=1, y=2;

void add_diag(char c) {
    diag[cur_diag] = c;
    cur_diag++;
}

int add(int a, char c) {
    int len = min(a/2, n-y+1);
    blk[x].push_back({y, y+len-1, c});
    
    y += len;
    if (y > n) {
        x++;
        y = x+1;
    }
    
    return len * 2;
}

char get(int x, int y) {
    if (x == y) {
        return diag[x];
    }
    
    if (x > y) {
        swap(x, y); 
    }
    
    return (upper_bound(
        blk[x].begin(),
        blk[x].end(),
        block{y, 0, '#'}
    ) - 1) -> c;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int k; cin >> n >> k;
    
    int odd=0;
    for (int i=1; i<=k; i++) {
        cin >> rules[i].c >> rules[i].a;
        
        odd += rules[i].a & 1;
        if (odd > n) {
            cout << "IMPOSSIBLE";
            return 0;
        }
    }
    sort(rules+1, rules+k+1);
    
    for (int i=1; i<=k; i++) {
        char c = rules[i].c;
        int a = rules[i].a;
        
        while (a) {
            if (x >= cur_diag) {
                add_diag(c);
                a--;
            }
            if (a % 2) {
                add_diag(c);
                a--;
            }
            
            a -= add(a, c);
        }
    }
    
//  for (int i=1; i<=n; i++) {
//      for (block &b: blk[i]) {
//          printf("(%d,%d,%c) ", b.l, b.r, b.c);
//      }
//      printf("\n");
//  }

    int p; cin >> p;
    for (int i=1; i<=p; i++) {
        cin >> col[i];
    }
    for (int x=1; x<=n; x++) {
        for (int i=1; i<=p; i++) {
            cout << get(x, col[i]);
        }
        cout << '\n';
    }
    
    return 0;
}
```
:::

## 拆分问题——[P6412 [COCI 2008/2009 #3] BST](https://www.luogu.com.cn/problem/P6412)

拆分成：

1. 找到插入点
2. 获取深度

维护插入点区间，用类似珂朵莉树的手法。

:::details
```cpp
#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;

struct inspt {
    int l, r;
    int dep;
    
    bool operator < (const inspt &b) const {
        return l < b.l;
    }
};

set<inspt> bst;

long long c;

void insert(int x) {
    auto it = bst.upper_bound({x, 0, 0});
    it--;
    
    int l=it->l, r=it->r, dep=it->dep;
    
    c += dep;
    bst.erase(it);
    
    if (l <= x-1) {
        bst.insert({l, x-1, dep+1});
    }
    if (x+1 <= r) {
        bst.insert({x+1, r, dep+1});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    bst.insert({-inf, inf, 0});
    
    for (int i=1; i<=n; i++) {
        int a; cin >> a;
        insert(a);
        cout << c << '\n';
    }
    
    return 0;
}
```
:::

## 数据范围提示做法——[P4302 [SCOI2003] 字符串折叠](https://www.luogu.com.cn/problem/P4302)

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=128;
char s[maxn];
int f[maxn][maxn];

int declen(int x) {
    int ans=0, p10=1;
    while (x > p10-1) {
        p10 *= 10;
        ans++;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> (s+1);
    int n = strlen(s+1);
    
    memset(f, 0x3f, sizeof(f));
    for (int i=1; i<=n; i++) {
        f[i][i] = 1;
    }
    
    for (int len=2; len<=n; len++) {
        for (int l=1; l+len-1<=n; l++) {
            int r = l+len-1;
            
            // 不折叠
            for (int mid=l; mid<r; mid++) {
                f[l][r] = min(f[l][r], f[l][mid]+f[mid+1][r]);
            }
            
            // 折叠
            for (int fold=1; fold<=len/2; fold++) {
                if (len % fold) {
                    continue;
                }
                
                for (int i=l+fold; i<=r; i++) {
                    if (s[i] != s[i-fold]) {
                        goto nxt;
                    }
                }
                
//              printf("[%d, %d] can fold %d\n", l, r, fold);
                f[l][r] = min(f[l][r], declen(len/fold)+2+f[l][l+fold-1]);
            
                nxt:;
            }
            
//          printf("f(%d, %d) = %d\n", l, r, f[l][r]);
        }
    }
    
    cout << f[1][n];
    
    return 0;
}
```
:::

## [P3389 【模板】高斯消元法](https://www.luogu.com.cn/problem/P3389)

数学拓展班恰好讲了，遂做。

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=128;
int n;
double a[maxn][maxn], b[maxn];
double x[maxn];

inline void subx(int i, int j, double k) {
    for (int c=1; c<=n; c++) {
        a[i][c] -= a[j][c] * k;
    }
    b[i] -= b[j] * k;
}

inline void swp(int i, int j) {
    for (int c=1; c<=n; c++) {
        swap(a[i][c], a[j][c]);
    }
    swap(b[i], b[j]);
}

bool gauss() {
    for (int i=1; i<=n; i++) {
        int row=-1;
        for (int r=i; r<=n; r++) {
            if (abs(a[r][i]) > 1e-6) {
                row = r;
                break;
            }
        }

        if (row == -1) {
            return false;
        }

        if (i != row) {
            swp(i, row);
        }

        for (int j=i+1; j<=n; j++) {
            subx(j, i, a[j][i]/a[i][i]);
        }
    }

    for (int i=n; i>=1; i--) {
        double t=b[i];
        for (int j=i+1; j<=n; j++) {
            t -= a[i][j] * x[j];
        }
        x[i] = t / a[i][i];
    }

    return true;
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            cin >> a[i][j];
        }
        cin >> b[i];
    }

    if (!gauss()) {
        cout << "No Solution";
        return 0;
    }

    for (int i=1; i<=n; i++) {
        printf("%.2f\n", x[i]);
    }

    return 0;
}
```
:::

## 树形 DP 套贪心、调整、变量大小关系、交叉主项公式、树形父子依赖——[P3574 [POI 2014] FAR-FarmCraft](https://www.luogu.com.cn/problem/P3574)

树形算法看清楚父子之间的依赖，别搞错了。

另外，根据变量大小关系，我们有交叉主项公式简化贪心调整：

:::lemma 交叉主项公式
若 $a \ge c, b \le d$，则
$$\operatorname{cmp}(\max\{a, b\}, \max\{c, d\}) = \operatorname{cmp}(a, d)$$
其中 $\operatorname{cmp}(a, b) = \operatorname{sgn}(a-b) = \begin{cases}1,&a>b\\0,&a=b\\-1,&a<b\end{cases}$
:::

:::details
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5+10;
int n;
int c[maxn];
vector<int> G[maxn];
int siz[maxn];

int f[maxn];  // f: 从刚刚进入到全部安装完成 

bool cmp(int x, int y) {
    return 2*siz[x] - f[x] < 2*siz[y] - f[y];
}

void dp(int u, int p) {
    siz[u] = 1;
    for (int v: G[u]) {
        if (v != p) {
            dp(v, u);
            siz[u] += siz[v];
        }
    }
    
    sort(G[u].begin(), G[u].end(), cmp);
    int drive=0;
    for (int v: G[u]) {
        if (v == p) {
            continue;
        }
        
        f[u] = max(f[u], drive+1+f[v]);
        drive += 2 * siz[v];
    }
    
    if (u == 1) {
        f[u] = max(f[u], 2*n-2+c[u]);
    } else {
        f[u] = max(f[u], c[u]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> c[i]; 
    }
    for (int i=1; i<=n-1; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u); 
    }
    
    dp(1, -1);
    
    cout << f[1];
    
    return 0;
}
```
:::

## 树上背包——[P1272 重建道路](https://www.luogu.com.cn/problem/P1272)

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=160;
int n, p;
vector<int> G[maxn];
int f[maxn][maxn];

void dp(int u, int pa) {
    f[u][1] = 0;
    
    for (int v: G[u]) {
        if (v == pa) {
            continue;
        }
        
        dp(v, u);
        
        for (int i=n; i>=1; i--) {
            f[u][i]++;
            for (int j=1; j<=i-1; j++) {
                f[u][i] = min(f[u][i], f[u][i-j]+f[v][j]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    memset(f, 0x3f, sizeof(f));
    
    cin >> n >> p;
    for (int i=1; i<=n-1; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    dp(1, -1);
    
    int ans = f[1][p];
    for (int i=1; i<=n; i++) {
        ans = min(ans, f[i][p]+1);
    }
    cout << ans;
    
    return 0;
}
```
:::

## `long long`——[P4158 [SCOI2009] 粉刷匠](https://www.luogu.com.cn/problem/P4158)

:::details
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=60, maxt=3000;
int n, m, t;
int f[maxn][maxn][maxt];
char s[maxn][maxn];
int sum[maxn][maxn];

inline int paint(int row, int l, int r) {
    int ones = sum[row][r] - sum[row][l-1];
    return max(ones, r-l+1-ones);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> t;
    for (int i=1; i<=n; i++) {
        cin >> (s[i]+1);
    }
    
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            sum[i][j] = sum[i][j-1] + (s[i][j]=='1');
        }
    }
    
    // O(n^3 T)
    for (int i=1; i<=n; i++) {
        for (int k=0; k<=t; k++) {
            f[i][0][k] = f[i-1][m][k];
        }
        
        for (int j=1; j<=m; j++) {
            for (int k=0; k<=t; k++) {
                f[i][j][k] = f[i][j-1][k];
            }
            
            for (int s=1; s<=j; s++) {
                for (int k=1; k<=t; k++) {
                    f[i][j][k] = max(f[i][j][k], 
                        f[i][s-1][k-1] + paint(i, s, j)
                    );
                }
            }
        }
    }
    
    cout << f[n][m][t];
    
    return 0;
}
```
:::

## 拆分问题、相似变量混淆、线段树模板、分段调试——[P2894 [USACO08FEB] Hotel G](https://www.luogu.com.cn/problem/P2894)

维护最长连续空闲段。另注意到第一个连续空闲 $x$ 房间的结尾 $=$ 第一个使得 $[1,i]$ 有 $x$ 个房间的 $i$。打个倍增就好了。（我偷懒打了 $O(n \log^2 n)$ 的，也很快）

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=5e4+100, maxlogn=16;
int n, m;

struct node {
    int siz, l, r;
    int len;
    bool clr;
};

inline node merge (const node &a, const node &b) {
    if (a.clr && b.clr) {
        return {0, 0, 0, a.len+b.len, true};
    } else if (a.clr) {
        return {
            b.siz, a.len+b.l, b.r,
            a.len+b.len, false
        };
    } else if (b.clr) {
        return {
            a.siz, a.l, a.r+b.len,
            a.len+b.len, false
        };
    } else {
        return {
            max(max(a.siz, b.siz), a.r+b.l),
            a.l, b.r, a.len+b.len, false
        };
    }
}

inline void fillnode(node &a) {
    a.siz = a.l = a.r = a.clr = 0;
}

inline int value(const node &a) {
    return a.clr? a.len: max(max(a.l, a.r), a.siz);
}

char NORM=0, CLR=1, FILL=2;

struct segtree {
    node tree[maxn*4];
    char lz[maxn*4];
    
    inline int lc(int x) { return x<<1; }
    inline int rc(int x) { return (x<<1)|1; }
    inline int md(int x, int y) { return (x+y)>>1; }
    
    void build(int tn, int tl, int tr) {
        tree[tn].len = tr - tl + 1;
        if (tl != tr) {
            int mid = md(tl, tr);
            build(lc(tn), tl, mid);
            build(rc(tn), mid+1, tr);
        }
    }
    
    void pushup(int tn) {
        tree[tn] = merge(tree[lc(tn)], tree[rc(tn)]);
        
//      if (clr[lcn] && clr[rcn]) {
//          clr[tn] = true;
//      } else if (clr[lcn]) {
//          clr[tn] = false;
//          siz[tn] = siz[rcn];
//          l[tn] = mid-tl+1 + l[rcn];
//          r[tn] = r[rcn];
//      } else if (clr[rcn]) {
//          clr[tn] = false;
//          siz[tn] = siz[lcn];
//          r[tn] = r[lcn] + tr-mid;
//          l[tn] = l[lcn];
//      } else {
//          clr[tn] = false;
//          siz[tn] = max(siz[lcn], siz[rcn], r[lcn]+l[rcn]);
//          l[tn] = l[lcn];
//          r[tn] = r[rcn];
//      }
    }
    
    void pushdown(int tn) {
        int lcn=lc(tn), rcn=rc(tn);
        if (lz[tn] == CLR) {
            lz[tn] = NORM;
            tree[lcn].clr = tree[rcn].clr = true;
            lz[lcn] = lz[rcn] = CLR;
        } else if (lz[tn] == FILL) {
            lz[tn] = NORM;
            fillnode(tree[lcn]);
            fillnode(tree[rcn]);
            lz[lcn] = lz[rcn] = FILL;
        }
    }
    
    node query(int tn, int tl, int tr, int x, int y) {
        if (tr<x || y<tl) {
            return {0, 0, 0, 0, 0};
        }
        
        if (x<=tl && tr<=y) {
//          printf("[%d,%d]: [%d] %d-%d-%d\n", tl, tr, tree[tn].clr, tree[tn].l, tree[tn].siz, tree[tn].r);
            return tree[tn];
        }
        
//      printf("to #%d[%d, %d]\n", tn, tl, tr);
        
        pushdown(tn);
        
        int mid = md(tl, tr);
        
//      node no = merge(
//          query(lc(tn), tl, mid, x, y),
//          query(rc(tn), mid+1, tr, x, y)
//      );
//      printf("[%d,%d]: [%d] %d-%d-%d\n", tl, tr, no.clr, no.l, no.siz, no.r);
//      return no;
        
        return merge(
            query(lc(tn), tl, mid, x, y),
            query(rc(tn), mid+1, tr, x, y)
        );
    }
    
    void clear(int tn, int tl, int tr, int x, int y) {
        if (tr<x || y<tl) {
            return;
        }
        
        if (x<=tl && tr<=y) {
            tree[tn].clr = true;
            lz[tn] = CLR;
            return;
        }
        
        pushdown(tn);
        
        int mid = md(tl, tr);
        clear(lc(tn), tl, mid, x, y);
        clear(rc(tn), mid+1, tr, x, y);
        pushup(tn);
        
//      printf("[%d,%d]: [%d] %d-%d-%d\n", tl, tr, tree[tn].clr, tree[tn].l, tree[tn].siz, tree[tn].r);
    }
    
    void fill(int tn, int tl, int tr, int x, int y) {
        if (tr<x || y<tl) {
            return;
        }
        
        if (x<=tl && tr<=y) {
            fillnode(tree[tn]);
            lz[tn] = FILL;
            return;
        }
        
        pushdown(tn);
        
        int mid = md(tl, tr);
        fill(lc(tn), tl, mid, x, y);
        fill(rc(tn), mid+1, tr, x, y);
        pushup(tn);
        
//      printf("[%d,%d]: [%d] %d-%d-%d\n", tl, tr, tree[tn].clr, tree[tn].l, tree[tn].siz, tree[tn].r);
    }
} sgt;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    sgt.build(1, 1, n);
    sgt.tree[1].clr = true;
    sgt.lz[1] = CLR;
    
//  while (m--) {
//      char c; int x, y;
//      cin >> c >> x >> y;
//      if (c == 'f') {
//          sgt.fill(1, 1, n, x, y);
//      } else if (c == 'c') {
//          sgt.clear(1, 1, n, x, y);
//      } else if (c == 'q') {
//          node no = sgt.query(1, 1, n, x, y);
//          printf("%d\n", no.clr? no.len: max(max(no.l, no.r), no.siz));
//      }
//  }

    while (m--) {
        int i; cin >> i;
        if (i == 1) {
            int x; cin >> x;
            int r=0;
            for (int j=maxlogn; j>=0; j--) {
                if (r + (1<<j) > n) {
                    continue;
                }
                if (value(sgt.query(1, 1, n, 1, r+(1<<j))) < x) {
                    r += 1<<j;
                }
            }
            
            if (r == n) {
                cout << "0\n";
            } else {
                cout << r-x+2 << '\n';
                sgt.fill(1, 1, n, r-x+2, r+1);
            }
        } else {
            int x, y; cin >> x >> y;
            sgt.clear(1, 1, n, x, x+y-1);
        }
    }
    
    return 0;
}
```
:::

## 树链剖分、线段树、四倍数组、`long long`——[P3178 [HAOI2015] 树上操作](https://www.luogu.com.cn/problem/P3178)

仍然建议数据结构不带壳先测一遍。

板子记熟。

另外要注意与数据范围有关的细枝末节。

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
typedef long long ll;

int n, m;
vector<int> G[maxn];
int aa[maxn];

int p[maxn], siz[maxn], wson[maxn];
void dfs1(int u, int fa) {
    p[u] = fa;
    siz[u] = 1;
    int wsiz = 0;
    
    for (int v: G[u]) {
        if (v == fa) {
            continue;
        }
        
        dfs1(v, u);
        siz[u] += siz[v];
        
        if (siz[v] > wsiz) {
            wsiz = siz[v];
            wson[u] = v;
        }
    }
}

int dfn[maxn], idfn[maxn], top[maxn];
int dft;

void dfs2(int u, int tp) {
    dft++;
    dfn[u] = dft;
    idfn[dft] = u;
    top[u] = tp;
    
//  printf("%d: dfn=%d, top=%d\n", u, dft, tp);
    
    if (wson[u]) {
        dfs2(wson[u], tp);
    }
    
    for (int v: G[u]) {
        if (v == wson[u] || v == p[u]) {
            continue;
        }
        
        dfs2(v, v);
    }
}

struct segtree {
    ll a[maxn*4], lz[maxn*4];
    
    inline int md(int x, int y) { return (x+y)>>1; }
    inline int lc(int x) { return x<<1; }
    inline int rc(int x) { return (x<<1)|1; }
    
    inline void pushup(int tn) {
        a[tn] = a[lc(tn)] + a[rc(tn)];
    }
    
    inline void pushdown(int tn, int tl, int tr) {
        int lcn=lc(tn), rcn=rc(tn), mid=md(tl,tr);
        a[lcn] += lz[tn]*(mid-tl+1); a[rcn] += lz[tn]*(tr-mid);
        lz[lcn] += lz[tn]; lz[rcn] += lz[tn];
        lz[tn] = 0;
    }
    
    void build(int tn, int tl, int tr) {
        if (tl == tr) {
            a[tn] = aa[idfn[tl]];
            return;
        }
        
        int mid = md(tl, tr);
        build(lc(tn), tl, mid);
        build(rc(tn), mid+1, tr);
        pushup(tn);
//      printf("#%d[%d, %d] -> %d\n", tn, tl, tr, a[tn]);
    }
    
    void add(int tn, int tl, int tr, int x, int y, ll w) {
        if (tr<x || y<tl) {
            return;
        }
        
        if (x<=tl && tr<=y) {
            a[tn] += w * (tr-tl+1);
            lz[tn] += w;
            return;
        }
        
        pushdown(tn, tl, tr);
        
        int mid = md(tl, tr);
        add(lc(tn), tl, mid, x, y, w);
        add(rc(tn), mid+1, tr, x, y, w);
        pushup(tn);
    }
    
    ll query(int tn, int tl, int tr, int x, int y) {
        if (tr<x || y<tl) {
//          printf("query #%d[%d, %d] -> %d (empty)\n", tn, tl, tr, 0);
            return 0;
        }
        
        if (x<=tl && tr<=y) {
//          printf("query #%d[%d, %d] -> %d (contain)\n", tn, tl, tr, a[tn]);
            return a[tn];
        }
        
        pushdown(tn, tl, tr);
        
        int mid = md(tl, tr);
        ll ret = (query(lc(tn), tl, mid, x, y)
                + query(rc(tn), mid+1, tr, x, y));
//      printf("query #%d[%d, %d] -> %d\n", tn, tl, tr, ret);
        return ret;
    }
} sgt;

ll query(int u) {
    ll ans=0;
    while (u) {  // p[1] = 0
        ans += sgt.query(1, 1, n, dfn[top[u]], dfn[u]);
        u = p[top[u]];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        cin >> aa[i];
    }
    for (int i=1; i<=n-1; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    dfs1(1, 0);
    dfs2(1, 1);
    sgt.build(1, 1, n);
    
    while (m--) {
        int op; cin >> op;
        if (op == 1) {
            int x, a; cin >> x >> a;
            sgt.add(1, 1, n, dfn[x], dfn[x], a);
        } else if (op == 2) {
            int x, a; cin >> x >> a;
            sgt.add(1, 1, n, dfn[x], dfn[x]+siz[x]-1, a);
        } else if (op == 3) {
            int x; cin >> x;
            cout << query(x) << '\n';
        }
    }
    
    return 0;
}
```
:::