机试笔记

创建：2026/9/5 算法数据结构

机试开卷资料。

单调栈：维护一个单调递增或单调递减的栈
常用于：下一个更大元素；下一个更小元素；左边第一个更大/更小元素；柱状图最大矩形（求当前柱子左右更矮的柱子）；每日温度

// a[1..n]
// ans[i] = i右边第一个比a[i]大的位置，不存在则为-1
stack<int> st;

for(int i=n;i>=1;i--) {
    // 保持栈中对应元素单调递减
    while(!st.empty() && a[st.top()]<=a[i])
        st.pop();

    if(st.empty()) ans[i]=-1;
    else ans[i]=st.top();

    st.push(i);
}

单调队列：一般用deque实现，用于维护窗口最大值/最小值
以窗口最大值为例，保持队列单调递减（当前元素大于队尾元素时弹出队尾并插入当前元素），队首永远是窗口最大值，每个元素最多进队一次、出队一次，所以总复杂度 O(n)

// a[1..n]
deque<int> q;

for(int i=1;i<=n;i++) {
    // 1. 删除已经离开窗口的元素
    while(!q.empty() && q.front() < i-k+1)
        q.pop_front();

    // 2. 保持队列对应元素单调递减
    while(!q.empty() && a[q.back()] <= a[i])
        q.pop_back();

    q.push_back(i);

    // 3. 队首就是当前窗口最大值
    if(i>=k)
        cout << a[q.front()] << " ";
}

最近公共祖先LCA（普通二叉树）

vector<int> g[N];

int lca(int u, int fa, int p, int q) {
    if(u==p || u==q) return u;

    int cnt=0, res=0;

    for(int v:g[u]) {
        if(v==fa) continue;

        int x=lca(v,u,p,q);
        if(x) {
            cnt++;
            res=x;
        }
    }

    if(cnt>=2) return u;
    return res;
}

验证BST（二叉搜索树）：BST 要求整棵左子树都小于 root，整棵右子树都大于 root
中序遍历递增：

int pre;
bool hasPre = false;

bool isValidBST(int u) {
    if(u==0) return true;

    if(!isValidBST(lc[u])) return false;

    if(hasPre && pre >= val[u]) return false;
    pre = val[u];
    hasPre = true;

    return isValidBST(rc[u]);
}

最大/小堆是完全二叉树结构
插入元素时插到末尾，然后向上调整；删除元素时将末尾元素提到堆顶，然后向下调整
priority_queue默认为大根堆；小根堆：
```
priority_queue<int, vector<int>, greater<int>> pq
```
TopK（求数组第k大元素）：小根堆，大小维护为k
合并 K 个有序链表：用小根堆维护每个链表当前头节点

并查集

const int N = 1e6+5;
int fa[N],n;
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    fa[fx]=fy;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<=n;i++) {
        fa[i]=i;
    }
    return 0;
}

树状数组（比线段树更短，适合单点修改）

ll a[N]; // a[1]->[1,1]  a[2]->[1,2] a[3]->[3,3] a[4]->[1,4] a[6]->[5,6] a[8]->[1,8]
int lowbit(int x) { // 取出 x 的最低一位1所代表的数 如lowbit(12)=4
    return x&(-x);
}
void add(int x,int k) {  // 沿着 x, x+lowbit(x), ... 往上更新（找所有包含 x 的区间）
    while(x<=n) {
        a[x]+=k;
        x+=lowbit(x);
    }
}
ll query(int x) {  // 沿着 x, x-lowbit(x), ... 往回累加（把前缀拆成若干段），求[1,x]前缀和
    ll res=0;	
    while(x>0) {
        res+=a[x];
        x-=lowbit(x);
    }
    return res;
} //[l,r] 区间和：query(r)-query(l-1)

常见设计类数据结构
MinStack 最小栈：使用两个栈，一个正常栈，另一个维护最小值，同步push/pop即可
用栈实现队列：in栈负责入队，out栈负责出队，出队时如果 out 不空，直接弹；如果 out 空，把 in 全部倒到 out
用队列实现栈：一个队列即可，push 后，把前面的元素重新放到队尾，让新元素到队首

排序
归并排序
重要应用：归并排序求逆序对

