该篇为《算法导论》学习笔记，包含部分章节的理论阐释、典型问题、和代码实现。

算法

时间复杂度

1.渐近符号：

θ--渐近紧确界； f(n)=θ(g(n)):g(n)是f(n)的渐进紧确界. 定义:存在c1,c2,n0,对任意n>=n0,有：0<=c1g(n)<=f(n)<=c2g(n). f(n)=θ(g(n)),当且仅当:f(n)=O(g(n))且f(n)=欧姆. O--渐近上界；[欧姆]--渐近下界 o--非紧确渐近上界；ω--非紧确渐近下界 f(n)=O(g(n))中,0<=f(n)<cg(n)对某个常量c>0成立； f(n)=o(g(n))中,0<=f(n)<cg(n)对所有常量c>0成立.

2.主定理求时间复杂度:

T(n)=aT(n/b)+f(n). 比较n1和f(n):选择多项式意义上更大的。 1.f(n)=O(n(logb(a)-ε)),则:T(n)=θ(n(logb(a)). 2.f(n)=0(n(logb(a))),则:T(n)=θ(n(logb(a)lgn). 3.f(n)=欧姆,则:T(n)=θ(f(n)). 注意：T(n)=2T(n/2)+nlgn. nlgn非多项式意义大于n,落入2，3间隙,不适用主定理.

快速幂/质数

1.快速幂：求a^b.

1
2
3
4
5
6
7
8
long long fpm(long long a,long long b){
    long long ans=1;
    for(;b!=0;b>>=1,a=a*a%M)
    {
        if(b&1) ans=ans*a%M;
    }
    return ans;
}

求矩阵n次幂:An--θ(n3)->θ(n^2*logn). 

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>
#define maxn 205
typedef long long ll;
const int p = 1e9 + 7;
using namespace std;
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;
} 

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        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");
        }
    }
}

2.分解质因数

质数个数:O(n/logn). (1)朴素算法:遍历i. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[N],p[N],k=0;      //p记录n的质因数;a记录n的质因数的指数;k为不同质因数个数
void decompose(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0)
        {
            p[k]=i;a[k]=0;
            while(n%i==0) {a[k]++;n/=i;}
            k++;
        }
    }
    if(n!=1){
        p[k]=n;a[k]=1;k++;
    }   //此时p[0],...,p[k-1]为最初n的k个质数
}
(2)优化：预先运用埃氏筛/欧氏筛打表出2~n的质数,改为遍历prime[i].

埃氏筛:O(n*loglogn) 欧式筛:O(n)

3.逆元:若x*y=1(mod p),则x,y互为模p意义下的逆元.

由费马小定理:x^(-1)=x^(p-2)(mod p),p为质数.
求阶乘的逆元:
    递推实现(i!)^(-1)=((i+1)!)^(-1)*(i+1)(mod p).
    令:inv[i]表示i!的逆元,则:inv[i-1]=inv[i]*i(mod p).
    O(logn)求n!的逆元,O(n)递推得所有数的逆元.

4.秦九韶算法:快速计算sigma(ai*x^i)(i=0~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
long long a[30005],b[30005];
#define E 10007

int main(){
    int n;scanf("%d",&n);
    for(int i=0;i<=n;i++) scanf("%lld",&a[i]);
    int m;scanf("%d",&m);
    for(int i=0;i<=m;i++) scanf("%lld",&b[i]);
    int q;long long x,y;scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        scanf("%lld%lld",&x,&y);
        x%=E;y%=E;
        long long sum1=0,mi=1;
        for(int i=0;i<=n;i++)
        {
            sum1=(sum1%E+(a[i]%E)*(mi%E))%E;
            mi=(mi*x)%E;
        }
        
        mi=1;
        long long sum2=0;
        for(int i=0;i<=m;i++)
        {
            sum2=(sum2%E+(b[i]%E)*(mi%E))%E;
            mi=(mi*y)%E;
        }
        long long res=((sum1%E)*(sum2%E))%E;
        printf("%lld\n",res);
    }
    return 0;
}

5.辗转相除法:

1
2
3
4
5
int gcd(int a,int b){
    if(a==0||b==0) return a+b;
    else if(a%b==0) return b;
    else return gcd(b,a%b);
}

递推/模拟

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
//卡特兰数存放在data中,进行n次查询
long long data[1005]={0};
#define MAX 998244353

void calculate(int num,int *now){
    int k=*now;
    while(num>=k)
    {
        long long sum=0;
        for(int i=0;i<k;i++)
        {
            sum=(((data[i]%MAX)*(data[k-1-i]%MAX))%MAX+sum)%MAX;
        }
        data[k]=sum%MAX;
        k++;
    }
    *now=k-1;
}
int main(){
    int n;scanf("%d",&n);int now=1;
    data[0]=data[1]=1;
    for(int i=0;i<n;i++)
    {
        int num;scanf("%d",&num);
        if(num<=now) printf("%lld\n",data[num]);
        else
        {
            calculate(num,&now);
            printf("%lld\n",data[num]);
        }
    }
    return 0;
}

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//合并同类项:O(n)
int a[100005],b[100005],A[100005],B[100005],c[200005],C[200005];
int main(){
    int t,n,m;scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        
        for(int i=0;i<n;i++) scanf("%d",&a[i]);     //系数
        for(int i=0;i<n;i++) scanf("%d",&A[i]);     //指数,非负递增
        scanf("%d",&m);
        for(int i=0;i<m;i++) scanf("%d",&b[i]);     //系数
        for(int i=0;i<m;i++) scanf("%d",&B[i]);     //指数,非负递增
        
        //(合并后,不会出现和为0的项)
        int i=0,j=0,k=0;
        while(i<n&&j<m)
        {
            if(A[i]==B[j])
            {
                C[k]=A[i];c[k++]=a[i++]+b[j++];
            }
            else if(A[i]<B[j])
            {
                C[k]=A[i];c[k++]=a[i++];
            }
            else
            {
                C[k]=B[j];c[k++]=b[j++];
            }
        }
        while(i<n) {C[k]=A[i];c[k++]=a[i++];}
        while(j<m) {C[k]=B[j];c[k++]=b[j++];}
        
        printf("%d\n",k);
        for(int t=0;t<k;t++) printf("%d ",c[t]);
        printf("\n");
        for(int t=0;t<k;t++) printf("%d ",C[t]);
        printf("\n");
        
        memset(a,0,sizeof(int)*i);memset(A,0,sizeof(int)*i);
        memset(b,0,sizeof(int)*j);memset(B,0,sizeof(int)*j);
        memset(c,0,sizeof(int)*k);memset(C,0,sizeof(int)*k);
    }
    return 0;
}

