记录代码。

1. 试除法求约数
2. 约数个数
3. 单链表
4. 并查集—路径压缩+大集并小集
5. 排序
6. 散列表—线性检测
7. 拓扑排序 思想
8. 生成树–kruskal—道路村村通
9. 链式向前星
10. 树的遍历----附加 有向边求树根
11. 最大子序列和
12. 拿不拿问题之—状态压缩
13. 多重背包
14. 匈牙利二分图(简)
15. 高精度乘法
16. 汉诺塔问题思想

汉诺塔问题思想

核心:考虑将左边n-1个盘子移动到中间
将第n个盘子移动到右边。
将中间n-1个盘子移动到右边
其中左边n-1个盘子移动到中间h和将中间n-1个盘子移动到右边，这两个操作又相当于一个子的汉诺塔问题，所以就继续套下去跑一遍

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
struct node
{
    int n;
    char a,b,c;
    node(int n1,char a1,char b1,char c1)
    {
        n=n1;a=a1;b=b1;c=c1;
    }
};
int main()
{
    stack<node> s;
    int n;
    cin>>n;
    s.push(node(n,'a','b','c'));
    while(!s.empty())
    {
        node t=s.top();
        s.pop();
        if(t.n==1)
        {
            printf("%c -> %c\n",t.a,t.c);
        }
        else
        {
            s.push(node(t.n-1,t.b,t.a,t.c));//移动(n-1)个从左到中
            s.push(node(1,t.a,t.b,t.c));//这个就是输出从a到c
            s.push(node(t.n-1,t.a,t.c,t.b));//在把(n-1)从中间移动到右边。（因为我们上面并没有真正的把n-1个盘子从左边放到中，所以，其实用a来表示就可以了。（不关心过程，只关心结果。））
        }
    }
    return 0;
} 

高精度乘法

关键有c--缓存
跟质因数一样，要把c清干净。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
/*
1230 *9
*/
vector<int> v1,v2,ans;

void cheng(vector<int> v1,int a)
{
    int c=0;
    for(int i=0;i<v1.size();i++)
    {
        c+=v1[i]*a;
        ans.push_back(c%10);
        c=c/10;
    }
    //把剩下多的位数放到后面
    while(c)
    {
        ans.push_back(c%10);
        c/=10;
    }

}
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    for(int i=s1.size()-1;i>=0;i--) v1.push_back(s1[i]-'0');
    //for(int i=s1.size()-1;i>=0;i-=4) v1.push_back(s1[i]*1000+s1[i+1]*100+s1[i+2]*10+s1[i+3]);

    cheng(v1,stoi(s2));
    //因为倒着的，所以要去掉前导零
    int pos=ans.size()-1;
    while(!ans[pos]&&pos!=0) pos--;//注意：不要越界。&&pos!=0
    for(int i=pos;i>=0;i--) printf("%d",ans[i]);



    system("pause");
    return 0;
}

匈牙利二分图(简)

bool find(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(e[x][i]&&!use[i])
        {
            use[i]=1;
            if(boy[i]==0||find(boy[i]))
            {
                boy[i]=x;
                return 1;
            }
        }
    }
    return 0;
}

多重背包

将c拆成多个2进制表示

        for(int k=1;k<=c;k*=2)//将所谓的k拆成2进制的形式
        {
            c-=k;
            g.push_back({k*a,k*b});
        }
        if(c>0) g.push_back({c*a,c*b});//和求质因子一样。考虑是否还有剩下

