目录

知识点归纳1.AcWing116. 飞行员兄弟 (POJ 2965) （dfs/位运算状态压缩）1.DFS2.位运算+二进制枚举2.AcWing.117. 占卜DIY （模拟）3.AcWing 118. 分形(POJ 2083)（递归/分形）4.AcWing 120. 防线（前缀和+二分判定）5.AcWing 121. 赶牛入圈(离散化 + 二维数组前缀和 + 二分查找)6.AcWing 123. 士兵（排序贪心）7.AcWing 125. 耍杂技的牛8.AcWing 126. 最大的和（贪心，一维前缀和）

声明：

本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，主要是因为我三本都买了按照《算法竞赛进阶指南》的目录顺序学习，包含书中的少部分重要知识点、例题解题报告及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（习题和代码可全都是我自己敲哒）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》——作者李煜东，强烈安利，好书不火系列，谢谢配合。

下方链接为学习笔记目录链接（中转站）

学习笔记目录链接

ACM-ICPC在线模板

知识点归纳

位运算

快速乘，快速幂，各种按位运算，二进制状态压缩；

枚举、模拟、递推

能想象问题的“状态空间”，理解各种算法本质是对状态空间进行遍历和映射

递归

理解递归的思想、子问题、递归边界、回溯时还原现场

分治思想

二分

整数集合二分，实数域二分

单峰函数三分求极值

二分答案，把求解转化为判定

排序

各种排序算法：数据结构基础

离散化

中位数相关问题

求第k大数的O(n)算法

归并排序求解逆序数对数

倍增

序列上的倍增算法及其应用

RMQ-ST算法

贪心

贪心的思想及其证明手段

多通过题目开拓视野，归纳总结

练习：

1.AcWing116. 飞行员兄弟 (POJ 2965) （dfs/位运算状态压缩）

题目链接：/problem/content/118/

1.DFS

正解应该是状态压缩，但是这里暴力dfs也能过。使用dfs主要是因为题目中如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。要求答案排序选顺序最小的输出，所以从0，0开始dfs这样得到的答案一定是按照题目要求最小的那一组

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<math.h>#include<stack>#include<vector>#define ls (p<<1)#define rs (p<<1|1)#define over(i,s,t) for(register int i=s;i<=t;++i)#define lver(i,t,s) for(register int i=t;i>=s;--i)//#define int __int128using namespace std;typedef pair<int,int> PII;typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！const int N=10;const ll mod=1e9+7;const double EPS=1e-5;//-10次方约等于趋近为0int n,m;char mp[N][N];vector<PII>tmp,ans;void turn_one(int x,int y){if(mp[x][y]=='+'){mp[x][y]='-';}else mp[x][y]='+';}void turn_all(int x,int y){over(i,0,3){turn_one(x,i);turn_one(i,y);}turn_one(x,y);//上面的xy多转了一次}void dfs(int x,int y){if(x==3&&y==4){//dfs必须上来就先判断边界bool flag=true;over(i,0,3)over(j,0,3){if(mp[i][j]=='+'){flag=false;goto hello;}}hello:;if(flag){//要先判空在size()if(ans.empty()||tmp.size()<ans.size()){ans=tmp;}}return;}if(y==4){x++,y=0;}//对于每个点分两种情况：turn或者不turn//turn：tmp.push_back({x,y});turn_all(x,y);dfs(x,y+1);tmp.pop_back();//回溯turn_all(x,y);//不turndfs(x,y+1);}int main(){over(i,0,3){scanf("%s",mp[i]);}dfs(0,0);printf("%d\n",ans.size());over(i,0,ans.size()-1){printf("%d %d\n",ans[i].first+1,ans[i].second+1);}return 0;}

2.位运算+二进制枚举

作者：

秦淮岸灯火阑珊

链接：

/solution/acwing/content/794/

算法标签：位运算+二进制枚举

解题思路：这道题目解题思路大致是，首先我们可以构造一个16位的二进制数，然后呢，二进制数的每一位代表4*4矩阵中的一位，例如1代表(1,1),2代表(1,2),3代表(1,3),4代表(1,4),5代表(2,1)。既然这样的话，那么我们只需要枚举这个16位的二进制数，就可以确定我们的方案，因为题目只需要最优解方案，所以时间复杂度大约是O(16 * 2^16)

2.AcWing.117. 占卜DIY （模拟）

输入样例：

8 5 A AK 5 3 29 6 0 63 4 3 43 4 4 55 6 7 68 7 7 79 9 8 89 0 0 0K J J JQ A Q KJ Q 2 2A K Q 2

