ACM模板

发表于   |   分类于

遇到就更新。。。

数论

筛选法素数打表

1
2
3
4
5
6
7
8
9
10
11
int a[N]={1,1,0};
void isPrime()
{
    for(int i=2;i<N;i++){
        if(!a[i]){
            for(int j=i+i;j<N;j+=i){
                a[j]=1;
            }
        }
    }
}

欧拉函数

朴素算法

1
2
3
4
5
6
7
8
9
10
11
12
13
int Eular(int n)
{
    int s=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)
            s=s/i*(i-1);
        while(n%i==0)
            n/=i;
    }
    if(n>1)
        s=s/n*(n-1);
    return s;
}

筛选法打表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N=1000010;
int a[N]={1,1,0};
void priEular()   
{
    int i,j;
    for(i=2;i<N;i++){
        if(a[i]==0){
            for(j=i;j<N;j+=i){
                if(a[j]==0)
                    a[j]=j;
                a[j]=a[j]/i*(i-1);
            }
        }
    }
}

快速幂取余

1
2
3
4
5
6
7
8
9
10
11
12
LL powerMod(LL a,LL b,LL mod)
{
    LL ans=1;
    a%=mod;
    while(b){
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

快乘取余

1
2
3
4
5
6
7
8
9
10
11
LL mulMod(LL x,LL y,LL mod)
{
    LL ans=0;
    while(y){
        if(y&1)
            ans=(ans+x)%mod;
        x=(x+x)%mod;
        y>>=1;
    }
    return ans;
}

扩展欧几里德

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//a*x+b*y=gcd(a,b)
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    LL d=exgcd(b,a%b,x,y);
    LL t=x;
    x=y;
    y=t-a/b*y;
    return d;
}

定理：设a,b,c为任意整数，若方程ax+by=c的一组整数解为（x0,y0）则它的任意整数解都可以写成(x0+kb’,y0-ka’),其中a’=a/gcd(a,b),b’=b/gcd(a,b),k为任意整数
若ax+by=g (g=gcd(a,b),即g是a,b的最大公约数),有整数解(x1,y1),则ax+by=c（c是g的倍数）有整数解(c*x1/g,c*y1/g)

中国剩余定理

令$m_{1},m_{2},\cdots,m_{n}$为两两互素的正整数，则同余方程组
$$
\left[
\begin{matrix}
x \equiv a_{1} \pmod {m_{1}} \\
x \equiv a_{2} \pmod {m_{2}} \\
\vdots \\
x \equiv a_{n} \pmod {m_{n}}
\end{matrix}
\right.
$$
有唯一的模$m=m_{1}m_{2} \cdots m_{n}$解。（即有一个解x，使0≤x≤m，且所有其他的解均与此解模m同余。）

1
2
3
4
5
6
7
8
9
10
11
12
13
LL china(int n)
{
    LL M=1,x=0;
    for(int i=0;i<n;i++)
        M*=m[i];
    for(int i=0;i<n;i++){
        LL w=M/m[i];
        LL d,y;
        d=exgcd(m[i],w,d,y);
        x=(x+y*w*a[i])%M;
    }
    return (x+M)%M;
}

逆元

对于正整数a,n,满足a*x≡1(mod n)的x值就是a关于n的乘法逆元。当且仅当a和n互质即gcd(a,n)=1时有解

扩展欧几里德求逆元

1
2
3
4
5
6
7
//模n下a的逆，如果不存在返回-1
LL inv(LL a,LL n)
{
    LL d,x,y;
    d=exgcd(a,n,x,y);
    return d==1?(x+n)%n:-1;
}

费马小定理（求逆元）

假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)
即 a^(p-2)≡1/a (mod p)

图论

链式前向星

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
//存储结构
struct Edge
{
    int to;  //边的终点
    int w;   //边的权值
    int next; //起点相同的下一条边
}edge[M];   //M为边数，N为顶点数
int head[N]; //head[i]是以i为起点的第一条边的编号
int cnt;  //记录边数
//初始化
cnt=0;
memset(head,-1,sizeof(head));
//建图
void addEdge(int u,int v,int w)
{
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
//遍历以u为起点的邻接边
for(int i=head[u];i!=-1;i=edge[i].next){
    int to=edge[i].to; //终点
    int w=edge[i].w;   //权值
}

最小生成树

prim算法(O(n^2))

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
int prim()
{
    bool vis[N];
    int low[N],pos=1; //pos为当前选的点的下标，初始可以任选一点
    for(int i=1;i<=n;i++)
        low[i]=edge[pos][i]; //low数组用来记录已选点到其他点的最小权值
    memset(vis,false,sizeof(vis));     //标记顶点是否已选
    low[pos]=0;
    vis[pos]=true;
    bool flag=true;
    int sum=0;
    for(int i=1;i<n;i++){
        int min=INF;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&low[j]<min){
                min=low[j];
                pos=j;
            }
        }
        if(min==INF){
            flag=false;
            break;
        }
        sum+=min;
        vis[pos]=true;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&edge[pos][j]<low[j])
                low[j]=edge[pos][j];
    }
    return flag?sum:-1;
}