拿不拿问题之—状态压缩

      //枚举所有拿与不拿
        for(int i=0;i<(1<<15);i++)//---(1<<15)-1 就枚举了15个空位的所有分布情况
        {
            for(int j=0;j<15;j++)//
                if(i>>j&1)//判断是否拿。 
                    XXXX

最大子序列和

#include<bits/stdc++.h>
using namespace std;
const int INF =0x3f3f3f3f;
const int maxn=1e5+10;
//typedef long long ll;
/*
最长子序列和+输出区间

递归中 可以将很多值通过形参的形式 一代传一代，传到最底层。
但如果我们想将底层的很多值进行保存返回给上层，可以结构体“打包”

//arr[mid]而不是arr[l]开始的原因是，我们以mid为中点，试探的求中间的最大值是多少。
*/
int a[maxn];
int n;
int ll,rr;
struct node
{
    int ans,l,r;
    node(){}
    node(int a,int b,int c) {ans=a,l=b,r=c;}
}e[maxn];

node q_sort(int arr[],int l,int r)
{
    if(l>=r) {return node(arr[l],l,r);}
    int mid=l+r>>1;
    node lans=q_sort(arr,l,mid);
    node rans=q_sort(arr,mid+1,r);

    //求左边---倒着遍历的原因
    int sum=0,lmax=arr[mid],rmax=arr[mid+1];
    for(int i=mid;i>=1;i--){sum+=arr[i];if(sum>=lmax) lmax=sum,ll=i;}//根据错误点2 所以要加上等于号。

    sum=0;//求右边
    for(int i=mid+1;i<=r;i++) {sum+=arr[i];if(sum>=rmax) rmax=sum,rr=i;}//根据错误点2 所以要加上等于号。
    int ans=lmax+rmax;

    //比较法
    node t=node(ans,ll,rr);
    if(lans.ans>=ans) {t=lans;}//可以这样，但return不行
    if(rans.ans>=ans) {t=rans;}
    return t;
}
int main()
{
    cin>>n;
    int f=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
        if(a[i]>=0) f=1;
    }
    ll=1,rr=n;
    node t=q_sort(a,1,n);
    if(f) cout<<t.ans<<" "<<a[t.l]<<" "<<a[t.r]<<endl; else cout<<0<<" "<<a[1]<<" "<<a[n]<<endl;
    return 0;
}
/*
错误点1--题目每理解清楚
6
-1 -2 0 -3 -4 -5
ans:0 0 0

错误点2---0也要加进去
8
-2 0 1 2 3 4 0 -3
ans:10 0 4 ---考虑0的情况
*/

树的遍历----附加 有向边求树根

对链式向前星里的每个点一直递到最深处。

void dfs(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        ll v=e[i];
        if(v==fa) continue;//注意，特判掉回父节点
        dfs(v,u);
    }
}

求树根

int st[maxn],root=1;
    for(int i=1;i<n;i++)
    {
        scanf("%d %d",&v,&u);
        add(u,v);
        st[v]=1; //就是入度
    }

    while(st[root]) root++;//根据性质，入度为0的点就是根节点

链式向前星

//一开始头结点都是-1
void add(int u,int v,int w)//相当于链接表，不断更新头结点。旧的头结点向下移。 
{
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];//我链式u 的下一个指向就是当前的头结点,所以是head[u]；
    head[u]=cnt++;//更新当前的cnt是链式u的头节点。
}

或者

int e[maxn<<1],w[maxn<<1],ne[maxn<<1],h[maxn<<1],cnt=0;
void add(int u,int v,int w)
{
    e[cnt]=v,w[cnt]=w,ne[cnt]=h[u],h[u]=cnt++;
}

遍历
for(int i=h[u];i!=-1;i=ne[i])
{
    int v=e[i];//以h[u]为头节点的链表。for循环是告诉你下个节点是在e数组中第i个位置。所以下一个节点v是=e[i];
    if(v==fa) continue ;
    .......
}

生成树–kruskal—道路村村通

#include<bits/stdc++.h>
using namespace std;
const int maxn =1e6+10;
struct node
{
    int from,to,cost;
    friend bool operator<(const node &a,const node &b)
    {
        return a.cost<b.cost;
    }
} e[maxn];
int N,E;
int f[maxn];
//====================使用kruskal
int find(int x)
{
    return f[x]<0?x:f[x]=find(f[x]);
}
void union1(int a,int b)
{
    int x=find(a),y=find(b);
    if(x==y) return;
    f[x]=y;
}

int kruskal()
{
    //直接建树。
    int sum=0;
    int cnt=0;//边的个数
    for(int i=0;i<E;i++)
    {
        if(find(e[i].from)!=find(e[i].to))
        {
            cnt++;
            //============================就是一个累加和合并==============
            sum+=e[i].cost;
            union1(e[i].from,e[i].to);
            //============================就是一个累加和合并==============
        }
    }
    if(cnt<N-1) return -1;
    return sum;
}
int main()
{
    memset(f,-1,sizeof f);
    cin>>N>>E;
    for(int i=0;i<E;i++)
    {
        cin>>e[i].from>>e[i].to>>e[i].cost;
    }
    sort(e,e+E);
    cout<<kruskal()<<endl;
    system("pause");
    return 0;
}