3.大数乘法:θ(m*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
33
34
35
36
37
38
void multiply(char* a,char* b)
{
    int len1=strlen(a);
    int len2=strlen(b);
    int *res=(int *)malloc(sizeof(int)*(len1+len2+1));
    
    for (int i=0;i<len1+len2;i++) res[i]=0;
    for(int i=0;i<len1;i++)
        for(int j=0;j<len2;j++)
            res[i+j+1]+=(a[i]-'0')*(b[j]-'0');
    for (int i=len1+len2-1;i>0;i--)
        if (res[i]>=10)
        {
            res[i-1]+=res[i]/10;
            res[i]%=10;
        }
    int i=0;
    while(res[i]==0&&i<len1+len2) i++;
    if(i==len1+len2) {printf("0\n");return;}
    for(int j=i;j<len1+len2;j++) printf("%c",res[j]+'0');
    //for(int j=i;j<=len1+len2+1;j++) printf("%c",res[j]+'0');
    printf("\n");
    
}

char A[2005],B[2005];
int main(){
    int T;scanf("%d",&T);getchar();
    while(T--)
    {
        memset(A,'\0',sizeof(char)*2005);memset(B,'\0',sizeof(char)*2005);
        fgets(A,2004,stdin);fgets(B,2004,stdin);
        int lenA=strlen(A);int lenB=strlen(B);//printf("%d",lenA);
        A[lenA-1]='\0';B[lenB-1]='\0';
        //printf("%s",A);printf("%s",B);
        multiply(A,B);
    }
}

4.高精度除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
double divide(long numerator,long denominator){
    double offset=1.0;
    double q=0.0;
    long a=numerator;
    long b=denominator;
    while(b>1){
        if(a>=b){
            a=a-b;
            q=q+offset;
        }else{
            offset=offset*0.1;
            b=denominator*offset;
            //printf_s("%f\n",q);
            //printf_s("%d\n",b);
        }
    }
    return q;
}

分治

1.最大子数组问题:寻找A的和最大的非空连续子数组.

朴素：O(n^2)；分治：O(nlgn).--买一次股票问题. 

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
//分治思路:change数组储存相邻两天变化.change[low,high]的最大值(change[j]-change[i])来自:
//change[low,mid]最大值;change[mid+1,high]最大值;横跨mid的最大值.
#define INFINITY -2147483647
int findMaxCrossingSubarray(int *changes,int low,int mid,int high){
    int left_sum=INFINITY,right_sum=INFINITY,sum=0;
    for(int i=mid;i>=low;i--)
    {
        sum+=changes[i];
        if(sum>left_sum) left_sum=sum;
    }
    sum=0;
    for(int j=mid+1;j<=high;j++)
    {
        sum+=changes[j];
        if(sum>right_sum) right_sum=sum;
    }
    return left_sum+right_sum;
}
int findMaxSubarray(int *changes,int low,int high){
    if(low==high) return changes[low];
    int mid=(low+high)/2;
    int leftSum=findMaxSubarray(changes,low,mid),rightSum=findMaxSubarray(changes,mid+1,high),crossSum=findMaxCrossingSubarray(changes,low,mid,high);
    if(leftSum>=rightSum&&leftSum>=crossSum) return leftSum;
    else if(rightSum>=leftSum&&rightSum>=crossSum) return rightSum;
    else return crossSum;
}

int maxProfit(int *prices,int pricesSize){
    if(pricesSize==0||pricesSize==1) return 0;
    int *changes=(int *)malloc(sizeof(int)*(pricesSize-1));
    for(int i=0;i<pricesSize-1;i++) changes[i]=prices[i+1]-prices[i];
    return findMaxSubarray(changes,0,pricesSize-2)>0?findMaxSubarray(changes,0,pricesSize-2):0;
}

2.树状数组:

引入辅助数组C,C[i]管辖的元素个数：\(2^k\)个（k为i的二进制末尾0的个数）.

求前缀和:求sum(A1+…+Am)：查询的m转为二进制，不断消除当前末尾1，直至全部为0停止。 例：7(0111)[C7] -> 6(0110)[C6] -> 4(0100)[C4] -> 0. 故sum(A1+…+A7)=C4+C6+C7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    //如何求m的二进制表示的末尾1位置？
    int lowbit(int m){
            return m&(-m);
    }
    //求前缀和：O(logn)
    int ans=0;
    int getSum(int m){
            while(m>0)
            {
                    ans+=C[m];
                    m-=lowbit(m);
            }
    }
    //单点更新a[i]：i转为二进制，不断对当前末尾1 +1，直至达到数组下标的最大值n结束.
    //例：更新A[2](+value)：
        //更新 (+value)(0010)->更新C[4](+value)(0100)->更新C[8](+value)(1000).
void update(int i,int value){
    A[i]+=value;
    while(i<=n)
    {
        C[i]+=value;
        i+=lowbit(i);
    }
}

例：求逆序对数目 

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
//原数组A标记数i是否出现,A[i]=0未出现,A[i]=1出现.求前缀和,即为正序对数目
int lowbit[200010];
int sum[200010];        //树状数组
int main(){
    for(int i=1;i<=200005;i++) lowbit[i]=i&(-i);
    int T,n,op;     //T为数据组数，n为每组数据个数
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(sum,0,sizeof(int)*200010);
        long long ans=0;        //ans记录逆序对数量之和
        for(int i=0;i<n;i++)
        {
            scanf("%d",&op);        //op为当前a[i]
            long long nowsum=0;

            //原数组A标记数i是否出现,A[i]=0未出现,A[i]=1出现.sum为A对应树状数组
            //求A[1]~A[op]前缀和.
            for(int j=op;j>0;j-=lowbit[j]) nowsum+=sum[j];
            
            ans+=i-nowsum;          //a[i]前有i个数,nowsum为小于a[i]=op的数个数
            
            //更新数组:A[op]=1.
            for(int j=op;j<=200000;j+=lowbit[j]) sum[j]++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
### 3.归并排序:O(n*lgn). 
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
//归并过程中求逆序对
long long merge(int r[],int s[],int left,int mid,int right)//将r数组分为两部分，排序后存到s数组中
{
    int i,j,k;
    long long num = 0;
    i=left;//左数组的索引
    j=mid+1;//右数组的索引
    k=left;
    while((i<=mid)&&(j<=right))
    {       
        if(r[i]<=r[j]) s[k++] = r[i++];//左半边的元素进入新数组，所以不用交换
        else//右半边的元素进入新数组，要交换
        {
            num += j - k;
            s[k++]=r[j++];
        }        
    }
    while(i<=mid) s[k++]=r[i++];
    while(j<=right) s[k++]=r[j++];
    return num;
}

long long merge_sort(int r[],int s[],int left,int right)//r[] 是原始数组, s[] 是用于存储结果的临时数组
{
    long long ans = 0;
    int mid;
    int t[100010];//一个用于临时存储数据的数组。
    if(left==right)//如果 left 等于 right，说明子数组只包含一个元素，无需排序，直接将该元素放入 s 中
    {
        s[left]=r[right];
        return 0;
    }
    else
    {
        mid=(left+right)/2;
        ans+=merge_sort(r,t,left,mid);
        ans+=merge_sort(r,t,mid+1,right);
        ans+=merge(t,s,left,mid,right);
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, a[100010];
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        printf("%lld\n", merge_sort(a,a,0,n-1));
    }
}
## 堆 ### 1.C语言实现 
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//1.维护堆的性质:
//A[i]左右子树都是最大堆,调整以A[i]为根结点的二叉树为最大堆
//时间复杂度:T(n)<=T(2n/3)+theta(1),T(n)=O(lgn).
void swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
void max_heapify(int *A,int heapsize,int i){
    int l=2*i,r=2*i+1,largest;
    if(l<=heapsize&&A[l]>A[i]) largest=l;
    else largest=i;
    if(r<=heapsize&&A[r]>A[largest]) largest=r;
    
    if(largest!=i)
    {
        //交换A[i]与A[largest]
        swap(&A[i],&A[largest]);
        max_heapify(A,heapsize,largest);
    }
}

//2.建堆:
//自底向上,用max_heapify将数组转为最大堆:A[len/2+1,...,len]为叶节点,每个叶节点看作一个元素的堆
//时间复杂度:非紧确界:O(n*lgn);紧确界:O(n).
void build_maxHeap(int *A,int len){
    int heapsize=len;
    for(int i=len/2;i>=1;i--) max_heapify(A,heapsize,i);
}

//3.堆排序(升序):
void heapSort(int *A,int len){
    build_maxHeap(A,len);       //建立初始最大堆
    int heapsize=len;
    for(int i=len;i>=2;i--)
    {
        swap(&A[1],&A[i]);
        heapsize-=1;
        max_heapify(A,heapsize,1);
    }
}

//4.最大优先队列,去除最大元素:
//时间复杂度:O(logn)
int heap_extract_max(int *A,int *heapsize){
    if(*heapsize<1) return -1;       //无效
    int max=A[1];
    A[1]=A[*heapsize];
    (*heapsize)--;
    max_heapify(A,*heapsize,1);
    return max;
}

//5.最大堆元素值增加后,调整最大堆
//时间复杂度:O(lgn)
void heap_increase_key(int *A,int i,int key){
    if(A[i]>key) return;
    A[i]=key;
    while(i>1&&A[i/2]<A[i])
    {
        swap(&A[i/2],&A[i]);    //上浮:与父节点交换
        i=i/2;
    }
}

//6.最大堆插入元素
//时间复杂度:O(lgn)
#define INFINITY -10000
void maxHeap_insert(int *A,int key,int *heapsize){
    (*heapsize)++;
    A[*heapsize]=INFINITY;
    heap_increase_key(A,*heapsize,key);
}

int A[100005];
int main(){
    int n,op,x,heapsize=0;scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d",&x);
            maxHeap_insert(A,x,&heapsize);
        }
        else if(op==2) heap_extract_max(A,&heapsize);
        else if(op==3) printf("%d\n",A[1]);
    }
    qsort(&A[1],heapsize,sizeof(int),cmp);
    for(int i=1;i<=heapsize;i++) printf("%d ",A[i]);
    return 0;
}
### 2.C++实现:最大优先队列 最大优先队列:队首为最大元素 
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
#include<queue>
#include<functional>
using namespace std;
//最大优先队列(底层实现:heap)
priority_queue<int>p;
priority_queue<int,vector<int>,less<int>>p;
//最小优先队列
priority_queue<int,vector<int>,greater<int>>q;
//成员函数:
p.push(1);          //插入元素
cout<<p.top();      //访问队首元素
p.pop();            //移除队首元素
if(p.empty())       //检查是否为空

//自定义比较函数:例--比较年龄
struct Person{
    string name;
    int age;
    Person(const string &n,int a):name(n),age(a){}
};
struct compareByAge{
bool operator()(const Person& p1,const Person& p2)const{
    return p1.age>p2.age;       //按年龄从小到大排序
    }
};
int main(){
    priority_queue<Person,vector<Person>,compareByAge>q;
}

快速排序

性能分析

最坏划分：两子问题分别包括0和n-1个元素:T(n)=T(n-1)+θ(n),得T(n)=θ(n^2). 最好划分：T(n)=2T(n/2)+θ(n),得T(n)=θ(nlgn). 平衡划分:常数比例的划分,递归树深度为θ(lgn),每层工作量为O(n).总运行时间O(nlgn). 使用RANDOMIZED-PARTITION,在输入元素互异时,快排的期望运行时间为O(nlgn).

C语言实现

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
//写法一:
void quickSort(int list[],int left,int right,int *cnt){
    if(left>=right) return;
    int last=left;
    for(int i=left+1;i<=right;i++)
    {
        (*cnt)++;
        if(list[i]<list[left]) swap(&list[++last],&list[i]);  //list[left]作为基准值：将小于基准值的元素，换至last以前
    }
    swap(&list[left],&list[last]);
    quickSort(list,left,last-1,cnt);
    quickSort(list,last+1,right,cnt);
}

//写法二:
int partition(int *A,int p,int r){
    int x=A[r];     //主元
    int i=p-1;
    for(int j=p;j<=r-1;j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            swap(&A[i],&A[j]);
        }
    }
    swap(&A[i+1],&A[r]);
    return i+1;
}

int Randomized_Partition(int *A,int p,int r){
    int i=p+rand()%(r-p);
    swap(&A[i],&A[r]);
    return partition(A,p,r);
}

void quicksort(int *A,int p,int r){
    if(p<r)
    {
        int q=Randomized_Partition(A,p,r);
        quicksort(A,p,q-1);
        quicksort(A,q+1,r);
    }
}

求顺序统计量

求A[p,r]中第i小的元素--期望时间:θ(n);最坏时间:θ(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
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include<stdlib.h>
void swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
int partition(int *A,int p,int r){
    int x=A[r];     //主元
    int i=p-1;
    for(int j=p;j<=r-1;j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            swap(&A[i],&A[j]);
        }
    }
    swap(&A[i+1],&A[r]);
    return i+1;
}
int Randomized_Partition(int *A,int p,int r){
    int i=p+rand()%(r-p);           //rand()返回0~32767间的随机数
    swap(&A[i],&A[r]);
    return partition(A,p,r);
}
//A[p...r]中,找第i小的元素
int Randomized_Select(int *A,int p,int r,int i){
    if(p==r) return A[p];
    int q=Randomized_Partition(A,p,r);
    //int q= partition(A,p,r);
    int k=q-p+1;
    if(i==k) return A[q];
    else if(i<k) return Randomized_Select(A,p,q-1,i);
    else return Randomized_Select(A,q+1,r,i-k);
}

int main(){
    int A[10]={0,9,4,3,1,2,5,7,6,8};
    for(int i=1;i<=10;i++) printf("%d ",Randomized_Select(A,0,9,i));
    return 0;
}

线性时间排序

1.比较排序算法

O(n*lgn)时间内排序n个数:
    归并排序,堆排序--最坏情况达到θ(n*lgn);
    快速排序--平均情况达到θ(n*lgn).

排序算法下界:最坏情况下，任何比较排序算法都需要欧姆次比较. 推论:堆排序,归并排序都是渐近最优的比较排序算法.

