算法设计与分析期末上机板子——课内题目题意与题解分析+课外知识点总结！

真正的模板！！！

文章目录

课内
- - 堆实现C语言
  - 矩阵连乘
  - E1D连分数计算
  - C3A-钢管切割：动态规划
  - C3C-流水线调度：动态规划
  - C3E-矩阵连乘效率：区间动态规划
  - C3F-导弹轰炸（小偷问题）：动态规划
  - C4F-最长公共子串/子序列长度：动规|||考虑加一个输出字符串
  - E3B-锯钢条:优先队列贪心
  - E3F-身高变化:动态规划
- 图论
- - C4E-无向图源点到所有点最短距离：Dijkstra模板！
  - C4G-1到其他的最短距离+负环：Bellman_Ford模板
  - C4I-有向图最长路径:动规
  - C4J-通过所有边的简单路径:欧拉路径模板
  - E3H-:fenwick树状数组模板
  - C5A-有向图任意两点最短路径:Floyd模板
  - E4A-字典序最大Topo：Topo模板
  - E4B-最小生成树:Krusal模板
  - E4C-:Dinic最大流模板
  - E4E-约会大作战：二分图匈牙利最大匹配
  - E4G-不超过k条边的最短路径：BF
  - E4J-不经过某点最短路径:
  - E5D-二分图最大权完美匹配:KM算法
- 计算几何
- - C5E/F-凸包面积&旋转卡壳:凸包模板
  - C5G-最小曼哈顿距离：线段树模板
- FFT
- - C6B-高精度乘法:FFT模板
- 字符串匹配
- - C6A-字符串匹配:kmp模板//也可以直接用find或strstr
  - C6E-前缀等于后缀的长度：Next数组
  - C6D-最长回文子串:中心扩散定理
  - C6G-:字符串哈希表
课外
- 快读
- 树状数组
- 线段树
- 并查集
- 堆优化Dijkstra
- 乘法逆元
- 快速幂
- 矩阵快速幂
- 欧拉素数筛
- KMP
- 最长上升子序列
- 最大连续子序列和

课内

//解决爆栈，手动加栈，必须放在头文件之前
#pragma comment(linker,"/STACK:1024000000,1024000000") 

//万能头文件，部分比赛中可能不让用
#include <bits/stdc++.h> //C++

//STL专用，使用了哪种数据结构，就要用到哪种头文件
#include <map> //C++
#include <vector> //C++
#include <set> //C++
#include <stack>//c++
#include <deque>//双端队列
//C++必备头文件，cin、cout及其相关函数在这里
#include <isotream> //C++

//strlen()、strcat()等字符串操作函数在这里
#include <cstring> //C++
#include <string.h> //C语言

//min()、max()等在这里
#include <cstdlib> //C++
#include <stdlib.h> //C语言

//scanf()、printf()以及和它们长得像的函数在这里
#include <cstdio> //C++
#include <stdio.h> //C语言

//sort()在这里
#include <algorithm>> //C++

//log()、sin()、pow()等数学运算的函数在这里
#include <cmath>> //C++
#include <math.h> //C语言

//文件模板
#include<bits/stdc++.h>
inline int getint(){//快读
    int x = 0, f = 1;char ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch -'0';ch = getchar();}
    return x * f;
}
using namespace std;
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}

堆实现C语言

题意：第一行一个正整数 n（1 \le n \le 10^5），表示操作的数量。接下来 n 行，每行为一个操作，数据保证后两种操作时堆非空。格式如下：

1 x：向堆中插入元素 xx（1 \le x \le 10^91 \le x \le 10^9）。
2：删除堆顶元素。
3：查询堆顶元素。

输出

对于每次查询堆顶元素时，输出一行一个正整数，表示此时堆顶元素的值。在所有操作结束后，将堆中的元素从大到小依次输出到一行中。

#define maxn 1000005
#define inf 0x3f3f3f3f
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

int n, sz, a[maxn];

void swap(int *a, int *b) {
    int t = *a;
    *a = *b, *b = t;
}

void maxHeapify(int x) {
    int l = ls(x), r = rs(x), larg;
    if (l <= sz && a[l] > a[x]) larg = l;
    else larg = x;
    if (r <= sz && a[r] > a[larg]) larg = r;
    if (larg != x) swap(&a[x], &a[larg]), maxHeapify(larg);
}

void increaseKey(int i, int key) {
    a[i] = key;
    while (i > 1 && a[i / 2] < a[i]) {
        swap(&a[i / 2], &a[i]);
        i = i / 2;
    }
}

void insert(int x) {
    sz += 1;
    a[sz] = -inf;
    increaseKey(sz, x);
}

int top() {
    return a[1];
}

void pop() {
    if (sz < 1) exit(1);
    a[1] = a[sz];
    sz -= 1;
    maxHeapify(1);
}

int main() {
    scanf("%d", &n);
    int i;
    for (i = 1; i <= n; i++) {
        int op, x;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d", &x);
            insert(x);
        }
        if (op == 2) pop();
        if (op == 3) printf("%d\n", top());
    }
    while (sz) {
        printf("%d ", top()), pop();
    }
}

矩阵连乘

题意：每组数据第一行-方阵阶数n 接下来n行，表示整数方阵A。输出 $A^n$

#define maxn 205
typedef long long ll;
const int p = 1e9 + 7;
int n;
ll k;
struct Martix {
    ll a[maxn][maxn];
};
inline Martix multiply(Martix x, Martix y) {
    Martix z;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            z.a[i][j] = 0;
            for (int k = 1; k <= n; k++) {
                z.a[i][j] += x.a[i][k] * y.a[k][j];
                z.a[i][j] %= p;
            }
        }
    }
    return z;
}

inline Martix fpow(Martix x, ll k) {
    Martix y;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) y.a[i][j] = 1;
            else y.a[i][j] = 0;
        }
    }
    while (k) {
        if (k & 1) y = multiply(y, x);
        x = multiply(x, x);
        k >>= 1;
    }
    return y;
}
void solve{
    scanf("%d%", &n);
    k = n;
    Martix x;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) 
            scanf("%lld", &x.a[i][j]);
    x = fpow(x, k);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%lld ", x.a[i][j]);
        }
        printf("\n");
    }
}

E1D连分数计算

题意：
可用一组序列表示，我们记其第 $n$ 项表示为
$\frac{p_n}{q_n} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\ddots + \frac{1}{a_n}}}}}$
现给出 $a_0, a_1, \cdots, a_n$ ，求出其表示的分数 $\frac{p_n}{q_n}$ 在模 $998244353$ 意义下的值。即输出 $r_n = p_n \cdot q_n^{-1} \bmod 998244353$ ，其中 $q_n^{-1} 满足q_n \cdot q_n^{-1} \equiv 1 \pmod{998244353}$ 。测试数据保证 $q_n$ 的逆元 $q_n^{-1}$ 存在

