算法模板-2022

目录:

• • 树和图
  • 字符串和字典树
  • 记忆化搜索
  • 排序及逆序对
  • 离散化
  • 树链剖分
  • 素数筛法:
  • 同余定理
  • 单调栈
  • 数学期望
  • LCA
  • 计算几何

树和图

Acwing285. 没有上司的舞会
Ural 大学有 N 名职员，编号为 1～N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
输入格式
第一行一个整数 N。
接下来 N 行，第 i 行表示 i 号职员的快乐指数 Hi。
接下来 N - 1 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。
输出格式
输出最大的快乐指数。

数据范围
1≤N≤6000,
-128≤Hi≤127
输入样例：
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
输出样例：
5

#include
using namespace std;
const int N = 6500, M = 2 * N;
int h[N], e[M], ne[M], idx; 
int dp[N][2], a[N], vis[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u,int fa)
{
    dp[u][1] = a[u];
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j != fa)
        {
            dfs(j, u);
            dp[u][0] += max(dp[j][0], dp[j][1]);
            dp[u][1] += dp[j][0];
        }
    }
}

int main()
{
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int i = 0; i < n - 1; i ++){
        int x, y;
        cin >> x >> y;
        add(y, x);
        vis[x] = 1;
    }
    int root = 1;
    while(vis[root]) root ++;
    dfs(root, -1);
    cout << max(dp[root][0], dp[root][1]) << endl;
    return 0;
}

dijstra算法

#include
using namespace std;
const int N = 3000,INF = 0x3f3f3f3f;
int a[N][N];
int d[N],n,ts,te;
bool v[N];
int dijstra(int v0){
    v[v0]=true;
    for(int i=1;i<=n;i++){
        d[i]=a[v0][i];
    }
    for(int i=1;i<n;i++){
        int x=-1,minnum=INF;
        for(int j=1;j<=n;j++){
            if(v[j]==false&&(x==-1||minnum>d[j])){
                minnum=d[j];
                x=j;
            }
        }
        v[x]=true;
        for(int y=1;y<=n;y++){
            d[y]=min(d[y],d[x]+a[x][y]);
        }
    }
    return d[te];
}
int main(){
    int c;
    scanf("%d%d%d%d",&n,&c,&ts,&te);
    memset(a,INF,sizeof(a));
    while(c--){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=a[y][x]=min(a[y][x],z);
    }
    printf("%d\n",dijstra(ts));
}

单源最短路的综合应用.
重庆城里有 n 个车站，m 条 双向 公路连接其中的某些车站
每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。
在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 1，他有五个亲戚，分别住在车站 a,b,c,d,e。
过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。
怎样走，才需要最少的时间？
输入格式
第一行：包含两个整数 n,m，分别表示车站数目和公路数目。
第二行：包含五个整数 a,b,c,d,e，分别表示五个亲戚所在车站编号。
以下 m 行，每行三个整数 x,y,t，表示公路连接的两个车站编号和时间。
输出格式
输出仅一行，包含一个整数 T，表示最少的总时间。
数据范围
1≤n≤50000,
1≤m≤10^5,
1 1≤x,y≤n,
1≤t≤100
输入样例：
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7
输出样例：
21

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef pair<int, int> PII;

const int N = 50010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[6][N];
int source[6];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra(int start, int dist[])
{
    memset(dist, 0x3f, N * 4);
    dist[start] = 0;
    memset(st, 0, sizeof st);

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, start});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int dfs(int u, int start, int distance)
{
    if (u > 5) return distance;

    int res = INF;
    for (int i = 1; i <= 5; i ++ )
        if (!st[i])
        {
            int next = source[i];
            st[i] = true;
            res = min(res, dfs(u + 1, i, distance + dist[start][next]));
            st[i] = false;
        }

    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    source[0] = 1;
    for (int i = 1; i <= 5; i ++ ) scanf("%d", &source[i]);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < 6; i ++ ) dijkstra(source[i], dist[i]);

    memset(st, 0, sizeof st);
    printf("%d\n", dfs(1, 0, 0));

    return 0;
}

单源最短路的扩展应用.
有一天，琪琪想乘坐公交车去拜访她的一位朋友。
由于琪琪非常容易晕车，所以她想尽快到达朋友家。
现在给定你一张城市交通路线图，上面包含城市的公交站台以及公交线路的具体分布。
已知城市中共包含 n 个车站（编号1~n）以及 m 条公交线路。
每条公交线路都是 单向的，从一个车站出发直接到达另一个车站，两个车站之间可能存在多条公交线路。
琪琪的朋友住在 s 号车站附近。
琪琪可以在任何车站选择换乘其它公共汽车。
请找出琪琪到达她的朋友家（附近的公交车站）需要花费的最少时间。
输入格式
输入包含多组测试数据。
每组测试数据第一行包含三个整数 n,m,s，分别表示车站数量，公交线路数量以及朋友家附近车站的编号。
接下来 m 行，每行包含三个整数 p,q,t，表示存在一条线路从车站 p 到达车站 q，用时为 t。
接下来一行，包含一个整数 w，表示琪琪家附近共有 w 个车站，她可以在这 w 个车站中选择一个车站作为始发站。
再一行，包含 w 个整数，表示琪琪家附近的 w 个车站的编号。
输出格式
每个测试数据输出一个整数作为结果，表示所需花费的最少时间。
如果无法达到朋友家的车站，则输出 -1。
每个结果占一行。
数据范围
n≤1000,m≤20000,
1≤s≤n,
0 0 输入样例：
5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1
输出样例：
1
-1

#include
using namespace std;
const int N = 1011, M = 220000, INF = 0x3f3f3f3f;
int n, m, s;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];
bool st[N];