2.计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
//计数排序:n个元素为0~k之间的整数,当k=O(n)时,排序时间为O(n).
//A为原数组,B存放排序输出,C进行计数
void countSort(int *A,int *B,int n,int k){
    int *C=(int *)malloc(sizeof(int)*(k+1));
    for(int i=0;i<=k;i++) C[i]=0;
    for(int j=0;j<n;j++) C[A[j]]+=1;        //C[i]记录等于i的元素个数
    for(int i=1;i<=k;i++) C[i]=C[i]+C[i-1]; //C[i]记录小于等于i的元素个数
    for(int j=n-1;j>=0;j--)
    {
        B[C[A[j]]]=A[j];    //C[A[j]]中为小于等于A[j]的元素个数,这些元素储存在下标0~C[A[j]]-1的位置
        C[A[j]]--;          //元素不完全互异时,将下一个等于A[j]的元素,置于A[j]前一个位置上
    }
}

滑动窗口

例:求序列的所有长度为k的连续子序列中,最大的数字种类数.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N=1e5+5;
int n,k,cnt,ans,a[N];
void solve(){
    cin>>n>>k;
    set<int> s;
    map<int,int> m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s.insert(a[i]);
    }
    if((int)s.size!=k) {cout<<"-1"<<endl;return;}
    ans=0;
    for(int i=1;i<=n;i++){
        m[a[i]]++;
        if(i>k)
        {
            m[a[i-k]]--;
            if(m[a[i-k]]==0) m.erase(a[i-k]);
        }
        ans=max(ans,(int)m.size());
    }
}

动态规划:

1.最优子结构：可由子问题最优解，构造原问题的最优解。（子问题无关，不共享资源，结果互不影响） 2.重叠子问题：反复求解相同的子问题，将解存入备忘录中。 （分治：每一步生成全新的子问题） ### 1.钢管切割：总长度固定，不同长度不同售价 r[n]=max(p[i]+r[n-i]).i=1~n. C语言实现:θ(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
32
33
34
35
36
37
38
39
#define max(a,b) a>b?a:b
#define INFINITY -2147483648
void print_cut_rod_solution(int *p,int n,int *s){       //打印长度为n的最优切割方案
    while(n>0)
    {
        printf("%d ",s[n]);
        n-=s[n];
    }
}
    //3.自底向上递归:θ(n^2)
int bottom_up_cut_rod(int *p,int n){
    int *r=(int *)malloc(sizeof(int)*(n+1));    //辅助数组,r记录最大利润
    int *s=(int *)malloc(sizeof(int)*(n+1));    //s记录切割方案
    r[0]=0;
    for(int j=1;j<=n;j++)
    {
        int q=INFINITY;
        for(int i=1;i<=j;i++)
        {
            if(q<p[i]+r[j-i])
            {
                q=p[i]+r[j-i];
                s[j]=i;     //s[j]:规模为j的子问题中,第一段钢条的最优切割长度
            }
            //q=max(q,p[i]+r[j-i]);
        }
        r[j]=q;
    }
    print_cut_rod_solution(p,n,s);
    return r[n];        //最大总利润
}

    long long p[10005];     //p[i]:长度为i的钢管价格
    int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
    bottom_up_cut_rod(p,n);
    return 0;
}
#### 变式：每次切割固定成本c 
1
2
3
4
5
6
7
8
9
10
11
int modify_cut_rod(int *p,int n,int c){
    int *r=(int *)malloc(sizeof(int)*(n+1));
    r[0]=0;
    for(int j=1;j<=n;j++)
    {
        int q=p[j];         //不切割,长度j整段出售
        for(int i=1;i<=j-1;i++) q=max(q,p[i]+r[j-i]-c);
        r[j]=q;
    }
    return r[n];
}
### 2.矩阵链乘法:求完全括号化方案，使得计算A1A2...An所需标量乘法次数最少. 括号化方案数量:卡特兰数 设:矩阵Ai的大小为：p[i-1]xp[i]. m[i,j]=min(m[i,k]+m[k+1,j]+p[i-1]p[k]p[j]),i<j. #### (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
//1.自底向上
//p=<p0,...,pn>.
#define N 100
#define INFINITY_2 2147483647
int m[N][N],s[N][N];     //m记录Ai...Aj结果,s[i][j]记录m[i][j]对应最优分割点k
int matrix_chain_order(int *p,int n){
    for(int l=2;l<=n;l++)       //长度
    {
        for(int i=1;i<=n-l+1;i++)
        {
            int j=n-l+1;    //保持i~j长度为l
            m[i][j]=INFINITY_2;
            for(int k=i;k<=j-1;k++)
            {
                int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(q<m[i][j])
                {
                    m[i][j]=q;
                    s[i][j]=k;
                }
            }
        }
    }
    return m[1][n];
}
#### (2)带备忘的自顶向下 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int lookup_chain(int *p,int i,int j){
    if(m[i][j]<INFINITY_2) return m[i][j];      //查询是否记录
    if(i==j) m[i][j]=0;
    else
    {
        for(int k=i;k<=j-1;k++)
        {
            int q=lookup_chain(p,i,k)+lookup_chain(p,k+1,j)+p[i-1]*p[k]*p[j];
            if(q<m[i][j]) m[i][j]=q;
        }
    }
    return m[i][j];
}

int memorized_matrix_chain(int *p,int n){
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++) m[i][j]=INFINITY_2;
    }
    return lookup_chain(p,1,n);
}
#### 构造最优解： 
1
2
3
4
5
6
7
8
//s[i][j]记录m[i][j]对应最优分割点k
void print_optimal_parens(int **s,int i,int j){
    if(i==j) {printf("A%d",i);return;}
    printf("(");
    print_optimal_parens(s,i,s[i][j]);
    print_optimal_parens(s,s[i][j]+1,j);
    printf(")");
}

3.流水线调度

dp[i][j]:在流水线上完成第j个步骤时的最小时间。 for(int k=0;k<3;k++) dp[i][j] = min(dp[i][j],(j>=1?dp[k][j-1]+t[k][i]:0LL)+p[i][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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
using namespace std;
#define MAXN 12
#define MAXM 22
typedef long long ll;
const ll inf = 1e18;

int a[MAXN][MAXM], t[MAXN][MAXN];
//a[i][j]:流水线i处理j的时间; t[i][j]:流水线i->j的转移时间.
ll dp[MAXN][MAXM],nxt[MAXN][MAXM]; //dp[i][j]:在流水线i上完成j时的最小时间.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        int m,n;cin>>m>>n;      //n条流水线,m个步骤
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++) cin >> a[i][j];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) cin >> t[i][j];
        //for(int i = 1; i <= n; i++) dp[i][m] = a[i][m];
        for (int j = m; j >= 1; j--)    //逆推:从终点出发,0开始计时,前往起点
        {
            for (int i = 1; i <= n; i++)
            {
                dp[i][j] = inf;             //当前在第i条流水线完成j
                for (int k = 1; k <= n; k++)        //遍历：在第k条流水线完成j+1.
                {
                    ll p=(j<=m-1?dp[k][j+1]+t[i][k]:0LL)+a[i][j];
                    if (p < dp[i][j])
                    {
                        dp[i][j] = p;
                        nxt[i][j] = k;      //第i条上完成j后,下一步转移至第k条最佳.
                    }
                }
            }
        }
        ll ans=dp[1][1],cur=1;
        for(int i=1;i<=n;i++)
        {
            if(ans>dp[i][1]) {ans=dp[i][1];cur=i;}
        }
        cout<<ans<<"\n";
        for(int i=1;i<=m;i++)
        {
            cout<<"Station"<<i<<": Line"<<cur<<"\n";
            cur = nxt[cur][i];
        }
    }
    return 0;
}
### 4.OBST(最优二叉搜索树）--区间dp 关键字的升序序列：K=<k1,...,kn>,有：k1<...<kn.--概率pi.(内部节点) n+1个伪关键字：d0,...,dn.有：ki<di<k(i+1).--概率qi.(叶节点) 有:sum(pi)+sum(qi)=1. 搜索代价：E=sum[(depth(ki)+1)*pi]+sum[(depth(di)+1)*qi] =1+sum[depth(ki)*pi]+sum[depth(di)*qi].

设:e[i,j]表示:在包含关键字ki,...,kj的OBST中搜索一次的期望代价. w[i,j]表示:包含关键字ki,...,kj的子树,概率之和: w[i,j]=sum(pl)(l=ij)+sum(ql)(l=i-1j). root[i,j]表示包含关键字ki,...,kj的子树的根.

递归公式:e[i,j]=q[i-1] if j==i-1. =min{e[i,r-1]+e[r+1,j]+w(i,j)}(i<=r<=j) if i<=j.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define inf 2147483647
int e[MAXN+1][MAXN+1],w[MAXN+1][MAXN+1],root[MAXN+1][MAXN+1];
//e[1...n+1,0...n],w[1...n+1,0...n],root
//(p1,...,pn),(q0,...,qn)为概率,规模n.
void OBST(int *p,int *q,int n){
    for(int i=1;i<=n+1;i++) {e[i][i-1]=w[i][i-1]=q[i-1];}
    for(int l=1;l<=n;l++)
    {
        for(int i=1;i<=n-l+1;i++)
        {
            int j=i+l-1;e[i][j]=inf;
            w[i][j]=w[i][j-1]+p[j]+q[j];
            for(int r=i;r<=j;r++)
            {
                int t=e[i][r-1]+e[r+1][j]+w[i][j];
                if(t<e[i][j]){e[i][j]=t;root[i][j]=r;}
            }
        }
    }
}

5.最长公共子序列(LCS)--O(n^2)

c[i][j]=0. if i==0||j==0. c[i-1][j-1]+1. if i,j>0&&x[i]=y[j]. max(c[i][j-1],c[i-1][j]). if i,j>0&&x[i]!=y[j].

θ(mn)个子问题. 

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//c[i,j]记录:Xi,Yj的LCS长度.
//可按行主次序计算:先从左至右i第一行,再第二行...
#define max_M 100
#define max_N 100
int c[max_M+1][max_N+1],b[max_M][max_N],a[max_M+1][max_N+1];
    //a[i][j]记录:Xi,Yj的最长公共子串长度(字符连续).
void print_LCS(char *X,int i,int j){        //时间复杂度:O(m+n).
    if(i==0||j==0) return;
    if(b[i][j]==-1)
    {
        print_LCS(X,i-1,j-1);
        printf("%c",X[i]);
    }
    else if(b[i][j]==0) print_LCS(X,i-1,j);
    else print_LCS(X,i,j-1);
}

