算法竞赛进阶指南
位运算
AcWing 89. a^b
#include<iostream> using namespace std; int main(void) { long long a,b,p; cin>>a>>b>>p; long long ans=1%p; while(b) { if(b&1)//判断b当前二进制位是否为1 { ans=ans*a%p; } a=a*a%p;//每跨越一个二进制位，b就是多加一次2的(k-1)次方，假设当前跨越到第二个二进制位，那么b就会加上一个2^(2-1)次方 b>>=1;//b右移一位 } cout<<ans; return 0; }
AcWing 90. 64位整数乘法
#include<iostream> using namespace std; int main(void) { long long a,b,p,ans=0; cin>>a>>b>>p; while(b) { if(b&1) { ans=(ans+a)%p; } a=a*2%p; b>>=1; } cout<<ans; return 0; }
AcWing 998. 起床困难综合症
#include<iostream> using namespace std; int n,m; typedef pair<string,int>PII; PII a[100010]; int calc(int bit,int now) { for(int i=1;i<=n;i++) { int x=a[i].second>>bit&1;//拿到当前x的第bit位是0/1 if(a[i].first=="AND") now&=x; else if(a[i].first=="OR") now|=x; else if(a[i].first=="XOR") now^=x; } return now; } int main(void) { cin>>n>>m; for(int i=1;i<=n;i++) { char op[5]; int x; scanf("%s %d",op,&x); a[i]={op,x}; } int val=0,ans=0,maxi=-10010; //枚举bit位 for(int bit=29;bit>=0;bit--) { int res0=calc(bit,0);//当第bit位为0的时候 int res1=calc(bit,1);//当第bit位为1的时候 if(val+(1<<bit)<=m&&res0<res1)//当前bit位确定为1，并且初始攻击val加上新bit位之后还是＜m { val+=1<<bit,ans+=(res1<<bit);//更新初始的攻击值，更新答案 }else { ans+=(res0<<bit);//第bit位为0，所以不需要对val+值 } //cout<<"res0 = "<<res0<<" res1 = "<<res1<<endl; maxi=max(maxi,ans); } cout<<maxi; return 0; }
递推与递归
AcWing 92. 递归实现指数型枚举
#include<iostream> #include<vector> using namespace std; int n; vector<int>chosen; void calc(int x) { //边界 if (x == n + 1) { for (int i = 0; i < chosen.size(); i++) { printf("%d ", chosen[i]); } puts(""); return; } //不选当前数 calc(x+1);//递归分支 //选择当前数 chosen.push_back(x); calc(x+1);//递归分支 chosen.pop_back();//回溯 } int main(void) { cin >> n; calc(1); return 0; }
AcWing 93. 递归实现组合型枚举
#include<iostream> #include<vector> using namespace std; int n,m; vector<int>chosen; void calc(int x) { if(chosen.size()>m||chosen.size()+(n-x+1)<m) return ;//如果当前选择数字超过了m个，或者当前选的数字加上剩余的数字都不足m个就可以return剪枝了 //边界 if (x==n+1) { for (int i = 0; i < chosen.size(); i++) { printf("%d ", chosen[i]); } puts(""); return; } chosen.push_back(x); calc(x+1); chosen.pop_back(); calc(x+1); } int main(void) { cin >> n>>m; calc(1); return 0; }
AcWing 94. 递归实现排列型枚举
#include<iostream> using namespace std; int n; bool st[20]; int ans[20]; void dfs(int x) { if(x==n+1) { for(int i=1;i<=n;i++) { printf("%d ",ans[i]); } puts(""); } for(int i=1;i<=n;i++) { if(st[i]) continue; st[i]=true;//i被选了 ans[x]=i;//第x个位置选了i dfs(x+1);//递归分支 st[i]=false;//回溯 } } int main(void) { cin>>n; dfs(1); return 0; }
AcWing 95. 费解的开关
#include<iostream> #include<cstring> using namespace std; const int N=6; char g[N][N],backup[N][N]; int dx[N] = { -1, 0, 1, 0, 0 }, dy[N] = { 0, 1, 0, -1, 0 }; void turn(int x,int y) { for(int i=0;i<5;i++) { int ax=x+dx[i],ay=y+dy[i]; if(ax<0||ax>=5||ay<0||ay>=5) continue; if(g[ax][ay]=='0')g[ax][ay]='1'; else g[ax][ay]='0'; } } int main(void) { int n=0; cin>>n; while(n--) { for(int i=0;i<5;i++) cin>>g[i]; int res=10010; for(int op=0;op<32;op++)//因为每一组有5行，所以方案数为2^5=32种方案,可以利用二进制序列来遍历这32种方案，从00000->11111 //0表示不按，1表示按 { int step=0;//步数 memcpy(backup,g,sizeof g);//因为要对原来的地图进行修改且不止一种方案，如果不对地图进行备份，原地图就会丢失。 for(int i=0;i<5;i++)//通过对二进制进行右移i位，得到右移后的最后一个位置的二进制序列是否为1 { if(op>>i&1)//如果是1，就表示要按下去 { step++; turn(0,i); } } //第一行遍历了之后下面的方案已经定下来了，直接莽 for(int i=0;i<4;i++) { for(int j=0;j<5;j++) { if(g[i][j]=='0') { step++; turn(i+1,j); } } } //检查答案 bool dark=false; for(int j=0;j<5;j++) { if(g[4][j]=='0') { dark=true; break;//已经不满足条件了，退出检查 } } //得还原地图咯 memcpy(g,backup,sizeof g); if(!dark) res=min(res,step);//更新最短距离 } if(res>6) res=-1; cout<<res<<endl; } return 0; }