拓扑排序 思想

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
/*
第一步邻接矩阵，维护入度。入度为0的点就可以做起点。
第二步拓扑排序，用队列来维护起点，做广搜。--（）
*/
int g[110][110];
int d[maxn],t[maxn];
int n,m;
int ans=-1;
//=======================================核心部分
int topu()
{
    //总是从0开始。
    int u,v;
    int cnt=0;
    queue<int> q;
    for(int i=0;i<n;i++)
    {
        if(d[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        u=q.front(),q.pop();
        cnt++;
        for(v=0;v<n;v++)
        {
            if(g[u][v]!=INF)//因为0可能有用，所有INF作为不存在的边。
            {
                d[v]--;//入度--
                if(d[v]==0) q.push(v);
                t[v]=max(t[v],t[u]+g[u][v]);//该节点的最早开始时间
                ans=max(ans,t[v]);//我们不知道谁是终点，但我们知道，终点的时间一定是最长的。
            }
        }
    }
    return cnt;
}
//=======================================核心部分
int main()
{
    cin>>n>>m;
    int x,y,z;
    memset(g,INF,sizeof g);
    for(int i=0;i<m;i++)
    {
        cin>>x>>y>>z;
        g[x][y]=z;
        d[y]++;
    }
    int cnt=topu();
    if(cnt==n) printf("%d\n",ans); else puts("Impossible");

    return 0;
}

散列表—线性检测

#include <bits/stdc++.h>
using namespace std;
/*
难度在哪些地方？
获得一个p大小整型数组的首地址
线性检测。核心部分
平方检测：如何退出死循环？---步长大于表长的一半  kase>p/2
*/
int vis[200010];//散列确实不要用静态，用动态。
int main()
{
    int t, k, n, p;//m映射表长度
    int *hash =new int[p];//获得一个p大小整型数组的首地址
    memset(hash,0,sizeof(int)*p);
    cin>>n>>p;
    for(int i=0;i<n;i++)
    {
        cin>>k;

        //==================核心
        t=k%p;
        while(hash[t]&&hash[t]!=k)//---hash[t]!=k 判重
        //比如7 7  如果不加hash[t]!=k  就会出现对应两个的情况。
        {
            t=(t+1)%p;
        }
        hash[t]=k;
        //=================核心

        i==0?printf("%d",t):printf(" %d",t);
    }
    system("pause");
    return 0;
}

排序

#include<bits/stdc++.h>
using namespace std;
//插入类排序 
void insert_sort(int a[],int n); //简单插入排序 O(n^2)
void shell_sort(int a[],int n);//希尔排序  消去不止一个逆序对

//选择类排序 
void select_sort(int a[],int n);//简单选择排序  O(n^2)
void percdown(int a[],int i,int n);
void heap_sort(int a[],int n);//堆排序  O(nlogn)

//交换类排序 
void bubble_sort(int a[],int n);//冒泡排序  O(n^2)
int Median3(int a[],int l,int h);
void quick_sort( int A[], int left, int right);//快速排序  O(nlogn)

//归并排序 
void merge_sort(int a[],int n); 

//直接插入排序
void insert_sort(int a[],int n) { // //简单插入排序，稳定, O(n^2)
    int i,j,t;
    for(i=1; i<n; i++) { //从第2张牌开始
        t = a[i];   // 摸一张牌
        for(j = i; j>=1 && a[j-1] > t; j--) { //找插入位置
            a[j] = a[j-1]; //移出空位,只消去一个逆序对
        }
        a[j] = t; //新牌落位
    }
}
//希尔排序---对直接插入排序改进---最坏还是O(N^2)
void shell_sort(int a[],int n) { //希尔排序，不稳定
    int d,j,i,t;
    for(d=n/2; d>=1; d/=2) { //d间隔
        for(i=d; i<n; i++) {
            t=a[i];
            for(j=i; j>=d && a[j-d]>t; j-=d) {
                a[j]=a[j-d];//消去多个逆序对
            }
            a[j]=t;
        } // 结束一趟插入排序
    }
}


void select_sort(int a[],int n) {//简单选择排序 O(n^2)
    int i,j,min;
    for(i=0; i<n-1; i++) {
        min = i;  //记录最小数的位置，假设
        for(j=i+1; j<n; j++) { //从其后中找最小的
            if(a[j] < a[min])  min = j;  //更新min，记录最小数的位置
        }
        swap(a[i],a[min]);//不稳定
    }
}//没有保留必要的比较信息

//堆的筛选
void percdown(int a[],int i,int n) {
    int parent,child,t;
    t=a[i];

    for(parent = i; 2*parent+1<n; parent = child) { //O(logn)
        child = 2*parent+1;//-----------------------------------------------------为什么要+1，不是很懂
        if(child != n-1 && a[child] < a[child+1]) child++; //child指向较大孩子编号
        if(a[child]<t)
            break;
        else
            a[parent] = a[child]; //大孩子向上渗透
    }
    a[parent] = t;
}
//堆排序---对简单选择排序改进
void heap_sort(int a[],int n) { //O(nlogn)
    int i;
    for(i=n/2; i>=0; i--)    //建堆O(n)
        percdown(a,i,n);

    for(i=n-1; i>0; i--) {
        swap(a[i],a[0]); //a[0]即为堆顶，最大，将a[0]与当前堆的最后一个元素a[i]换位 
        percdown(a,0,i); // 将有i个元素的新堆从根结点向下过滤调整
    }
}


void bubble_sort(int a[],int n) {//冒泡排序 ,稳定，O(n^2)
    int i,j;
    for(i=n-1; i>0; i--) {
        int flag = 0;   //优化,标记该次循环中是否发生交换，若无，则说明整个序列有序
        for(j=0; j<i; j++) {
            if(a[j]>a[j+1]) {
                flag = 1;
                swap(a[j],a[j+1]); //只消去一个逆序对
            }
        }
        if(flag == 0) break;
    }
}

//求中位数
int Median3(int a[],int l,int h) {
    int mid = (l+h)/2;
    if(a[l] > a[mid]) swap(a[l],a[mid]);
    if(a[l] > a[h]) swap(a[l],a[h]);
    if(a[mid] > a[h]) swap(a[mid],a[h]);
    swap(a[mid],a[h-1]);
    return a[h-1];
}
//快速排序---对冒泡排序改进  （分治法）
void quick_sort( int A[], int left, int right ) {
    int i,j;
    int Cutoff=10, Pivot;
    if ( Cutoff <= right-left ) {
        Pivot = Median3( A, left, right );
        i = left;
        j = right-1;
        for( ; ; ) { //将序列中比基准小的移到基准左边，大的移到右边
            while ( A[ ++i ] < Pivot ) { }
            while ( A[ --j ] > Pivot ) { }
            if ( i < j )
                swap( A[i], A[j] );  //消去多个逆序对
            else break;
        }
        swap( A[i], A[ right-1 ] );

        quick_sort( A, left, i-1 );  //递归求解左边序列
        quick_sort( A, i+1, right ); //递归求解右边序列
    } else
        insert_sort( A+left, right-left+1 );
}
/* 
void quicksort(int r[],int low,int high) { //快速排序
    int Pivot = r[low];
    int left = low, right = high;
    if ( low >= high ) return;
    swap ( &r[low], &r[right] ); //将基准与最后一个元素交换

    while (1) {   //将序列中比基准小的移到基准左边，大的移到右边
        while ( (low < high) && (Pivot  >=  r[low]) )  low++ ;
        while ( (low < high) && (Pivot  <=  r[high]) ) high-- ;
        if ( low < high )   swap ( &r[low], &r[high] ) ;
        else  break;
    }
    swap ( &r[low], &r[right] ) ; // 将最后的基准换到正确的位置
    quicksort ( r, left, low - 1 ) ;
    quicksort ( r, low + 1, right ) ;
}
*/

void merge(int a[],int t[],int l,int r,int end) {
    int lend = r-1;
    int tmp=l;
    int num = (end-l+1);
    while(l<=lend && r<=end) {
        if(a[l]<=a[r])  t[tmp++]=a[l++];
        else            t[tmp++]=a[r++];
    }
    while(l<=lend)      t[tmp++]=a[l++];
    while(r<=end)       t[tmp++]=a[r++];

    for(int i=0; i<num; i++,end--)
        a[end] = t[end];
}
void msort(int a[],int t[],int l,int end) {
    int mid;
    if(l<end) {
        mid = (end+l)/2;
        msort(a,t,l,mid);
        msort(a,t,mid+1,end);
        merge(a,t,l,mid+1,end);
    }
}
//归并排序---分治法   时间复杂度O(nlogn) 
void merge_sort(int a[],int n) {
    int * t = new int[n]; // 额外的辅助数组---存储中间排序结果，空间复杂度O(n)
    if(t) {
        msort(a,t,0,n-1);
        delete t;
    }
}
int a[100000],i,n;
int main() {
    cin>>n;
    for(i=0; i<n; i++)
        cin>>a[i];
    merge_sort(a,n);
    for(i=0; i<n; i++)
        i==0?cout<<a[i]:cout<<" "<<a[i];
    return 0;
}

并查集—路径压缩+大集并小集

int find(int x) {return f[x]<0?x:f[x]= find(f[x]);}//--非常熟练
f[x]+=f[y];f[y]=x;//--顺序不能错。
memset(f,-1,sizeof f);//--初始化-1    都是根节点。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e6+10;
const int INF=0x3f3f3f3f;
const int P=1e9+7;
int n,m;
int x,k;
string op;
int a,b;
int f[maxn];
int find(int x) {return f[x]<0?x:f[x]= find(f[x]);}//--重要
void union1(int a,int b)
{
    int x=find(a),y=find(b);
    if(x==y) return ;
    if(f[x]<f[y])//x多
    {
        f[x]+=f[y];f[y]=x;//--顺序重要
    }
    else
    {
        f[y]+=f[x];f[x]=y;
    }
}
int main()
{
    memset(f,-1,sizeof f);//--重要
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>op;
        if(op=="M")
        {
            cin>>a>>b;
            union1(a,b);
        }
        else
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;else cout<<"No"<<endl;
        }
    }

    system("pause");
    return 0;   
}