输出样例：

9

模拟题。只要没有遇见K就一直移动牌

根据题意，每一张牌直接按照上面的数字放到第几堆里，以后就不会再变了，所以用sum数组记录有几张牌已归位。用val数组存当前这一堆牌还剩几张没有移位，移走一张牌实际上就是val[i]--。因为已经归位的牌是不会再动的了，所以不用放入vector里，不然就会WA。最后扫描一遍看有多少堆牌已归位，输出答案即可。

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<math.h>#include<stack>#include<vector>#define ls (p<<1)#define rs (p<<1|1)#define over(i,s,t) for(register int i=s;i<=t;++i)#define lver(i,t,s) for(register int i=t;i>=s;--i)//#define int __int128using namespace std;typedef pair<int,int> PII;typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！const int N=100007;const ll mod=1e9+7;const double EPS=1e-5;//-10次方约等于趋近为0vector<int>a[50];int n,m;int val[50],sum[50];void init(){over(i,1,13){a[i].push_back(0);val[i]=4;over(j,1,4){char ch;cin>>ch;if(ch=='0')a[i].push_back(10);else if(ch<='9'||ch>='2')a[i].push_back(ch-'0');else if(ch=='A')a[i].push_back(1);else if(ch=='J')a[i].push_back(11);else if(ch=='Q')a[i].push_back(12);else if(ch=='K')a[i].push_back(13);}}}int ans;int main(){init();over(i,1,4){int now=a[13][i];while(now!=13){sum[now]++;//数字为几就会跑到第几堆，不会再变了now=a[now][val[now]--];}}over(i,1,12){if(sum[i]==4)ans++;}printf("%d\n",ans);return 0;}

3.AcWing 118. 分形(POJ 2083)（递归/分形）

比较简单的分形，写这类的题的时候需要自己先画图，确定好递归的边界和下一个状态是如何转移过去的，注意递归其实是从大往小了走，这是递归的特性，所以对于一个大问题，直接利用递归将其分解来成为一个最小的子问题就好。

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<bitset>#include<vector>#include<unordered_map>#define ls (p<<1)#define rs (p<<1|1)#pragma GCC optimize (2)#pragma G++ optimize (2)#define over(i,s,t) for(register int i = s;i <= t;++i)#define lver(i,t,s) for(register int i = t;i >= s;--i)//#define int __int128#define lowbit(p) p&(-p)using namespace std;#undef midtypedef long long ll;typedef pair<int,int> PII;const int N = 1007;const ll mod = 1e9+7;const ll INF = 1e15+7;const double EPS = 1e-10;const int base = 131;int qpow(int a,int b){int res = 1;while(b){if(b&1)res = (res*a)%mod;a = (a*a)%mod;b>>=1;}return res%mod;}int mp[N][N];void solve(int n,int x,int y){if(n == 1){mp[x][y] = 1;return ;}int len = qpow(3,n-2);solve(n-1,x,y);solve(n-1,x+2*len,y);solve(n-1,x+len,y+len);solve(n-1,x,y+2*len);solve(n-1,x+2*len,y+2*len);}int n;int main(){while(~scanf("%d",&n)&&n != -1){memset(mp,0,sizeof mp);solve(n,1,1);over(i,1,qpow(3,n-1)){over(j,1,qpow(3,n-1)){if(mp[i][j])printf("X");else printf(" ");}puts("");}puts("-");}return 0;}

4.AcWing 120. 防线（前缀和+二分判定）

%%%

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<bitset>#include<limits.h>#include<unordered_map>#define ls (p<<1)#define rs (p<<1|1)#pragma GCC optimize (2)#pragma G++ optimize (2)#define over(i,s,t) for(register int i = s;i <= t;++i)#define lver(i,t,s) for(register int i = t;i >= s;--i)//#define int __int128using namespace std;#undef midtypedef long long ll;typedef pair<int,int> PII;const int N = 200007;const ll mod = 1e9+7;const ll INF = 1e15+7;const double EPS = 1e-10;const int base = 131;struct node{int s,e,d;}a[N];int t;int n,m;int get_sum(int x){//get前缀和int res = 0;over(i,1,n)if(a[i].s<=x)res += ( min(x,a[i].e) - a[i].s ) / a[i].d + 1;return res;}bool check(int l,int r){return (get_sum(r)-get_sum(l-1))&1;//判断是否为奇数}int main(){scanf("%d",&t);while(t--){int minn = 2147483647,maxx = -2147483647;scanf("%d",&n);over(i,1,n){scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].d);minn = min(minn,a[i].s);maxx = max(maxx,a[i].e);}if(!(get_sum(maxx)&1)){//如果总和都不是奇数，那一定没有printf("There's no weakness.\n");}else {int l = minn,r = maxx;while(l<r){int mid = (l+r)>>1;if(!check(l,mid))l = mid+1;//如果左边不是奇数，那奇数一定在右边else r = mid;}printf("%d %d\n",l,get_sum(l) - get_sum(l-1));//前缀和求这个点上的防具的个数（他们是x相同，y不同）}}return 0;}

