0x01 位运算

移位运算

左移

        在二进制表示下把数字向左移动，低位以0填充，高位越界后舍弃

                                        

算术右移

        在二进制补码表示下把数字同时向右移动，高位以符号位填充，低位越界后舍弃。

                                                

算术右移等于除以2向下取整，( - 3 ) >> 1 = - 2  ,  3  >>  1 = 1。

整数/2在C++中实现为除以2向0取整，-3/2=-1，3/2=1。

逻辑右移

        在二进制补码表示下把数字同时向右移动，高位以0填充，低位越界后要舍弃。

89. a^b - AcWing题库

 

//while
#include<bits/stdc++.h>
signed main()
{long long a,b,p;//求a的b次方模pstd::cin>>a>>b>>p;long long res=1;while(b){if(b&1) res=a*res%p;b=b>>1;a=a*a%p;}std::cout<<res%p;return 0;
}
//for
#include<bits/stdc++.h>
const int N=1e5+10;
using ll=long long;
ll pow(int a,int b,int p)
{ll ans=1%p;//必须要写成1%p，当p为0时，结果应该为0for(;b;b>>=1){if(b&1) ans=(ll)ans*a%p;a=(ll)a*a%p; }return ans;
}
signed main()
{int a,b,p;std::cin>>a>>b>>p;std::cout<<pow(a,b,p)<<'\n';return 0;
} 

 90. 64位整数乘法 - AcWing题库

//while
#include<bits/stdc++.h>
signed main()
{long long a,b,p;std::cin>>a>>b>>p;long long res=0;while(b){if(b&1)  res=(res+a)%p;b=b>>1;a=a*2%p;}std::cout<<res%p;return 0;
}
//for
#include<bits/stdc++.h>
const int N=1e5+10;
using ll=long long;
ll pow(ll a,ll b,ll p)//a*b%p
{ll ans=0;for(;b;b>>=1){if(b&1) ans=(ll)(ans+a)%p;a=(ll)a*2%p; }return ans;
}
signed main()
{ll a,b,p;std::cin>>a>>b>>p;std::cout<<pow(a,b,p)<<'\n';return 0;
} 

二进制状态压缩

        二进制状态压缩，是指将一个长度为m的bool数组用一个 m 位二进制整数表示并存储的方法。可以直接利用C++ STL 提供的 bitset 实现。

998. 起床困难综合症 - AcWing题库

 给定n组操作，确定操作数x属于[0,m]，使得操作之后得到的数字最大

操作之后得到的数字的第n位只与操作数的第n位和每次操作的数字的第n位所决定。因此枚举位数，29-0，判断这一位取0更大还是1更大。用cal函数计算这一位取x时，得到的结果是几，cal函数遍历这n次操作，每次将x与第n次的操作数的第bit位进行对应运算。

#include<bits/stdc++.h>
const int N=1e5+10;
typedef std::pair<std::string,int> PII;
PII a[N];int n,m;
int cal(int bit,int x)
{for(int i=1;i<=n;i++)//将n组操作数的每一个第bit位的数字与x做运算 {int h=a[i].second>>bit&1;if(a[i].first=="AND") x&=h;else if(a[i].first=="OR") x|=h;else x^=h;	}	return x;
}
signed main()
{std::cin>>n>>m;for(int i=1;i<=n;i++){std::string s;int x;std::cin>>s>>x;a[i]={s,x}; }int ans=0,val=0;//得到的操作数字的第n位的大小只与x的第n位和 for(int i=29;i>=0;i--){int res0=cal(i,0);//当前位置是0时，这一位得到的结果是多少int res1=cal(i,1);if(res1>res0&&val+(1<<i)<=m){val+=1<<i;ans+=res1<<i;}else{ans+=res0<<i;}} std::cout<<ans<<'\n';return 0;
} 

0x02递推与递归

递推

92. 递归实现指数型枚举 - AcWing题库