const int mod = 998244353;
long long fp(long long a, long long x) {
    long long ret = 1;
    while (x) {
        if (x & 1) { ret *= a; ret %= mod; }
        a *= a; a %= mod;
        x >>= 1;
    }
    return ret;
}
void solve(){
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    vector<long long> p(n + 1), q(n + 1);
    for (int i = 0; i <= n; i++) 
        cin >> a[i];
    p[0] = a[0];
    q[0] = 1;
    p[1] = (a[0] * a[1] + 1) % mod;
    q[1] = a[1];
    for (int i = 2; i <= n; i++) {
        p[i] = (a[i] * p[i - 1] + p[i - 2]) % mod;
        q[i] = (a[i] * q[i - 1] + q[i - 2]) % mod;
    }
    cout << p[n] * fp(q[n], mod - 2) % mod << '\n';
}

C3A-钢管切割：动态规划

题意：第一行一个正整数 $n$ （ $\le n \le 10^4$ ），表示钢管的总长度。第二行 $n$ 个正整数 $p_1,p_2,\ldots,p_n$ （ $\le p_i \le 10^7$ ），表示长度 $i$ 钢管的价格。

输出：第一行一个正整数，表示最大总销售价格。第二行一个正整数 $k$ ，表示钢管被分割成 $k$ 段。第三行 $k$ 个正整数 $a_1, \dots, a_k$ ，表示钢管的分割方式，需保证 $\sum a_i = n$

#include<bits/stdc++.h>
#define maxn 200005
typedef long long ll;
using namespace std;

ll read(){
    ll x = 0, f = 1;char ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
int n, p[maxn];
ll f[maxn];
vector<int> ans;

void solve(){
    n = read();
    for(int i = 1; i <= n; i++) p[i] = read();
    for(int i = 1; i <= n; i++){
       for(int j = 0; j < i; j++){
          f[i] = max(f[i], f[j] + p[i - j]);
       }
    }
    printf("%lld\n", f[n]);
    int now = n;
    while(now){
       for(int i = 1; i <= now; i++){
          if(f[now] == f[now - i] + p[i]){
             ans.push_back(i);
             now -= i;
             break;
          }
       }
    }
    printf("%d\n", ans.size());
    for(int i = 0; i < ans.size(); i++) printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
}

C3C-流水线调度：动态规划

题意：

#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18;
const int M = 1e5 + 5;

int p[3][M], t[3][3];
long long dp[3][M];

void solve() {
    int m;
    cin >> m;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < m; j++) {
            cin >> p[i][j];
        }
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> t[i][j];
        }
    }
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < 3; i++) {
            dp[i][j] = inf;
            for (int k = 0; k < 3; k++) {
                dp[i][j] = min(
                        dp[i][j],
                        (j - 1 >= 0 ? dp[k][j - 1] + t[k][i] : 0LL) + p[i][j]
                );
            }
        }
    }
    long long ans = inf;
    for (int i = 0; i < 3; i++) {
        ans = min(ans, dp[i][m - 1]);
    }
    cout << ans << '\n';
}

C3E-矩阵连乘效率：区间动态规划

题意：第一行一个整数 $n$ （ $\le n \le 300$ ），表示矩阵的个数。第二行 $n + 1$ 个正整数 $a_1,a_2,\ldots,a_{n+1}$ （ $\le a_i \le 10^3$ ），表示矩阵 $A_i$ 的行数和列数为 $a_i$ 和 $a_{i+1}$ 。

输出：一行一个浮点数，表示运算次数最多是最少的多少倍，结果保留4位小数。

#include<bits/stdc++.h>
#define maxn 305
typedef long long ll;
using namespace std;

ll read(){
    ll x = 0, f = 1;char ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
int n, a[maxn];
ll f[maxn][maxn];
void solve(){
    n = read();
    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= n + 1; i++) a[i] = read(), f[i][i] = 0;
    for(int len = 2; len <= n; len++){
        for(int l = 1; l + len - 1 <= n; l++){
            int r = l + len - 1;
            for(int k = l; k < r; k++){
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + 1ll * a[l] * a[k + 1] * a[r + 1]);
            }
        }
    }
    ll mx = f[1][n];
    memset(f, 0, sizeof(f));
    for(int len = 2; len <= n; len++){
        for(int l = 1; l + len - 1 <= n; l++){
            int r = l + len - 1;
            for(int k = l; k < r; k++){
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + 1ll * a[l] * a[k + 1] * a[r + 1]);
            }
        }
    }
    printf("%.4f\n", 1.0 * f[1][n] / mx);
}

C3F-导弹轰炸（小偷问题）：动态规划

题意：每组测试数据包含两行。第一行包含一个正整数 $\le n \le 10^5)$ 。第二行包含 $n$ 个正整数 $w_1, w_2, \dots, w_n (1 \le w_i \le 10^5)$ ，表示每个前哨站的重要程度。数据保证 $\sum n \le 4 \cdot10^5$ 。不能轰炸连续两个前哨战。

输出：对于每组测试数据，输出一行一个整数，表示在导弹互不干扰的情况下，能够轰炸的前哨站的重要程度之和的最大值。

#define maxn 200005
typedef long long ll;
const double eps = 1e-9;
const int mod = 998244353;
ll read(){
    ll x = 0, f = 1;char ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
int n;
ll w[maxn], f[maxn][2];
void solve(){
    n = read();
    for(int i = 1; i <= n; i++) w[i] = read(), f[i][0] = f[i][1] = 0;
    for(int i = 1; i <= n; i++){
       f[i][0] = max(f[i - 1][0], f[i - 1][1]);
       f[i][1] = w[i] + (i == 1 ? 0 : max(f[i - 2][0], f[i - 2][1]));
    }
    printf("%lld\n", max(f[n][0], f[n][1]));
}

C4F-最长公共子串/子序列长度：动规|||考虑加一个输出字符串

每组数据：输入两个字符串，输出一行两个整数，表示最长公共子串/最长公共子序列长度

const int N = 2005;
int n1, n2;
char s1[N], s2[N];
int f[N][N], g[N][N];
int maxf, maxg;
void solve() {
    scanf("%s", s1 + 1);
    scanf("%s", s2 + 1);
    n1 = strlen(s1 + 1);
    n2 = strlen(s2 + 1);
    maxf = maxg = 0;
    for (int i = 1; i <= n1; i++)
        for (int j = 1; j <= n2; j++) {
            f[i][j] = s1[i] == s2[j] ? f[i - 1][j - 1] + 1 : 0;
            g[i][j] = max({g[i - 1][j - 1] + (s1[i] == s2[j]), g[i - 1][j], g[i][j - 1]});
            maxf = max(maxf, f[i][j]);
            maxg = max(maxg, g[i][j]);
        }
    printf("%d %d\n", maxf, maxg);
}

E3B-锯钢条:优先队列贪心

输入：第一行一个整数n,表示需要钢条数量，第二行n个整数，表示每个钢条的长度。

把钢条切成两段的代价为总长度的二倍，一次只能切一刀。输出最小代价。

typedef long long ll;
int n;
priority_queue<ll, vector<ll>, greater<> > q;//小根堆，默认大
int main(){
    scanf("%d", &n);
    for(int i = 1;i <= n;i++){
        int x;
        scanf("%d", &x);
        q.push(x);
    }
    ll ans = 0;
    for(int i = 1;i < n;i++){
        ll x = q.top();q.pop();
        x += q.top();q.pop();
        ans += x * 2;
        q.push(x);
    }
    printf("%lld", ans);

E3F-身高变化:动态规划

每组数据：输入：第一行n,m,k表示有n个事件，k次跳过机会，h表示初始身高。第二行n个整数，表示n个事件。若事件为正，身高增加；若事件为负，若身高+事件>0,那么可以越过，否则身高减半（向下取整），也可以使用一次跳过。当身高变为0,则失败

输出：若可以走完全程，输出最大值，否则输出"-1"

void solve(){
    int n, k, h;
    cin >> n >> k >> h;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<long long> f(k + 1, h), g(k + 1);
    long long s = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] >= 0) {
            s += a[i];
            continue;
        }
        for (int j = 0; j <= k; j++)
            if (f[j] > 0) f[j] += s;
        s = 0;
        for (int j = 0; j <= k; j++)
            g[j] = max(f[j] > -a[i] ? f[j] : f[j] / 2,j + 1 <= k ? f[j + 1] : 0);
        swap(f, g);
    }
    long long ans = *max_element(f.begin(), f.end());
    if (ans <= 0) cout << -1 << '\n';
    else cout << ans + s << '\n';
}