//空间复杂度:θ(mn).
int LCS_length(char *X,char *Y,int m,int n){
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(X[i]==Y[j])
            {
                c[i][j]=c[i-1][j-1]+1;b[i][j]=-1;   //LCS
                a[i][j]=a[i-1][j-1]+1;          //最长公共子串
            }
            else if(c[i-1][j]>=c[i][j-1])
            {
                c[i][j]=c[i-1][j];b[i][j]=0;        //LCS
                a[i][j]=0;
            }
            else
            {
                c[i][j]=c[i][j-1];b[i][j]=1;        //LCS
                a[i][j]=0;
            }
        }
    }
    print_LCS(X,m,n);
    return c[m][n];
}

char A[2005],B[2005],C[2005],D[2005];
int main(){
    int T;scanf("%d",&T);getchar();
    while(T--){
        memset(A,'\0',sizeof(char)*2005);
        memset(B,'\0',sizeof(char)*2005);
        memset(C,'\0',sizeof(char)*2005);
        memset(D,'\0',sizeof(char)*2005);
        memset(c,0,sizeof(int)*2006*2006);
        memset(b,0,sizeof(int)*2006*2006);
        ans1=0;ans2=0;
        
        fgets(A,2003,stdin);
        fgets(B,2003,stdin);
        int lenA=strlen(A),lenB=strlen(B);
        if(A[lenA-1]=='\n')
        {
            A[lenA-1]='\0';
            lenA--;
        }
        if(B[lenB-1]=='\n')
        {
            B[lenB-1]='\0';
            lenB--;
        }
        strcpy(&C[1],A);strcpy(&D[1],B);
        //printf("%d %d\n",lenA,lenB);
        LCS_length(C,D,lenA,lenB);
        printf("%d %d\n",ans2,ans1);
    }
    ans1=c[m][n];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]>ans2) ans2=a[i][j];
        }
    }
    return 0;
}
### 6.最长上升子序列(LIS)--O(n*logn) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//时间复杂度:O(n*logn);空间复杂度:O(n).
int LIS(vector<int> &nums){
    int len=1,n=(int)nums.size();
    if(n==0) return 0;
    vector<int> d(n+1,0);   //d[i]:长度为i的LIS的末尾元素最小值
    d[len]=nums[0];
    //初始len=1,d[1]=nums[0].
    for(int i=1;i<n;i++)            //将nums[i]加在序列末尾
    {
        if(nums[i]>d[len]) d[++len]=nums[i];
        else{
            int l=1,r=len,pos=0;
            //在d数组中二分查找,找到第一个(最大的)比nums[i]小的数d[k],更新:d[k+1]=nums[i].
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(d[mid]<nums[i]) {pos=mid;l=mid+1;}
                else r=mid-1;
            }
            d[pos+1]=nums[i];
        }
    }
    return len;
}
拓展：最长公共上升子序列 思路：f[i][j]表示:所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合. 
1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= m; ++ i) {
        int maxv = 1;
        for (int j = 1; j <= n; ++ j) {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++ i) ans = max(f[n][i], ans);

7.背包问题

(1)0-1背包:一种物品使用一次

压缩为一维:f[j]表示:背包容量不超过j时的最大价值. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int f[N],v[N],w[N]; //w[i]是价值，v[i]是体积

int main()
{
    int n,m;
    cin>>n>>m; //n件物品和体积限制m
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)              //滚动数组,倒序优化
            f[j] = max(f[j],f[j-v[i]]+w[i]); 
    cout<<f[m]<<endl;
    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
//二维动态规划
typedef struct{
    int val;
    int weight;
}goods;
#define N 1005
//#define max(a,b) a>b?a:b
goods all[N+1];     //all[1...n]记录商品
int max(int a,int b){
    if(a>b) return a;
    else return b;
}

int Knapsack(int n,int W){        //n为商品数量,W为背包承载量
    int **K=(int **)malloc(sizeof(int *)*(n+1));
    for(int i=0;i<=n;i++) K[i]=(int *)malloc(sizeof(int)*(W+1));
    
    //K[i][j]表示:承载量为j的背包,装前i件物品,所得最大价值
    for(int i=1;i<=n;i++) K[i][0]=0;
    for(int j=1;j<=W;j++) K[0][j]=0;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=W;j++)
        {
            //是否将第i件商品装入背包
            if(j<all[i].weight) K[i][j]=K[i-1][j];      //一定装不进
            else K[i][j]=max(K[i-1][j],K[i-1][j-all[i].weight]+all[i].val);     //装/不装
        }
    }
    //return K;
    return K[n][W];
}

int main(){
    int T,n,V;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&V);
        for(int i=1;i<=n;i++) scanf("%d%d",&all[i].val,&all[i].weight);
        printf("%d\n",Knapsack(n,V));
    }
    return 0;
}
#### (2)完全背包:每种物品可使用无限次 与0-1背包对比： 二维:f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]); //01背包 f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包 一维:如代码. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int f[N],v[N],w[N]; //w[i]是价值，v[i]是体积

int main()
{
    int n,m;
    cin>>n>>m; //n件物品和体积限制m
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)              //滚动数组,正序优化
            f[j] = max(f[j],f[j-v[i]]+w[i]); 
    cout<<f[m]<<endl;
    return 0;
}
#### (3)多重背包:每件物品最多有si件. 无法优化为一维. f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); //和完全背包问题的朴素代码一样 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int v[N],w[N],s[N];
int f[N][N];

int main()
{
    int n,m;
    cin>>n>>m;     //n件物品和体积限制m
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];   //s[i]:最多数量
    for(int i=1;i<=n;i++)          //枚举种数
        for(int j=0;j<=m;j++)         //然后枚举体积，注意，这里不能从v[i]开始枚举
        {
            for(int k=0;k*v[i]<=j&&k<=s[i];k++)  //最后枚举第i种物品的个数
                f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
        }
    cout<<f[n][m]<<endl;
    return 0;	
}```

#### (4)分组背包:同一组内物品最多选一个
```C
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int v[N][N],w[N][N];//第i组第j个物品的体积和价值
int s[N];//第i组物品的数量
int f[N];

int main()
{
    int n,m;
    cin>>n>>m;          //n个组,背包容量m.
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];              //每组物品数量
        for(int j=0;j<s[i];j++)
            cin>>v[i][j]>>w[i][j];  //第i组第j个物品的体积/价值
    }
    
    for(int i=1;i<=n;i++)           //枚举物品组
        for(int j=m;j>=0;j--)       //枚举体积
            //枚举决策，也就是选这个物品组的哪个物品
            for(int k=0;k<s[i];k++)
                if(v[i][k]<=j)
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
    cout<<f[m]<<endl;
    return 0;
}

8.一些记录

长高问题：dp[0..k][0..n],dp[i][j]为:完成第j个点时,跳过i次深坑,得到的最大身高(应有:i<=j)

贪心

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
//贪心算法:局部最优解,导致全部最优解

//1.活动选择问题:找最大兼容活动集
//动态规划:c[i,j]=max{c[i,k]+c[k,j]+1}--(ak属于Sij)
//贪心选择:反复选择结束时间最早的活动,保留兼容的活动
#define N 100005
typedef struct{
    long long start;
    long long finish;
}act;
act all[N];     //储存所有活动的数组
act ans[N];     //答案数组
int n;          //活动总个数
int cnt;        //答案数组中活动个数

int cmp(const void *e1,const void *e2){
    act *p=(act *)e1,*q=(act *)e2;
    return p->finish-q->finish;
}
//qsort(&all[1],n,sizeof(act),cmp);         //all数组按完成时间升序排序

//求解时调用:recursive_activity_selector(0,n).
//(已排序时)时间复杂度:theta(n).
void recursive_activity_selector(int k,int n){      //返回Sk的最大兼容活动集
    int m=k+1;
    while(m<=n&&all[m].start<all[k].finish) m=m+1;      //找与活动k兼容的,最早结束的活动
    if(m<=n)
    {
        ans[cnt++]=all[m];
        recursive_activity_selector(m,n);
    }
    else return;
}

int main(){
    int T,n;scanf("%d",&T);
    while(T--){
        cnt=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) {scanf("%lld%lld",&all[i].start,&all[i].finish);all[i].finish+=all[i].start;}
        qsort(&all[1],n,sizeof(act),cmp);         //all数组按完成时间升序排序
        recursive_activity_selector(0,n);
        printf("%d\n",cnt);
    }
    return 0;
}

2.Huffman编码

变长编码,每个字符用唯一的一个二进制串表示(性质：没有任何码字是其他码字的前缀） 问题：构造Huffman树，使得:B(T)=c.freqd(c)最小,c.freq为点权重，d(c)为点深度 贪心算法构造:n-1次合并,每次合并时:最小优先队列(最小堆实现)选取最小两个元素,合并为一个元素,插入队列--O(nlgn) 

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
//每个不可分割钢条为叶节点,从树顶往下切割,非根节点为当前钢条长度,问题转为:求Huffman树的最小代价
//类Huffman树:选取当前长度最小的两个点,合并
#include <bits/stdc++.h>
#define maxn 200086
using namespace std;
typedef long long ll;
int n;
priority_queue<ll, vector<ll>, greater<ll> > 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);
}
### 3.合法括号序列 
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
//贪心策略填括号.先计算需要新填入的左/右括号数量,在不超过的前提下,优先填左括号.
//时间复杂度:O(n).

char S[100005];
int l,r,no;
int left,right;     //left,right记录当前位置之前的:左/右括号数量
bool judge(int n){
    if(n%2) return false;   //奇数长度,一定不能构成合法括号序列
    for(int i=0;i<n;i++)    //初始化,统计左/右/待填括号数量
    {
        if(S[i]=='(') l++;
        else if(S[i]==')') r++;
        else no++;
    }
    //printf("%d,%d,%d\n",l,r,no);
    if(l+no<r||r+no<l) return false;
    l=n/2-l;r=n/2-r;        //此时l,r为可新填入的左/右括号数量
    for(int i=0;i<n;i++)
    {
        if(left<=right&&left!=0) return false;   //left==right不满足:S任一非空且非自身前缀均不为合法括号序列
        if(S[i]=='(') left++;
        else if(S[i]==')') right++;
        else
        {
            if(left<n/2&&l>0)    //优先填左括号
            {
                S[i]='(';left++;l--;
            }
            else
            {
                S[i]=')';right++;r--;
            }
        }
        //printf("%s\n",S);
    }
    return true;
}
int main(){
    int n;scanf("%d",&n);
    scanf("%s",S);
    int len=strlen(S);
    if(S[len-1]=='\n') {S[len-1]='\0';len--;}

    if(!judge(n)) printf(":(");
    else printf("%s",S);
    return 0;
}