kruskal (O(eloge))

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
bool cmp(stu a,stu b) //将边按从小到大排序
{
    return a.w<b.w;
}
int find(int x)      //找父亲结点
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}
int kruskal()
{
    int k=0,sum=0;
    for(int i=1;i<=m;i++){  //枚举边
        int x=find(edge[i].u);
        int y=find(edge[i].v);
        if(x!=y){     //判断u,v是否属于同一集合
            k++;
            sum+=edge[i].w;
            f[x]=y;
            if(k==n-1)  //找到n-1条边就停止
                break;
        }
    }
    return k==n-1?sum:-1;
}

最小树形图 (朱刘算法)

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
struct edg {
    int u, v, w;
} edge[M];
int n, m;
int in[N],id[N],vis[N],pre[N];
int Directed_MST(int root) {
    int ret = 0;
    while(true) {
        for(int i=0;i<n;i++)
            in[i]=inf;
        for(int i=0;i<m;i++){    //找最小入边
            int u = edge[i].u;
            int v = edge[i].v;
            if(edge[i].w < in[v] && u != v) {
                in[v] = edge[i].w;
                pre[v] = u;
            }
        }
        for(int i=0;i<n;i++) { //如果存在除root以外的孤立点，则不存在最小树形图
            if(i == root)  continue;
            if(in[i] == inf)  return -1;
        }
        int cnt = 0;  //顶点从0开始编号
        memset(vis,-1,sizeof(vis));
        memset(id,-1,sizeof(id));
        in[root] = 0;
        for(int i=0;i<n;i++) {    //找环
            ret += in[i];
            int v = i;
            while(vis[v] != i && id[v] == -1 && v != root) {
                vis[v] = i;
                v = pre[v];
            }
            if(v != root && id[v] == -1) {  //重新标号
                for(int u = pre[v]; u != v; u = pre[u])
                    id[u] = cnt;
                id[v] = cnt++;
            }
        }
        if(cnt == 0) break;
        for(int i=0;i<n;i++)
            if(id[i] == -1)
                id[i] = cnt++;    //重新标号
        for(int i=0;i<m;i++){    //更新其他点到环的距离
            int v =edge[i].v;
            edge[i].u = id[edge[i].u];
            edge[i].v = id[edge[i].v];
            if(edge[i].u != edge[i].v)
                edge[i].w -= in[v];
        }
        n = cnt;
        root = id[root];
    }
    return ret;
}

最短路