#include<bits/stdc++.h>
int n;
std::vector<int> v;
void dfs(int x)
{if(x==n+1){for(auto i :v){std::cout<<i<<" ";}std::cout<<'\n';return ;}//选择这个数v.push_back(x);dfs(x+1);v.pop_back();dfs(x+1);
}
signed main()
{std::cin>>n;dfs(1);return 0;
}

93. 递归实现组合型枚举 - AcWing题库

#include<bits/stdc++.h>
const int N=1e5+10;
using ll=long long;
//从n个数中选m个
//相比于前面的指数型枚举，从n个数中随机选任意个，组合型枚举规定了要选择m个
//因此前面加上剪枝，当前选择数>m 或者 剩下的不够凑成m个 就返回，就能保证最后会选择m个
int n,m;
std::vector<int> v; 
void dfs(int x)
{if(v.size()>m || v.size()+n-x+1<m) return ;if(x==n+1) {for(auto i:v){std::cout<<i<<" ";}std::cout<<'\n';return ;}v.push_back(x);dfs(x+1);v.pop_back();dfs(x+1);
} 
signed main()
{std::cin>>n>>m;dfs(1);return 0;
} 

94. 递归实现排列型枚举 - AcWing题库

#include<bits/stdc++.h>
const int N=1e5+10;
using ll=long long;
//n个数所有的排列 
int n;
int a[15];//这个位置上选什么 
bool st[15]; //这个数是否被使用 
void dfs(int x)//枚举位置 
{if(x==n+1) {for(int i=1;i<=n;i++){std::cout<<a[i]<<" ";}std::cout<<'\n';return ; }for(int i=1;i<=n;i++){if(st[i]) continue;st[i]=true;a[x]=i;dfs(x+1);st[i]=false;}	
} 
signed main()
{std::cin>>n;dfs(1);return 0;
} 

95. 费解的开关 - AcWing题库

#include<bits/stdc++.h>
const int N=10;
char g[N][N],backup[N][N];
int dx[]={0,1,0,-1,0};
int dy[]={0,0,-1,0,1};
void turn(int x,int y)
{for(int i=0;i<5;i++){int a=x+dx[i],b=y+dy[i];if(a<0||b<0||a>=5||b>=5) continue;g[a][b]^=1;}
}
void solve()
{for(int i=0;i<5;i++) std::cin>>g[i];int res=1e9;for(int op=0;op<32;op++)//2e5=32{memcpy(backup,g,sizeof g);int step=0;for(int i=0;i<5;i++)//第一层{if((op>>i)&1){turn(0,i);step++;}}for(int i=0;i<4;i++)//对0-3，也就是前四层顺着操作{for(int j=0;j<5;j++){if(g[i][j]=='0'){step++;turn(i+1,j);}}}bool dark=false;for(int i=0;i<5;i++){if(g[4][i]=='0'){dark=true;break;}}memcpy(g,backup,sizeof g);if(!dark) res=std::min(res,step);}if(res>6) res=-1;std::cout<<res<<'\n';
}
signed main()
{int t;std::cin>>t;while(t--){solve();}return 0;
}

96. 奇怪的汉诺塔 - AcWing题库

#include<bits/stdc++.h>
const int N =20;
int d[N],f[N];
signed main()
{d[1]=1;for(int i=2;i<=12;i++)d[i]=2*d[i-1]+1;memset(f,0x3f,sizeof f);f[1]=1;for(int i=2;i<=12;i++)for(int j=1;j<i;j++) f[i]=std::min(f[j]*2+d[i-j],f[i]);for(int i=1;i<=12;i++)std::cout<<f[i]<<'\n';return 0;
}

分治

分治法是把一个问题划分成若干个规模更小的同类问题，对这些子问题递归求解，然后在回溯时通过它们推导出原问题的解。

 97. 约数之和 - AcWing题库

 

先复习867. 分解质因数 - AcWing题库 

算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。

 再来看约数之和这个问题：

等比数列公式 

 这个连乘式的每一部分都是对一个等比数列求和，由等比数列求和公式，对分母求逆元一样可以得到结果。 

特别地，