4.求不超过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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 505;
char a[N], b[N];
int n, mid;

int leq()
{
    for (int i = 1; i <= n; i++){
        if (b[i] < a[i]) return 1;	
        if (b[i] > a[i]) return 0;
    }
    return 1;
}
void solve()
{
    scanf("%s", a + 1);
    n = strlen(a + 1);
    mid = 1;
    for (int i = 1, j = n; i <= j; i++, j--)
    {
        b[i] = b[j] = a[i];
        mid = i;
    }
    b[n + 1] = 0;
    if (leq())
    {
        printf("%s\n", b + 1);
        return;
    }
    b[mid]--;
    for (int i = mid; i && b[i] < '0'; i--)
    {
        b[i] += 10;
        b[i - 1]--;
    }
    for (int i = 1; i <= mid; i++)
        b[n - i + 1] = b[i];
    if (b[1] != '0' && leq())
    {
        printf("%s\n", b + 1);
        return;
    }
    for (int i = 1; i < n; i++)
        b[i] = '9';
    b[n] = 0;
    printf("%s\n", b + 1);
}
int main()
{
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

图论

1.DFS

例: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
33
34
35
36
37
38
39
40
41
42
43
44
//各位的n次方之和等于该数,该数共n位.
#include<iostream>
using namespace std;
#define ll long long
int n;
ll pw[10],cnt[10],bit[10],ans;

int check(ll s){
    for(int i=0;i<10;i++) bit[i]=0;
    while(s>0){
        bit[s%10]++;
        s/=10;
    }
    for(int i=0;i<10;i++){
        if(cnt[i]!=bit[i]) return 0;
    }
    return 1;
}
//ubound:可供选择的n次方最大的底数;num为当前的n次方之和
void dfs(int bound,ll num,ll limit){
    if(num<limit/10) return;
    ans+=check(num)*num;
    for(int i=0;i<=bound;i++){
        cnt[i]++;
        dfs(i,num+pw[i],limit*10);
        cnt[i]--;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        cin>>n;         //n次方
        ans=0;
        for(int i=0;i<10;i++){
            cnt[i]=0;pw[i]=1;
            for(int j=0;j<n;j++) pw[i]*=i;
        }
        dfs(9,0,1);
        cout<<ans<<endl;
    }
    return 0;
}

2.BFS

例:地图中每个格子,有可向上下左右移动的步数,求(1,1)->(n,m)的最小次数.

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
//[1,1]->[n,m]最小次数
#include<iostream>
#include<vector>
#include<queue>
#include<array>
#define ll long long
using namespace std;
int n,m;

//n为总行/列数;l为当前格子可向上/下/左/右移动的步数;
ll calc(ll x,ll step,ll n,int neg){
    if(n==1) return x;
    if(neg){
        ll a=(x-step%(2*n-2)+(n-2)+(2*n-2))%(2*n-2);
        if(a>=n-2) return a-(n-2);
        else return (n-2)-a;
    }else{
        ll a=(x+step%(2*n-2))%(2*n-2);     //n+(n-1)=2n-2.
        if(a>=n) return 2*n-2-a;
        else return a;
    }
}

//由于每个格子处有不同的指定步数,且均可向上下左右移动,因此无法用dp.
//BFS访问,队列记录.
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;cin>>tt;
    while(tt--){
        cin>>n>>m;
        vector<vector<int>>a (n,vector<int>(m));
        vector<vector<bool>>vis (n,vector<bool>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++) cin>>a[i][j];
        }
        queue<array<ll,3>>q;
        vis[0][0]=true;
        q.push({0,0,0});
        ll ans=-1;
        while(!q.empty()){
            ll r=q.front()[0],c=q.front()[1],w=q.front()[2];
            q.pop();
            if(r==n-1&&c==m-1) {ans=w;break;}

            int step=a[r][c];
            ll nr,nc;
            nr=calc(r,step,n,0);nc=c;
            if(!vis[nr][nc]) {vis[nr][nc]=true;q.push({nr,nc,w+1});}
            nr=calc(r,step,n,1);nc=c;
            if(!vis[nr][nc]) {vis[nr][nc]=true;q.push({nr,nc,w+1});}
            nr=r;nc=calc(c,step,m,0);
            if(!vis[nr][nc]) {vis[nr][nc]=true;q.push({nr,nc,w+1});}
            nr=r;nc=calc(c,step,m,1);
            if(!vis[nr][nc]) {vis[nr][nc]=true;q.push({nr,nc,w+1});}
        }
        cout<<ans<<'\n';
    }
}

3.单源最短路问题

(1)Bellford:可能包括负环

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
#define N 2005
#define M 6005
#define inf 1e9
#define min(a,b) a<b?a:b
struct edge{
    int u,v,w;
};
struct edge Edges[M];
int dis[N];     //dis[i]记录:源点到点i的距离(i=1,...,n)

int n,m;    //n个点,m条边

bool BellFord(int s){
    fill(dis,dis+n+1,inf);
    dis[s]=0;
    for(int i=1;i<n;i++)    //每条边松弛n-1次
    {
        for(int j=1;j<=m;j++)
        {
            dis[Edges[j].v]=min(dis[Edges[j].v],dis[Edges[j].u]+Edges[j].w);
        }
    }
    for(int j=1;j<=m;j++)
    {
        if(dis[Edges[j].v]>dis[Edges[j].u]+Edges[j].w) return false;    //有负环
    }
    return true;
}
int main(){
#ifdef abyss
    freopen("in.txt", "r", stdin);
#endif

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int T;cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=m;i++) cin>>Edges[i].u>>Edges[i].v>>Edges[i].w;  //输入边
        bool ans=BellFord(1);
        if(ans==false) cout<<"boo how\n";
        else
        {
            for(int i=1;i<=n;i++) cout<<dis[i]<<(i==n?"\n":" ");
        }
    }
    return 0;
}

(2)Dijkstra算法：无向图,无负环

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

//无向图：单源最短路径问题
//无负边,无负环--Dijkstra
//1.已确定点集S,未确定点集T,初始化所有点属于T集合,dis(s)=0,其他点dis=inf;
//2.不断从T中选取dis最小的节点u,加入S中;
//3.对u的所有出边执行松弛操作.dis(v)=min(dis(v),dis(u)+w).
//贪心构建集合S;选取dis最小的点,用优先队列实现O(MlogM).