dijkstra(非负权单源最短路)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//用edge邻接矩阵存边，顶点i,j有边edge[i][j]为边的权值，无边时设为无穷大
void dijkstra(int n,int pos) //顶点数，源点
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i]=edge[pos][i];
    dis[pos]=0;
    vis[pos]=true;
    for(int i=1;i<n;i++){
        int min=INF;
        for(int j=1;j<=n;j++){ //从尚未使用的顶点中选一个距离最小的
            if(!vis[j]&&dis[j]<min){
                pos=j;
                min=dis[j];
            }
        }
        vis[pos]=true;
        for(int j=1;j<=n;j++){ //松弛
            if(!vis[j]&&dis[pos]+edge[pos][j]<dis[j])
                dis[j]=dis[pos]+edge[pos][j];
        }
    }
}

bellman-ford(可判负权回路)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool bellmanford(int pos)  //源点
{
    for(int i=1;i<=n;i++) //n为顶点数
        dis[i]=INF;
    dis[pos]=0;
    for(int i=1;i<n;i++){  //最多松弛n-1次
        for(int j=1;j<=m;j++){  //m为边数
            if(dis[edge[j].u]+edge[j].w<dis[edge[j].v])
                dis[edge[j].v]=dis[edge[j].u]+edge[j].w;
        }
    }
    for(int i=1;i<=m;i++){  //若松弛n-1次后还能松弛，则存在负权回路
        if(dis[edge[i].u]+edge[i].w<dis[edge[i].v])
            return true;
    }
    return false;
}

SPFA(可判负权回路，bellman-ford的优化)

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
//链式前向星实现，也可用邻接矩阵
bool SPFA(int pos)  //源点
{
    memset(vis,0,sizeof(vis)); //标记是否在队列
    memset(num,0,sizeof(num)); //记录各顶点松弛次数(即进队列的次数)
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    dis[pos]=0;
    q.push(pos);
    vis[pos]=true;
    num[pos]++;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int to=edge[i].to;
            if(dis[u]+edge[i].w<dis[to]){
                dis[to]=dis[u]+edge[i].w;
                if(!vis[to]){
                    q.push(to);
                    vis[to]=true;
                    num[to]++;
                    if(num[to]>=n) //当某顶点松弛次数大于或等于n时，存在负权回路
                        return true;
                }
            }
        }
    }
    return false;
}

floyd(多源最短路)

1
2
3
4
5
6
7
8
9
//应用：传递闭包
void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(edge[i][k]+edge[k][j]<edge[i][j])
                    edge[i][j]=edge[i][k]+edge[k][j];
}

二分图的最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dfs(int pos)
{
    for(int i=1;i<=m;i++){
        if(edge[pos][i]&&!used[i]){
            used[i]=1;
            if(link[i]==-1||dfs(link[i])){
                link[i]=pos;
                return 1;
            }
        }
    }
    return 0;
}
int hungarian()
{
    int sum=0;
    memset(link,-1,sizeof(link));
    for(int i=1;i<=n;i++){
        memset(used,0,sizeof(used));
        sum+=dfs(i);
    }
    return sum;
}

最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联
knoig定理:二分图的最小顶点覆盖数 = 二分图的最大匹配数（m）
最小路径覆盖:用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点
结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）
二分图的最大独立集
结论：二分图的最大独立集数 = 节点数（n）- 最大匹配数（m）

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int tpSort(int n)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        int pos=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&rd[j]==0){ //找到入度为0的点
                s[i]=j;
                vis[j]=true;
                pos=j;
                break;
            }
        }
        if(pos==-1) //存在回路
            return 0;
        for(int j=1;j<=n;j++){ //与pos相连的边入度都减一
            if(edge[pos][j])
                rd[j]--;
        }
    }
    return 1;
}

计算几何

两圆相交面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//求两点间的距离
double Distance(point a,point b)  
{  
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));  
}  
double InterArea(point a,double R,point b,double r)  
{  
    if(R<r){  
        double temp=R;  
        R=r;  
        r=temp;  
    }
    double dis=Distance(a,b);  
    if(dis>=R+r)    //两圆相离，相交面积为0  
        return 0;  
    if(dis<=R-r)    //两圆内含，相交面积为小圆的面积  
        return PI*r*r;  
    //两圆相交时  
    double angle1=acos((R*R+dis*dis-r*r)/(2.0*R*dis));  
    double angle2=acos((r*r+dis*dis-R*R)/(2.0*r*dis));  
    double s=R*angle1*R+r*angle2*r;  
    s-=R*dis*sin(angle1);  
    return s;  
}