单链表

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e6+10;
const int INF=0x3f3f3f3f;
int n,m;
int head,e[maxn],ne[maxn],idx;
//=======================================核心部分
void init() {head=-1,idx=0;}
void head_add(int x){e[idx]=x,ne[idx]=head;head=idx++;}
void add(int k,int x) {e[idx]=x;ne[idx]=ne[k],ne[k]=idx++;}
void del(int k) {ne[k]=ne[ne[k]];}
//=======================================核心部分
char op,x,k;
int main()
{
    init();
    cin>>n;
    while(n--)
    {
        cin>>op;
        if(op=='H')
        {
            cin>>x;
            head_add(x);
        }
        if(op=='I')
        {
            cin>>k>>x;
            add(k-1,x);//if(k==0)那么就是特判用head_add()函数了。 k就是数组的位子-代表第k时出现。
        }
        if(op=='D')
        {
            cin>>k;
            if(!k) head=ne[head]; 
            else del(k-1);
        }
    }
    for(int i=head;i!=-1;i=ne[i]) cout<< e[i]<<" ";
    puts("");
    system("pause");
    return 0;   
}

约数个数

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int MOD=1e9+7;
//struct node
//{
//  int a;
//  int b; 
//}e[maxn];
//似乎用map更方便 
map<int,int> mp; 
int main()
{
    vector<int>v;
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        //求质因数。
//=======================================核心部分
        for(int i=2;i<=n/i;i++)--从2开始。(心说)
        {
            if(n%i==0)
            {
                int cnt=0;
                while(n%i==0)
                {
                    cnt++;
                    n=n/i;
                }
                mp[i]+=cnt;
            }
        }
        if(n>1) mp[n]++;
    }