//写法一:邻接表实现
#define inf 1e18
class Dijkstra{
public:
    int n;
    vector<vector<pair<int ,long long>>>g;      //g[u]存储u的出边及权重构成的pair
    vector<long long>dis;
    Dijkstra(int k):n(k){
        g.resize(n+1);
        dis.resize(n+1,inf);
        //resize意义:如果n+1小于当前容器大小:保留,保留前n+1个元素,去除多余的值;
        //若n+1大于当前容器大小,在结尾插入一定数量的inf,使大小达标.
    }
    void add(int u,int v,long long w){
        g[u].emplace_back(v,w);     //加入u的出边
    }
    void solve(int s){
        vector<bool>vis(n+1);
        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
            //小根堆
        for(int i=1;i<=n;i++) dis[i]=inf;       //注意！再重新赋值一次
        dis[s]=0;
        q.push({0,s});
        while(!q.empty()){
            int u=q.top().second;       //q中存储<dis,u>对:u为点编号
            q.pop();
            if(vis[u]) continue;
            vis[u]=true;        //加入已访问的点集S
            for(auto [v,w]:g[u]){
                if(dis[v]>dis[u]+w) dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
};

//写法二：链式前向星实现
class Dijkstra2{
public:
    int n;
    vector<int>head;                //head[u]:点u的第一条出边编号
    vector<int>nxt;                 //nxt[i]:边i的下一条边编号
    vector<pair<int,long long>>to;  //(v,w)
    vector<long long>dis;
    Dijkstra2(int k):n(k){
        head.resize(n+1,-1);
        dis.resize(n+1,inf);
    }
    void add(int u,int v,long long w){
        int cnt=nxt.size();
        to.emplace_back(v,w);
        nxt.push_back(head[u]);
        head[u]=cnt;
    }
    void solve(int s){
        vector<bool>vis(n+1);
        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
        for(int i=1;i<=n;i++) dis[i]=inf;
        dis[s]=0;
        q.push({0,s});
        while(!q.empty()){
            int u=q.top().second;
            q.pop();
            if(vis[u]) continue;
            vis[u]=true;
            for(int i=head[u];i!=-1;i=nxt[i])       //遍历u的出边
            {
                auto [v,w]=to[i];
                if(dis[v]>dis[u]+w) dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
};
 
/*
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,s,x,y;      //n个点,m条边,s为源点
    long long t0,t;
    cin>>n>>m>>s>>t0;
    Dijkstra prob(n);
    for(int i=0;i<m;i++)
    {
        cin>>x>>y>>t;
        prob.add(x,y,t);        //无向图双向插入
        //prob.add(y,x,t);
    }
    prob.solve(s);
    
    //输出:1.不可到达的点;2.时间大于t0的点
    int cnt=0;
    vector<int>ans;
    for(int i=1;i<=n;i++)
    {
        if(prob.dis[i]==inf||prob.dis[i]>t0)
        {
            cnt++;
            ans.push_back(i);
        }
    }
    cout<< cnt<<'\n';
    for(auto i:ans) cout<<i<<' '<<(prob.dis[i]==inf?-1:prob.dis[i])<<'\n';
    return 0;
}*/

//变式:E4.D
//求出1到n,且经过点{p1,...,pk}中至少一点的最短路径.
/*
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;cin>>t;
    while(t--){
        int n,m,k;cin>>n>>m>>k;
        vector<int>mid(k);      //中间点集
        for(int i=0;i<k;i++) cin>>mid[i];
        
        Dijkstra d(n);
        for(int i=0;i<m;i++)
        {
            int x,y;long long w;
            cin>>x>>y>>w;
            d.add(x,y,w);
            d.add(y,x,w);
        }
        d.solve(1);         //求点1到所有点的最短距离
        vector<long long>d1(n+1);
        for(int i=1;i<=n;i++) d1[i]=d.dis[i];
        d.solve(n);         //求点n到所有点的最短距离
        long long ans=inf;
        //分别求点1,点n到以中间点集中每个点的距离之和
        for(int i=0;i<k;i++) ans=min(ans,d1[mid[i]]+d.dis[mid[i]]);
        cout<<(ans<inf?ans:-1)<<"\n";
    }
    return 0;
}
*/

4.所有点间的最短路问题--Floyd

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
#define N 305
#define M 100005
#define inf 1e18
int n,m,q;
long long dis[N][N];        //各顶点间最短距离
int u,v;
long long w;

void floyd(){       //O(V^3).
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++) dis[i][j]=inf;
        dis[i][i]=0;
    }
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        dis[u][v]=min(dis[u][v],w);
    }
    floyd();
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>u>>v;
        if(dis[u][v]>inf/2) cout<<"-1\n";
        else cout<<dis[u][v]<<"\n";
    }
    return 0;
}

5.拓扑排序

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include<algorithm>
#include<queue>

using namespace std;
//A
//拓扑排序(对有向无环图):
//1.定义队列L,放入所有入度为0的点;
//2.取队首节点s,删除所有以s为起点的边,更新终点的入度,为0时加入队列L;
//3.重复处理,直至队列L为空.

//法一：链式向前星储存图
/*
#define N 100005
#define M 400005
struct edge{        //链式向前星储存图
    int to,next,weight;        //to为:边的终点;next:下一条边编号
};
edge G[M];     //G[i]表示:编号为i的下一条边编号
int head[N];       //head[u]表示:以u为起点的第一条边编号
int weight[M];
int cnt;        //边编号
int din[N];    //点的入度

//加入边:链表头插法--将当前边插入当前起点的第一条出边
//每次为当前边分配新编号(++cnt);获取当前起点的第一条出边编号,让当前边指向该边,起点的第一条出边更新为当前边
void add(int u,int v,int w){    //(u,v)为有向边,w为权重
    G[++cnt].next=head[u];
    head[u]=cnt;
    G[cnt].to=v;
}

priority_queue<int,vector<int>, less<int>> L;       //拓扑序列(最大优先队列)--保证输出字典序最大的拓扑排序
//删除所有u的出边
void deleteEdge(int u){
    for(int i=head[u];i!=0;i=G[i].next)
    {
        din[G[i].to]--;         //终点入度-1
        if(din[G[i].to]==0) L.push(G[i].to);     //入度为0的点加入队列L
    }
}
int main(){
    int n,m,s,e;cin>>n>>m;      //n个点,m条有向边
    for(int i=0;i<m;i++)
    {
        cin>>s>>e;
        add(s,e,1);
        din[e]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(!din[i]) L.push(i);        //入度为0的点加入队列
    }
    
    while(!L.empty()){
        int cur=L.top();      //取队首元素
        L.pop();
        deleteEdge(cur);
        cout<<cur<<" ";
    }
    return 0;
}
*/

//法二：邻接表储存图
#define N 100005
#define M 400005
int n,m,din[N];
vector<int> e[M];
priority_queue<int> q;

int main(){
    int u,v;cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        e[u].push_back(v);
        din[v]+=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(din[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int u=q.top();q.pop();
        cout<<u<<" ";
        for(auto v:e[u])
        {
            din[v]-=1;
            if(din[v]==0) q.push(v);
        }
    }
    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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//顶点间有依赖关系,同一时间可平行访问多个顶点,求访问完所有顶点的最小时间.
//链式前向星实现:
/*
#define N 100005
#define M 200005
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
int head[N],nxt[M],to[M],cnt;   //head[u]:点u第一条出边编号; nxt[i]:边i的下一条边编号; to[i]:边i的终点
int inDegree[N];        //点i的入度
int fTime[N];           //fTime[u]:点u的完成时间
int n,m;

int q[N];       //队列

void addEdge(int u,int v){
    nxt[++cnt]=head[u];     //当前边的后继
    head[u]=cnt;            //更新u的第一条出边
    to[cnt]=v;
    inDegree[v]+=1;      //终点入度+=1.
}

void solve(){    //n个顶点,m条边
    for(int i=1;i<=n;i++) head[i]=inDegree[i]=fTime[i]=0;   //初始化
    //memset(head,0,n+1);memset(inDegree,0,n+1);memset(fTime,0,n+1);cnt=0;  //使用会TLE?
    //memset(nxt,0,m+1);memset(to,0,m+1);
    int u,v;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        addEdge(u,v);
    }
    
    int ans=0;cnt=0;
    
    queue<int> q;
    for(int i=1;i<=n;i++)       //加入入度为0的点
    {
        if(inDegree[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        fTime[x]+=1;    //队首点x,完成
        ans=max(ans,fTime[x]);
        for(int i=head[x];i!=0;i=nxt[i])    //遍历x的出边
        {
            fTime[to[i]]=max(fTime[to[i]],fTime[x]);
            if(--inDegree[to[i]]==0) q.push(to[i]);
        }
    }
    cout<<ans<<"\n";
}

int main(){
    int T;cin>>T;
    while(T--){
        cin>>n>>m;
        solve();
    }
    return 0;
}*/

//队列操作另一种写法:
/*
int front=1,rear=0;
for(int i=1;i<=n;i++)
{
    if(inDegree[i]==0) q[++rear]=i;
}
while(front<=rear)
{
    int x=q[front++];
    fTime[x]+=1;
    ans=max(ans,fTime[x]);
    for(int i=head[x];i!=0;i=nxt[i])    //遍历x的出边
    {
        fTime[to[i]]=max(fTime[to[i]],fTime[x]);
        if(--inDegree[to[i]]==0) q[++rear]=to[i];
    }
}
*/

6.最小生成树--Kruskal:O(m*logm)

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
#include <bits/stdc++.h>

using namespace std;

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]))); }
    inline bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            p[x] = y;
            return true;
        }
        return false;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        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';
    }
    return 0;
}

7.网络流--Dinic算法

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//Dinic算法:n点m边有向图,每条边有最大容量,求s到t的最大流
#include<queue>
#include<iostream>
using namespace std;

const long long inf=2005020600;
int n,m,s,t,u,v;
long long w,ans,dis[105];
int tot=1,now[105],head[105];

struct node {
    int to,net;
    long long val;
} e[10010];

inline void add(int u,int v,long long w) {
    e[++tot].to=v;
    e[tot].val=w;
    e[tot].net=head[u];
    head[u]=tot;
    
    e[++tot].to=u;
    e[tot].val=0;
    e[tot].net=head[v];
    head[v]=tot;
}

inline int bfs() {  //在残量网络中构造分层图
    for(int i=1;i<=n;i++) dis[i]=inf;
    queue<int> q;
    q.push(s);
    dis[s]=0;
    now[s]=head[s];
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].net) {
            int v=e[i].to;
            if(e[i].val>0&&dis[v]==inf) {
                q.push(v);
                now[v]=head[v];
                dis[v]=dis[x]+1;
                if(v==t) return 1;
            }
        }
    }
    return 0;
}

inline long long dfs(int x,long long sum) {  //sum是整条增广路对最大流的贡献
    if(x==t) return sum;
    long long k,res=0;  //k是当前最小的剩余容量
    for(int i=now[x];i&&sum;i=e[i].net) {
        now[x]=i;  //当前弧优化
        int v=e[i].to;
        if(e[i].val>0&&(dis[v]==dis[x]+1)) {
            k=dfs(v,min(sum,e[i].val));
            if(k==0) dis[v]=inf;  //剪枝，去掉增广完毕的点
            e[i].val-=k;
            e[i^1].val+=k;
            res+=k;  //res表示经过该点的所有流量和（相当于流出的总量）
            sum-=k;  //sum表示经过该点的剩余流量
        }
    }
    return res;
}

int main() {
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d",&n,&m,&s,&t);
        for(int i=1;i<=m;i++) {
            scanf("%d%d%lld",&u,&v,&w);
            add(u,v,w);
        }
        ans=0;
        while(bfs()) {
            ans+=dfs(s,inf);  //流量守恒（流入=流出）
        }
        printf("%lld\n",ans);
        tot=1;ans=0;
        for(int i=0;i<=n;i++) now[i]=head[i]=0;
    }
    return 0;
}

8.二分图匹配:O(n^3)

(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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

//无权二分图匹配--HK算法:DFS,若每次调用时,匹配成功,则匹配数+1;否则不变.
//总复杂度:O(mn).
int n;
class HK{
public:
    int n;
    vector<vector<int>> g;
    vector<int>match;
    vector<int>vis;
    HK(int _n):n(_n),g(_n+1),match(_n+1),vis(_n+1){}
    void add(int u,int v) {g[u].push_back(v);}
    
    bool find(int x){
        for(int i:g[x])         //遍历x所有出边的终点
        {
            if(!vis[i])
            {
                vis[i]=true;
                if(!match[i]||find(match[i]))
                    //若该点未匹配,进行匹配;
                    //若已匹配,递归该点左边匹配的点,看是否能换一个点匹配,若可以,返回匹配成功;否则,匹配失败.
                {
                    match[i]=x;        //match[y]=x表示:左边点x,匹配到右边点y.
                    return true;
                }
            }
        }
        return false;
    }
    int solve()
    {
        int res=0;
        for(int i=1;i<=n;i++)
        {
            fill(vis.begin(),vis.end(),false);
            if(find(i)) res+=1;
        }
        return res;
    }
};

struct{
    int first,second;
}male[405],female[405];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    HK k(n);
    for(int i=1;i<=n;i++) cin>>male[i].first;
    for(int i=1;i<=n;i++) cin>>male[i].second;
    for(int i=1;i<=n;i++) cin>>female[i].first;
    for(int i=1;i<=n;i++) cin>>female[i].second;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(male[i].first>=female[j].second&&female[j].first>=male[i].second) k.add(i,j);
        }
    }
    cout<<k.solve()<<endl;
    return 0;
}

(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
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//E5.D
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

#define ll long long
#define ul unsigned long long
#define pr pair<ll,ll>
#define MAX 250
#define inf 0x3f3f3f3f3f
using namespace std;

int n;          //两部各n个点的二分图
ll x,y;         //点坐标
pr from[MAX],to[MAX];       //记录左/右点坐标
int match[MAX];     //右点匹配的左点
int va[MAX],vb[MAX];    //标记点是否在交替路中
ll w[MAX][MAX];
ll la[MAX],lb[MAX];     //左/右顶标
ll slack[MAX];          //松弛数组

void init(){
    memset(w,0xbf,sizeof(w));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) w[i][j]=-abs(from[i].first-to[j].first)-abs(from[i].second-to[j].second);
    }
}

