6.1 位运算
6.1.1 90. 64位整数乘法
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL qadd(LL a,LL b,LL p) { LL res=0; while(b) { if(b&1) res=(res+a)%p; a=(a+a)%p; b>>=1; } return res; } int main() { LL a,b,p; cin>>a>>b>>p; cout<<qadd(a,b,p); return 0; }
6.2 递推与递归
6.2.1 95. 费解的开关
代码：
#include<bits/stdc++.h> using namespace std; const int N=6; char g[N][N],bg[N][N]; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; void turn(int x,int y) { if(g[x][y]=='0') g[x][y]='1'; else g[x][y]='0'; for(int i=0;i<4;i++) { int a=x+dx[i],b=y+dy[i]; if(a<0||a>4||b<0||b>4) continue; if(g[a][b]=='0') g[a][b]='1'; else g[a][b]='0'; } } int main() { int T; cin>>T; while(T--) { int res=10; for(int i=0;i<5;i++) cin>>bg[i]; for(int op=0;op<32;op++) { int cnt=0; memcpy(g,bg,sizeof bg); // 操作第一行的开关 for(int i=0;i<5;i++) { if(op>>i&1) { turn(0,i); cnt++; } } // 递推出第1~4行开关的状态 for(int i=0;i<4;i++) { for(int j=0;j<5;j++) { if(g[i][j]=='0') { turn(i+1,j); cnt++; } } } // 检查最后一行灯是否全亮 bool success=true; for(int i=0;i<5;i++) { if(g[4][i]=='0') success=false; } if(success&&res>cnt) res=cnt; } if(res>6) res=-1; cout<<res<<endl; } return 0; }
6.2.2 97. 约数之和
代码：
#include<bits/stdc++.h> using namespace std; const int mod=9901; int qmi(int a,int k) { int res=1; a%=mod; while(k) { if(k&1) res=res*a%mod; a=a*a%mod; k>>=1; } return res; } int sum(int p,int k) { if(k==1) return 1; if(k%2==0) return (1+qmi(p,k/2))*sum(p,k/2)%mod; return (sum(p,k-1)+qmi(p,k-1))%mod; } int main() { int a,b; cin>>a>>b; int res=1; // 对a分解质因数 for(int i=2;i*i<=a;i++) { if(a%i==0) { int s=0; while(a%i==0) { a/=i,s++; } res=res*sum(i,b*s+1)%mod; } } if(a>1) res=res*sum(a,b+1)%mod; if(a==0) res=0; cout<<res; return 0; }
6.2.3 98. 分形之城
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; struct Point { LL x,y; Point(){} Point(LL _x,LL _y) { x=_x,y=_y; } }; Point get(LL n,LL a) { if(n==0) return Point(0,0); LL block=1ll<<n*2-2,len=1ll<<n-1; //1ll是表示long long型的1，而不是一百一十一 Point p=get(n-1,a%block); LL x=p.x,y=p.y; int z=a/block; if(z==0) return Point(y,x); else if(z==1) return Point(x,y+len); else if(z==2) return Point(x+len,y+len); return Point(len*2-1-y,len-1-x); } int main() { int T; cin>>T; while(T--) { LL n,a,b; cin>>n>>a>>b; Point pa=get(n,a-1); Point pb=get(n,b-1); double dx=pa.x-pb.x,dy=pa.y-pb.y; //小心按照double输出变成科学计数法 LL res=round(sqrt(dx*dx+dy*dy)*10); cout<<res<<endl; } return 0; }
6.3 前缀和与差分
6.3.1 99. 激光炸弹
代码：
#include<bits/stdc++.h> using namespace std; const int N=5010; int n,r; int g[N][N]; int main() { cin>>n>>r; for(int i=1;i<=n;i++) { int x,y,w; cin>>x>>y>>w; g[x+1][y+1]+=w; } //注意这里是5001是整个前缀和矩阵，而不是n for(int i=1;i<=5001;i++) { for(int j=1;j<=5001;j++) { g[i][j]+=g[i][j-1]+g[i-1][j]-g[i-1][j-1]; } } int res=-1; if(r>5001) cout<<g[5001][5001]<<endl; else { for(int i=1;i+r<=5002;i++) { for(int j=1;j+r<=5002;j++) { int x1=i,y1=j,x2=i+r-1,y2=j+r-1; res=max(res,g[x2][y2]-g[x1-1][y2]-g[x2][y1-1]+g[x1-1][y1-1]); } } cout<<res<<endl; } return 0; }
6.3.2 100. 增减序列
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=100010; int n; LL a[N],b[N]; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]-a[i-1]; } LL p=0,q=0; for(int i=2;i<=n;i++) { if(b[i]>0) p+=b[i]; else if(b[i]<0) q-=b[i]; } LL op=0,cnt=0; op=max(p,q); cnt=max(p,q)-min(p,q)+1; cout<<op<<endl; cout<<cnt<<endl; return 0; }