如果a没有逆元，那么a必须为0。这是因为，在模m下的乘法逆元，必须满足以下条件：

x * a % m = 1

如果a没有逆元，那么这个方程组在模m下无解。特别地，如果a不为0，那么我们可以找到一个整数x，使得x * a % m = 0，这意味着a有逆元。因此，如果a没有逆元，那么a必须为0。

#include<bits/stdc++.h>
const int N=20;
const int mod=9901;
int a,b,m,ans=1;
int p[N],c[N];//pec
using ll=long long;
void divide(int n)//分解质因数
{m=0;for(int i=2;i<=n/i;i++){if(n%i==0){p[++m]=i,c[m]=0;while(n%i==0) {n/=i;c[m]++;}	}	}	if(n>1) p[++m]=n,c[m]=1;
} 
int qmi(int a,ll b)//快速幂
{ll res=1;while(b){if(b&1) res=(ll)res*a%mod;b>>=1;a=(ll)a*a%mod;}return res;
}
signed main()
{std::cin>>a>>b;if(a==0){std::cout<<0;return 0;}divide(a);//分解质因数for(int i=1;i<=m;i++){//有逆元的充要条件，gcd（a，p）==1if(std::__gcd(p[i]-1,mod)!=1)//分母p-1没有逆元时 {ans=((ll)b*c[i]+1)%mod*ans%mod;continue; }	int x=qmi(p[i],(ll)b*c[i]+1);x=(x-1+mod)%mod;int y=p[i]-1;//分母 y=qmi(y,mod-2);ans=(ll)ans*x%mod*y%mod; } std::cout<<ans<<'\n';return 0;
}

分治 

#include<bits/stdc++.h>
const int N=20;
const int mod=9901;
int a,b,m,ans=1;
int p[N],c[N];
using ll=long long;
void divide(int x)
{m=0;for(int i=2;i*i<=x;i++){if(x%i==0){p[++m]=i;while(x%i==0){x/=i;c[m]++;}}}if(x>1) p[++m]=x,c[m]=1;return ;
}
ll qmi(int a,int b)
{ll res=1%mod;while(b){if(b&1) res=(ll)res*a%mod;a=(ll)a*a%mod;b>>=1;}return res;
}
ll sum(int p,int c)
{if(c==0) return 1;if(c%2) return sum(p,(c-1)/2)*((1+qmi(p,(c+1)/2))%mod)%mod;else return ((1+qmi(p,c/2))%mod*sum(p,c/2-1)%mod+qmi(p,c))%mod;
}
signed main()
{std::cin>>a>>b;if(a==0){std::cout<<0;return 0;}divide(a);for(int i=1;i<=m;i++){ ans=(ll)ans*sum(p[i],c[i]*b)%mod;	}std::cout<<ans<<'\n';return 0;
}

分形

98. 分形之城 - AcWing题库

#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
const int N=1e5+10;
using PII=std::pair<int,int>;
using ll=long long;PII cal(int n,int num)//传入城市等级和位置编号返回坐标位置 
{if(n==0) return {0,0};  //第n级与第n-1级别有关//第n级有2e2n个方块，分成四份除以4是2e2n-2个 int cnt=1ll<<(2*n-2);//一个小正方形里应该有cnt个方块 int len=1ll<<(n-1);//一个小方块的边长为lenauto p=cal(n-1,num%cnt); int x=p.fir,y=p.sec;int count=num/cnt;//代表在第n级种所处的位置 if(count==0) return {y,x};if(count==1) return {x,y+len};if(count==2) return {x+len,y+len};if(count==3) return {2*len-y-1,len-x-1};
}
void solve()
{int n,a,b;std::cin>>n>>a>>b;//城市等级以及两个街区的编号//找到编号为a的房屋在图中的坐标，对坐标算直线距离auto x=cal(n,a-1),y=cal(n,b-1);double xx=x.fir-y.fir,yy=x.sec-y.sec;printf("%.lf\n",std::sqrt(xx*xx+yy*yy)*10);
}
signed main()
{int t=1; std::cin>>t;while(t--) {solve();}return 0;
}