bool dfs(int x){
    va[x]=1;            //标记x在交替路中
    for(int y=1;y<=n;y++)           //遍历点x的所有边:可以据情况改动.
    {
        if(vb[y]) continue;
        ll t=la[x]+lb[y]-w[x][y];
        if(t==0)            //相等子图
        {
            vb[y]=1;            //标记y在交替路中
            if(match[y]==-1||dfs(match[y]))
            {
                match[y]=x;         //找到增广路,更新匹配
                return true;
            }
        }
        else slack[y]=min(slack[y],t);      //不在相等子图中,更新松弛数组
    }
    return false;
}

ll KM(){
    memset(match,-1,sizeof(match));         //初始化match[y]=-1:未匹配
    memset(lb,0,sizeof(lb));                //初始化右顶标为0.
    for(int i=1;i<=n;i++)           //初始化左顶标为与之相连边的最大权值
    {
        la[i]=-inf;
        for(int j=1;j<=n;j++) la[i]=max(la[i],w[i][j]);
    }
    for(int i=1;i<=n;i++)
    {
        memset(slack,0x3f,sizeof(slack));
        while(true)
        {
            memset(va,0,sizeof(va));
            memset(vb,0,sizeof(vb));
            if(dfs(i)) break;           //找到增广路,退出
            ll d=inf;
            for(int j=1;j<=n;j++)
            {
                if(!vb[j]) d=min(d,slack[j]);
            }
            for(int j=1;j<=n;j++)       //更新顶标
            {
                if(va[j]) la[j]-=d;     //S中的点,左顶标-d.
                if(vb[j]) lb[j]+=d;     //T中的点,右顶标+d.
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++) ans+=w[match[i]][i];
    return ans;
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>x>>y;
            from[i]=make_pair(x,y);
        }
        for(int i=1;i<=n;i++)
        {
            cin>>x>>y;
            to[i]=make_pair(x,y);
        }
        init();             //init()环节:计算权重矩阵
        cout<<-KM()<<endl;
    }
    return 0;
}

计算几何

1.判断三点是否共线(三维)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Point {  
    double x, y, z;  
};  
  
bool areThreePointsCollinear(struct Point p1, struct Point p2, struct Point p3) {  
    // 计算向量 v1 = p2 - p1, v2 = p3 - p2  
    struct Point v1 = {p2.x - p1.x, p2.y - p1.y, p2.z - p1.z};  
    struct Point v2 = {p3.x - p2.x, p3.y - p2.y, p3.z - p2.z};  
  
    // 计算向量叉积 v1 × v2，如果叉积为0，则三点共线  
    double crossProduct[3] = {v1.y * v2.z - v1.z * v2.y,  
                             v1.z * v2.x - v1.x * v2.z,  
                             v1.x * v2.y - v1.y * v2.x};  
  
    // 如果叉积的绝对值小于一个很小的值（例如 1e-9），则可以认为叉积为0  
    return fabs(crossProduct[0]) < 1e-9 && fabs(crossProduct[1]) < 1e-9 && fabs(crossProduct[2]) < 1e-9;  
}

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
32
33
34
35
36
37
38
39
40
41
42
43
44
typedef long long ll;
typedef struct{
    ll x,y;
}P;

ll direction(P pi,P pj,P pk){
    return (pk.x-pi.x)*(pj.y-pi.y)-(pj.x-pi.x)*(pk.y-pi.y);
}

bool on_Segment(P pi,P pj,P pk){        //pk是否在线段pipj上.
    if(min(pi.x,pj.x)<=pk.x&&pk.x<=max(pi.x,pj.x)&&min(pi.y,pj.y)<=pk.y&&pk.y<=max(pi.y,pj.y)) return true;
    else return false;
}

bool parallel(P p1,P p2,P p3,P p4){
    if((p2.y-p1.y)*(p4.x-p3.x)==(p4.y-p3.y)*(p2.x-p1.x)) return true;
    else return false;
}

void Segments_Intersect(P p1,P p2,P p3,P p4){       //判断线段p1p2和线段p3p4是否相交
    ll d1=direction(p3,p4,p1);
    ll d2=direction(p3,p4,p2);
    ll d3=direction(p1,p2,p3);
    ll d4=direction(p1,p2,p4);
    
    if(((d1>0&&d2<0)||(d1<0&&d2>0))&&((d3>0&&d4<0)||(d3<0&&d4>0))) cout<<"intersect\n";
    else if(d1==0&&on_Segment(p3,p4,p1)) cout<<"intersect\n";
    else if(d2==0&&on_Segment(p3,p4,p2)) cout<<"intersect\n";
    else if(d3==0&&on_Segment(p1,p2,p3)) cout<<"intersect\n";
    else if(d4==0&&on_Segment(p1,p2,p4)) cout<<"intersect\n";
    else if(parallel(p1,p2,p3,p4)) cout<<"parallel\n";
    else cout<<"neither\n";
}
P p1,q1,p2,q2;

int main(){
    int t;cin>>t;
    while(t--){
        cin>>p1.x>>p1.y>>q1.x>>q1.y;
        cin>>p2.x>>p2.y>>q2.x>>q2.y;
        Segments_Intersect(p1,q1,p2,q2);
    }
    return 0;
}

3.求点到线段最小距离

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
struct Pt{
    double x,y;
};

struct Segment{
    Pt p1,p2;
};
double getDis(Pt p1,Pt p2){
    return sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2));
}

double disToSegment(Pt p,Segment l){
    double len=getDis(l.p1, l.p2);
    if (len==0)
    {
        return getDis(p, l.p1);
    }
    double v = ((p.x - l.p1.x) * (l.p2.x - l.p1.x) + (p.y - l.p1.y) * (l.p2.y - l.p1.y)) / pow(len, 2);
    if (v <= 0)
    {
        return getDis(p, l.p1);
    }
    else if (v >= 1)
    {
        return getDis(p, l.p2);
    }
    else
    {
        Pt u={ l.p1.x+v*(l.p2.x-l.p1.x),l.p1.y+v*(l.p2.y-l.p1.y)};
        return getDis(p,u);
    }
}
double xa,ya,xp,yp,xq,yq;

int main() {
    int t;cin>>t;
    while(t--){
        cin>>xa>>ya>>xp>>yp>>xq>>yq;
        Pt p ={xa,ya};
        Segment l = {{xp,yp},{xq,yq}};
        printf("%.3f\n",disToSegment(p,l));
    }
    return 0;
}

4.求凸包面积

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

//E:计算凸包面积

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;

bool onleft(const Vec &a, const Vec &b) { return a * b < 0; }       //cross product
bool onright(const Vec &a, const Vec &b) { return a * b > 0; }

//Graham扫描算法求凸包点集:函数返回逆时针排列的点集.
// c0 - c1 - ... - ck (- c0), counter-clockwise
Polygon convex(Points p)
{
    int sz = p.size();
    sort(p.begin(), p.end(), [&](const Point &a, const Point &b) { return a.x != b.x ? a.x < b.x : a.y < b.y; });                   //先按x升序,再按y升序排列.
    Polygon c(p.size() + 1);
    int n = 0;
    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();
    int 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;
}

int n;
Points p;       //点集

void solve()
{
    scanf("%d", &n);
    p.resize(n);
    for (int i = 0; i < n; i++)
        p[i].read();        //依据函数void read(),读入两个数
    p = convex(p);
    long long r = areadb(p);
    printf("%lld.%lld\n", r / 2, (r & 1) * 5);      //保留1位小数
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        solve();
    return 0;
}

FFT

1.DFT模版--大数乘法

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include <cstring>
#define N (1<<18)+5        //超长整数位数
const double pi=acosl(-1.0);
using namespace std;

struct complex{
    double r,i;
    complex(){r=0;i=0;}
    complex(double re,double im){r=re;i=im;}
    double 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 * (double k,const complex &y){return complex(k*y.r,k*y.i);}
complex operator * (const complex &y,double k){return complex(k*y.r,k*y.i);}
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,double y){return complex(x.r/y,x.i/y);}
complex operator / (const complex &x,const complex &y){return x*y.bar()/y.len2();}
const double pi=acosl(-1.0);

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

void DFT(complex c[],int inv=0){            //由系数表达c,求点值表达v,重装回c中.
    for(int i=0;i<len;i++) v[rev[i]]=c[i];
        //c[0,2,...,2n-2]放在v[0,...,n-1];c[1,...,2n-3]放在v[n,...,2n-2].
    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)             //逆DFT:点值表达->系数表达
    {
        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 multiple(){
    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;}
    }
    //rev[0]=0,
    DFT(a);DFT(b);
    for(int i=0;i<len;i++) b[i]=a[i]*b[i];      //点值相乘
    DFT(b,1);
    for(int i=0;i<len;i++)
    {
        ans[i]+=round(b[i].r);
        ans[i+1]+=ans[i]/10;            //十进制数--10;八进制数,这两行改为8.
        ans[i]%=10;
    }
    while(len>1&&ans[len-1]==0) len-=1;
    for(int i=len-1;i>=0;i--) cout<<ans[i];
    cout<<"\n";
}
int main(){
    int T;cin>>T;
    while(T--) multiple();
    return 0;
}

2.逆DFT

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
//逆DFT:由点值表达->系数表达
vector<int> computeRev(int n){
    vector<int>rev(n);
    for(int i=0;i<n;i++)
    {
        rev[i]=0;
        int j,t;
        for(j=1,t=i;j<n;j<<=1,t>>=1) {rev[i]<<=1;rev[i]+=t&1;}
    }
    return rev;
}

vector<complex> inverseDFT(vector<complex>y,int n){
    vector<int>rev=computeRev(n);
    //for(int i=0;i<n;i++) cout<<rev[i]<<" ";
    //cout<<"\n";
    vector<complex> c(n);
    
    for(int i=0;i<n;i++) c[rev[i]]=y[i];
    for(int i=2;i<=n;i<<=1)
    {
        complex wn(cosl(2*pi/i),sinl(2*pi/i));
        for(int j=0;j<n;j+=i)
        {
            complex w(1,0);
            for(int k=0;k<(i>>1);k++)
            {
                complex x=c[j+k],y=c[j+k+(i>>1)]*w;
                c[j+k]=x+y;
                c[j+k+(i>>1)]=x-y;
                w=w*wn;
            }
        }
    }
    for(int i=0;i<n;i++) c[i]=c[i]/n;
    for(int i=1,j=n-1;i<j;i++,j--) swap(c[i],c[j]);
    return c;
}
int main(){
    int k;cin>>k;int n=pow(2,k);
    vector<complex> y(n);
    double a;
    for(int i=0;i<n;i++)
    {
        cin>>a;y[i]=complex(a,0);
    }
    vector<complex>c=inverseDFT(y,n);
    for(int i=0;i<n;i++)
    {
        if(abs(c[i].r-0)<0.005) c[i].r=0;       //四舍五入保留两位小数时,-0.00写作0.00.
        if(abs(c[i].i-0)<0.005) c[i].i=0;
        printf("%.2lf %.2lf\n",c[i].r,c[i].i);
    }
    return 0;
}