叉积

|c|=|a×b|=|a||b|sin 可用来求平行四变形面积
利用叉积判断两向量的顺逆时针关系：
若 P × Q > 0 , 则P在Q的顺时针方向。
若 P × Q < 0 , 则P在Q的逆时针方向。
若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。

1
2
3
4
double chaji(point a,point b)
{
    return a.x*b.y-a.y*b.x;
}

点积

cos=a·b/(|a|*|b|),可用来判断两向量是否垂直(a·b=0)

1
2
3
4
double dianji(point a,point b)
{
    return a.x*b.x+a.y*b.y;
}

pick定理

Pick定理：设平面上以格子点为顶点的多边形的内部点个数为a，边上点个数为b，面积为S,则 S = a + b/2 -1.
以格子点为顶点的线段，覆盖的点的个数为gcd(|dx|,|dy|)，其中，|dx|,|dy|分别为线段横向增量和纵向增量。

凸包

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
int m,top;  
int chaji(struct stu p1,struct stu p2,struct stu p3)   //叉积  
{  
    return (p1.x-p2.x)*(p3.y-p2.y)-(p3.x-p2.x)*(p1.y-p2.y);  
}  
double dis(struct stu p1,struct stu p2)    //两点的距离的平方  
{  
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);  
}  
int cmp(struct stu p1,struct stu p2)  
{  
    int k;  
    k=chaji(p1,p[0],p2);  
    if(k>0||(k==0&&dis(p1,p[0])<dis(p2,p[0])))  
        return 1;  
    return 0;  
}  
void graham()  
{  
    int i,k=0;  
    struct stu t;  
    for(i=1;i<m;i++)  //先找到最左下的点作为凸包的第一个顶点
        if(p[i].y<p[k].y||(p[i].y==p[k].y&&p[i].x<p[k].x))
            k=i;                                                    
    t=p[k];  
    p[k]=p[0];  
    p[0]=t;  //将除凸包第一个顶点外，按任意两点与第一个顶点的叉积正负排序
    sort(p+1,p+m,cmp);  
    s[0]=p[0];  
    s[1]=p[1];  
    top=1;  
    for(i=2;i<m;i++){  
        while(top>=1&&chaji(s[top-1],s[top],p[i])>=0)  
            top--;  
        top++;  
        s[top]=p[i];  
    }  
}

动态规划

背包

01背包

1
2
3
4
5
void zeroOne(int cost,int weight)
{
    for(int i=V;i>=cost;i--)
        f[i]=max(f[i],f[i-cost]+weight);
}

初始化：若没有要求必须将背包装满，而是只希望价值尽量大，初始化时应该将f[0…V]全设为0
若要求背包恰好装满，则要将f[0]=0，其他赋为负无穷，因为背包为0可由0件物品恰好装满，得到的价值为0

完全背包

1
2
3
4
5
void complete(int cost,int weight)
{
    for(int i=cost;i<=V;i++)
        f[i]=max(f[i],f[i-cost]+weight);
}

多重背包

1
2
3
4
5
6
7
8
9
10
11
12
void multiple(int cost int weight,int amount)
{
    if(cost*amount>=V){
        complete(cost,weight);
        return ;
    }
     for(int k=1;k<amount;k*=2){  
        zeroone(k*cost,k*weight);  
        amount-=k;  
    }  
    zeroone(amount*cost,amount*weight);  
}

LCS(最长公共子序列)

1
2
3
4
5
6
7
8
9
10
11
void LCS()  //s[1-m],t[1-n]
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++){
            if(s[i]==t[j])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
}