void add(int a,int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa()
{
    int hh = 0, tt = 1;
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    q[0] = s;
    
    while(hh!=tt){
        int  t = q[hh++]; 
        if(hh == N)hh = 0;
        st[t] = false;
        for(int i = h[t]; i!=-1 ; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt == N)tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    
}


int main()
{
    while(scanf("%d%d%d", &n, &m, &s)!=EOF)
    {
        memset(h, -1, sizeof h);
        idx = 0;
        
        int p,q,t;
        while (m -- ){
            scanf("%d%d%d",&p,&q,&t);
            add(q, p, t);
        }
        
        spfa();
        
        int ans = INF;
        int W;
        scanf("%d",&W);
        for(int i=0;i<W;i++){
            int z;
            scanf("%d",&z);
            ans = min(ans , dist[z]);
        }
        
        if(ans == INF)ans = -1;
        printf("%d\n",ans);
    }
    return 0;
}

Floyd：
给定 n 个变量和 m 个不等式。其中 n 小于等于 26，变量分别用前 n 的大写英文字母表示。
不等式之间具有传递性，即若 A>B 且 B>C，则 A>C。
请从前往后遍历每对关系，每次遍历时判断：
如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
如果发生矛盾，则结束循环，输出有矛盾；
如果循环结束时没有发生上述两种情况，则输出无定解。
输入格式
输入包含多组测试数据。
每组测试数据，第一行包含两个整数 n 和 m。
接下来 m 行，每行包含一个不等式，不等式全部为小于关系。
当输入一行 0 0 时，表示输入终止。
输出格式
每组数据输出一个占一行的结果。
结果可能为下列三种之一：
如果可以确定两两之间的关系，则输出 “Sorted sequence determined after t relations: yyy…y.”,其中’t’指迭代次数，'yyy…y’是指升序排列的所有变量。
如果有矛盾，则输出： “Inconsistency found after t relations.”，其中’t’指迭代次数。
如果没有矛盾，且不能确定两两之间的关系，则输出 “Sorted sequence cannot be determined.”。
数据范围
2≤n≤26，变量只可能为大写字母 A～Z。

输入样例1：
4 6
A A B C B A 3 2
A B 26 1
A 0 0
输出样例1：
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
输入样例2：
6 6
A B C F D E 0 0
输出样例2：
Inconsistency found after 6 relations.
输入样例3：
5 5
A B C D E 0 0
输出样例3：
Sorted sequence determined after 4 relations: ABCDE.

#include 
#include 
#include 
using namespace std;
const int N = 30;
int n, d[N][N], g[N][N];
int st[N];

void floyd()
{
    memcpy(d , g ,sizeof d);

    for(int k = 0 ; k < n ; k ++)
        for (int i = 0; i < n; i ++ )
            for(int j = 0; j < n ; j ++)
                    d[i][j] |= d[i][k] && d[k][j];
} 

int check()
{
    for(int i = 0 ; i < n; i ++)
        if(d[i][i]) return 2;    //如果产生矛盾则返回2
    for(int i = 0; i < n ;i ++)
        for(int j = 0; j < i ;j ++)
            if(!d[i][j] && !d[j][i]) //如果没有矛盾且没有关系的话就返回1
                return 0;
    return 1;   //没有矛盾且都有关系
}

char get_min(){
    for(int i = 0; i < n; i ++)
    {
        if(!st[i])
        {
            int fl = 1;
            for(int j = 0; j < n; j ++){
                if(!st[j] && d[j][i]){
                    fl = 0;
                    break;
                }
            }
            if(fl){
                st[i] = true;
                return i + 'A';
            }
        }

    }
}

int main()
{
    int m;
    while(scanf("%d%d",&n, &m) , n || m)
    {
        memset(g, 0, sizeof g);
        int type = 0, ans = 0;
        for(int i = 1; i <= m ; i ++)
        {
            char str[5];
            scanf("%s",str);

            int a = str[0] - 'A', b = str[2] - 'A';
            if(!type)
            {
                g[a][b] = 1;
                floyd();
                type = check();
                if(type)
                    ans = i;
            }
        }
        if(type == 0){
            printf("Sorted sequence cannot be determined.\n");
        }
        else if(type == 2){
            printf("Inconsistency found after %d relations.\n", ans);
        }
        else{
            printf("Sorted sequence determined after %d relations: ",ans);
            memset(st, 0, sizeof st);
            for(int i = 0 ; i < n; i ++)
            {
                printf("%c",get_min());
            }
            printf(".\n");
        }   
    }
    return 0;
}

最小生成树:
Prim：

#include 
#include 
#include 
using namespace std;
const int N = 500;
int n;
int dist[N], g[N][N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 1 ; j <= n ;j ++){
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        res += dist[t];
        st[t] = true;
        for(int j = 1 ; j <= n ; j ++){
            dist[j] = min(dist[j] , g[t][j]);
        }
    }
    return res;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            cin >> g[i][j];
        }
    }
    cout << prim() << endl;
}

Krusal：
给定一棵 N 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。
求增加的边的权值总和最小是多少。
注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。
输入格式
第一行包含整数 t，表示共有 t 组测试数据。
对于每组测试数据，第一行包含整数 N。
接下来 N?1 行，每行三个整数 X,Y,Z，表示 X 节点与 Y 节点之间存在一条边，长度为 Z。
输出格式
每组数据输出一个整数，表示权值总和最小值。
每个结果占一行。
数据范围
1≤N≤6000
1≤Z≤100
输入样例：
2
3
1 2 2
1 3 3
4
1 2 3
2 3 4
3 4 5
输出样例：
4
17

#include
using namespace std;
#define ll long long
#define x first
#define y second
const int N = 6010, M = 2 * N; 
int fa[N], sz[N];

struct Node{
    int a, b, c;
    bool operator < (const Node &t)
        {return c < t.c;}
}edg[M];
 
int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

void solve(){
    int n;
    cin >> n;
    for(int i = 0; i < n - 1; i ++){
        int x, y, z;
        cin >> x >> y >> z;
        edg[i] = {x, y, z};
    }
    sort(edg, edg + n - 1);
    for(int i = 0; i <= n ; i ++)fa[i] = i, sz[i] = 1;
    ll ans = 0;
    for(int i = 0; i < n - 1; i ++){
        int x = find(edg[i].a), y = find(edg[i].b), w = edg[i].c;
        if(x != y)
        { 
            ans += (sz[x] * sz[y] - 1) * (w + 1);
            fa[x] = y;
            sz[y] += sz[x];
        }
    }
    cout << ans << endl;
}

int main()
{
    int T;
    cin >> T;
    while(T --){
        solve();
    }
}