void mergeSort(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (l >= r) return;

    int mid = l + (r - l) / 2;

    mergeSort(a, l, mid, tmp);
    mergeSort(a, mid + 1, r, tmp);

    int i = l;
    int j = mid + 1;
    int k = l;

    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }

    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    for (int p = l; p <= r; p++) {
        a[p] = tmp[p];
    }
}

快速排序

void quickSort(vector<int>& nums,int l,int r)
{
    if(l>=r)
        return;

    int pivot=nums[r];

    int i=l;

    for(int j=l;j<r;j++)
    {
        if(nums[j]<pivot)
        {
            swap(nums[i],nums[j]);
            i++;
        }
    }
    swap(nums[i],nums[r]);//最后交换标杆元素

    quickSort(nums,l,i-1);
    quickSort(nums,i+1,r);
}

二分查找
lower_bound：找第一个大于等于 target 的位置

int lowerBound(vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) { //将等号去掉即为upper_bound：找第一个大于target的位置
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

二分答案

找最小的满足条件的答案：
int l = 最小可能答案;
int r = 最大可能答案;

while (l < r) {
    int mid = l + (r - l) / 2;

    if (check(mid)) {
        r = mid;
    } else {
        l = mid + 1;
    }
}

return l;

找最大的满足条件的答案：
int l = 最小可能答案;
int r = 最大可能答案;

while (l < r) {
    int mid = l + (r - l + 1) / 2; //注意这里 mid 要向上取整，否则可能死循环

    if (check(mid)) {
        l = mid;
    } else {
        r = mid - 1;
    }
}

return l;

双指针
左右指针：
求有序数组两数之和为定值，复杂度为O(n)
三数之和：先排序，枚举第一个数i，在i后面用双指针找两个数，最后去重，复杂度为O(n^2)
快慢指针与滑动窗口
和为 k 的子数组个数：前缀和+哈希表
含负数的连续子数组问题，很多时候要用前缀和 + 哈希，而不是滑动窗口
二维前缀和：pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j];

回溯
含重复元素的排列：

void backtrack(vector<int>& nums) {
    if (path.size() == nums.size()) {
        ans.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        } //若为不含重复元素的排列，去掉这三行判断
        used[i] = true;
        path.push_back(nums[i]);
        backtrack(nums);
        path.pop_back();
        used[i] = false;
    }
}

N皇后：

unordered_set<int> cols; // 同一列不能有皇后
unordered_set<int> diag1; // row - col，同一主对角线不能有皇后
unordered_set<int> diag2; // row + col，同一副对角线不能有皇后

贪心
求到达最后位置的最少跳跃次数->不需要用动态规划，O(n)就够了
```
int jump(vector<int>& nums) {
    int end = 0;// 当前这一步能覆盖的边界
    int farthest = 0;//下一步能覆盖的边界
    int steps = 0;//步数

    for (int i = 0; i < nums.size() - 1; i++) {
        farthest = max(farthest, i + nums[i]);

        if (i == end) {
            steps++;
            end = farthest;
        }
    }

    return steps;
}
```
区间问题
1. 合并区间要先排序
2. 无重叠区间（删除最少区间，使剩余区间不重叠）：按右端点排序，优先保留结束更早的区间
哈弗曼编码：
1. 将所有字符按权值放入小根堆
2. 每次取两个最小权值节点
3. 合并成新节点
4. 新节点权值=两者之和
5. 放回堆
6. 重复直到只剩一个节点
7. 左0右1生成编码

动态规划

一、基础 DP

打家劫舍：每个房子里有一定金额。你是小偷，但不能偷相邻的两家，否则会触发报警
dp[i]表示前i个房子的最大值，dp[i]=max(dp[i-1],dp[i-2]+a[i]);
背包问题：注意01背包第二层循环要倒序，因为每个物品只能选一次
最长递增子序列LIS：
解法1. O(n^2)，dp[i]表示以nums[i]结尾的最长递增子序列长度

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

解法2. O(nlogn)，贪心+二分，tails[i]表示长度为i+1的递增子序列中，最小的结尾元素，整个tails构成了最优的递增子序列