LIS(最长上升子序列)

O(n^2)

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
void back_path(int pos)
{
    if(pos!=path[pos])
        back_path(path[pos]);
    printf("%d\n",pos);
}
int LIS(int n)
{
    for(int i=1;i<=n;i++){
        dp[i]=1;
        path[i]=i; //记录路径
        for(int j=1;j<i;j++){
            if(a[j]<a[i]&&dp[j]+1>dp[i]){
                dp[i]=dp[j]+1;
                path[i]=j;  //记录路径
            }
        }
    }
    int k=1;
    for(int i=2;i<=n;i++){ //求最大值
        if(dp[i]>dp[k]){
            k=i;
        }
    }
    back_path(k);  //回溯路径
    return dp[k];
}

O(n*log 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
int bin_find(int x)
{
    int l=0,r=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(x>c[mid])
            l=mid+1;
        else if(x<c[mid])
            r=mid-1;
        else
            return mid;
    }
    return l;
}
int LIS()
{
    for(int i=0;i<=n;i++)
        c[i]=INF;
    c[0]=-1;
    c[1]=a[0];
    int len=1;
    for(int i=1;i<n;i++){
        int j=bin_find(a[i]);
        c[j]=a[i];
        if(j>len)
            len=j;
    }
    return len;
}

字符串

最长回文串(Manacher算法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int manacher()
{   //先在原串的字母间添加'#',开头添加特殊字符'$',末尾为空字符
    int id=0,mx=0,maxlen=0;
    p[0]=0;
    for(int i=1;s[i]!='\0';i++){
        p[i]=mx>i?min(p[2*id-i],mx-i):1;
        while(s[i+p[i]]==s[i-p[i]])
            p[i]++;
        if(i+p[i]>mx){
            mx=i+p[i];
            id=i;
        }
        if(p[i]>maxlen)  //求最大回文长度
            maxlen=p[i];
    }
    return maxlen-1;
}

数据结构

树状数组

一维

1
2
3
4
5
6
7
8
9
10
11
12
void update(int pos,int x)  //将a[pos]增加x
{
    for(int i=pos;i<=n;i+=lowbit(i))
        c[i]+=x;
}
int query(int x)  //查询[1,n]的和
{
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i))
        ans+=c[i];
    return ans;
}

二维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void update(int x, int y, int val) //将a[x][y]的值增加val
{
    for (int i = x; i <=n; i += lowbit(i))
        for (int j = y; j <=n; j += lowbit(j))
            c[i][j] += val;
}
int query(int x, int y)    //查询 1<=i<=x,1<=j<=y的和
{
    int ans = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        for (int j = y; j >= 1; j -= lowbit(j))
            ans += c[i][j];
    return ans;
}

线段树

单点更新，区间求和

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
void pushUp(int node)
{
    tree[node]=tree[node<<1]+tree[node<<1|1];
}
void build(int l,int r,int node)
{
    if(l==r){
        tree[node]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,node<<1);
    build(mid+1,r,node<<1|1);
    pushUp(node);
}
void update(int l,int r,int node,int pos,int val)
{
    if(l==r){
        tree[node]+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=pos)
        update(l,mid,node<<1,pos,val);
    else
        update(mid+1,r,node<<1|1,pos,val);
    pushUp(node);
}
int query(int l,int r,int node,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        return tree[node];
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(mid>=ql)
        ans+=query(l,mid,node<<1,ql,qr);
    if(mid<qr)
        ans+=query(mid+1,r,node<<1|1,ql,qr);
    return ans;
}