负环:
农夫约翰在巡视他的众多农场时，发现了很多令人惊叹的虫洞。
虫洞非常奇特，它可以看作是一条 单向 路径，通过它可以使你回到过去的某个时刻（相对于你进入虫洞之前）。
农夫约翰的每个农场中包含 N 片田地，M 条路径（双向）以及 W 个虫洞。
现在农夫约翰希望能够从农场中的某片田地出发，经过一些路径和虫洞回到过去，并在他的出发时刻之前赶到他的出发地。
他希望能够看到出发之前的自己。
请你判断一下约翰能否做到这一点。
下面我们将给你提供约翰拥有的农场数量 F，以及每个农场的完整信息。
已知走过任何一条路径所花费的时间都不超过 10000 秒，任何虫洞将他带回的时间都不会超过 10000 秒。
输入格式
第一行包含整数 F，表示约翰共有 F 个农场。
对于每个农场，第一行包含三个整数 N,M,W。
接下来 M 行，每行包含三个整数 S,E,T，表示田地 S 和 E 之间存在一条路径，经过这条路径所花的时间为 T。
再接下来 W 行，每行包含三个整数 S,E,T，表示存在一条从田地 S 走到田地 E 的虫洞，走过这条虫洞，可以回到 T 秒之间。
输出格式
输出共 F 行，每行输出一个结果。
如果约翰能够在出发时刻之前回到出发地，则输出 YES，否则输出 NO。
数据范围
1≤F≤5
1≤N≤500,
1≤M≤2500,
1≤W≤200,
1≤T≤10000,
1≤S,E≤N
输入样例：
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
输出样例：
NO
YES

#include
using namespace std;
const int N = 505,M = 5210;
int n;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N], cnt[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = b, w[idx] = c , ne[idx] = h[a], h[a] = idx ++;
}

bool spfa(){
    int hh = 0, tt = 0;
    memset(dist, 0, sizeof dist);
    memset(cnt , 0 ,sizeof cnt);
    memset(st, 0, sizeof st);
    for (int i = 1; i <= n; i ++ ){
        q[tt ++] = i ;
        st[i] = true;
    }
    while(hh != tt)
    {
        int t = q[hh ++];
        if(hh == N)hh = 0;
        st[t] = false;

        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n)return true;
                if(!st[j]){
                    q[tt ++] = j;
                    if(tt == N)tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}



int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        memset(h, -1, sizeof h);
        idx = 0;
        int m , W;
        scanf("%d%d%d", &n, &m, &W);
        for (int i = 0; i < m; i ++ ){
            int a, b, c;
            scanf("%d%d%d",&a, &b, &c);
            add(a, b, c),add(b, a, c);
        }
        for (int i = 0; i < W; i ++ ){
            int a, b, c;
            scanf("%d%d%d",&a, &b, &c);
            add(a, b, -c);
        }
        if(spfa())puts("YES");
        else puts("NO");  
    }
    return 0;
}

染色法判断二分图:
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。

数据范围
1≤n,m≤10^5
输入样例：
4 4
1 3
1 4
2 3
2 4
输出样例：
Yes

#include
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u, int c)
{
    color[u] = c;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!color[j]){
            if(!dfs(j, 3 - c)) return false;
        }
        else
         if(color[j] == c) return false;
    }
    return true;
}

void solve(){
    memset(h, -1, sizeof h);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i ++){
        int x, y;
        cin >> x >> y;
        add(x, y), add(y, x);
    }
    for(int i = 1; i <= n; i ++){
        if(!color[i])
        {
            if(!dfs(i, 1)){
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
}

int main()
{
    solve();
}

给定一个二分图，其中左半部包含 n1 个点（编号 1～n1），右半部包含 n2 个点（编号 1～n2），二分图共包含 m 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1、 n2 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。

数据范围
1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤105
输入样例：
2 2 4
1 1
1 2
2 1
2 2
输出样例：
2

#include
#include
using namespace std;
const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];

void add(int a , int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void init()
{
    memset(h,-1,sizeof h);
}

int find(int x)
{
    //遍历自己喜欢的女孩
    for(int i = h[x] ; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true;//那x就预定这个女孩了
            //如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩。配对成功
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }

        }
    }
    //自己中意的全部都被预定了。配对失败。
    return false;
}
int main()
{
    init();
    cin>>n1>>n2>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }


    int res = 0;
    for(int i = 1; i <= n1 ;i ++)
    {  
         //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
          memset(st,false,sizeof st);
        if(find(i)) 
          res++;
    }  

    cout<<res<<endl;
}

字符串和字典树

KMP模板:

#include 

using namespace std;

const int N = 1000010, M = 100110; //N为模式串长度，M匹配串长度

int n, m;
int ne[M]; //next[]数组，避免和头文件next冲突
char s[N], p[M];  //s为模式串， p为匹配串

int main()
{
    cin >> m >> p+1 >> n >> s+1;  //下标从1开始

    //求next[]数组
    for(int i = 2, j = 0; i <= m; i++)
    {
        while(j && p[i] != p[j+1]) j = ne[j];
        if(p[i] == p[j+1]) j++;
        ne[i] = j;
    }
    //匹配 *** 作
    for(int i = 1, j = 0; i <= n; i++)
    {
        while(j && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1]) j++;
        if(j == m)  //满足匹配条件，打印开头下标, 从0开始
        {
            //匹配完成后的具体 *** 作
            //如：输出以0开始的匹配子串的首字母下标
            printf("%d ", i - m);// (若从1开始，加1)
            j = ne[j];            //再次继续匹配
        }
    }

    return 0;
} 

Trie字典树:
维护一个字符串集合，支持两种 *** 作：
I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。
共有 N 个 *** 作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N，表示 *** 作数。
接下来 N 行，每行包含一个 *** 作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。
每个结果占一行。
5
I abc
Q abc
Q ab
I ab
Q ab
结果：
1
0
1

#include 
using namespace std;
const int N = 1e5 + 100;
int idx, son[N][26], cnt[N];
char str[N];

void insert(char str[])
{
    int p = 0;
    for(int i= 0; str[i]; i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p] ++;
}

int query(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}


int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++){
        char op[2];
        cin >> op >> str;
        if(op[0] == 'I') insert(str);
        else cout << query(str) << endl;
    }
    return 0;
}

最大异或对
在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入样例：
3
1 2 3
输出样例：
3

#include 
using namespace std;
const int N = 1e5 + 100, M = 31 * N;
int son[M][2], idx, cnt[N], a[N];