int lengthOfLIS(vector<int>& nums)
{
    vector<int> tails;
    for(int x:nums)
    {
        auto it=lower_bound(tails.begin(), tails.end(), x);
        if(it==tails.end())
            tails.push_back(x);
        else
            *it=x;
    }
    return tails.size();
}

最长公共子序列LCS
dp[i][j]=text1前i个字符和text2前j个字符的最长公共子序列长度
如果相等：
```
dp[i][j]=dp[i−1][j−1]+1
```
否则：
```
dp[i][j]=max(dp[i−1][j],dp[i][j−1])
```

区间 DP：石子合并

有一排石子，每次只能合并相邻两堆，代价为两堆石子总数，求全部合并的最小代价。

定义： $d p [l] [r]$ = 将区间 $[l, r]$ 合并成一堆的最小代价

最后一次合并一定把区间分成 $[l, k]$ 和 $[k + 1, r]$

因此：

d p [l] [r] = min_{l \leq k < r} {d p [l] [k] + d p [k + 1] [r] + s u m (l, r)}

代码框架：

vector<vector<long long>> dp(n, vector<long long>(n));
vector<long long> pre(n + 1);

for (int i = 0; i < n; i++) {
    pre[i + 1] = pre[i] + a[i];
}

for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        dp[l][r] = LLONG_MAX;
        long long sum = pre[r + 1] - pre[l];
        for (int k = l; k < r; k++) {
            dp[l][r] = min(
                dp[l][r],
                dp[l][k] + dp[k + 1][r] + sum
            );
        }
    }
}

复杂度： $O (n^{3})$

区间 DP 的识别信号：

对一个区间不断分割或合并；
最后一步枚举分割点；
状态通常为 dp[l][r]。

戳气球：枚举最后一个

这类题最关键的思想是：

“第一个被选择的元素”周围情况会变化，但“最后一个被选择的元素”两侧边界已经确定。

定义： $d p [l] [r]$ = 只处理开区间 $(l, r)$ 内气球的最大收益

若 $k$ 是最后一个被戳的气球：
$d p [l] [r] = max_{l < k < r} [d p [l] [k] + d p [k] [r] + a_{l} \cdot a_{k} \cdot a_{r}]$
这是非常经典的”换一个角度定义最后一步”。

状态压缩 DP：旅行商模型
当 $n \leq 20$ ，需要记录一个集合“哪些选过/访问过”，可以用二进制集合表示已访问节点。
定义： $d p [m a s k] [i]$ = 已经访问集合 $m a s k$ ，最后位于 $i$ 的最短距离
转移：

d p [m a s k \cup {j}] [j] = min_{i \in m a s k} [d p [m a s k] [i] + w_{i j}]

其中 $i \in m a s k, j \notin m a s k$ , 复杂度： $O (2^{n} \cdot n^{2})$

int total = 1 << n;
vector<vector<long long>> dp(
    total, vector<long long>(n, INF)
);
dp[1 << 0][0] = 0;
for (int mask = 0; mask < total; mask++) {
    for (int u = 0; u < n; u++) {
        if (!(mask & (1 << u))) continue;
        if (dp[mask][u] == INF) continue;
        for (int v = 0; v < n; v++) {
            if (mask & (1 << v)) continue;
            int nextMask = mask | (1 << v);
            dp[nextMask][v] = min(
                dp[nextMask][v],
                dp[mask][u] + w[u][v]
            );
        }
    }
}
ll ans = INF;
int full = (1 << n) - 1;
for(int i=0;i<n;i++)
    ans = min(ans, dp[full][i]); //从 0 出发，访问所有点，最后停在任意点
cout << ans << '\n';

有 n 个人和 n 个任务，cost[i][j] 表示第 i 个人做第 j 个任务的代价，每个任务只能分配一次，求最小总代价。

int total = 1 << n;
vector<ll> dp(total, INF);

dp[0] = 0;

for(int mask=0; mask<total; mask++) {
    int i = __builtin_popcount(mask);  // 用来计算一个整数的二进制表示里有多少个1, i代表当前轮到第i个人（从0开始）

    for(int j=0; j<n; j++) {
        if(mask & (1<<j)) continue;     // 任务j已经被选了

        int nextMask = mask | (1<<j);

        dp[nextMask] = min(
            dp[nextMask],
            dp[mask] + cost[i][j]
        );
    }
}