图论

C4E-无向图源点到所有点最短距离：Dijkstra模板！

求出无向图中一个源点到其余点的最短距离，并判断这个最短距离是否可接受。

第一行四个正整数n,m,s,t表示点/边/源点/限制

接下来m行，每行x,y,t表示x和y之间有边，代价为t

输出：第一行k表示有k个点不超过限制，接下来k行，每行x,t表示超过限制的节点以及代价。若无法到达该点，代价为-1.

typedef long long ll;
const ll inf=2e18;
class Dijkstra{
public :
    int n;
    vector<vector<pair<int,ll>>>g;
    vector<ll>distance;
    Dijkstra(int _n):n(_n){
        g.resize(n+1);
        distance.resize(n+1,inf);
    }
    void add(int u,int v,ll w){
        g[u].emplace_back(v,w);
    }
    void solve(int s){//源点s
        vector<bool> vis(n);
        priority_queue<pair<ll,int>>q;//默认大根堆
        distance[s]=0;
        q.push({0,s});
        while(!q.empty()){
            int u=q.top().second;q.pop();
            if(vis[u]) continue;
            vis[u]=true;
            for(auto p:g[u]){//u的所有出边
                int v=p.first;
                ll w=p.second;
                if(distance[v]>distance[u]+w){//可以更新距离
                    distance[v]=distance[u]+w;
                    q.push({-distance[v],v});//压入负距离，小根堆
                }
            }
        }
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,s,cnt=0;ll t;
    vector<int>ans;
    cin>>n>>m>>s>>t;
    Dijkstra d(n);
    for(int i=1;i<=m;i++){
        int u,v;ll w;
        cin>>u>>v>>w;
        d.add(u,v,w);
        d.add(v,u,w);
    }
    d.solve(s);
    for(int i=1;i<=n;i++)
        if(d.distance[i]>t)
            cnt++,ans.push_back(i);
    cout<<cnt<<endl;
    for(auto i:ans) cout<<i<<" "<<(d.distance[i]==inf?-1:d.distance[i])<<"\n";
}

C4G-1到其他的最短距离+负环：Bellman_Ford模板

每组数据：输入：第一行n,m接下来m行，每行三个整数u,v,w，表示u->v权值为w

输出：若存在负环输出“boo how”否则输出1点到每个点(1-n)的最短距离

#define MAXN 2003
#define MAXM 6003
#define MAX 1000000000
int n, m;
struct edge {
    int from, to, val;
} e[MAXM * 2];
int dis[MAXN];
bool Bellman_Ford(int s) {
    fill(dis, dis + n + 1, 2 * MAX);
    dis[s] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dis[e[j].to] = min(dis[e[j].to], dis[e[j].from] + e[j].val);

    for (int i = 1; i <= m; i++)
        if (dis[e[i].to] > dis[e[i].from] + e[i].val)
            return true;
    return false;
}
void solve(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> e[i].from >> e[i].to >> e[i].val;
    bool res = Bellman_Ford(1);
    if (res) cout << "boo how\n";
    else
        for (int i = 1; i <= n; i++)
            cout << (dis[i] >= MAX ? MAX : dis[i]) << " \n"[i == n];
}

C4I-有向图最长路径:动规

无权有向图最长路径

每组数据：输入：第一行n,m表示点/边，接下来m行，每行两个整数u,v表示u->v边，输出：有向图最长路径长度

const int maxn=2000009;
int n,m,ans=0,cnt=0;
int in[maxn],f[maxn],head[maxn];//in:依赖几个，f:完成此步的时间，head:
struct node{
    int nex;
    int to;
}e[maxn];
void add(int u,int v){
    cnt++;
    e[cnt].nex=head[u];
    e[cnt].to=v;
    head[u]=cnt;
    in[v]++;
}
void solve(){
    ans=0;
    cin>>n>>m;
    for(int i=0;i<=n;i++)
        in[i]=0,head[i]=0,f[i]=1;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        add(u,v);
    }
    queue<int>q;
    for(int i=1;i<=n;i++) if(!in[i]) q.push(i);//可以进行的
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nex){
            int v=e[i].to;
            f[v]=max(f[v],f[u]+1);
            if(--in[v]==0) q.push(v);//依赖的全完成了
        }
    }
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
    cout<<ans<<endl;
}

C4J-通过所有边的简单路径:欧拉路径模板

每组数据：输入：第一行n,m表示点/边个数，接下来m行，每行两个整数，表示u->v的边。

输出：若不存在欧拉路径，输出"mission impossible",否则输出字典序最小的欧拉路径。

题解：欧拉路径充要条件：

图是连通图（弱联通）
无向图：奇点为0或2，一个为起点，一个为终点
有向图：可以存在2个点，入度不等于出度，其中一个入度比出度大1（起点），另一个出度比入度大一（终点）。或者不存在这样的点。

const int N = 2.5e4 + 5;
const int E = 5e4 + 5;
int n, m;
int h[N], to[E], nx[E], et;
int indeg[N], outdeg[N];
int u[E], v[E], p[E];
int q[E], cnt;
void ae(int u, int v) {
    et++;
    to[et] = v;
    nx[et] = h[u];
    h[u] = et;
    indeg[v]++;
    outdeg[u]++;
}
bool cmp(int a, int b) {
    return v[a] > v[b];
}
void dfs(int u) {
    for (int i = h[u]; i; i = h[u]) {
        h[u] = nx[i];
        dfs(to[i]);
    }
    q[++cnt] = u;
}
void solve() {
    scanf("%d%d", &n, &m);
    et = 0;
    for (int i = 1; i <= n; i++)
        h[i] = indeg[i] = outdeg[i] = 0;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u[i], &v[i]);
        p[i] = i;
    }
    sort(p + 1, p + m + 1, cmp);
    for (int i = 1; i <= m; i++)
        ae(u[p[i]], v[p[i]]);
    int s = 1, i0 = 0, o0 = 0;
    while (s < n && outdeg[s] == 0)
        s++;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == outdeg[i])
            continue;
        if (indeg[i] < outdeg[i]) {
            i0 += outdeg[i] - indeg[i];
            s = i;
        }
        if (indeg[i] > outdeg[i])
            o0 += indeg[i] - outdeg[i];
    }
    if (i0 > 1 || o0 > 1) {
        printf("mission impossible\n");
        return;
    }
    cnt = 0;
    dfs(s);//拓扑，弱连通
    if (cnt != m + 1) {//不是联通图
        printf("mission impossible\n");
        return;
    }
    for (int i = cnt; i; i--)
        printf("%d%c", q[i], " \n"[i == 1]);
}

