查看源代码：
20251128NOIP.md

---
title: 请输入标题
createTime: 2025/11/28
categories:
    - IT
tags:
    - OI
---

## 教练曰

- 随机生成样例只能检查显然问题。
  - 变量初始化 / 清空
- 一些相近的板子有变式
- 教得太快，忽略经典解法
  - LIS，换变量变成二分，直接维护变成线段树

## 杂

### 没有思路怎么办？

- 手玩样例
- 看数据范围
- 看部分分
- 考虑 DP（无复杂结构无修问题几乎通用）/ 贪心 / 二分 / 图论建模（特别是不明二元关系）……

### 写代码注意什么？

- 数组大小 / 数字范围（`long long`）
- 看好每个变量  
  避免相似字母（特别是表示规模的）/输入顺序混淆。
- 想好变量的依赖关系
- 写一个函数之前想好干什么
- 空间（如滚动数组？）  
  \* 空间问题比时间隐蔽，且更严重。  
  另外，“不是有效的 Win32 应用程序”也有可能是爆空间导致的。

### 如何调试？

- 可读地输出函数调用链和关键变量/数组  
  别输出错。
- 拆壳调试不同部分
- 手造极端样例
- 有些输出少的题目可能会用错误的方法部分撞对，在此时也应详尽输出小样例。

## 检查什么？

- 删干净断点，提交前重新编译运行 + `fc` 防止意外修改。
- 检查有没有多的警告。

数组足够大；

## 贪心策略

- 邻项交换 / 逐步调整
- 策略支配
- 化成更简单的贪心之后根据额外条件微调
- 反悔贪心（设计反悔堆）

注：复杂策略时用 `set` 可能比 `priority_queue` 更好。

## DP

### DP 策略

- 设计状态很重要
  - 遇到无法处理的地方，就把它加入状态。

### DP 的优化技巧

- 滚动数组
- 推式子
  - 分离变量
  - 前缀和化
  - 求和化简
    - 求和换序
    - 艾弗森括号
  - 数据结构维护（线段树/单调队列）
- 决策单调性
- 结合贪心

## 顺序无关或单调数列

首先，若顺序无关，可以指定一个顺序。很多贪心是这么运作的。

其次可以桶化。例如统计长度为 $n$，值属于 $[1,m]$ 的严格单调数列，即为 $\displaystyle\binom{n}{m}$。

## 线段树

线段树空间开四倍。

记得在合适位置 `pushup` / `pushdown`

## Tarjan

边双连通分量写法和强连通分量不一样。

:::details 比较（简单的部分不作比较，无向图最好记录边 ID）
```cpp
int dfn[maxn], low[maxn];
int dft;

void tarjan(int u) {
    dft++;
    dfn[u] = low[u] = dft;

    for (int v: G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (!co[v]) {
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u]==low[u]) {
    if (fa==-1 || low[u]>dfn[f]){
        ...
    }
}
```
:::

连通分量的求法也有区别，SCC 直接进栈，BCC 需要先标记桥边 ID 再做 flood fill。

有一些东西可以直接在 dfs 树上统计，不用缩点。强连通分量也一样——有些东西在 Tarjan 时可写，就不用二次搜索增加复杂性。

以及，有向图的 Tarjan 序是缩点图反图的一个拓扑序。

### 图论建模

对不明二元关系特攻。可以转成连通性问题。

## KMP

KMP 稍微记一下。不难。

:::details Code
```cpp
int n; char s[maxn];
int m; char t[maxn];
int p[maxn];
vector<int> ans;

void pre() {
    int j = 0;
    for (int i=2; i<=m; i++) {
        while (t[j+1] != t[i]) {
            j = p[j];
        }
        if (t[j+1] == t[i]) {
            j++;
        }

        p[i] = j;
    }
}

void kmp() {
    int j = 0;
    for (int i=1; i<=n; i++) {
        while (t[j+1] != s[i]) {
            j = p[j];
        }
        if (t[j+1] == s[i]) {
            j++;
        }

        if (j == m) {
            ans.push_back(i - m + 1);
            j = p[j];
        }
    }
}
```
:::

## 区间技巧

忽略重复贡献时，考虑给左端点排序，此时可以忽略贡献部分可以表成一个 $(-\infty, \max r]$ 的区间。取每个区间和 $[\max r+1, \infty)$，然后更新 $\max r$。

## 二分

灵活选择 `mid` 的上/下取整。

## 整体二分

一个大概是紫的技巧。也是与移动有关，不过是单边移动，然后同时处理多个询问。

:::details Code
```cpp
int cur;
void shift(int d) {
    if (d > cur) {
        for (int i=cur+1, i<=d; i++) {
            add(cur);
        }
    } else {
        for (int i=d+1; i<=cur; i++) {
            del(cur);
        }
    }
}

void solve(int l, int r, const vector<int> items) {
    int mid = (l + r) / 2;
    shift(mid);

    vector<int> lv, rv;
    for (int i: items) {
        if (checkl(i)) { 
            lv.push_back(i);
        } else {
            rv.push_back(i);
        }
    }

    solve(l, ..., lv);
    solve(..., r, rv);
}
```
:::

若 `add` 和 `del` 是 $T_a$，`check` 是 $T_c$，则时间为 $T_a n \log n + T_c \log n$。

## 其他 trick

曼哈顿/切比雪夫距离互转。

序列往左加往右加等价于拆成两个子列，翻转一个之后拼起来。