区间更新，延迟标记

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
void pushUp(int node)
{
    tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
}
void pushDown(int l,int r,int node)
{
    if(tree[node].mark){
		//延迟标记由父结点转向子结点
        tree[node<<1].mark+=tree[node].mark;
        tree[node<<1|1].mark+=tree[node].mark;
        int mid=(l+r)>>1;
        //更新左右孩子
        tree[node<<1].sum+=(mid-l+1)*tree[node].mark;
        tree[node<<1|1].sum+=(r-mid)*tree[node].mark;
        tree[node].mark=0;  //父结点延迟标记取消
    }
}
void build(int l,int r,int node)
{
    if(l==r){
        tree[node].sum=a[l];
        tree[node].mark=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,node<<1);
    build(mid+1,r,node<<1|1);
    pushUp(node);
}
void update(int l,int r,int node,int ul,int ur,LL val)
{
    if(ul<=l&&r<=ur){
        tree[node].mark+=val;
        tree[node].sum+=val*(r-l+1);
        return ;
    }
    pushDown(l,r,node);
    int mid=(l+r)>>1;
    if(ul<=mid)
        update(l,mid,node<<1,ul,ur,val);
    if(mid<ur)
        update(mid+1,r,node<<1|1,ul,ur,val);
    pushUp(node);
}
LL query(int l,int r,int node,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        return tree[node].sum;
    }
    pushDown(l,r,node);
    int mid=(l+r)>>1;
    LL sum=0;
    if(ql<=mid)
        sum+=query(l,mid,node<<1,ql,qr);
    if(mid<qr)
        sum+=query(mid+1,r,node<<1|1,ql,qr);
    return sum;
}

并查集

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
void init() //初始化
{
    for(int i=1;i<=n;i++){
        f[i]=i;
        rank[i]=0;
    }
}
//递归法压缩路径
int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}
//普通合并
void Union(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        f[fx]=fy;
}
//考虑rank合并
void Union(int a,int b)  
{  
    int fa=find(a);  
    int fb=find(b);  
    if(rank[fa]>rank[fb])  
        f[fb]=fa;  
    else
        f[fa]=fb;  
    if(rank[fa]==rank[fb])  
        rank[fb]++;  
}

排序

归并排序

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
void merge(int l,int r)
{
    int left[N],right[N];
    int mid=(l+r)/2;
    int m=0,n=0;
    for(int i=l;i<=mid;i++)   //左半部分
        left[m++]=a[i];
    for(int i=mid+1;i<=r;i++)  //右半部分
        right[n++]=a[i];
    int i=0,j=0,k=l;
    while(i<m&&j<n){
        if(left[i]<=right[j]){
            a[k++]=left[i++];
        }
        else{
            a[k++]=right[j++];
        }
    }
    while(i<m) a[k++]=left[i++];
    while(j<n) a[k++]=right[j++];
}
void mergeSort(int l,int r)
{
    if(l<r){
        int mid=(l+r)/2;
        mergeSort(l,mid);
        mergeSort(mid+1,r);
    }
    merge(l,r);
}

其他

博弈论

巴什博弈

问题模型：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。
结论：n%(m+1)!=0时，先手赢，否则后手赢

1
2
3
4
if(n % (m + 1) != 0) //必胜局面  
    printf("Win\n");  
else
    printf("Lose\n");

威佐夫博奕

问题模型：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

1
2
3
4
5
6
7
if(num1 > num2)  
    swap(num1, num2);   
tmp = floor((num2 - num1) * (1 + sqrt(5.0)) / 2.0); //黄金分割  
if(tmp == num1)
    printf("Lose\n"); //奇异局势必败  
else
    printf("Win\n");

尼姆博弈

问题模型：有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下：
1)每一步应取走至少一枚石子，每一步只能从某一堆中取走部分或全部石子；
2)如果谁取到最后一枚石子就胜

1
2
3
4
5
6
7
8
9
for( i = 0; i < n; i++ )  
    cin >> temp[ i ]; //第i堆物品的数量  
min = temp[ 0 ];  
for( i = 1; i < n ; i++ )  
    min = min^temp[ i ]; //按位异或  
if( min == 0 )  
    cout << "Lose" << endl; //输  
else  
    cout << "Win" << endl; //赢