E3H-:fenwick树状数组模板

我们称一个二维点集 $S$ 是优雅的，当且仅当对任意的点 $(x_1, y_1), (x_2, y_2) \in S$ ，都有 $(\min(x_1, x_2), \min(y_1, y_2)) \in S$ 。

现在给出一个二维点集 $S$ ，请你向其中加入最少的点，使其变为优雅的点集 $S ’$ ，求出 $S ’$ 中点的个数。

每组数据：输入：第一行n表示n个点，接下来n行，每行两个点，表示点坐标。

输出： $S^{'}$ 中点的个数

class fenwick {
public:
    int n;
    vector<int> a;
    fenwick(int _n) : n(_n) { a.resize(n); }
    void modify(int x, int val) {
        while (x < n) {
            a[x] += val;
            x |= (x + 1);
        }
    }
    int get(int x) {
        int ret = 0;
        while (x >= 0) {
            ret += a[x];
            x = (x & (x + 1)) - 1;
        }
        return ret;
    }
};
void solve() {
    set<pair<int, int>> st;
    int n;
    cin >> n;
    vector<int> x(n), y(n), sy(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        st.insert({x[i], y[i]});
        sy[i] = y[i];
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int u, int v) {
        return (x[u] > x[v]) || (x[u] == x[v] && y[u] < y[v]);
    });
    sort(sy.begin(), sy.end());
    map<int, int> sp;
    int id = 0;
    for (int i = 0; i < n; i++) {
        if (sp.find(sy[i]) == sp.end()) {
            sp[sy[i]] = id++;
        }
    }
    fenwick tr = fenwick(n);
    vector<bool> vis(n);
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int a = sp[y[p[i]]];
        if (!vis[a]) {
            tr.modify(a, 1);
            vis[a] = true;
        }
        if (i == n - 1 || x[p[i]] > x[p[i + 1]])
            ans += tr.get(a);
    }
    cout << ans << '\n';
}

C5A-有向图任意两点最短路径:Floyd模板

输入：第一行两个整数n,m表示点/边，接下来m行，每行三个整数u,v,w表示u->v权值为w的有向边。接下来一个整数q，表示询问q次，接下来q行，每行两个整数u,v，询问u->v最短距离

输出：每次询问，到达自身为0，无法到达为-1，输出最短距离

#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
class Floyd {
public:
    int n;
    vector<vector<long long>> g;
    Floyd(int _n) : n(_n) {
        g.resize(n);
        for (int i = 0; i < n; i++) g[i].resize(n, inf);
        for (int i = 0; i < n; i++) g[i][i] = 0;
    }
    void add(int u, int v, long long w) { g[u][v] = min(g[u][v], w); }
    void solve() {
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    }
};

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int n, m, u, v, w,q;
    cin >> n >> m;
    Floyd f = Floyd(n);
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        u--, v--;
        f.add(u, v, w);
    }
    f.solve();
    cin >> q;
    while (q--) {
        cin >> u >> v;
        u--, v--;
        long long ans = f.g[u][v];
        if (ans == inf) ans = -1;
        cout << ans << '\n';
    }
    return 0;
}

E4A-字典序最大Topo：Topo模板

输入：第一行n,m表示n点m边的有向无环图，接下来m行，每行两个整数u,v表示存在u->v的有向边

输出：字典序最大的拓扑排序

int in[200009] ;
vector<int>dag[200009];
priority_queue<int>q;//默认大根堆
//priority_queue<int,vector<int>,greater<>>q;//小根堆实现
void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        in[v]++; dag[u].push_back(v);
    }
    for(int i=1;i<=n;i++) 
        if (in[i] == 0)
            q.push(i);
    while(!q.empty()){
        int now=q.top();q.pop();
        cout<<now<<" ";
        for(int v : dag[now]){
            in[v]--;
            if(in[v]==0) q.push(v);
        }
    }
}

E4B-最小生成树:Krusal模板

每组数据：输入：第一行n,m表示n点m边的无向图，接下来m行，每行三个整数u,v,w，表示u和v之间边权为w

class dsu {//并查集
public:
    int n; vector<int> p;
    dsu(int _n) : n(_n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }
    //查找
    inline int find(int x) 
    { return (x == p[x] ? x : (p[x] = find(p[x]))); }
    //把x合并到y
    inline bool unite(int x, int y) {
        x = find(x),y = find(y);
        if (x != y) { p[x] = y; return true; }
        return false; }
};
void solve(){
    int n, m; cin >> n >> m;
    vector<array<int, 3>> e(m);
    for (int i = 0; i < m; i++) {//读边
        int u, v, w; cin >> u >> v >> w;
        u--,v--; e[i] = {u, v, w}; }
    vector<int> p(m);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int u, int v) {return e[u][2] < e[v][2];});
    dsu d = dsu(n);
    long long ans = 0;
    for (int i : p) {
        int u = e[i][0], v = e[i][1];
        if (d.unite(u, v)) 
            ans += e[i][2];
    }
    cout << ans << '\n';
}

E4C-:Dinic最大流模板

给定 $n$ 个点 $m$ 条边的有向图，每条边有最大容量，求从点 $s$ 到点 $t$ 的最大流。（可以存在重边和自环）

每组数据：输入：第一行四个整数n,m,s,t表示n点m边，源点s,汇点t;接下来m行，每行三个数u,v,w表示u->v存在有向边，权值w

输出：最大流

const int N = 105;
const int E = 1e4 + 5;
const long long oo = 1e18;
int n, m, s, t;
int h[N], nx[E], to[E], et;
long long ans,cap[E];
int d[N], q[N], ql, qr;
void add(int u, int v, long long w) {
    et++;
    to[et] = v;
    cap[et] = w;
    nx[et] = h[u];
    h[u] = et;
}
bool bfs(int s, int t) {
    for (int i = 1; i <= n; i++) d[i] = n + 1;
    d[s] = 1; q[1] = s; ql = qr = 1;
    while (ql <= qr) {
        for (int i = h[q[ql]]; i; i = nx[i])
            if (cap[i] && d[to[i]] == n + 1) {
                d[to[i]] = d[q[ql]] + 1;
                q[++qr] = to[i];
            }
        ql++;
    }
    return d[t] <= n;
}
long long dfs(int u, int t, long long c) {
    if (!c) return 0;
    if (u == t) return c;
    long long r = 0;
    for (int i = h[u]; i; i = nx[i])
        if (d[to[i]] == d[u] + 1) {
            long long v = dfs(to[i], t, min(c - r, cap[i]));
            if (v) {
                r += v;
                cap[i] -= v;
                cap[i ^ 1] += v;
                if (r == c) return r;
            }
        }
    if (r == 0) d[u] = n + 1;
    return r;
}