cout << dp[(1<<n)-1] << '\n';

DAG 上的动态规划

有向无环图的最长路径可以按拓扑序 DP。

定义： $d p [v]$ = 到达 $v$ 的最长路径

对于边 $u \to v$ ，转移：
$d p [v] = max (d p [v], d p [u] + w (u, v))$
为什么必须按拓扑序？因为处理 $v$ 前，需要确保所有可能转移到 $v$ 的前驱都已经处理。

DAG 上即使存在负权边，也能在线性时间内求最短路径： $O (V + E)$

单调队列优化DP

deque<int> q;
for(int i=1;i<=n;i++) {
    while(!q.empty() && q.front() < i-k)
        q.pop_front();

    if(!q.empty())
        dp[i] = a[i] + dp[q.front()];

    while(!q.empty() && dp[q.back()] >= dp[i])
        q.pop_back();

    q.push_back(i);
}

二、树形 DP 经典题

树上最大独立集：选择若干节点，要求相邻节点不能同时选择，最大化权值和。
定义：
- $d p [u] [0]$ = 不选 $u$ 时，子树最大权值
- $d p [u] [1]$ = 选择 $u$ 时，子树最大权值
  转移：
$d p [u] [1] = w_{u} + \sum_{v \in c h i l d (u)} d p [v] [0]$
因为选了 $u$ ，孩子不能选。
$d p [u] [0] = \sum_{v \in c h i l d (u)} max (d p [v] [0], d p [v] [1])$
代码：
```
vector<array<long long, 2>> dp;
vector<vector<int>> graph;
vector<int> weight;

void dfs(int u, int parent) {
    dp[u][0] = 0;
    dp[u][1] = weight[u];
    for (int v : graph[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}
```
最终答案： $max (d p [r o o t] [0], d p [r o o t] [1])$

树的直径

树的直径是任意两点之间的最长路径。
定义：
down[u]=从 u 向其子树走的最长路径
对于节点 u，经过它的最长路径由最大的两条子树路径组成。

vector<int> g[N];
int ans = 0;

int dfs(int u, int fa) {
    int mx1 = 0, mx2 = 0;  // 最长、次长向下路径
    for(int v : g[u]) {
        if(v == fa) continue;
        int d = dfs(v, u) + 1;
        if(d > mx1) {
            mx2 = mx1;
            mx1 = d;
        }
        else if(d > mx2) {
            mx2 = d;
        }
    }
    ans = max(ans, mx1 + mx2);
    return mx1;  // 向父节点只能贡献最长的一条
}

树最大路径和

节点权值可能为负，路径可以从任意节点开始和结束。
代码：

vector<int> g[N];
ll w[N];
ll ans = LLONG_MIN;

ll dfs(int u, int fa) {
    ll mx1 = 0, mx2 = 0;

    for(int v : g[u]) {
        if(v == fa) continue;

        ll x = max(0LL, dfs(v, u));

        if(x > mx1) {
            mx2 = mx1;
            mx1 = x;
        }
        else if(x > mx2) {
            mx2 = x;
        }
    }

    // 完整路径可以从一个子树经过u，再进入另一个子树
    ans = max(ans, w[u] + mx1 + mx2);

    // 向父节点只能贡献一条路径
    return w[u] + mx1;
}

树上背包

题目形式：
每个节点有价值；选择节点数量有限；选择关系受树结构约束；求最大价值。

定义： $d p [u] [j]$ = 在 $u$ 的子树中选择 $j$ 个节点的最大价值

初始化： $d p [u] [1] = w_{u}$

合并一个孩子 $v$ 时：
$d p [u] [j + k] = max [d p [u] [j + k], d p [u] [j] + d p [v] [k]]$
这相当于每个子树都是一个“物品组”，需要枚举给该子树分配多少选择数量。

骨架：
```
void dfs(int u, int parent) {
    size[u] = 1;
    dp[u][1] = value[u];

    for (int v : graph[u]) {
        if (v == parent) continue;

        dfs(v, u);

        for (int j = min(size[u], m); j >= 1; j--) {
            for (int k = 1;
                k <= size[v] && j + k <= m;
                k++) {
                dp[u][j + k] = max(
                    dp[u][j + k],
                    dp[u][j] + dp[v][k]
                );
            }
        }

        size[u] += size[v];
    }
}
```
识别信号：