void insert(int x){
    int p = 0;
    for(int i = 30; i >= 0; i --){
        int u = (x >> i) & 1;
        if(!son[p][u])son[p][u] = ++idx;
        p = son[p][u];
    } 
}

int query(int x){
    int p = 0, ans = 0;
    for(int i = 30; i >= 0; i --){
        int u = (x >> i) & 1;
        if(son[p][!u]){
            ans |= (1 << i);
            p = son[p][!u];
        }
        else p = son[p][u];
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n;i ++){
        cin >> a[i];
        insert(a[i]);
    }
    int ans = 0;
    for(int i = 0; i < n; i ++)
        ans = max(ans, query(a[i]));
    cout << ans << endl;
}

字符串哈希(RK哈希):
Antinomy正在西大陆的法师圣殿修行，由于出色的天赋以及无敌的记忆能力（转生在异世带来的金手指），帮助他打破了精神海的限制成为了一名炼金法师。圣殿方面决定派他去破解一处秘境，这处秘境的入口处有着两条长度为\mathit nn的由小写字母组成的字符串。Antinomy发现它的金手指可以将任意一条字符串中的首字母移到其自身的末尾，并且不限制次数。当两个字符串相同时，秘境大门就可以打开。由于Antinomy的实力严重灌水，他自己无法判断能否通过金手指来打开秘境大门，希望你们能够帮助他解决这个问题，让他在异世界不被暴露。
输入:
5
abcde
Cdeab
输出:
Wow
输入:
5
abdea
Abade
输出:
TAT

#include  
typedef unsigned long long ull;
using namespace std;
const int maxn=200005+5;
const int maxm=200005+5;
const int base=29;
ull pow[maxm];
char W[maxm],T[maxn];
ull hashw[maxn],hasht[maxn];
int n;
ull hashs;
int ans;
void init()
{
    ans=0;
    hashs=0;
    pow[0]=1;
    for(int i=1;i<=200005;i++)//预处理base^n
    	pow[i]=pow[i-1]*base;
}
int main()
{
    scanf("%d",&n);
    init();//初始化
    scanf("%s",W+1);
    scanf("%s",T+1);
    int lens=n;
    int lent=n;
    for(int i=1;i<=n;i++){
    	hasht[i]=hasht[i-1]*base+(ull)(T[i]-'A'+1);
    	hashw[i]=hashw[i-1]*base+(ull)(W[i]-'A'+1);	
	}    
	int f=0;
    for(int i=1;i<=n;i++)
	{
		if(hashw[i]==hasht[n]-hasht[n-i]*pow[i] && hashw[n]-hashw[i]*pow[n-i]==hasht[n-i]){
			printf("wow\n");
			f=1;
			break;
		}
	} 
	if(f==0){
		printf("TAT\n");
	}
    return 0;
}

记忆化搜索

给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
在给定矩阵中，一条可行的滑行轨迹为 24?17?2?1。
在给定矩阵中，最长的滑行轨迹为 25?24?23?…?3?2?1，沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 R 和 C。
接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。
数据范围
1≤R,C≤300,
0≤矩阵中整数≤10000
输入样例：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出样例：
25

#include
using namespace std;
#define ll long long
#define x first
#define y second
const int N = 500;
int dp[N][N], a[N][N];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
int ans = 0, n, m;

int dfs(int x, int y){
	if(dp[x][y]) return dp[x][y];
	for(int i = 0; i < 4; i ++){
		int tx = x + dx[i], ty = y + dy[i];
		if(tx >= 0 && ty >= 0 && tx < n && ty < m && a[x][y] > a[tx][ty]){
			dp[x][y] = max(dp[x][y], dfs(tx, ty) + 1);
		} 
	}	
	ans = max(ans, dp[x][y]);
	return dp[x][y];
}

void solve()
{
     cin >> n >> m;
     for(int i = 0; i < n; i ++){
     	for(int j = 0; j < m; j ++){
     		cin >> a[i][j];  
	    }
	}
	for(int i = 0; i < n; i ++){
     	for(int j = 0; j < m; j ++){
     		dfs(i, j);
		}
    }
    cout << ans + 1 << endl;
}

int main(){ 
    solve();
}

排序及逆序对

快速排序:

#include 
using namespace std;
const int N = 1000010;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    return 0;
} 

归并排序求逆序对:

#include 
using namespace std;
#define ll long long
const int N = 1e6 + 10;

int q[N], tmp[N]; 
ll cnt = 0;

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid); merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ], cnt += 1ll * mid - i + 1;
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    cout << cnt << endl;
    return 0;
} 

离散化

离散化:
1.不去重的离散化

#include
#include
#include
#include
using namespace std;
struct node
{
	int val,id;
	bool operator < (const node &a)const//重载小于运算符用来排序
		return val<a.val;	//值小的在前面
};
int n;	//序列长度
node a[1005];//原序列
int f[1005];//离散化后的序列

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		a[i].id=i+1;
	} 
	sort(a, a + n);
	for(int i = 0; i < n; i ++)
		f[a[i].id] = i + 1;
	for(int i = 0; i < n; i ++)
		printf("%d ", f[i+1]);
	return 0;
} 

2.去重的离散化

#include
#include
#include
#include
using namespace std; 
int n;	//序列长度
int a[1005];//原序列 
vector<int> ys;

int find(int x){
	return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}

int main()
{
	scanf("%d",&n);
	for(int i = 0; i < n; i ++)
	{
		scanf("%d",&a[i]); 
		ys.push_back(a[i]);
	}
	sort(ys.begin(), ys.end());
	ys.erase(unique(ys.begin(),ys.end()),ys.end());//去重 
	for(int i = 0; i < n; i ++){
		cout << find(a[i]) << " ";
	} 
	return 0;
} 

组合数:

#include
using namespace std;
#define ll long long
const int N = 1e6+10,mod = 1e9+7;
ll G[N];

//预处理阶乘
void init(){
    G[0]=1;
    for(int i=1;i<N;i++)
        G[i]=(G[i-1]*i)%mod;
}

//快速幂
ll fastpow(ll a,ll b){
    ll res=1;
    for(;b;b>>=1){
        if(b&1)res=(res*a)%mod;
        a=a*a%mod;
    }
    return res%mod;
}