5.AcWing 121. 赶牛入圈(离散化 + 二维数组前缀和 + 二分查找)

离散化 + 二维数组前缀和 + 二分查找优化到O(n2logn)O(n^2logn)O(n2logn)，勉强能过。

坐标的范围在1 ~10000，如果直接开二维数组遍历显然不现实，再看N的范围最大是500，那么我们就可以将坐标离散化后存在一个数组里，用这个数组来进行前缀和运算的操作，就会大大降低时间复杂度。

但要注意的是，这珠作死的草会在 1 × 1 的方格里，所以在算正方形边长的时候，需要在 x2 - x1 之后再加上一个单位长度，y1,y2同理（x1,y1,x2,y2是当前选取的正方形的左上角和右下角的坐标）。而在算边长的时候，需要查找离散化之前的坐标来进行运算。最后需要提的是，这珠草可以正好落在正方形边长上，所以在最后计算一个正方形范围内的草的数目的时候公式应该为 sum[x2][y2]−sum[x1−1][y2]−sum[x2][y1−1]+sum[x1−1][y1−1]sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]sum[x2][y2]−sum[x1−1][y2]−sum[x2][y1−1]+sum[x1−1][y1−1]

不同于之前的激光炸弹，激光炸弹因为不能算边界，所以不需要-1。

作者：逆乾 链接：/solution/AcWing/content/1091/

来源：AcWing

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<math.h>#include<bitset>#include<limits.h>#define ls (p<<1)#define rs (p<<1|1)#define mid (l+r>>1)#define over(i,s,t) for(register int i=s;i<=t;++i)#define lver(i,t,s) for(register int i=t;i>=s;--i)//#define int __int128using namespace std;#undef midtypedef long long ll;typedef unsigned long long ull;typedef pair<int,int> PII;const int N=1e3+7;const int mod=1e9+7;const ll INF=1e15+7;const double EPS=1e-10;const int p=131;//13331int n,m;int c;vector<PII>point;//存坐标vector<int>num;//离散化int sum[N][N];//二维前缀和int get_id(int x){//得离散化return lower_bound(num.begin(),num.end(),x)-num.begin();}bool check(int len){for(int x1=1,x2=1;x2<num.size();x2++){while(num[x2]-num[x1]+1>len)x1++;//一旦越界了就赶紧跟进for(int y1=1,y2=1;y2<num.size();y2++){while(num[y2]-num[y1]+1>len)y1++;if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]>=c)return false;}}return true;}int main(){cin>>c>>n;num.push_back(0);//先插入边界哨兵over(i,1,n){int x,y;scanf("%d%d",&x,&y);num.push_back(x);num.push_back(y);point.push_back({x,y});}sort(num.begin(),num.end());num.erase(unique(num.begin(),num.end()),num.end());//去重over(i,0,n-1){int x=get_id(point[i].first),y=get_id(point[i].second);sum[x][y]++;}//因为先插入的边界0，所以应该从1开始size-1结束over(i,1,num.size()-1)over(j,1,num.size()){//这里一单位的草占的是一个1x1的框sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];}int l=1,r=10000;while(l<r){int mid=l+r>>1;if(check(mid))l=mid+1;//如果小了。else r=mid;}printf("%d\n",r);return 0;}

6.AcWing 123. 士兵（排序贪心）

本题是要求x相邻，y是相等，的两个子问题，那么首先对于y相等求最短路径的问题，很明显是一个求中位数，直接求就行。那么下一个问题，要求x相邻，求最少的路径，我们将x排序，那么x最小的x1，移动到新位置以后还会是x1，最小的哪一个。而第二个x2的位置应该是x1+1，…xn就应该是x+n-1。

对x进行排序后,要求使得士兵全部相邻的最小移动次数.那么在移动前和移动后，士兵的相对位置是不变的.举例来说,记add为移动后的最左端的士兵的前一位置x[ 1 ] -> add + 1;x[ 2 ] -> add + 2;…x[ n ] -> add + n;转换一下x[ 1 ] - 1 -> add;x[ 2 ] - 2 -> add;…x[ n ] - n -> add;这就转化为了跟y轴一样的问题了

