• 汪汪熊の模板

    STL

    二分

    整数二分

    答案尽量往左找

    int binary_find(int l, int r)
{
    while(l < r)
    {
        int mid = (l + r) >> 1;//向下取整
        if(check(mid))l = mid + 1;
        else r = mid;
    }
    return l;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    答案尽量往右找

    int binary_find(int l, int r)
{
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;//向上取整
        if(check(mid))l = mid;
        else r = mid - 1;
    }
    return l;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    浮点二分

    double binary_find(double l, double r)
{
    double eps = 1e-6;//一般比要求的精度多两位
    while(l + eps < r)
    {
        double mid = (l + r) / 2;
        if(check(mid))l = mid;
        else r = mid;
    }
    return l;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    二分答案

    前缀和

    一维前缀和

    for(int i = 1; i <= n; ++i)
{
    scanf("%d", &arr[i]);
    arr[i]+=arr[i-1];
}

    • 1
    • 2
    • 3
    • 4
    • 5

    二维前缀和

    预处理

    s[i,j]=s[i,j-1]+s[i-1,j]-s[i-1,j-1]+arr[i,j]

    • 1

    查询

    矩形 ( x 1 , y 1 ) (x1,y1) (x1,y1)到 ( x 2 , y 2 ) (x2,y2) (x2,y2)内所有元素的和为

    sum=s[x2,y2]-s[x2,y1-1]-s[x1-1,y2]+s[x1-1,y1-1]

    • 1

    差分

    一维差分

    二维差分

    #include <iostream>
using namespace std;
const int MAXN=1010;
int a[MAXN][MAXN],b[MAXN][MAXN];
int n,m,q,x1,y1,x2,y2,c;

//以(x1,y1)左上角，(x2,y2)右下角的矩阵所有数加上一个c
void insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&a[i][j]);
            insert(i,j,i,j,a[i][j]);
        }
    while(q--)
    {
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        insert(x1,y1,x2,y2,c);
    }
    
    //输出矩阵中每个元素的值
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
            printf("%d ",b[i][j]);
        }
        printf("\n");
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    离散化

    sort(v.begin(),v.end())
v.erase(unique(v.begin(),v.end()),v.end());
再二分求得下标，注意求得的下标有时候要+1

    • 1
    • 2
    • 3

    单调栈

    求一个序列里的某个数，左边或者右边离它最近的比它小或者比它大的第一个数

    while(arr[top]>=x)top--;
while(arr[top]<=x)top--;

    • 1
    • 2

    单调队列

    一般用来求一个固定窗口内的最大值或者最小值

    if(hh<=tt && q[hh]<=i-k)hh++;
while(hh<=tt && arr[q[tt]]>=arr[i])tt--;
q[++tt]=i;

    • 1
    • 2
    • 3

    字符串

    KMP

    #include<bits/stdc++.h>

using namespace std;
const int MAXN = 1e6 + 10;
int n, m, ne[MAXN];
char p[MAXN], s[MAXN];