3.啰嗦的解释

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
//FFT:多项式乘法--两个次数界为n的多项式,theta(n*lgn)时间内完成乘法
//1.系数表达:(a0,a1,...,a(n-1)).霍纳法则:A(x0)=a0+x0(a1+x0(a2+...+x0(a(n-2)+x0*a(n-1))...))--theta(n)完成求值运算
//2.点值表达:n个点值对的集合{(x0,y0),...,(x(n-1),y(n-1))}.所有xk各不相同,满足:yk=A(xk).

//互逆运算:n个点的求值/插值运算
//由系数表达求点值表达:theta(n^2).
//插值(由点值表达求系数表达):

//(系数形式)多项式快速相乘:
//朴素算法:系数表达--theta(n^2)
//点值表达--theta(n)
//解释:要插值获得次数界为2n的多项式C,需2n个点值对.
//扩展A:{(x0,y0),...,(x(2n-1),y(2n-1))},扩展B:{(x0,y0'),...,(x(2n-1),y(2n-1)')}
//C:{(x0,y0*y0'),...,(x(2n-1),y(2n-1)*y(2n-1)')},基于C(xk)=A(xk)*B(xk).

//普通乘法:(a0,a1,...,a(n-1)),(b0,b1,...,b(n-1))->(c0,a1,...,c(2n-2))--theta(n^2).
//快速乘法:
//1.扩展为2n次:(a0,a1,...,a(n-1)),(b0,b1,...,b(n-1))->(a0,a1,...,a(n-1),0,...,0),(b0,b1,...,b(n-1),0,...,0)
//2,2n阶FFT计算2n阶点值表达:(A(w2n^0),...,A(w2n^(2n-1))),(B(w2n^0),...,B(w2n^(2n-1)))--theta(n*lgn).
//(精心选择的插值点:2n阶单位复根.
//3.点值乘法:得(C(w2n^0),...,C(w2n^(2n-1)))--theta(n).
//4.插值:对2n个点值计算其逆DFT,得(c0,c1,...,c(2n-2))--theta(n*lgn).

//DFT:y=DFTn(a)--计算n次多项式A(x)在wn^0,...,wn^(n-1)这n个n次单位复根处的值.
//结果:y=(y0,...,y(n-1)),其中:yk=A(wn^k).

//FFT:利用单位复根特殊性质，在theta(n*lgn)时间内，计算DFTn(a).（朴素算法：theta(n^2)）.

字符串

1.KMP

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include<vector>
using namespace std;

//3.KMP算法
//预处理时间:theta(m);匹配时间:theta(n).
//模式P的前缀函数:pi:{1,2,...,m}->{0,1,...,m-1}.满足:pi[q]=max{k:k<q且Pk是Pq的后缀}.
vector<int>prefix(string s){
    int m=(int)s.length();
    vector<int>pi(m);
    pi[0]=0;
    for(int i=1;i<m;i++)
    {
        int j=pi[i-1];
        while(j>0&&s[i]!=s[j]) j=pi[j-1];
        if(s[i]==s[j]) j++;
        pi[i]=j;
    }
    return pi;
}

void kmp(string T,string P){
    int n=(int)T.length(),m=(int)P.length();
    vector<int>pi=prefix(P);
    
    int q=0;
    for(int i=0;i<n;i++){
        while(q>0&&P[q]!=T[i]) q=pi[q];
        if(P[q]==T[i]) q+=1;
        if(q==m)
        {
            cout<<"Pattern occurs with shift "<<i-m;
            q=pi[q];
        }
    }
}

//判断长为i的前缀和后缀是否相同
//法一:求前缀数组
//从大到小考虑:字符串n为最大解;pi[n-1]为次大解;下一个解为pi[pi[n-1]-1].递推直至解为0,逆序输出
void solve(string &s){          //加引用:因为此处string不是全局变量
    vector<int>pi=prefix(s),ans;
    int x=s.length();
    while(x){
        ans.push_back(x);
        x=pi[x-1];
    }
    for_each(ans.rbegin(),ans.rend(),[](const int &x){cout<<x<<' ';});      //rbegin,rend为逆向迭代器
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;cin>>t;
    string s;
    while(t--){
        cin>>s;solve(s);
    }
    return 0;
}

//初始T为空，两操作二选一：在T后添加一个字母;选择T的一前缀T',连在T后.
//操作的最小次数.
int main(){
    int T;cin>>T;
    while(T--){
        string s;cin>>s;
        vector<int>pi=prefix(s);
        int n=(int)s.length(),cnt=0,q=0;
        int i=n-1;
        while(i>=0)
        {
            q=pi[i];
            while(2*q>i+1) q=pi[q-1];       //避免产生重叠.
            if(q==0) {cnt+=1;i-=1;}
            else {cnt+=1;i-=q;}
            //cout<<q<<" "<<i<<" "<<cnt<<endl;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

2.状态机

由字符串S构建的字符串匹配自动机共有n+1个状态，其中n为字符串S的长度。第i个状态表示接收到的字符串的最后i−1个字符（长度为i−1的后缀）恰能匹配S的前i−1个字符，第n+1个状态表示已经匹配上字符串S，为字符串匹配自动机的终态。 

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
void compute_Trans(string &s){
    int n=(int)s.length();
    vector<int>pi=prefix(s);
    int **Trans=(int **)malloc(sizeof(int *)*n);
    for(int i=0;i<n;i++) Trans[i]=(int *)malloc(sizeof(int)*10);
    
    for(int j=0;j<10;j++){
        if(s[0]=='a'+j) Trans[0][j]=1;
        else Trans[0][j]=0;
    }

    for(int i=1;i<n;i++){
        for(int j=0;j<10;j++){
            if(s[i]=='a'+j) {Trans[i][j]=i+1;continue;}
            int q=pi[i-1];
            while(q>0&&s[q]!='a'+j) q=pi[q-1];
            if(s[q]=='a'+j) Trans[i][j]=q+1;
            else Trans[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++) printf("%d ",Trans[i][j]);
        printf("\n");
    }
}

3.字符串映射

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
//建立双向映射的哈希表
#define N 100005
int n;
char s[N],t[N];

int main(){
    int T;cin>>T;
    while(T--){
        scanf("%d",&n);
        scanf("%s",s);scanf("%s",t);
        
        unordered_map<char,char>m1,m2;
        unordered_map<char,char>::iterator it1=m1.begin(),it2=m2.begin();
        int flag=0;
        for(int i=0;i<n;i++)
        {
            it1=m1.find(s[i]);it2=m2.find(t[i]);
            if(it1==m1.end()&&it2==m2.end())    //找不到
            {
                m1.insert(make_pair(s[i],t[i]));
                m2.insert(make_pair(t[i],s[i]));
            }
            else if(it1!=m1.end()&&it2==m2.end()) {flag=1;break;}
            else if(it1==m1.end()&&it2!=m2.end()) {flag=1;break;}
            else
            {
                if(it1->second!=t[i]||it2->second!=s[i]) {flag=1;break;}
            }
        }
        if(flag==0) printf("Yes\n");
        else printf("No\n");
        memset(s,'\0',sizeof(char)*n);
        memset(t,'\0',sizeof(char)*n);
    }
    return 0;
}

4.判断字符串是否相同--建立哈希映射

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
typedef long long ll;
#define N 100005
const int B=26,M=998244353;
int n;

void prepose(){
    for(int i=p[0]=1;i<N;i++) p[i]=(ll)p[i-1]*B%M;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //prepose();
    unordered_map<ll,pair<string,int>>map;
    unordered_map<ll,pair<string,int>>::iterator it=map.begin();
    cin>>n;
    string s;
    int maxsize=1;
    for(int i=0;i<n;i++){
        cin>>s;
        int m=(int)s.size();
        ll k=0;
        for(int j=0;j<m;j++) k=(k*B+s[j])%M;
        //cout<<k<<" ";
        it=map.find(k);
        if(it==map.end()) map.insert(make_pair(k,make_pair(s,1)));
        else{
            //cout<<s<<" "<<it->second.first;
            if(s!=it->second.first) map.insert(make_pair(k,make_pair(s,1)));
            else
            {
                it->second.second+=1;
                if(it->second.second>maxsize) maxsize=it->second.second;
            }
        }
        //cout<<map.size()<<" "<<maxsize<<endl;
    }
    cout<<map.size()<<" "<<maxsize;
    return 0;
}

5.1,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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//G--C,E结合的变式
//同一集合内字符串相似:
//1.对每个字符串的字符建立映射,哈希值与字符位置相关(设为m.size()+1),求整个字符串的哈希值;
//2.对所有字符串建立映射,每个字符串的哈希值由步骤1得出.
typedef long long ll;
#define N 100005
const int B=26,M=998244353;
int n;

ll Hash(string &s){
    map<char,int>m;
    map<char,int>::iterator it=m.begin();
    int len=(int)s.size();
    ll k=0;
    for(int j=0;j<len;j++){
        it=m.find(s[j]);
        if(it==m.end())
        {
            m.emplace(s[j],m.size()+1);
            k=(k*B+m.size())%M;
        }
        else k=(k*B+it->second)%M;
    }
    return k;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    unordered_map<ll,int>whole_map;
    unordered_map<ll,int>::iterator it1=whole_map.begin();
    cin>>n;int maxsize=1;
    string s;
    
    for(int i=0;i<n;i++){
        cin>>s;
        ll k=Hash(s);
        //cout<<k<<endl;
        it1=whole_map.find(k);
        if(it1==whole_map.end()) whole_map.insert(make_pair(k,1));
        else{
            it1->second+=1;
            if(it1->second>maxsize) maxsize=it1->second;
        }
    }
    cout<<whole_map.size()<<" "<<maxsize;
    return 0;
}

  1. logb(a)↩︎