//=======================================核心部分
    long long ans=1;
    for(auto it:mp)//返回的不是地址？ 
    {
        ans=ans*( it.second +1)%MOD;
    }
    printf("%lld\n",ans);
    return 0;
}

试除法求约数

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int ans=1e6;//他的倍数 
const int eps =1e-8;
int n,m;
//=======================================核心部分
vector<int > fun(int n)
{
    vector<int> v;
    for(int i=1;i<=n/i;i++)
    {
        if(n%i==0)
        {
            v.push_back(i);
            if(i!=n/i) v.push_back(n/i);
        }
    }
    sort(v.begin(),v.end());
    return v;
}
//=======================================
int main()
{
    vector<int>v;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        v=fun(n);
        for(int i=0;i<v.size();i++)
        {
            printf("%d ",v[i]);
        }
        puts("");
    }   
    return 0;
}

小细节

每次一个程序跑完记得及时清空。—离散化的时候忘记对bk数组初始化，导致结果出现错误。

体会

1. 树状数组可以用来求前n及“下”的和，配合前缀和思想，可以实现快速区间查询。
   1. 树状数组也支持单点修改，区间修改。
   2. 经典应用就是求逆序对。----求小于i的个数有多少个，树状数组一建就知道O(1)的查询。然后当前个数-小于i的个数-1就是逆序对个数。
   3. 注意：由于lowbit的缘故，pos是不能为0的。所以下标都是从1开始