0x03前缀和与差分

前缀和

99. 激光炸弹 - AcWing题库

#include<bits/stdc++.h>
const int N=5e3+10;
int g[N][N];
int n,r;signed main()
{std::cin>>n>>r;r=std::min(r,5001);for(int i=1;i<=n;i++){int x,y,w;std::cin>>x>>y>>w;g[++x][++y]+=w;	}	for(int i=1;i<=5001;i++){for(int j=1;j<=5001;j++){g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];}}int ans=0;for(int i=r;i<=5001;i++){for(int j=r;j<=5001;j++){ans=std::max(ans,g[i][j]-g[i-r][j]-g[i][j-r]+g[i-r][j-r]);}}std::cout<<ans;return 0;
}

差分

100. 增减序列 - AcWing题库

给定长为n的数组，每次可以选择区间[l,r]内的数字都加一或者减一，至少多少次操作能让数列里的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

可以先求出a的差分序列b，b[i] = a[i] - a[i-1]，题目要求最后数列中的所有数字都一样，也就是b中序号2-n的数字都为0，最后a中所有的数字都等于b[1]。

区间[l,r]内的数字都加一或者减一，就要让b[l]+1,b[r+1]-1。

想让2-n中的所有数字都为0，要求次数最少，我们每次需要选择一对数，因此我们每一次找到一个正数-1，负数+1就可以让次数最少。因此我们可以统计正数的和maxn，负数的和的绝对值minn，min(maxn,minn)就是每次选择一个正数和一个负数的操作次数。

差abs（maxn-minn）就是还需要解决的数，我们可以选择b[1]和多余的进行操作，也可以选择b[n+1]和多余的进行操作，只需要操作abs（maxn-minn）次。

因此，最少操作次数就是abs（maxn-minn）+min(maxn,minn) = max(minn,maxn)

同时，最后得到的序列a只与b[1]的取值有关，因为最后a中所有的数字都等于b[1]。

只有第二次操作有可能改变b[1]的取值，最多可以操作abs（maxn-minn）次，每操作一次就有一个新的取值，因此一共有abs（maxn-minn）+1种

#include<bits/stdc++.h>
const int N=2e5+10;using ll=long long;
ll a[N],b[N];
void solve()
{int n;std::cin>>n;ll maxn=0,minn=0;for(int i=1;i<=n;i++){std::cin>>a[i];b[i]=a[i]-a[i-1];}//每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一for(int i=2;i<=n;i++){if(b[i]>0) maxn+=b[i];else minn-=b[i];}std::cout<<std::max(maxn,minn)<<'\n'<<std::abs(maxn-minn)+1;//输出最少操作次数。
}
signed main()
{int t=1;//std::cin>>t;while(t--){solve();}return 0;
}

101. 最高的牛 - AcWing题库

#include<bits/stdc++.h>
const int N=5e3+10;
using PII=std::pair<int,int>;
using ll=long long;
std::map<PII,int> st;
//题目给定身高的相对大小关系，如果给a，b就把a+1到b-1的数字全部-1，
//最高的一定是0，最后身高就是最高身高加上H 
//把a+1到b-1的数字全部-1，另外创建一个数组d，作为c的差分数字，最后把d求前缀和即可得到c数组 
int c[N],d[N];
void solve()
{int n,p,h,m;std::cin>>n>>p>>h>>m;for(int i=1;i<=m;i++){int x,y;std::cin>>x>>y;if(x>y) std::swap(x,y);if(st[{x,y}]) continue;else st[{x,y}]=1;d[x+1]--,d[y]++;		} for(int i=1;i<=n;i++){c[i]=c[i-1]+d[i];std::cout<<c[i]+h<<'\n';}
}
signed main()
{int t=1;//std::cin>>t;while(t--){solve();}return 0;
}

 0x04二分

 整数二分模板

int l=1,r=n,res=-1;
while(l<=r)
{int mid=l+r>>1;if(check(mid)) {res=mid;l=mid+1;}else r=mid-1; 
}

 实数二分模板