//求逆元
ll Inv(ll x){
    return fastpow(x, mod-2)%mod;
}

//求组合数
ll C(int n,int m){
    return ((G[n]%mod*Inv(G[n-m]*G[m]%mod)%mod))%mod;
}

//检查
bool cheack(ll x,int a,int b){
    while(x){
        if(x%10!=a && x%10!=b)return false;
        x/=10;
    }
    return true;
}

int main(){
    init();
    int a,b,n;
    scanf("%d%d%d",&a,&b,&n);
    ll ans = 0;
    for(int i=0;i<=n;i++){//i来枚举a的个数
        int j=n-i;        //j来表示b的个数
        ll x=i*a+j*b;
        if(cheack(x,a,b)){
            ans=(ans+C(n,i))%mod;
        }
    }
    printf("%lld\n",ans);
}

求组合数2:

#include
using namespace std;
#define ll long long
const int N = 100010, mod = 1e9 + 7;

ll G[N], Infact[N];

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

ll Inv(ll x){
    return Infact[x] % mod;
}

void init(){
    G[0] = Infact[0] = 1;
    for(int i = 1; i < N; i ++)
        G[i] = (G[i - 1] * i) % mod, Infact[i] = (Infact[i - 1] * fastpow(i, mod - 2)) % mod;
}

ll C(ll a, ll b)
{
    return (G[a] * Infact[b] % mod * Infact[a - b] % mod) % mod;
}

void solve(){
    ll a, b;
    cin >> a >> b;
    cout <<  C(a, b) << endl;
}

int main()
{
    init();
    int T;
    cin >> T;
    while(T -- )
    {
        solve();
    }
}

卢卡斯定理求组合数:

#include
using namespace std;
#define ll long long

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

ll Inv(ll x, ll mod){
    return fastpow(x, mod - 2, mod) % mod;
}

ll C(ll a, ll b, ll mod){
    ll res = 1;
    for(ll i = 1, j = a; i <= b; i ++, j --){
        res = (res * j) % mod;
        res = (res * Inv(i, mod)) % mod;        
    }
    return res;
}

ll lucas(ll a, ll b, ll mod){
    if(a < mod && b < mod) return C(a, b, mod);
    return (lucas(a % mod, b % mod, mod) * lucas(a / mod, b / mod, mod) % mod);
}

void solve(){
    ll a, b, mod;
    cin >> a >> b >> mod;
    cout << lucas(a, b, mod) << endl;
}

int main()
{
    int T;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

组合数(卡特兰数,卡特兰数递推公式C1=1,Cn=Cn-1*((4n-2)/(n+1))
满足条件的01序列
给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
输出的答案对 10^9+7 取模。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示答案。
数据范围
1≤n≤10^5
输入样例：
3
输出样例：
5
思路:画出二维图表，1往上，0往右，(y为1,x为0)那么方案不能超过y<=x这条轴，那么最后到达的点为(n,n),任何一条超过y<=x这条轴的直线都对应一条终点在(n-1,n+1)的直线.所以最终答案ans=C2n^n - C2n ^n-1=C2n ^2/(n+1).即卡特兰数.

#include
using namespace std;
#define ll long long
const int N = 2e5 + 100, mod = 1e9 + 7;
ll G[N], n;

void init(){
    G[0] = G[1] = 1;
    for(int i = 1; i < N; i ++)G[i] = (G[i - 1] * i) % mod;
}

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

ll Inv(ll x){
    return fastpow(x, mod - 2) % mod;
}

ll work(ll a, ll b){
    ll res = 1;
    for(ll i = 1, j = a; i <= b; i ++, j --){
        res = (res * j) % mod;
        res = (res * Inv(i)) % mod;        
    }
    res = res * Inv(n + 1) % mod;
    return res;
}

int main()
{
    init(); 
    cin >> n;
    ll a = 2 * n, b = n;
    ll ans = work(2 * n, n);
    cout << ans << endl;
}

树链剖分

给定一棵树，树中包含 n 个节点（编号 1～n），其中第 i 个节点的权值为 ai。
初始时，1 号节点为树的根节点。
现在要对该树进行 m 次 *** 作， *** 作分为以下 4 种类型：
1 u v k，修改路径上节点权值，将节点 u 和节点 v 之间路径上的所有节点（包括这两个节点）的权值增加 k。
2 u k，修改子树上节点权值，将以节点 u 为根的子树上的所有节点的权值增加 k。
3 u v，询问路径，询问节点 u 和节点 v 之间路径上的所有节点（包括这两个节点）的权值和。
4 u，询问子树，询问以节点 u 为根的子树上的所有节点的权值和。
输入格式
第一行包含一个整数 n，表示节点个数。
第二行包含 n 个整数，其中第 i 个整数表示 ai。
接下来 n?1 行，每行包含两个整数 x,y，表示节点 x 和节点 y 之间存在一条边。
再一行包含一个整数 m，表示 *** 作次数。
接下来 m 行，每行包含一个 *** 作，格式如题目所述。
输出格式
对于每个 *** 作 3 和 *** 作 4，输出一行一个整数表示答案。
数据范围
1≤n,m≤105,
0≤ai,k≤105,
1≤u,v,x,y≤n
输入样例：
5
1 3 7 4 5
1 3
1 4
1 5
2 3
5
1 3 4 3
3 5 4
1 3 5 10
2 3 5
4 1
输出样例：
16
69

#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, M = N << 1;

int n, m;
int h[N], w[N], e[M], ne[M], idx; //建树
int id[N], nw[N], cnt; //id:节点的dfn序编号，nw[id[i]]是i的权值w（w -> nw的映射）
int dep[N], sz[N], top[N], fa[N], son[N];
//sz:子树节点个数，top:重链的顶点，son:重儿子，fa:父节点
struct SegmentTree
{
    int l, r;
    LL sum, flag;
}tr[N << 2];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
//dfs1预处理
void dfs1(int u, int father, int depth)
{
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j; //重儿子是子树节点最多的儿子
    }
}
//dfs2做剖分（t是重链的顶点）
void dfs2(int u, int t)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
    if (!son[u]) return; //叶节点结束
    dfs2(son[u], t); //重儿子重链剖分
    //处理轻儿子
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j); //轻儿子的重链顶点就是他自己
    }
}