void solve() {
    et = 1,ans = 0; cin>>n>>m>>s>>t;
    for (int i = 1; i <= n; i++) h[i] = 0;
    for (int i = 1; i <= m; i++) {
        int u, v;long long w; cin>>u>>v>>w;
        add(u, v, w),add(v, u, 0);
    }
    while (bfs(s, t)) ans += dfs(s, t, oo);
    cout<<ans<<'\n';
}

E4E-约会大作战：二分图匈牙利最大匹配

输入：第一行n,表示n对男女生，下面四行，每行n个数，第一行是男生魅力，第二行是男生要求对方最低值，第三行是女生魅力，第四行是女生要求对方魅力最低值

输出：最多能匹配几队

const int N = 500;
int n,a[N], p[N], b[N], q[N],girl[N];
bool mat[N][N],vis[N];
bool find(int x) {
    for (int i = 1; i <= n; i++)
        if (mat[x][i] && !vis[i]) {
            vis[i] = true;
            if (!girl[i] || find(girl[i])) {
                girl[i] = x;
                return true;
            }
        }
    return false;
}
void solve(){
    cin>>n;
    for (int i = 1; i <= n; i++) cin>>a[i];
    for (int i = 1; i <= n; i++) cin>>p[i];
    for (int i = 1; i <= n; i++) cin>>b[i];
    for (int i = 1; i <= n; i++) cin>>q[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (b[j] >= p[i] && a[i] >= q[j])
                mat[i][j] = true;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if (find(i))
            ans++;
    }
    printf("%d", ans);
}

E4G-不超过k条边的最短路径：BF

给定带权无向图，处理q次询问，每次询问从s到t不超过t条边的最短路长度（没有重边和自环）

输入：第一行n,m,q,表示n点，m边，q次询问，接下来m行，每行三个整数u,v,w表示u和v之间有无向边，权值w。接下来q行，每行三个整数s,t,k

输出：若不存在，输出-1，否则输出不超过k条边最短路长度

const int N = 105;
const long long oo = 1e18;
int n, m, q;
long long f[N][N][N];
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 0; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                f[i][j][k] = oo;
    for (int x = 0; x <= n; x++)
        for (int i = 1; i <= n; i++)
            f[x][i][i] = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        f[1][u][v] = min(f[1][u][v], 1ll * w);
        f[1][v][u] = min(f[1][v][u], 1ll * w);
    }
    for (int t = 1; t < n; t++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                f[t + 1][i][j] = f[t][i][j];
                for (int k = 1; k <= n; k++)
                    f[t + 1][i][j] = min(f[t + 1][i][j], f[t][i][k] + f[1][k][j]);
            }
    while (q--) {
        int s, t, k;
        scanf("%d%d%d", &s, &t, &k);
        k = min(k, n);
        long long ans = f[k][s][t];
        if (ans == oo)
            ans = -1;
        printf("%lld\n", ans);
    }
    return 0;
}

E4J-不经过某点最短路径:

输入：有向无环带权图第一行n,m,q表示n点，m边，q次询问，接下来m行，每行三个整数u,v,w表示u->v有向边权值为w。接下来q行，每行三个整数u,v,s，表示从u到v不经过s

输出：若能到达，输出最短路径；若不能到达输出0

const int N = 305;
const int C = 45005;
int n, m, t;
int d[N][N];
int vf[N][C], vg[N][C];
int *f[N][N], *g[N][N];
int deg[N], p[N], pre[N];
int q[N], ql, qr;
int a, b, w,u, v, s, last;

int main() {
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= n; i++) pre[i] = n - i;
    for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];
    for (int i = 0; i <= n + 1; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = &vf[i][pre[j - 1]] - j;
    for (int i = 0; i <= n + 1; i++)
        for (int j = 1; j <= n; j++)
            g[i][j] = &vg[i][pre[j - 1]] - j;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &s);
        if (d[a][b] == 0 || s < d[a][b])
            d[a][b] = s;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[i][j])
                deg[j]++;
    ql = 1; qr = 0;
    for (int i = 1; i <= n; i++)
        if (!deg[i])
            q[++qr] = i;
    while (ql <= qr) {
        int cur = q[ql];
        p[cur] = ql;
        for (int i = 1; i <= n; i++)
            if (d[cur][i]) {
                deg[i]--;
                if (!deg[i])
                    q[++qr] = i;
            }
        ql++;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[q[i]][q[j]]) {
                f[0][i][j] = d[q[i]][q[j]];
                g[n + 1][i][j] = d[q[i]][q[j]];
            }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                f[k][i][j] = f[k - 1][i][j];
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                if (i < k && k < j)
                    if (f[k][i][k] && f[k][k][j])
                        if (f[k][i][j] == 0 ||
                            f[k][i][k] + f[k][k][j] < f[k][i][j])
                            f[k][i][j] = f[k][i][k] + f[k][k][j];
    }
    for (int k = n; k; k--) {
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                g[k][i][j] = g[k + 1][i][j];
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                if (i < k && k < j)
                    if (g[k][i][k] && g[k][k][j])
                        if (g[k][i][j] == 0 ||
                            g[k][i][k] + g[k][k][j] < g[k][i][j])
                            g[k][i][j] = g[k][i][k] + g[k][k][j];
    }
    while (t--) {
        scanf("%d%d%d", &u, &v, &s);
        if (p[u] >= p[v] || u == s || v == s) {
            last = 0;
            printf("%d\n", last);
            continue;
        }
        last = d[u][v];
        for (int i = 1; i <= n; i++)
            if (p[u] < i && i < p[v] && q[i] != s)
                if (f[p[s] - 1][p[u]][i] && g[p[s] + 1][i][p[v]])
                    if (last == 0 || f[p[s] - 1][p[u]][i] + g[p[s] + 1][i][p[v]] < last)
                        last = f[p[s] - 1][p[u]][i] + g[p[s] + 1][i][p[v]];
        printf("%d\n", last);
    }
    return 0;
}

E5D-二分图最大权完美匹配:KM算法

二维平面上两组点，要求必须两两配对，求最小曼哈顿距离和

typedef long long ll;
const ll Maxn = 505;
const ll inf = 1e18;
ll n, m, Map[Maxn][Maxn], matched[Maxn];
ll slack[Maxn], pre[Maxn], ex[Maxn], ey[Maxn];//ex,ey顶标
bool visx[Maxn], visy[Maxn];

void match(ll u) {
    ll x, y = 0, yy = 0, delta;
    memset(pre, 0, sizeof(pre));
    for (ll i = 1; i <= n; i++)slack[i] = inf;
    matched[y] = u;
    while (true) {
        x = matched[y];
        delta = inf;
        visy[y] = true;
        for (ll i = 1; i <= n; i++) {
            if (visy[i])continue;
            if (slack[i] > ex[x] + ey[i] - Map[x][i]) {
                slack[i] = ex[x] + ey[i] - Map[x][i];
                pre[i] = y;
            }
            if (slack[i] < delta) {
                delta = slack[i];
                yy = i;
            }
        }
        for (ll i = 0; i <= n; i++) {
            if (visy[i])ex[matched[i]] -= delta, ey[i] += delta;
            else slack[i] -= delta;
        }
        y = yy;
        if (matched[y] == -1)break;
    }
    while (y) {
        matched[y] = matched[pre[y]];
        y = pre[y];
    }
}
ll KM() {
    memset(matched, -1, sizeof(matched));
    memset(ex, 0, sizeof(ex));
    memset(ey, 0, sizeof(ey));
    for (ll i = 1; i <= n; i++) {
        memset(visy, 0, sizeof(visy));
        match(i);
    }
    ll res = 0;
    for (ll i = 1; i <= n; i++)
        if (matched[i] != -1)res += Map[matched[i]][i];
    return res;
}
struct node {
    long long x, y;
} n1[250], n2[250];