树上选择固定数量节点；
每个子树需要分配容量；
合并子树时出现两层容量循环。
换根 DP：每个节点到其他节点的距离和

要求对每个节点 $u$ ，计算：
$a n s [u] = \sum_{v} d i s t (u, v)$
第一遍 DFS

计算：
- $s i z e [u]$ = $u$ 子树节点数
- $d o w n [u]$ = $u$ 到子树所有节点的距离和
转移：
$s i z e [u] = 1 + \sum_{v} s i z e [v]$ $d o w n [u] = \sum_{v} (d o w n [v] + s i z e [v])$
因为从 $u$ 到 $v$ 子树的每个节点，都比从 $v$ 出发多走一条边。

第二遍 DFS

已知 $a n s [u]$ ，将根从 $u$ 移到孩子 $v$ ：
- $v$ 子树中的 $s i z e [v]$ 个节点距离全部减少 1
- 其余 $n - s i z e [v]$ 个节点距离全部增加 1
所以：
$a n s [v] = a n s [u] + n - 2 \cdot s i z e [v]$
这是换根 DP 最经典的公式。

树上染色

ll dp[N][3];

void dfs(int u,int fa) {
    dp[u][0] = w[u];   // u染色
    dp[u][1] = 0;      // u被孩子覆盖
    dp[u][2] = 0;      // u等父亲覆盖

    ll extra = INF;
    for(int v:g[u]) {
        if(v==fa) continue;
        dfs(v,u);
        dp[u][0] += min({dp[v][0],dp[v][1],dp[v][2]});
        dp[u][2] += min(dp[v][0],dp[v][1]);
        dp[u][1] += min(dp[v][0],dp[v][1]);
        // 强制至少一个孩子染色
        extra = min(
            extra,
            dp[v][0] - min(dp[v][0],dp[v][1])
        );
    }

    dp[u][1] += extra;
}

三、图论

最短路算法

dijkstra

int n,m,s,t,dis[1010];
bool vis[1010];
vector<pair<int, int>>e[1010]; //pair<v,w>
struct ty {
    int x,dis;
    bool operator < (const ty & a) const {
        return dis>a.dis;
    }
};
priority_queue<ty>q;
int dijkstra() {
    dis[s]=0;
    ty temp={s,dis[s]};
    q.push(temp);
    while(!q.empty()) {
        temp=q.top();
        q.pop();
        if(vis[temp.x]) continue;
        vis[temp.x]=true;
        for(auto [v,w] : e[temp.x]) {
            if(vis[v]) continue;
            if(dis[v]>dis[temp.x]+w) {
                dis[v]=dis[temp.x]+w;
                q.push({v,dis[v]});
            }
        }
    }
    return dis[t]==inf?-1:dis[t];
}

Floyd，多源最短路
注意不能调换循环的顺序，k是指允许经过前k个节点，是动态规划的阶段体现

void floyd(vector<vector<int>>& dist) {
    int n = dist.size();

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

SPFA，解决负权边问题

queue<int>q;
int SPFA() {
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto [v,w]:e[u]) {
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if(!vis[v]) {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[t]==inf) return -1;
    return dis[t];
}

最小生成树MST
Kruskal算法：1. 所有边按权重从小到大排序；2. 依次尝试加入边；3. 如果不会形成环（即边的两个端点祖先不同），就加入；4. 用并查集判断是否成环
Prim算法：≈ Dijkstra 去掉路径累加，从一个点开始，每次选择一条连接“已选点集合”和“未选点集合”的最小边，把新的点加入，直到所有点都加入

const int N=1e5+10;
int t,n,m,fa[N];
int find(int x){
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
void merge(int x,int y) {
    fa[find(x)]=find(y);
}
struct ty {
    int x,y,val;
}edge[10*N];
int kruskal() {
    int cnt=0;
    int ans=0;
    for(int i=1;i<=m;i++) {
        int fx=find(edge[i].x);
        int fy=find(edge[i].y);
        if(fx==fy) continue;
        merge(fx,fy);
        ans+=edge[i].val;
        cnt++;
        if(cnt>=n-1) break;
    }
    return ans;
}
bool cmp(struct ty a,struct ty b) {
    return a.val<b.val;
}
void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)  fa[i]=i;
    for(int i=1;i<=m;i++)  cin>>edge[i].x>>edge[i].y>>edge[i].val;
    sort(edge+1,edge+1+m,cmp);
    int ans=kruskal();
    cout<<ans;
}