//------------------------线段树的部分------------------------\

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.flag)
    {
        left.sum += root.flag * (left.r - left.l + 1);
        left.flag += root.flag;
        right.sum += root.flag * (right.r - right.l + 1);
        right.flag += root.flag;
        root.flag = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, nw[r], 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int k)
{
    if (l <= tr[u].l && r >= tr[u].r)
    {
        tr[u].flag += k;
        tr[u].sum += k * (tr[u].r - tr[u].l + 1);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) update(u << 1, l, r, k);
    if (r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}

LL query(int u, int l, int r)
{
    if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL res = 0;
    if (l <= mid) res += query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

//------------------------线段树的部分------------------------\

void update_path(int u, int v, int k)
{
    while (top[u] != top[v])    //向上爬找到相同重链
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, id[top[u]], id[u], k);    //dfs序原因，上面节点的id必然小于下面节点的id
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[u], k); //在同一重链中，处理剩余区间
}
LL query_path(int u, int v)
{
    LL res = 0;
    while (top[u] != top[v])    //向上爬找到相同重链
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    res += query(1, id[v], id[u]);  //在同一重链中，处理剩余区间
    return res;
}
void update_tree(int u, int k) //子树全部加上k
{
    update(1, id[u], id[u] + sz[u] - 1, k); //由于dfs序的原因，可以利用子树节点个数直接找到区间
}
LL query_tree(int u)
{
    return query(1, id[u], id[u] + sz[u] - 1); //原因同上
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 1; i <  n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs1(1, -1, 1);
    dfs2(1, 1);
    build(1, 1, n);
    scanf("%d", &m);
    while (m -- )
    {
        int t, u, v, k;
        scanf("%d%d", &t, &u);
        if (t == 1)
        {
            scanf("%d%d", &v, &k);
            update_path(u, v, k);
        }
        else if (t == 2)
        {
            scanf("%d", &k);
            update_tree(u, k);
        }
        else if (t == 3)
        {
            scanf("%d", &v);
            printf("%lld\n", query_path(u, v));
        }
        else printf("%lld\n", query_tree(u));
    }
    return 0;
}

素数筛法:

1.埃氏筛法.

void Primes(int n)
{
    for (int i = 2; i < n; i++) {
        if (v[i])continue;
        prime[cnt++] = i;
        for (int j = i; j <= n / i; j++) {
            v[i * j] = true;
        }
    }
}

2线性筛.

void init()
{
    for(int i = 2; i < N; i ++){
        if(!st[i])min_primes[i] = i , primes[cnt ++] = i;
        for(int j = 0; i * primes[j] < N; j ++){
            st[i*primes[j]] = true;
            min_primes[i*primes[j]] = primes[j];
            if(i % primes[j] == 0)break;
        }
    } 
}

同余定理

Acwing 203. 同余方程
求关于 x 的同余方程 ax≡1(modb) 的最小正整数解。
输入格式
输入只有一行，包含两个正整数 a,b，用一个空格隔开。
输出格式
输出只有一行，包含一个正整数 x，表示最小正整数解。
输入数据保证一定有解。
数据范围
2≤a,b≤210^9
输入样例：
3 10
输出样例：
7

#include 
#include 
#include 

using namespace std;

typedef long long LL;

int exgcd(int a, int b, int &x, int &y)
{
    //a∗1+b∗0=gcd(a,b),x=1,y=0
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    int a,b;
    cin >> a >> b;
    int x,y;
    exgcd(a,b,x,y);
    cout << (x%b+b)%b << endl;
    return 0;
}

单调栈

一天Antinomy正在练习魔法，他将n个魔法咒语排成一排，每个咒语都拥有一个威力值ai
一个魔法是一串非空连续的魔法咒语构成，一个魔法的施法时间就是咒语的数量，一个魔法的威力就是该魔法中咒语的最小威力值
Antinomy很好奇，对于相同的施法时间x(1≤x≤n),魔法的最大威力是多少，从x = 1开始输出.
5
3 7 7 2 4
输出:
7 7 3 2 2
施放时间x=1魔法最大威力的子数组是[7]
施放时间x=2魔法最大威力的子数组是[7,7]
施放时间x=3魔法最大威力的子数组是[3,7,7]
施放时间x=4魔法最大威力的子数组是[3,7,7,2],[7,7,2,4]
施放时间x=5魔法最大威力的子数组是[3,7,7,2,4]

#include
#include
using namespace std;
int a[200010]={0};
int ans[200010]={0};
int L[200010]={0};
int R[200010]={0};
stack<int>st;

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(!st.empty()&&a[i]<a[st.top()])R[st.top()]=i,st.pop();
        st.push(i);
    }
    while(!st.empty())R[st.top()]=n+1,st.pop();
    for(int i=n;i;i--){
        while(!st.empty()&&a[i]<a[st.top()])L[st.top()]=i,st.pop();
        st.push(i);
    }
    while(!st.empty())L[st.top()]=0,st.pop();
    for(int i=1;i<=n;i++){
        ans[R[i]-L[i]-1]=max(a[i],ans[R[i]-L[i]-1]);
    }
    for(int i=n-1;i>=0;i--){
        ans[i]=max(ans[i],ans[i+1]);
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}

数学期望

给出一个有向无环的连通图，起点为 1，终点为 N，每条边都有一个长度。
数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。
绿豆蛙从起点出发，走向终点。
到达每一个顶点时，如果有 K 条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K。
现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？
输入格式
第一行: 两个整数 N，M，代表图中有 N 个点、M 条边。
第二行到第 1+M 行: 每行 3 个整数 a,b,c，代表从 a 到 b 有一条长度为 c 的有向边。
输出格式
输出从起点到终点路径总长度的期望值，结果四舍五入保留两位小数。

数据范围
1≤N≤10^5,
1≤M≤2N
输入样例：
4 4
1 2 1
1 3 2
2 3 3
3 4 4
输出样例：
7.00

#include
#define x first
#define y second
#define ll long long
using namespace std;
const int N = 1e5 + 100, M = N << 1;
int idx, h[N], e[M], w[M], ne[M], sz[N];
double  dp[N];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