int main()
{
    cin >> n >> (p + 1) >> m >> (s + 1);

    for(int i = 2, j = 0; i <= n; ++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 <= m; ++i)
    {
        while(j && s[i] != p[j + 1])j = ne[j];
        if(s[i] == p[j + 1])j++;
        if(j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    trie树

    void insert()
{
    int p=0;//每次插入都是从第一行开始的，也就是p=0
    for(auto ch:str)
    {
        int u=ch-'a';
        if(!arr[p][u])//如果这个格子还没被用，那么就把这个字母放到这个格子
            arr[p][u]=++idx;
        p=arr[p][u];//指向下一个
    }
    ++cnt[p];//该字符串数目+1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    字符串哈希

    #include<bits/stdc++.h>

using namespace std;
const int MAXN = 1e5 + 10, P = 131;
#define ULL unsigned long long

ULL p[MAXN], arr[MAXN];
ULL n, m, l1, r1, l2, r2;
char str[MAXN];

ULL get(int l, int r)
{
    return arr[r] - arr[l - 1];
}

int main()
{
    cin >> n >> m;
    p[0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        cin >> str[i];
        p[i] = p[i - 1] * P;
        arr[i] = (str[i] - 'a' + 1) * p[i];
        arr[i] += arr[i - 1];
    }

    while(m--)
    {
        cin >> l1 >> r1 >> l2 >> r2;
        if(l1 > l2)swap(l1, l2), swap(r1, r2);
        if(get(l1, r1) * p[l2 - l1] == get(l2, r2))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    并查集

    初始化

    void init()
{
	for(int i=1;i<=n;++i）p[i]=i;
}

    • 1
    • 2
    • 3
    • 4

    查找祖宗结点

    int find(int x)
{
	if(p[x]!=x)//说明x不是根节点
		p[x]=find(p[x]);
	return p[x];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    合并a，b两个集合

    p[find(a)]=find(b);

    • 1

    查询

    if(find(a)==find(b))

    • 1

    图论

    邻接表存图

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


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    Dijkstra

    朴素Dijkstra算法 O ( n 2 ) O(n^2) O(n2)，要记得把arr数组初始化为inf

    int arr[510][510], dis[510], flag[510];
int n, m, x, y, z;

int dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));//把距离初始化为最大值
    dis[1] = 0;
//    flag[1] = true;//不能加这句话
    for(int i = 1; i <= n; ++i)
    {
        int t = -1;
        for(int j = 1; j <= n; ++j)//找到目前最小距离的下标
            if(!flag[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
                
        flag[t] = true;//t这个点已经确定了，所以把它加入已知最短距离的点的集合
        
        for(int j = 1; j <= n; ++j)//更新相连的点的距离
            dis[j] = min(dis[j], dis[t] + arr[t][j]);
    }
    return dis[n] == INF ? -1 : dis[n];
}

int main()
{
    memset(arr, 0x3f, sizeof(arr));
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &x, &y, &z);
        arr[x][y] = min(arr[x][y], z);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    堆优化Dijkstra

    int dijkstra()//用优先队列优化
{
    memset(dis, 0x3f, sizeof(dis));//把距离初始化为最大值
    dis[1] = 0;
    priority_queue<PII,vector<PII>,greater<>>heap;
    heap.push({0,1});//前面是距离，后面是点
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int distance=t.first,point=t.second;
        if(flag[point])//如果这个点已经被处理过了就不需要再处理了
            continue;
        flag[point]=true;//此时的point一定是当前距离最小的点，直接加入已处理过的点的集合
        for(int i=h[point];i!=-1;i=ne[i])//这里的i就相当于idx
        {
            int j=e[i];
            if(dis[j]>distance+w[i])//因为这里的i相当于idx，所以可以用w[i]
            {
                dis[j]=distance+w[i];
                heap.push({dis[j],j});//注意是先存距离，再存点
            }
        }
    }
    return dis[n] == INF ? -1 : dis[n];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    bellman-ford （有边数限制的最短路，可能存在负权路）

    例题：AcWing 853.有边数限制的最短路

    #include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;

struct Edge
{
    int a,b,c;
}edge[MAXN];
int dist[MAXN],backup[MAXN],n,m,k,x,y,z;

int bellman_ford()
{
    memset(dist,0x3f,sizeof(dist));//初始化
    dist[1]=0;
    
    for(int i=1;i<=k;++i)
    {
        memcpy(backup,dist,sizeof(dist));//记得备份啊
        for(int j=1;j<=m;++j)
            dist[edge[j].b]=min(dist[edge[j].b],backup[edge[j].a]+edge[j].c);
    }
    
    if(dist[n]>0x3f3f3f3f/2)
        printf("impossible");
    else
        printf("%d",dist[n]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        edge[i]={x,y,z};
    }
    
    bellman_ford();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    spfa

    spfa求最短路

    void spfa()
{
    memset(dist, 0x3f, sizeof(dist));//别忘了初始化
    dist[1] = 0;//别忘了初始化
    queue<int> Q;
    Q.push(1);//压入第一个元素
    st[1] = true;//那第一个元素状态设置为true
    while(Q.size())//只要队列不空
    {
        int t = Q.front();
        Q.pop();
        st[t] = false;//这里要设置成false，因为一个点可能会被更新多次
        for(int i = h[t]; i != -1; i = ne[i])//邻接表那一套
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])//这里的i相当于idx
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])//如果这个点没有在队列中就把它放进队列
                {
                    Q.push(j);
                    st[j] = true;//状态设置为true
                }
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f)
        printf("impossible");
    else
        printf("%d", dist[n]);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    spfa判断负环

    int dis[MAXN], flag[MAXN], cnt[MAXN];

bool spfa()
{
    queue<int> Q;
    for(int i = 1; i <= n; ++i)
    {
        flag[i] = true;
        Q.push(i);
    }
    while(Q.size())
    {
        int t = Q.front();
        Q.pop();
        flag[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dis[j] > dis[t] + w[i])
            {
                dis[j] = dis[t] + w[i];
                if(!flag[j])
                {
                    Q.push(j);
                    flag[j] = true;
                }
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n)
                    return true;
            }
        }
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    Floyd（多源最短路—包含多个源点）

    初始化

    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
        if(i==j)
            d[i][j]=0;
        else
            d[i][j]=INF;
while(m--)
{
	int x,y,z;
	scanf("%d%d%d",&x,&y,&z);
	d[x][y]=min(d[x][y],z);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    求最短路

    for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

    • 1
    • 2
    • 3
    • 4

    最小生成树

    prim

    朴素prim O ( n 2 ) O(n^2) O(n2)

    #include <bits/stdc++.h>

using namespace std;
#define INF 0x3f3f3f3f
int arr[510][510], dis[510];
bool flag[510];
int n, m, u, v, w;

int prim()
{
    int res = 0;
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 0; i < n; ++i)
    {
        int t = -1;
        for(int j = 1; j <= n; ++j)
            if(!flag[j] && (t == -1 || dis[t] > dis[j]))//这里的dis代表的是这个点到集合的距离
                t = j;

        if(i && dis[t] == INF)//首先排除第一个点，并且得出的t这个点距离集合的距离为INF说明他不会在集合里面，说明这个图不存在最小生成树
            return INF;

        if(i)//第一个点肯定不能加进去,因为这里我们大循环要循环n次，我们是从0开始的
            res += dis[t];//这里要把距离更新写在前面，避免负自环的影响
        for(int j = 1; j <= n; ++j)//更新与t这个点相连的点的距离，因为此时t已经确定可以加入集合了
            dis[j] = min(dis[j], arr[t][j]);
        flag[t] = true;
    }
    return res;
}

int main()
{
    memset(arr, 0x3f, sizeof(arr));
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &u, &v, &w);
        arr[v][u] = arr[u][v] = min(arr[u][v], w);
    }

    int t = prim();
    if(t == INF) printf("impossible");
    else printf("%d", t);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    堆优化prim（暂无）

    Kruskal O ( m l o g n ) O(mlogn) O(mlogn)

    #include<bits/stdc++.h>

using namespace std;
const int MAXN = 2e5 + 10;
int n, m, u, v, w, p[MAXN];
struct Edge
{
    int u, v, w;
} edge[MAXN];

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

int find(int x)
{
    if(p[x] != x)p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)//初始化
        p[i] = i;

    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        edge[i] = {u, v, w};
    }

    sort(edge + 1, edge + m + 1, cmp);//根据边的权重来排序

    int res = 0, cnt = 0;
    for(int i = 1; i <= m; ++i)
    {
        int a = edge[i].u, b = edge[i].v, w = edge[i].w;
        a = find(a), b = find(b);
        if(a != b)
        {
            ++cnt;//边数+1
            p[a] = b;//合并
            res += w;//加上权重
        }
    }

    if(cnt < n - 1)//如果边数小于n-1，说明n个点没有全部连通
        printf("impossible");
    else printf("%d", res);

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    二分图

    染色图判定二分图

    DFS实现

    #include <cstring>
#include <iostream>

using namespace std;
const int N = 100010, M = 200010;

int n, m;
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;
}

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

    bool flag = true;
    for(int i = 1; i <= n; i++)
        if(!color[i])
        {
            if(!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }

    if(flag) puts("Yes");
    else puts("No");

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    BFS实现 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)

    #include<bits/stdc++.h>

using namespace std;
const int MAXN = 1e5 + 10;

int e[MAXN * 2], ne[MAXN * 2], h[MAXN], idx;
int n, m, u, v, color[MAXN];

void add(int a, int b)//邻接表那一套
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool BFS(int x)
{
    queue<int> Q;
    Q.push(x);
    color[x] = 1;

    while(Q.size())
    {
        int t = Q.front();
        Q.pop();

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!color[j])
            {
                color[j] = 3 - color[t];
                Q.push(j);
            }
            else if(color[j] == color[t])return false;
        }
    }

    return true;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while(m--)
    {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);//无向边加两条
    }

    bool res = true;
    for(int i = 1; i <= n; ++i)//遍历所有的点，防止出现两个不连通的图的情况
        if(!color[i])//进入一次BFS后，会把一个连通图的点全部染色，比如123是一个图，1进去BFS后2也会被染色，那么当i=2时就不会BFS了
            if(!BFS(i))//这里BFS进去会把一个连通图的点全部染色，
            {
                res = false;
                break;
            }
    if(res)printf("Yes");
    else printf("No");
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    二分图最大匹配（匈牙利算法）

    #include <bits/stdc++.h>