long long mhd(node a, node b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}
void solve(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            Map[i][j] = -inf;
    for (int i = 1; i <= n; i++)
        cin >> n1[i].x >> n1[i].y;
    for (int i = 1; i <= n; i++)
        cin >> n2[i].x >> n2[i].y;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            Map[i][j] = -mhd(n1[i], n2[j]);
    printf("%lld\n", -KM());
}

计算几何

C5E/F-凸包面积&旋转卡壳:凸包模板

每组数据：输入：第一行n，表示n个点，接下来n行，每行两个正整数，表示一个点坐标。

输出：凸包面积 | | 最远两点距离平方

#include <bits/stdc++.h>
using namespace std;
/* template begin */
struct Vec {
    long long x, y;
    Vec() {}
    Vec(long long x, long long y) {this->x = x;this->y = y;}
    long long len2() const { return x * x + y * y; }
    void read() { scanf("%lld%lld", &x, &y); }
    void print() { printf("%lld %lld\n", x, y); }
};
typedef Vec Point;
//运算并返回一个点
Vec operator+(const Vec &a, const Vec &b) { return Vec(a.x + b.x, a.y + b.y); }
Vec operator-(const Vec &a, const Vec &b) { return Vec(a.x - b.x, a.y - b.y); }
Vec operator*(long long a, const Vec &b) { return Vec(a * b.x, a * b.y); }
// cross product叉积
long long operator*(const Vec &a, const Vec &b) { return a.x * b.y - b.x * a.y; }
// inner product点积
long long operator^(const Vec &a, const Vec &b) { return a.x * b.x + a.y * b.y; }
typedef vector<Point> Polygon;
typedef Polygon Points;
//a在b逆时针（左返回true
bool onleft(const Vec &a, const Vec &b) { return a * b < 0; }
//a在b顺时针（右返回true
bool onright(const Vec &a, const Vec &b) { return a * b > 0; }
//传入未排序点，返回凸包
Polygon convex(Points p) {
    int sz = p.size(),n=0;
    sort(p.begin(), p.end(), [&](const Point &a, const Point &b) { return a.x != b.x ? a.x < b.x : a.y < b.y; });
    Polygon c(p.size() + 1);
    for (int i = 0; i < sz; i++) {
        while (n > 1 && !onleft(p[i] - c[n - 2], c[n - 1] - c[n - 2])) n--;
        c[n++] = p[i];
    }
    int t = n;
    for (int i = sz - 1; i >= 0; i--) {
        while (n > t && !onleft(p[i] - c[n - 2], c[n - 1] - c[n - 2])) n--;
        c[n++] = p[i];
    }
    c.resize(--n);
    return c;
}
//传入凸包集合，返回凸包面积
long long areadb(Polygon &p) {
    long long r = 0;
    int n = p.size();
    for (int i = 0; i < n; i++)
        r += (p[i] - p[0]) * (p[(i + 1) % n] - p[i]);
    return r;
}
//旋转卡壳-凸包最大距离的平方
long long diameter2(Polygon &p) {
    long long r = 0;
    int n = p.size(), a = 0;
    for (int i = 0; i < n; i++) {
        Vec e = p[(i + 1) % n] - p[i];
        while (onleft(p[(a + 1) % n] - p[a % n], e) || a == i) {
            r = max({r, (p[i] - p[a]).len2(), (p[(i + 1) % n] - p[a]).len2()});
            a = (a + 1) % n;
        }
        r = max({r, (p[i] - p[a]).len2(), (p[(i + 1) % n] - p[a]).len2()});
    }
    return r;
}
/* template end */
int n;
Points p;
void solve() {
    scanf("%d", &n);
    p.resize(n);
    for (int i = 0; i < n; i++)
        p[i].read();
    p = convex(p);
    long long r = diameter2(p);
//    printf("%lld.%lld\n", r / 2, (r & 1) * 5);
    printf("%lld\n",r);
}

C5G-最小曼哈顿距离：线段树模板

每组数据：输入：第一行n，表示n个点，接下来n行，每行x,y表示点坐标。

输出:定义曼哈顿距离： $d(P, Q)=|x_P - x_Q| + |y_P - y_Q|$ 。求全局最小曼哈顿距离。

#define LL long long
const LL inf = 1e18;
const int N = 4e5 + 5;
vector<LL> seg1(N), tag1(N);
vector<LL> seg2(N), tag2(N);
void pushdown(int l, int r, int id, vector<LL> &seg,vector<LL> &tag) {
    if (l != r && tag[id]) {
        tag[2 * id] = max(tag[2 * id], tag[id]);
        tag[2 * id + 1] = max(tag[2 * id + 1], tag[id]);
        seg[2 * id] = max(seg[2 * id], tag[id]);
        seg[2 * id + 1] = max(seg[2 * id + 1], tag[id]);
        tag[id] = -inf;
    }
}

void modify(int ll, int rr, int l, int r, int id, LL val,vector<LL> &seg, vector<LL> &tag) {
    if (ll <= l && r <= rr) {
        tag[id] = max(tag[id], val);
        seg[id] = max(tag[id], val);
        return;
    }
    int m = l + (r - l) / 2;
    pushdown(l, r, id, seg, tag);
    if (ll <= m) modify(ll, rr, l, m, 2 * id, val, seg, tag);
    if (m < rr) modify(ll, rr, m + 1, r, 2 * id + 1, val, seg, tag);
    seg[id] = max(seg[2 * id], seg[2 * id + 1]);
}

LL get(int ll, int rr, int l, int r, int id, vector<LL> &seg,vector<LL> &tag) {
    if (ll <= l && r <= rr) return seg[id];
    int m = l + (r - l) / 2;
    LL ret = -inf;
    pushdown(l, r, id, seg, tag);
    if (ll <= m) ret = max(ret, get(ll, rr, l, m, 2 * id, seg, tag));
    if (m < rr) ret = max(ret, get(ll, rr, m + 1, r, 2 * id + 1, seg, tag));
    return ret;
}
void solve(){
    int n; cin >> n;
    for (int i = 0; i <= 4 * n + 1; i++) {
        seg1[i] = tag1[i] = -inf;
        seg2[i] = tag2[i] = -inf;
    }
    vector<pair<int, int>> p(n);
    vector<int> py(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
        py[i] = p[i].second;
    }
    sort(py.begin(), py.end());
    map<int, int> id;
    for (int i = 0; i < n; i++) 
        id[py[i]] = i + 1;
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int u, int v) {
        return p[u] < p[v];
    });
    LL ans = inf;
    for (int i : order) {
        LL x = p[i].first, y = p[i].second;
        int od = id[y];
        LL d = get(1, od, 1, n, 1, seg1, tag1);
        ans = min(ans, x + y - d);
        d = od + 1 <= n ? get(od + 1, n, 1, n, 1, seg2, tag2) : -inf;
        ans = min(ans, x - y - d);
        modify(od, od, 1, n, 1, x + y, seg1, tag1);
        modify(od, od, 1, n, 1, x - y, seg2, tag2);
    }
    cout << ans << '\n';
}