double dfs(int u){
    if(dp[u] >= 0) return dp[u];
    dp[u] = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dp[u] += 1.0 * (w[i] + dfs(j)) / sz[u];
    }
    return dp[u];
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i <= n; i ++) dp[i] = h[i] = -1;
    for(int i = 0 ; i < m; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        sz[a] ++;
    }
    printf("%.2lf\n", dfs(1));
    return 0;
}

LCA

倍增LCA:
树上差分:一棵树n个点,m次询问求x,y的最短距离

#include
using namespace std;
const int N = 40010 , M = 2 * N;

int n, m, root;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];
int q[N];

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs(int root)
{
    memset(depth , 0x3f , sizeof depth);
    depth[0] = 0;
    depth[root] = 1;
    int hh = 0 ,tt = 0;
    q[tt ++] = root;
    while(hh != tt){
        int t = q[hh ++];
        if(hh == N)hh = 0;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(depth[j] > depth[t] + 1){
                depth[j] = depth[t] + 1;
                q[tt++] = j;
                if(tt == N)tt = 0;
                fa[j][0] = t;
                for(int k = 1; k <= 15; k ++)
                    fa[j][k] = fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int lca(int a, int b)
{
    if(depth[a] < depth[b])swap(a,b);
    for(int k = 15; k >= 0; k --)
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if(a == b) return a;
    for(int k = 15; k >= 0; k --)
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

int main()
{
    memset(h, -1, sizeof h);
    idx = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int a, b;
        scanf("%d%d",&a,&b);
        if(b == -1) root = a;
        else add(b, a),add(a, b);
    }

    bfs(root);

    int m;
    scanf("%d", &m);

    while(m --)
    {
        int a , b , c;
        scanf("%d%d",&a,&b);
        c = lca(a , b);
        if(c == a)puts("1");
        else if(c == b)puts("2");
        else puts("0");
    }

    return 0;
}

计算几何

基础:
计算玩具收纳盒中，每个分区内的玩具数量。
约翰的父母有一个烦恼----约翰每次玩完玩具以后总会将玩具乱扔。
他们为约翰准备了一个长方形的玩具收纳盒，用来放他的玩具。
但是约翰非常调皮，每次都非常随意的将玩具扔进盒子中，使得所有玩具都随意混在一起，这让约翰难以找到他喜欢的玩具。
对此，约翰的父母想出了一个对策，用若干个纸板将收纳盒分隔成若干个分区，这样至少扔到不同分区的玩具之间还是能分开的。
下面是一个收纳盒的俯视图示例。
你的任务是，每当约翰将玩具扔进收纳盒中时，确定每个分区中有多少个玩具。
输入格式
本题包含多组测试数据。
对于每组数据，第一行包含 6 个整数 n,m,x1,y1,x2,y2，表示共有 n 个纸板，m 个玩具，收纳盒的左上角坐标为 (x1,y1)，右下角坐标为 (x2,y2)。
接下来 n 行，每行包含两个整数 Ui,Li，表示第 i 个纸板的两端点坐标分别为 (Ui,y1) 和 (Li,y2)。数据保证纸板之间不相交，且按照从左至右顺序依次给出。
接下来 m 行，每行包含两个整数 Xj,Yj，表示第 j 个玩具的位置坐标。玩具的给出顺序是随机的。数据保证玩具不会恰好落在纸板上，也不会落在盒子外。
输入由包含单个 0 的一行结束。
输出格式
对于每组数据，输出 n+1 行。
n 个纸板将收纳盒划分为了 n+1 个分区，从左到右编号为 0∼n。
按照分区编号从小到大的顺序，每行输出一行信息 i: j，其中 i 表示分区编号，j 表示分区内玩具数量。
每组数据之间，用空行隔开。

#include 
#include 
#include 
using namespace std;
#define ll long long
const int N = 5050;
int n, m;
struct Point{
    ll x, y;
}p1[N],p2[N];
ll x1, y1, x2, y2;

ll cross(ll x1,ll y1,ll x2,ll y2){
    return x1 * y2 - x2 * y1;
}


ll area(Point a,Point b,Point c){
    return cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

int find(ll x,ll y){
    int l = 0, r = n;
    while(l < r){
        int mid = l + r >> 1;
        if(area(p2[mid], p1[mid], {x,y}) > 0)r = mid;
        else l = mid + 1;
    }
    return r;
}

int main()
{
    int T = 1;
    while(scanf("%d%d%lld%lld%lld%lld", &n, &m, &x1, &y1, &x2, &y2),n)
    {
        if(T++ > 1)printf("\n");
        p1[n] = {x2, y1};p2[n] = {x2, y2};
        for(int i = 0; i < n; i ++){
            ll u, l;
            scanf("%lld%lld",&u, &l);
            p1[i] = {u, y1}; p2[i] = {l, y2};
        }
        int ans[N];
        memset(ans, 0 , sizeof ans);
        while (m -- ){
            ll x, y;
            scanf("%lld%lld",&x, &y);
            ans[find(x,y)] ++;
        }
        for(int i = 0; i <= n; i ++){
            printf("%d: %d\n",i, ans[i]);
        }    
    }
    return 0;
}

在二维平面内有 n 条线段，请你编写一个程序，判断是否存在一条直线满足将这 n 条线段投影到该直线上后，所有的投影线段至少具有一个公共点。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含整数 n，表示共有 n 条线段。
接下来 n 行，每行包含四个实数 x1,y1,x2,y2，其中 (x1,y1) 和 (x2,y2) 是一条线段的两端点坐标。
输出格式
对于每组数据，如果存在满足条件的线段，则输出一行 Yes!，否则输出一行 No!。
如果两个浮点数 a 与 b 满足 |a-b|<10^-8，则你可以认为这两个数相等。
数据范围
1≤T≤100,
1≤n≤100,
-10^{9≤x1,y1,x2,y2≤10}9

题意:求是否存在一条直线，使所有线段到这条直线的投影至少有一个点

思路：计算几何。这道题要思考到两点：
1.把问题转化为是否存在一条直线与每条线段都有交点。证明：若存在一条直线l和所有线段相交，做一条直线m和l垂直，则m就是题中要
求的直线，所有线段投影的一个公共点即为垂足。
2.枚举两两线段的各一个端点，连一条直线，再判断剩下的线段是否都和这条直线有交点。证明：若l和所有线段相交，则可保持l和
所有线段相交，左右平移l到和某一线段交于端点停止（“移不动了”）。然后绕这个交点旋转，也是转到“转不动了”（和另一线段交于其一个
端点）为止。这样就找到了一个新的满足题意，而且经过其中两线段的端点。

判断线段和直线l是否相交的方法：
1.利用叉积的性质，判断线段的两个端点是否在直线两边
2.求线段所在直线tmp，求tmp与l的交点p，由线段两端点到p的距离之和，与线段的距离比较，若相等则证明线段与直线相交。

#include 
#include 
#include 
#include 
using namespace std;
const int N = 150;
const double eps = 1e-8;
int n;

struct Point{
    double x, y;
}p[2 * N];

struct Segment{
    double x1, y1, x2, y2;
}seg[N];

int cmp(double x, double y){
    if(fabs(x - y) < eps)return 0;
    if(x < y)return -1;
    return 1;
}

int sign(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    return 1;
}

double cross(double x1, double y1, double x2, double y2){
    return x1 * y2 - x2 * y1;
}

double area(Point a, Point b, double x, double y){
    return cross(a.x - b.x, a.y - b.y, x - b.x, y - b.y);
}


bool check(){
    for(int i = 0; i < 2 * n; i ++){
        for(int j = i + 1; j < 2 * n; j ++){
            if(!cmp(p[i].x, p[j].x) && !cmp(p[i].y, p[j].y))continue;
            bool flag = true;
            for(int k = 0; k < n; k ++){
                if(sign(area(p[i], p[j], seg[k].x1, seg[k].y1))*sign(area(p[i], p[j], seg[k].x2, seg[k].y2)) > 0){
                    flag = false;
                    break;
                }
            }
            if(flag)return true;
        }
    }
    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for (int i = 0, j = 0; i < n; i ++ ){
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            p[j ++] = {x1, y1};
            p[j ++] = {x2, y2};
            seg[i] = {x1, y1, x2, y2};
        }
        if(check())puts("Yes!");
        else puts("No!");
    }
    return 0;
}

凸包:

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e4 + 100;
int n;
int stk[N], used[N];
struct Point {
    double x, y;
    bool operator< (const Point &t) const{
        if(x == t.x) return y > t.y;
        return x < t.x;
    }
}p[N];

double get_dist(Point a,Point b){
    double d1 = a.x - b.x;
    double d2 = a.y - b.y;
    return sqrt(d1 * d1 + d2 * d2);
}

double cross(double x1, double y1, double x2, double y2){
    return x1 * y2 - x2 * y1;
}

double area(Point a, Point b, Point c){
    return cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

double andrew(){
    int top = 0;
    for(int i = 0; i < n; i ++){
        while(top >= 2 && area(p[stk[top - 1]], p[stk[top]], p[i]) >= 0){
            if(area(p[stk[top - 1]], p[stk[top]], p[i]) > 0)
                used[stk[top --]] = false;
            else 
                top --;
        }
        stk[++ top] = i;
        used[i] = true;
    }
    used[0] = false;
    for(int i = n - 1; i >= 0; i --){
        if(used[i]) continue;
        while(top >= 2 && area(p[stk[top - 1]], p[stk[top]], p[i]) >= 0)
            top --;
        stk[++ top] = i;
    }
    double ans = 0;
    for(int i = 2; i <= top; i ++){
        ans += get_dist(p[stk[i]], p[stk[i-1]]);
    }
    return ans;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n ; i ++){
        scanf("%lf%lf",&p[i].x, &p[i].y);
    }
    sort(p, p + n);
    double ans = andrew();
    printf("%.2lf\n", ans);
    return 0;
}

最小圆覆盖:
在一个二维平面上给定 N 个点，请你画出一个最小的能够包含所有点的圆。
圆的边上的点视作在圆的内部。

#include 
#include 
#include 
#include 
using namespace std;
#define x first
#define y second
const int N = 1e5 + 10;
const double eps = 1e-8, PI = acos(-1);
typedef pair<double, double> PDD;
int n;
PDD q[N];
struct Circle{
    PDD p;
    double r;
};
int sign(double x){
    if(fabs(x) < eps) return 0;
    if(x > 0) return 1;
    return -1;
}
int dcmp(double x, double y){
    if(fabs(x - y) < eps) return 0;
    if(x > y) return 1;
    return -1;
}
PDD operator- (PDD a, PDD b){
    return {a.x - b.x, a.y - b.y};
}
PDD operator+ (PDD a, PDD b){
    return {a.x + b.x, a.y + b.y};
}
PDD operator* (PDD a, double t){
    return {a.x * t, a.y * t};
}
double operator* (PDD a, PDD b){
    return a.x * b.y - a.y * b.x;
} 
PDD operator/ (PDD a, double t){
    return {a.x / t, a.y / t};
}
PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w){
    auto u = p - q;
    double t = w * u / (v * w);
    return p + v * t;
}
PDD rotate(PDD a, double t){
    return {a.x * cos(t) + a.y * sin(t), -a.x * sin(t) + a.y * cos(t)};
}
double get_dist(PDD a, PDD b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
pair<PDD,PDD> get_line(PDD a, PDD b){
    return {(a + b)/ 2, rotate(b - a, PI / 2)};
}
Circle get_Cicle(PDD a,PDD b,PDD c){
    auto u = get_line(a, b), v = get_line(a, c);
    auto p = get_line_intersection(u.x, u.y, v.x, v.y);
    return {p, get_dist(p, a)};
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++){
        scanf("%lf%lf", &q[i].x, &q[i].y);
    }
    random_shuffle(q, q + n);
    Circle c({q[0], 0});
    for(int i = 0; i < n; i ++){
        if(dcmp(c.r, get_dist(c.p, q[i])) < 0)
        {
            c = {q[i], 0};
            for(int j = 0; j < i; j ++){
                if(dcmp(c.r, get_dist(c.p, q[j])) < 0){
                    c = {(q[i] + q[j]) / 2, get_dist(q[i], q[j]) / 2 };
                    for(int k = 0; k < j; k ++){
                        if(dcmp(c.r, get_dist(c.p, q[k])) < 0){
                            c = get_Cicle(q[i], q[j], q[k]);
                        }
                    }
                }
            }
        }
    }
    printf("%.10lf\n", c.r);
    printf("%.10lf %.10lf\n", c.p.x, c.p.y);
    return 0;
}