蓝桥杯算法总结

ACWing算法基础课笔记

闲���无事，利用阿里云做了个图床，已经将图片全部上传了。

1. 基础算法

1. 排序

快速：选择一个数，让数组中比他小的靠左，比他大的靠右，然后在左边右边同样进行操作。注意边界问题。O(nlogn)

一般选择mid

= l+r+1 >> 1，因为是用dowhile，所以设置i和j都是l和r往外一个。当i= j 说明左边都小于a[mid]，右边都大于a[mid]了，然后对于左边和右边再进行quick_sort，但是要注意左边是l,i-1,右边是i,r

#includeusing namespace std;const int N = 1e6 + 10;int q[N];int n;void quick_sort(int q[],int l,int r){if(l>=r){return;}int x = q[(l+r+1)/2], i = l-1, j = r+1;//如果取左端点，则下面为q,l,j  q,j+1,r，如果取右端点,则下面为q,l,i-1  q,i,l （因为会出现***循环） while(ia>>b;vector A;for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');vector C;int r;C = p(A,b,r);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);cout>b>>w;        d[a][b] = min(d[a][b],w);    }    floyd();    while(q--){        int a,b;        cin>>a>>b;        if(d[a][b] > INF / 2) cout>w;        g[a][b] = g[b][a] = min(g[a][b],w);    }    int t = prim();    if(t == INF) coutb>>w;        edges[i] = {a,b,w};    }    sort(edges , edges + m);    for(int i = 1;i b;        add(a,b);    }    int res = 0;    for(int i =1; i > s[i];    for(int i = 1; i  V;    int cnt = 0;    //在读入vws的时候就直接把这个转换为01背包问题，那么cnt就是新的数量n。    //为什么能这么转换是因为将一个数量s的物品转换为n组数量为a[i]的物品后，对这些物品的选择与否能够数量为s的物品选择任意个的结果。    //如s = 10,则转化为由个数1,2,4,3变成的新的四组物品，这四组物品的vi分别为v,2v,4v,3v，wi分别为w,2w,4w,3w    //而新的四组物品的01背包问题，能够组成原始多重背包问题j~j-10v+10w的最大值    //比如7的时候的最大值，可以选择第1、2、3组,就可以构成7,    //比如5的时候的最大值，可以选择第1、3组。    //为什么任意的s能够由一个二进制的组构成，是因为第一项能够构成0~1，加上第二项能够构成2~3，也就是0~3,加上第三项能够构成4~7,也就是0~7，加上第k项能够构成c~c+2^k-1=s,而c一定是小于等于2^k，否则能够把c分解成2^k+c1，此时c1作为新的c。而c小于等于2^k,而除开c之前的数能够构成2^k-1，因此能够构成0~s的任意一个数（类似用二进制优化）    for(int i = 1; i > a >>b >> s;        int k = 1;        while(k  0){            cnt ++ ;            v[cnt] = a * s;            w[cnt] = b * s;        }    }    n = cnt;    for(int i = 1; i = v[i]; j --){            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);        }    }    cout  n >> V;    for(int i = 1; i > s[i];        for(int j = 1; j > v[i][j] >> w[i][j];        }    }    for(int i = 1; i = 0; j --){            for(int k = 1; k