四、数学

最大公约数

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

最小公倍数

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

快速幂

long long power(long long a, long long b, long long mod) {
    long long res = 1;

    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }

    return res;
}

埃氏筛：求1-n的所有素数，O(nloglogn)

vector<int> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;

    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);

            if ((long long)i * i <= n) {
                for (long long j = (long long)i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    return primes;
}

线性筛：O(n)

bool prime[N];
int factor[N];
void pre_prime(int n)  //线性筛求1-n范围内的所有质数
{
    memset(prime,1,sizeof(prime));  //假设所有的数字都是质数

    int pos=0;
    for(int i=2;i<=n;i++)
    {
        if(prime[i]) factor[pos++]=i;  //如果没有被标记为不是质数，就把它放到factor中

        for(int j=0;j<pos;j++)
        {
            if(i*factor[j]>n) break; 
            prime[i*factor[j]]=0; //标记该数字不是质数
            if(i%factor[j]==0) break;//放入factor的i不是质数，所以退出循环（避免非质数的重复标记）
        }
    }
}

五、补充

st表

/*
st 表在这里实现了 区间最小值查询 的功能，通过预处理稀疏表，可以在 O(1) 时间复杂度内快速回答任意区间 [l, r] 的最小值问题。
*/
#include<bits/stdc++.h>
using namespace std;
int n,q;
long long a[200010],s[200010],c[200010];
long long st[200010][25];
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++) c[i]=s[i-1]-a[i];
    for(int i=1;i<=n;i++) st[i][0]=c[i];
    
    //重点
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
    
    while(q--){
        int l,r;
        cin>>l>>r;
        if(r==l){
            cout<<0<<"\n";
            continue;
        }
        int len=log2(r-l);
        long long ts=s[l-1];
        cout<<abs(min(0LL,min(st[l+1][len],st[r-(1<<len)+1][len])-ts))<<"\n";
    }
    return 0;
}

差分约束

如果题目出现：
$x_{i} - x_{j} \leq c$
移项：
$x_{i} \leq x_{j} + c$
对应一条最短路边：
```
j -> i，权值 c
```
因为最短路松弛：
$d i s [i] \leq d i s [j] + c$
所以：
$x_{i} - x_{j} \leq c \Rightarrow j \to i (c)$
其他形式：
$x_{i} - x_{j} \geq c$
变成：
$x_{j} - x_{i} \leq - c$
所以：
```
i -> j，权值 -c
```
相等：
$x_{i} - x_{j} = c$
拆成两个不等式。
最大流 / 最小割

网络流基本模型：
```
源点 S
↓
若干中间节点
↓
汇点 T
```
边有容量：
$c a p (u, v)$
最大流：

从 S 最多能向 T 运多少东西。

最小割

最大流最小割定理：
$maxflow = mincut$
最小割特别适合：
```
做某个选择需要付代价
选择之间有依赖关系
最大化收益 - 成本
```
假设有两个人。

1 号：

选择 A：代价 2
选择 B：代价 5

2 号：

选择 A：代价 6
选择 B：代价 1

而且如果两个人选择不同阵营：

额外代价 4
```
          2
        1 -----> T
        ↑
        5|
        |
    S ----+

            6
        2 -----> T
        ↑
        1|
        |
    S ----+

    1 <----4----> 2
```
A 选 ⇒ B 必须选只需要让边权=INF
最大权闭合子图
有一些项目：
```
选择 A 可以获得收益
但选择 A 必须同时选择 B
```
有两个项目 A、B。

做 A 能赚 8 元。

做 B 能赚 5 元。

但是做 A 必须买一台机器 X，机器成本 6。