其实这里的-1或者-10都没差，因为求的是一个相对位置

然后求两次中位数即可。

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<bitset>#include<limits.h>#include<unordered_map>#define ls (p<<1)#define rs (p<<1|1)#pragma GCC optimize (2)#pragma G++ optimize (2)#define over(i,s,t) for(register int i = s;i <= t;++i)#define lver(i,t,s) for(register int i = t;i >= s;--i)//#define int __int128using namespace std;#undef midtypedef long long ll;typedef pair<int,int> PII;const int N = 10007;const ll mod = 1e9+7;const ll INF = 1e15+7;const double EPS = 1e-10;const int base = 131;int n,m;int x[N],y[N];int solve(int *A){sort(A+1,A+1+n);int mid = A[n+1>>1];int ans = 0;over(i,1,n){ans += abs(mid-A[i]);}return ans;}int main(){scanf("%d",&n);over(i,1,n)scanf("%d %d",&x[i],&y[i]);sort(x+1,x+1+n);over(i,1,n)x[i]-=i-100;//x[i]-=i-100;都行，主要是要一个相对等差1（相邻嘛）的递增数列，只要是等差为1即可，最后求中位数的时候会统一的int ans = solve(x) + solve(y);printf("%d\n",ans);return 0;}

7.AcWing 125. 耍杂技的牛

首先本题的贪心，对答案有影响的有两个因素，一个是强壮程度，一个是自身的重量，是他们的差联合对答案造成影响，因为要最小，那么我们可以试着按照他们的和排序，（类似国王游戏，题中是乘积关系，所以按照两个因素的乘积排序即可）这种题可以根据题意猜测贪心策略，这里就可以试一试加或者差。

具体贪心策列证明：/solution/AcWing/content/845/

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<bitset>#include<vector>#include<unordered_map>#define ls (p<<1)#define rs (p<<1|1)#pragma GCC optimize (2)#pragma G++ optimize (2)#define over(i,s,t) for(register int i = s;i <= t;++i)#define lver(i,t,s) for(register int i = t;i >= s;--i)//#define int __int128#define lowbit(p) p&(-p)using namespace std;#undef midtypedef long long ll;typedef pair<int,int> PII;const int N = 50007;const ll mod = 1e9+7;const ll INF = 1e15+7;const double EPS = 1e-10;const int base = 131;PII a[N];int n;int main(){scanf("%d",&n);over(i,1,n){int x,y;scanf("%d%d",&x,&y);a[i].first = x+y;a[i].second = y;}sort(a+1,a+1+n);int res = -mod,sum = 0;over(i,1,n){//对于每头牛来说，不能算上自己的重量。sum -= a[i].second;res = max(res,sum);sum += a[i].first;}printf("%d\n",res);return 0;}

8.AcWing 126. 最大的和（贪心，一维前缀和）

因为这道题是矩形，如果是正方形的话可以直接DP，二维的DP，一维存右下角的坐标，一维存正方形的长度，时间复杂度O(n2)O(n^2)O(n2)。但是本题是矩形，所以把问题先拆分成一维，这样就是一个求最大子序列和的问题，那么对于这个子问题，我们是采用贪心的做法，对于新的结点，我们看上一个的最优解是否大于零，若大于零直接加上新的数，若小于零则从0开始加上这个数最优。

那么把问题扩展到二维上，我们求竖向的每一列的前缀和，这样就直接把二维的矩阵转化为了上面的一维最小序列和的问题了。

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<queue>#include<bitset>#include<limits.h>#include<unordered_map>#define ls (p<<1)#define rs (p<<1|1)#define mid (l+r>>1)#pragma GCC optimize (2)#pragma G++ optimize (2)//ÊÖ¶¯¿ªO2#define over(i,s,t) for(register int i = s;i <= t;++i)#define lver(i,t,s) for(register int i = t;i >= s;--i)//#define int __int128using namespace std;#undef midtypedef long long ll;typedef unsigned long long ull;typedef pair<ll,int> PLI;const int N = 150;const ll mod = 1e9+7;const ll INF = 1e15+7;const double EPS = 1e-10;const int base = 131;int n,m;int sum[N][N];int main(){scanf("%d",&n);over(i,1,n)over(j,1,n){cin>>sum[i][j];sum[i][j] += sum[i-1][j];}int ans = -23333333;over(i,1,n)over(j,i,n){int last = 0;over(k,1,n){last = max(last,0) + sum[j][k] - sum[i-1][k];ans = max(ans,last);}}cout<<ans<<endl;return 0;}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