FFT

C6B-高精度乘法:FFT模板

每组数据：输入两个十进制非负整数 $a, b$ （ $0\leq a, b< 10^{10^5}$ ）

输出：乘积

using ld = double;
const int N = (1 << 18) + 5;
const ld pi = acosl(-1.0);
struct Complex
{
    ld r, i;
    Complex() { r = 0; i = 0; }
    Complex(ld re, ld im) { r = re; i = im; }
    ld len2() const { return r * r + i * i; }
    Complex bar() const { return Complex(r, -i); }
};
Complex operator + (const Complex &x, const Complex &y) { return Complex(x.r + y.r, x.i + y.i); }
Complex operator - (const Complex &x, const Complex &y) { return Complex(x.r - y.r, x.i - y.i); }
Complex operator * (ld x, const Complex &y) { return Complex(x * y.r, x * y.i); }
Complex operator * (const Complex &x, ld y) { return Complex(x.r * y, x.i * y); }
Complex operator * (const Complex &x, const Complex &y) { return Complex(x.r * y.r - x.i * y.i, x.r * y.i + x.i * y.r); }
Complex operator / (const Complex &x, ld y) { return Complex(x.r / y, x.i / y); }
Complex operator / (const Complex &x, const Complex &y) { return x * y.bar() / y.len2(); }

char s[N], t[N];
int lens, lent,len;
Complex a[N], b[N];
Complex v[N];
int rev[N],ans[N];

void fft(Complex c[], int inv = 0) {
    for (int i = 0; i < len; i++) v[rev[i]] = c[i];
    for (int i = 2; i <= len; i <<= 1){
        Complex wn(cosl(2 * pi / i), sinl(2 * pi / i));
        for (int j = 0; j < len; j += i) {
            Complex w(1, 0);
            for (int k = 0; k < (i >> 1); k++) {
                Complex x = v[j + k], y = v[j + k + (i >> 1)] * w;
                v[j + k] = x + y;
                v[j + k + (i >> 1)] = x -y;
                w = w * wn;
            }
        }
    }
    if (inv){
        for (int i = 0; i < len; i++) v[i] = v[i] / len;
        for (int i = 1, j = len - 1; i < j; i++, j--) swap(v[i], v[j]);
    }
    for (int i = 0; i < len; i++) c[i] = v[i];
}

void solve() {
    scanf("%s", s); scanf("%s", t);
    lens = strlen(s); lent = strlen(t);
    len = 1;
    while (len <= lens + lent) len <<= 1;
    for (int i = 0; i < len; i++) {
        a[i] = b[i] = Complex(0, 0);
        ans[i] = 0;
    }
    for (int i = 0; i < lens; i++) a[i] = Complex(s[lens - 1 - i] - '0', 0);
    for (int i = 0; i < lent; i++) b[i] = Complex(t[lent - 1 - i] - '0', 0);
    for (int i = 0; i < len; i++) {
        rev[i] = 0;
        for (int j = 1, t = i; j < len; j <<= 1, t >>= 1)
            rev[i] <<= 1, rev[i] += t & 1;
    }//在此之前都是必写
    fft(a); fft(b);
    for (int i = 0; i < len; i++)  b[i] = a[i] * b[i];
    fft(b, 1);
    for (int i = 0; i < len; i++) {
        ans[i] += round(b[i].r);
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }
    while (len > 1 && ans[len - 1] == 0) len--;
    for (int i = len - 1; i >= 0; i--)  printf("%d", ans[i]);
    printf("\n");
}

字符串匹配

C6A-字符串匹配:kmp模板//也可以直接用find或strstr

每组数据：输入：两行两个字符串s,t,在s里匹配t,若一个位置被匹配了，那么该部分不能再次被匹配（两个匹配不能有交叉）

输出：一行若干整数，表示子串起始位置

const int N = 2e6;
char s[N], t[N];
int nxt[N];
bool kmp(int n, char *a, int m, char *b) {
    bool flag = true;int i, j，ans=0;
//    n=strlen(a);m=strlen(b);
    for (nxt[0] = j = -1, i = 1; i < n; nxt[i++] = j) {//求nxt数组
        while (~j && a[j + 1] != a[i]) j = nxt[j];
        if (a[j + 1] == a[i]) j++;
    }
    for (j = -1, i = 0; i < m; i++) {//匹配
        while (~j && a[j + 1] != b[i]) j = nxt[j];
        if (a[j + 1] == b[i]) j++;
        if (j == n - 1)  printf("%d ", i - n + 2), j = -1, flag = false;
        //if (j == n - 1) ans=i-n+1, j = nxt[j];匹配第一个
    }
    return flag;
    //return ans;
}

void solve() {
    scanf("%s", s); scanf("%s", t);
    int len1 = strlen(t), len2 = strlen(s);
    if (kmp(len1, t, len2, s)) cout << "-1";
    cout << endl;
}

C6E-前缀等于后缀的长度：Next数组

给定字符串 $s$ ，请你求出对于 $i=1,2,\ldots,|s|$ 而言，长度为 $i$ 的前缀和长度为 $i$ 后缀是否相同。

每组数据：输入：一行一个字符串

输出：从小打到大所有的 $i$

char s[1000010];
int next[1000010], ans[1000010];
void getNext(char *target) {
    int i = 0, j = -1; next[0] = -1;
    while (target[i] != '\0')
        if (j == -1 || target[i] == target[j]) next[++i] = ++j;
        else j = next[j];
}
void solve(){
    scanf("%s", s);
    getNext(s);
    int n = 1; ans[0] = strlen(s);
    for (int i = strlen(s); next[i] > 0; i = next[i])
        ans[n++] = next[i];
    for (int i = n - 1; i >= 0; i--) printf("%d ", ans[i]);
    printf("\n");
}
int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
    return 0;
}

C6D-最长回文子串:中心扩散定理

每组数据：输入：一个字符串

输出：最长回文子串

char ch[110005],pat[220005];
int pos,r[220005],ans,n;
void solve(){
    int i, j, u, v;
    scanf("%s", ch + 1);
    n = strlen(ch + 1);
    pat[0] = '@';
    ans = 0;
    for (int i = 0; i <= 2 * n + 2; i++) r[i] = 0;
    for (i = 1; i <= n; i++) pat[2 * i - 1] = ch[i], pat[2 * i] = '@';
    pos = 0, r[0] = 0;
    for (i = 1; i <= 2 * n; i++) {
        if (i <= pos + r[pos]) r[i] = min(pos + r[pos] - i, r[pos * 2 - i]);
        while (i > r[i] && pat[i + r[i] + 1] == pat[i - r[i] - 1]) r[i]++;
        if (i + r[i] > pos + r[pos]) pos = i;
        ans = max(ans, r[i]);
    }
    printf("%d\n", ans);
}

C6G-:字符串哈希表

给定一个只包含小写字母的字符串 $s$ ，请你判断该字符串的两个子串是否相等。