求最大利润。
```
        8
S ----------> A
            |
            | INF
            v
            X ----------> T
                6

        5
S ----------> B
```
答案：
$\sum_{正权} w_{i} - mincut = 8 + 5 - 6 = 7$
立刻想到：
$最大权闭合子图 → 最小割$
二分图匹配

如果问题明显分成两类：
```
人 ↔ 工作
学生 ↔ 导师
机器 ↔ 任务
男生 ↔ 女生
```
每个元素最多匹配一次：
$二分图匹配$
典型目标
```
最多能匹配多少对
```
用：
- 匈牙利算法
- 最大流
如果还有边权：
```
每个人做每个任务都有收益/成本
```
可能变成：
$KM / 最小费用最大流$
最小费用最大流

和最大流的区别：

每条边除了容量：
$c a p$
还有费用：
$c o s t$
目标一般是：

在流量最大的前提下，让总代价最小。

识别信号
```
每个人最多选一个任务
每个任务最多被一个人选

而且：
不同匹配方案有不同成本

要求：
匹配尽量多 + 总成本最小
```
想到：
$最小费用最大流$
SCC 强连通分量

SCC：

有向图中任意两点都能够互相到达的最大节点集合。

典型用途：
```
把有向图中的环缩成一个点
```
缩点之后：
$一定是 DAG$
然后经常继续：
```
SCC
→ 缩点
→ DAG DP
```
识别信号
```
有向图
互相可达
很多环
需要把环整体处理
```
想到：
$Tarjan SCC$
2-SAT

每个变量只有：
```
选 / 不选
true / false
```
而条件类似：
```
A 和 B 不能同时选
A 和 B 至少选一个
如果选 A，则必须选 B
```
可以转换成蕴含关系。
1. A 和 B 不能同时成立
$\neg (A \land B)$
等价于：
$A \Rightarrow \neg B$
和：
$B \Rightarrow \neg A$
建：

A -> notB
B -> notA
2. A 和 B 至少一个成立
$A \lor B$
等价于：

notA -> B
notB -> A
3. A 成立，则 B 必须成立
$A \Rightarrow B$
建：

A -> B
notB -> notA
4. A 和 B 必须不同

两种合法：

A=true, B=false
A=false, B=true

可以理解成：

A -> notB
B -> notA
notA -> B
notB -> A

最后：

如果 x 和 ¬x 在同一个 SCC 中，则无解。

识别信号
```
每个东西二选一
限制条件只涉及两个变量
问是否存在合法方案
```
想到：
$2-SAT$

斜率优化 DP

这个我建议你理解，不要求自己推导所有题。

适合优化这种：

d p [i] = min_{j} {d p [j] + f (i, j)}

暴力枚举：

O (n^{2})

如果把式子展开之后，可以写成：

Y_{j} = K_{i} X_{j} + B_{i}

或者：

k_{j} x_{i} + b_{j}

那么每一个 j 可以看成一条直线：

y = k_{j} x + b_{j}

对于每一个 i：

求所有直线在 (x=x_i) 时的最小/最大值。

这就是：

Convex Hull Trick / 斜率优化

经典例子

假设：

d p [i] = min_{j < i} (d p [j] + (x_{i} - x_{j})^{2} + C)

展开：

d p [i] = x_{i}^{2} + C + min_{j} (d p [j] + x_{j}^{2} - 2 x_{i} x_{j})

对于固定 j：

k_{j} = - 2 x_{j}

b_{j} = d p [j] + x_{j}^{2}

于是：

d p [i] = x_{i}^{2} + C + min_{j} (k_{j} x_{i} + b_{j})

变成：

有很多条直线，询问 (x_i) 处的最小 y。

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

typedef long long ll;
typedef __int128 i128;

struct Line {
    ll k, b;

    ll value(ll x) const {
        return k * x + b;
    }
};

deque<Line> q;

// 判断中间直线 b 是否永远没有用
// 这里要求斜率：a.k > b.k > c.k
bool useless(Line a, Line b, Line c) {
    // intersection(a,b) >= intersection(b,c)
    return (i128)(b.b - a.b) * (b.k - c.k)
        >= (i128)(c.b - b.b) * (a.k - b.k);
}