集合的整数表示

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
//空集
0
//只含有第i个元素的集合{i}
1<<i
//含有全部元素的集合
(1<<n)-1
//判断第i个元素是否在集合S中
if(S>>i&1)
//向集合中添加第i个元素
S|(1<<i)
//从集合中去除第i个元素
S&~(1<<i)
//集合S和集合T的并集
S|T
//集合S和集合T的交集
S&T
//枚举集合{0,1,...,n-1}的所有子集
for (int S=0;S<(1<<n);S++){
    //....
}
//枚举任意集合sup的所有子集
int sub=sup;
do{
    //...
    sub=(sub-1)&sup;
}while (sub!=sup);
//枚举{0,1,...,n-1}中所有的大小为k的子集
//(n位二进制，有k个1)
int comb=(1<<k)-1;
while (comb<(1<<n)){
    //...
    int x=comb&-comb,y=comb+x;
    comb=((comb&~y)/x>>1)|y;
}

位运算的应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//给定一个包含n个整数的数组，除了一个数出现一次外所有的整数均出现三次，
//找出这个只出现一次的整数。
int find_single(){
    int ones=0,twos=0,xthrees=0;
    int N;
    scanf("%d",&N);
    for (int i=1;i<=N;i++){
        int tmp;
        cin>>tmp;
        twos|=ones&tmp;
        ones^=tmp;
        xthrees=~(twos&ones);
        ones&=xthrees;
        twos&=xthrees;
    }
    return ones;
}

Java大数处理

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.math.*;
BigInteger add(BigInteger other);        //加
BigInteger subtract(BigInteger other);   //减
BigInteger multiply(BigInteger other);   //乘
BigInteger divide(BigInteger other);     //除
BigInteger mod(BigInteger other);        //取余
static BigInteger valueOf(long x)        //返回等于x的大数
int compareTo(BigInteger other);         //比较大小
//相等返回0，这个大数比另一个大返回正数，否则返回负数
//BigDecimal用来实现任意精度的浮点数运算，调用方法类似
BigInteger a=BigIntger.valueOf(100);  //将普通数转化为大数
BigInteger c=a.add(b);     //c=a+b;
BigInteger d=c.multiply(b.add(BigInteger.valueOf(2))); //d=c*(b+2)
1
2
3
4
5
6
7
8
9
10
11
12
//大数输入及相乘
import java.math.*;
import java.util.*;
public class Main{
    public static void main(String[] args)
    {
        Scanner input=new Scanner(System.in);
        BigInteger a=input.nextBigInteger();
        BigInteger b=input.nextBigInteger();
        System.out.println(a.multiply(b));
    }
}

STL algorithm 常用函数

next_permutation(first,last)
生成当前排列的下一个排列，返回为true表示生成下一排列成功，否则返回false
prev_permutation() 生成当前排列的前一个排列
accumulate(first,last,val) 求和，以val为累加初值，累加范围[first,last)
fill(first,last,val) 将[first,last)值都填充为val
fill_n(first,num,val) 从first开始依次将n个元素赋值为val

1
2
3
4
5
6
7
8
9
10
vector<int> ve(10);
vector<int>::iterator it;
fill(ve.begin(),ve.end(),1);
fill_n(ve.begin(),5,2);
for(it=ve.begin();it!=ve.end();it++)
    printf("%d ",*it);
int a[10];
fill(a,a+10,1);
fill_n(a,5,2);
// 2 2 2 2 2 1 1 1 1 1

lower_bound(first,last,val)
在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。
如果所有元素都小于val，则返回last的位置(指针)
upper_bound()
在first和last中的前闭后开区间进行二分查找，返回大于val的第一个元素位置
如果所有元素都小于val，则返回last的位置(指针)
unique(first,last)
去重，去除相邻的重复元素(只保留一个),返回去重后最后一个元素的地址

1
2
3
sort(id,id+n);
int m=unique(id,id+n)-id;  //先排序后去重
int pos=lower_bound(id,id+m,val)-id;