定义长度为的字符串 $s$ 的子串 $s u b [i, j]$ 为：

$\begin{cases} s_{i}s_{i+1} \cdots s_{j} &i \le j \\ s_{i} s_{i+1} \cdots s_{n} s_{1} \cdots s_{j} & i > j \end{cases}$

具体来说，对于字符串 $s$ ，给出两个子串 $s u b [a, b]$ 和 $s u b [x, y]$ ，请你判断两个子串是否相等

输入：第一行一个字符串，第二行一个数字Q，表示Q组查询，接下来Q行，每行四个数字a,b,x,y(保证两子串长度相等)

输出：Q行，若匹配"owo",不匹配"qeq"

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
struct Hash {//多项式哈希表
    //BASE:基数；P:大质数，取模确保不溢出；val:存放每个字符哈希值；pw:存储多项式系数
    long long BASE, P, val[MAXN], pw[MAXN];
    void init(int base, int p, string s) {
        BASE=base,P = p; int n = s.size();
        val[0] = s[0]; pw[0] = 1;
        for (int i = 1; i < n; i ++)
            val[i] = ((long long)val[i - 1] * base + s[i]) % p;
        for (int i = 1; i <= n; i ++) pw[i] = (long long)pw[i - 1] * base % p;
    }
    long long query(int l, int r) {//输出指定子串哈希值
        if (l) return (val[r] + P - (long long)val[l - 1] * pw[r - l + 1] % P) % P;
        return val[r];
    }
};
Hash hs; string s;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> s; int len = s.size();
    s = s + s;
    hs.init(233, 1000000007, s);
    int Q;  cin >> Q;
    while(Q--) {
        int a, b, x, y;
        cin >> a >> b >> x >> y;
        if(b < a) b += len;
        if(y < x) y += len;
        if(hs.query(a - 1, b - 1) == hs.query(x - 1, y - 1))
            cout << "owo\n";
        else cout << "qwq\n";
    }
    return 0;
}

课外

快读

#define ll long long
inline ll read() {
	ll s = 0, w = 1;
	char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') w = -1; c = getchar();}
	while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
	return s * w;
}

树状数组

// 此处为查询区间和的树状数组。
int bit[500010];
void add(int k, int x) {
	while (k <= n) {
		bit[k] += x;
		k += lowbit(k);
	}
}
int ask(int k) {
	int res = 0;
	while (k) {
		res += bit[k];
		k -= lowbit(k);
	}
	return res;
}

线段树

// 此处为区间修改区间查询区间和的线段树。
struct SegmentTree {
	ll sum[N << 2], lazy[N << 2];
	int l[N << 2], r[N << 2];
	void update(int rt) {
		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	}
	void pushdown(int rt) {
		if (!lazy[rt]) return ;
		sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt], lazy[rt << 1] += lazy[rt];
		sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
		lazy[rt] = 0;
		update(rt);
	}
	void build(int rt, int L, int R) {
		l[rt] = L, r[rt] = R;
		if (L == R) {
			sum[rt] = a[L];
			return ;
		}
		int mid = L + R >> 1;
		build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R);
		update(rt);
	}
	void change(int rt, int L, int R, int x) {
		if (L <= l[rt] && r[rt] <= R) {
			sum[rt] += (r[rt] - l[rt] + 1) * x;
			lazy[rt] += x;
			return ;
		}
		pushdown(rt);
		if (L <= r[rt << 1]) change(rt << 1, L, R, x);
		if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x);
		update(rt);
	}
	ll query(int rt, int L, int R) {
		if (L <= l[rt] && r[rt] <= R) return sum[rt];
		pushdown(rt);
		ll res = 0;
		if (L <= r[rt << 1]) res += query(rt << 1, L, R);
		if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R);
		return res;
	}
} tree;

并查集

struct Disjoint_Set {
	int p[N], size[N];
	void build() {
		for (int i = 1; i <= n; i++) p[i] = i, size[i] = 1;
	}
	int root(int x) {
		if (p[x] != x) return p[x] = root(p[x]);
		return x;
	}
	void merge(int x, int y) {
		x = root(x), y = root(y);
		if (size[x] > size[y]) swap(x, y);
		p[x] = y;
		size[y] += size[x];
	}
	bool check(int x, int y) {
		x = root(x), y = root(y);
		return x == y;
	}
} a;

堆优化Dijkstra

void dij(int s) {
	priority_queue <pii, vector<pii>, greater<pii> > q; 
	memset(dis, 0x7f7f7f7f, sizeof(dis));
	q.push({0, s});
	dis[s] = 0;
	while (!q.empty()) {
		pii u = q.top(); q.pop();
		int pos = u.second;
		if (vis[pos]) continue;
		vis[pos] = 1;
		for (int j = last[pos]; j; j = e[j].next) {
			int v = e[j].to;
			if (vis[v]) continue;
			if (dis[pos] + e[j].w < dis[v]) dis[v] = dis[pos] + e[j].w, q.push({dis[v], v});
		}
	}
}

乘法逆元

fac[0] = fac[1] = 1;
for (int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;

快速幂

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

矩阵快速幂

struct Martix {
	int n, m;
	ll a[N][N];
	void clear() {memset(a, 0, sizeof(a));}
	void init() {clear(); for (int i = 1; i <= n; i++) a[i][i] = 1;}
	Martix operator *(const Martix b) const {
		Martix res; res.clear(); res.n = n, res.m = b.m;
		for (int i = 1; i <= res.n; i++)
			for (int j = 1; j <= res.m; j++)
				for (int k = 1; k <= m; k++)
					res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
		return res;
	}
	Martix operator ^(ll x) const {
		Martix res, a = *this; res.n = res.m = n, res.init(); 
		while (x) {
			if (x & 1) res = res * a;
			a = a * a;
			x >>= 1;
		} 
		return res;
	}
} a;

欧拉素数筛

int prime[6000010], cnt;
bool isprime[N + 10];
void prim() {
	isprime[0] = isprime[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!isprime[i]) prime[++cnt] = i;
		for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
			isprime[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}

KMP

// s 和 t 为需要匹配的两个 char 类型数组。
// border[i] 表示 t 长度为 i 的前缀最长的 border 长度。
ls = strlen(s + 1), lt = strlen(t + 1);
int j = 0;
for (int i = 2; i <= lt; i++) {
	while (j >= 1 && t[j + 1] != t[i]) j = border[j];
	if (t[j + 1] == t[i]) j++;
	border[i] = j;
}
int sx = 1, tx = 0;
while (sx <= ls) {
	while (tx >= 1 && s[sx] != t[tx + 1]) tx = border[tx];
	if (t[tx + 1] == s[sx]) tx++;
	if (tx == lt) printf("%d\n", sx - lt + 1);
	sx++;
}

最长上升子序列

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

最大连续子序列和

#include <stdio.h>
int main() {
    int N, n, s, ans, m = 0;
    scanf("%d%d", &N, &n); //读取数组长度和序列中的第一个数
    ans = s = n; //把ans初始化为序列中的的第一个数
    for (int i = 1; i < N; i++) {
        if (s < m) m = s;
        scanf("%d", &n);s += n;
        if (s - m > ans) ans = s - m;
    }
    printf("%d\n", ans);
    return 0;
}