// 加入一条新直线
// 要求新加入的斜率单调不增
void addLine(ll k, ll b) {

    // 斜率相同，只保留截距更小的那条
    if(!q.empty() && q.back().k == k) {
        if(q.back().b <= b)
            return;
        q.pop_back();
    }

    Line now = {k, b};

    while(q.size() >= 2 &&
        useless(q[q.size()-2], q[q.size()-1], now)) {
        q.pop_back();
    }

    q.push_back(now);
}

// 查询 x 处最小值
// 要求查询 x 单调不减
ll query(ll x) {
    while(q.size() >= 2 &&
        q[0].value(x) >= q[1].value(x)) {
        q.pop_front();
    }

    return q.front().value(x);
}
const ll INF = (1LL << 62);

int n;
ll C;
ll x[100005];
ll dp[100005];

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

    cin >> n >> C;

    for(int i=1;i<=n;i++)
        cin >> x[i];

    // 假设 dp[1] = 0
    dp[1] = 0;

    // j=1 对应的直线
    addLine(
        -2 * x[1],
        dp[1] + x[1] * x[1]
    );

    for(int i=2;i<=n;i++) {

        dp[i] =
            x[i] * x[i]
            + C
            + query(x[i]);

        // i 以后可以作为 j
        addLine(
            -2 * x[i],
            dp[i] + x[i] * x[i]
        );
    }

    cout << dp[n] << '\n';
}

识别信号

看到：

d p [i] = min_{j}

并且展开后出现：

A_{j} B_{i} + C_{j}

也就是：

一部分只和 j 有关 × 一部分只和 i 有关。

就可以尝试：

斜率优化

离散化

如果坐标：

x_{i} \leq 10^{9}

甚至：

10^{18}

但实际只出现：

10^{5}

个不同坐标：

sort(v.begin(),v.end());

v.erase(
    unique(v.begin(),v.end()),
    v.end()
);

映射：

int id =
    lower_bound(v.begin(),v.end(),x)
    - v.begin();

把大坐标压缩到：

0 \sim n - 1

常用于

树状数组
线段树
扫描线
二维点问题

容斥原理

两个集合：
$| A \cup B | = | A | + | B | - | A \cap B |$
三个：
$| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |$

矩阵快速幂

一般 k 阶递推怎么构造矩阵

例如：

f_{n} = 2 f_{n - 1} + 3 f_{n - 2} + 4 f_{n - 3}

状态：

(\begin{matrix} f_{n} \\ f_{n - 1} \\ f_{n - 2} \end{matrix})

转移矩阵：

(\begin{matrix} 2 & 3 & 4 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})

规律：

识别信号

线性递推
状态数很少
n 特别大

想到：

矩阵快速幂

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

typedef long long ll;

const ll MOD = 1000000007;
const int MAXN = 10;

struct Matrix {
    int n, m;
    ll a[MAXN][MAXN];

    Matrix(int _n=0, int _m=0) {
        n = _n;
        m = _m;
        memset(a, 0, sizeof(a));
    }
};

Matrix operator * (const Matrix &A, const Matrix &B) {

    Matrix C(A.n, B.m);

    for(int i=0;i<A.n;i++) {
        for(int k=0;k<A.m;k++) {

            if(A.a[i][k] == 0)
                continue;

            for(int j=0;j<B.m;j++) {

                C.a[i][j] =
                    (C.a[i][j]
                    + A.a[i][k] * B.a[k][j] % MOD)
                    % MOD;
            }
        }
    }

    return C;
}

Matrix matrixPow(Matrix A, long long k) {

    Matrix res(A.n, A.n);

    // 单位矩阵
    for(int i=0;i<A.n;i++)
        res.a[i][i] = 1;

    while(k) {

        if(k & 1)
            res = res * A;

        A = A * A;

        k >>= 1;
    }

    return res;
}
ll fib(long long n) {

    if(n == 0)
        return 0;

    Matrix A(2,2);

    A.a[0][0] = 1;
    A.a[0][1] = 1;
    A.a[1][0] = 1;
    A.a[1][1] = 0;

    Matrix R = matrixPow(A, n-1);

    // [F1, F0] = [1, 0]
    return R.a[0][0];
}

LOADING

机试笔记

识别信号

识别信号

识别信号

经典例子

识别信号

常用于

识别信号