using namespace std;
const int MAXN = 510, MAXM = 1e5 + 10;
int h[MAXN], e[MAXM], ne[MAXM], idx;
int match[MAXN];//看当前这个女孩匹配的是谁
bool st[MAXN];//女孩的状态
int n1, n2, m, u, v;

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

int find(int x)
{
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])//这里之所以要判断是用来 判断递归的时候的状态，如果此时这个女孩未被选择
        {
            st[j] = true;
            if(match[j] == 0 || find(match[j]))//如果之前没被匹配，或者被匹配的男友能够通过递归找到下家
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d%d", &n1, &n2, &m);
    while(m--)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
    }

    int res = 0;
    for(int i = 1; i <= n1; ++i)
    {
        memset(st, false, sizeof(st));//把所有的女孩的状态都清空，以便于这次的遍历
        if(find(i))res++;
    }

    printf("%d", res);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    数学

    质数

    质数判定，试除法 O ( n ) O(\sqrt{n}) O(n ​)

    bool isPrime()
{
    if(a < 2)
        return false;
    for(int i = 2; i <= a / i; ++i)
        if(a % i == 0)
            return false;
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    分解质因数

    void output()
{
    for(int i = 2; i <= a / i; ++i)
    {
        if(a % i == 0)
        {
            int s = 0;
            while(a % i == 0)
            {
                a /= i;
                ++s;
            }
            printf("%d %d\n", i, s);
        }
    }
    if(a > 1)//n当中最多只包含一个大于根号n的质因子
        printf("%d %d\n", a, 1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    筛质数

    线性筛法 O ( n ) O(n) O(n)

    st数组存的是最小质因子

    int cnt, primes[MAXN];
int st[MAXN];

void euler_sieve(int n)
{
    for(int i = 2; i <= n; ++i)
    {
        if(!st[i])primes[++cnt] = i, st[i] = i;
        for(int j = 1; primes[j] <= n / i; ++j)
        {
            st[primes[j] * i] = primes[j];
            if(i % primes[j] == 0)break;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    约数

    试除法求约数 O ( n ) O(\sqrt{n}) O(n ​)

    for(int i = 1; i <= a / i; ++i)
{
    if(a % i == 0)
    {
        ans.push_back(i);
        if(i != a / i)
            ans.push_back(a / i);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    约数个数

    N = p 1 a 1 ∗ p 2 a 2 ∗ p 3 a 3 ⋅ ⋅ ⋅ p n a n ， 其 中 p 是 质 因 子 N=p_1^{a_1}*p_2^{a_2}*p_3^{a_3}···p_n^{a_n}，其中p是质因子 N=p1a1​​∗p2a2​​∗p3a3​​⋅⋅⋅pnan​​，其中p是质因子
    约数个数 c n t = ( a 1 + 1 ) ( a 2 + 1 ) ( a 3 + 1 ) ⋅ ⋅ ⋅ ( a n + 1 ) cnt=(a_1+1)(a_2+1)(a_3+1)···(a_n+1) cnt=(a1​+1)(a2​+1)(a3​+1)⋅⋅⋅(an​+1)

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
int n, a;

int main()
{
    map<int, int> m;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d", &a);
        for(int i = 2; i <= a / i; ++i)
        {
            if(a % i == 0)
            {
                while(a % i == 0)
                {
                    ++m[i];
                    a /= i;
                }
            }
        }
        if(a>1)//记得这里还要考虑如果还有一个比较大的质因数
            ++m[a];
    }

    ll res = 1;
    for(auto it: m)res = res * (1 + it.second) % mod;

    printf("%lld", res);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    约数之和

    N = p 1 a 1 ∗ p 2 a 2 ∗ p 3 a 3 ⋅ ⋅ ⋅ p n a n ， 其 中 p 是 质 因 子 N=p_1^{a_1}*p_2^{a_2}*p_3^{a_3}···p_n^{a_n}，其中p是质因子 N=p1a1​​∗p2a2​​∗p3a3​​⋅⋅⋅pnan​​，其中p是质因子
    N N N 的所有约数之和
    s u m = ( p 1 0 + p 1 1 + p 1 2 + ⋅ ⋅ ⋅ + p 1 a 1 ) ( p 2 0 + p 2 1 + p 2 2 + ⋅ ⋅ ⋅ + p 2 a 2 ) ⋅ ⋅ ⋅ ( p n 0 + p n 1 + p n 2 + ⋅ ⋅ ⋅ + p n a n ) sum=(p_1^0+p_1^1+p_1^2+···+p_1^{a_1})(p_2^0+p_2^1+p_2^2+···+p_2^{a_2})···(p_n^0+p_n^1+p_n^2+···+p_n^{a_n}) sum=(p10​+p11​+p12​+⋅⋅⋅+p1a1​​)(p20​+p21​+p22​+⋅⋅⋅+p2a2​​)⋅⋅⋅(pn0​+pn1​+pn2​+⋅⋅⋅+pnan​​)

    #include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int mod=1e9+7;

int n,a;

int main()
{
    scanf("%d",&n);
    map<int,int>m;
    while(n--)
    {
        scanf("%d",&a);
        for(int i=2;i<=a/i;++i)
            if(a%i==0)
            {
                while(a%i==0)
                {
                    ++m[i];
                    a/=i;
                }
            }
            
        if(a>1)
            ++m[a];
    }
    
    ll res=1;
    for(auto x:m)
    {
        int b=x.first,a=x.second;
        ll t=1;
        while(a--)
            t=(t*b+1)%mod;
        res=res*t%mod;
    }
    printf("%lld",res);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    最大公约数

    int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;//gcd()经过变换之后里面一定是左大右小
}

    • 1
    • 2
    • 3
    • 4
  • 相关阅读:
    记踩HttpRequest设置header无效导致404问题
    第1关：Hive的安装与配置
    springboot使用切面记录接口访问日志
    CTF-Crypto学习记录-第三天 MD5加密算法（信息摘要算法）“ “
    Android 13 全局监听播放器暂停与播放 （包含系统层和第三方app）
    JAVA练习题38：正则表达式基本练习
    Javascript知识【BootStrap】
    vscode怎么拷贝插件到另一台电脑
    为什么 BI 软件都搞不定关联分析
    分布式文件存储——文件秒传
  • 原文地址：https://blog.csdn.net/weixin_54209457/article/details/125526809