for(int i=1;i<=100;i++)//二分100次 
{double mid=(l+r)/2;if(check(mid)) r=mid;//右边是mid else l=mid;
}

三分求单峰函数极值

算法浅谈——讲透三分算法 - 知乎 (zhihu.com)

二分答案转化为判定

1.解空间有单调性，二分枚举

2.“最大值”最小，最优化问题

二分答案的本质是建立了一个定义域为解空间、值域为0或1的单调分段0/1函数，在这个函数上二分查找分界点。

102. 最佳牛围栏 - AcWing题库

用围栏将一部分连续的田地围起来，使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

求长度>=l的最大字段平均数

暴力

二重循环。先枚举子段长度，然后枚举起点，当n为1e5时超时。

#include<bits/stdc++.h>
#define fir first
#define sec second
const int N=1e5+10;
using PII=std::pair<int,int>;
using ll=long long;
int a[N];
ll s[N];void solve()
{int n,f;std::cin>>n>>f;for(int i=1;i<=n;i++){std::cin>>a[i];s[i]=s[i-1]+a[i];}double maxn=-1e9;for(int len=f;len<=n;len++)//枚举长度 {for(int i=1;i+len-1<=n;i++)//枚举起点 {int j=i+len-1;double ans=(double)(s[j]-s[i-1])/len;maxn=std::max(maxn,ans);}}printf("%.lf\n",maxn*1000);
}
signed main()
{int t=1; //std::cin>>t;while(t--) {solve();}return 0;
}

二分

直接找到最大平均数的区间需要遍历两次，O(n^2)，
但用有一种O(n)的办法可以判定存不存在一个区间，它的平均数超过某个数。

因此可以用二分搜索，在[0, 2000]的范围内搜索这个最大平均数。

这题如果用for循环二分100次会导致精度太大过不了题，循环30次才能过，但是正式比赛没有逐个尝试的机会，因此还是while判断比较稳妥。题目要求乘以 1000 再 向下取整，也就1e3，我们再往后取2位，也就是1e-5即可。同样的1e-10也过不了，精度太大了。

#include<bits/stdc++.h>
using ll=long long;
const int N=1e5+10;
double a[N],s[N];
int n,f;
bool check(double x)//判断是否存在一段区间的平均数大于等于x 
{for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i]-x;}//这一段代码会把所有可能的最大和走一遍，但是不确定长度//所以提前把每个数减去平均数，判断和是否大于等于0，即可判断这个平均数是否大于等于0double ans=-1e10;double minn=1e10;for(int i=f;i<=n;i++){minn=std::min(minn,s[i-f]);ans=std::max(ans,s[i]-minn);if(ans>=0) return true;}return false;
}
void solve()
{std::cin>>n>>f;for(int i=1;i<=n;i++) {std::cin>>a[i];}double l=1e-6,r=1e6;while(r-l>=1e-5){double mid=(l+r)/2;if(check(mid)) l=mid;else r=mid;	}	std::cout<<int(r*1000)<<'\n';//最大值乘以 1000再向下取整
}
signed main()
{int t=1;//std::cin>>t;while(t--){solve();}return 0;
} 

113. 特殊排序 - AcWing题库

主要就是交互式，说起来唬人，实际上就是调用一个函数，并且要求这个函数最多调用10000次。二分nlogn，对每个编号讨论应该放在哪个位置上。 

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.class Solution {
public:vector<int> specialSort(int N) {vector<int> res;res.push_back(1);for(int i=2;i<=N;i++)//有N个元素，对每个元素讨论插入的位置{int l=0,r=res.size()-1,ans=-1;while(l<=r){int mid=l+r>>1;if(compare(res[mid],i)){//i比mid大ans=mid;//需要插到mid后面l=mid+1;}else r=mid-1;}res.push_back(i);//需要插到ans后面for(int j=res.size()-2;j>=ans+1;j--)//从ans+1开始全部往后移，ans+1赋值为i{swap(res[j],res[j+1]);}res[ans+1]=i;}return res;}
};