位运算
1.64位整数乘法
这题就是很简单的龟速乘，因为1e=18*1e18会爆longlong,假如编译器支持可以用__int128_t，或者高精度也行
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll qadd(ll a,ll k,ll p)//龟速乘 { ll res=0;//加法的零元是0 while(k) { if(k&1) res=(res+a)%p; a=(a+a)%p; k>>=1; } return res; } int main() { ll a,b,p; scanf("%lld%lld%lld",&a,&b,&p); printf("%lld\n",qadd(a,b,p)); return 0; }
递推与递归
1.费解的开关
这题有多种做法，其中有bfs，或者终止状态递推6步，还有高斯消元的做法，现在让我们看看递推的做法
二进制枚举第一行所有会变到的状态，1表示改变这个位置，0表示不变，然后将第一锁死看第二行，枚举第二行的上一行假如上一行有0，则将这一行的这一位改变一下，这样就使得上一行的0全都变成1了，直到操作到最后一行，看看最后一行是不是全为0即可
1. #in#include<bits/stdc++.h> using namespace std; const int N=6; char str[N][N],temp[N][N]; int dx[6]={-1,0,1,0,0},dy[6]={0,1,0,-1,0};//上 右 下 左 中 void trans(int x,int y)//用来改变一个位置 { for(int i=0;i<5;i++)//枚举五个方向 { int tx=x+dx[i],ty=y+dy[i]; if(tx<0||tx>4||ty<0||ty>4) continue; temp[tx][ty]^=1; } } void solve() { for(int i=0;i<5;i++) scanf("%s",str[i]); int ans=7; for(int i=0;i<32;i++) { int cnt=0; memcpy(temp,str,sizeof str); for(int j=0;j<5;j++)//枚举改第一行的状态 if(i>>j&1) cnt++,trans(0,j); for(int j=0;j<4;j++)//枚举改剩下的几行 for(int k=0;k<5;k++) if(temp[j][k]=='0') cnt++,trans(j+1,k); for(int j=0;j<5;j++)//看看最后几行是不是全为1 if(temp[4][j]=='0') cnt=0x3f3f3f3f; ans=min(cnt,ans); } if(ans<=6) printf("%d\n",ans);//假如小于6了 else puts("-1"); } int main() { int T; scanf("%d",&T); while(T--) solve(); return 0; }
2.约数之和
约数之和的公式：
求等比数列也有公式就是p^k-1/p-1
然后这题用递归来做定义sum(p,k)是约数为p,次方是k的前k相等比数列的和
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=9901; int a,b; int qmi(int a,int k) { int res=1; while(k) { if(k&1) res=(ll)res*a%mod; a=(ll)a*a%mod; k>>=1; } return res; } int sum(int p,int k)//用来求sum { if(k==1) return 1;//假如是1了，就返回1 if(k&1) return (sum(p,k-1)+qmi(p,k-1))%mod;//奇数 else return ((1+qmi(p,k/2))*sum(p,k/2))%mod;//偶数 } int main() { int ans=1; cin>>a>>b; for(int i=2;i<=a/i;i++)//分解质因数 if(a%i==0) { int s=0; while(a%i==0) s++,a/=i;//获取质因数的个数 ans=(ll)ans*sum(i,b*s+1)%mod;//按照公式求一遍 } if(a>1) ans=(ll)ans*sum(a,b+1)%mod;//假如最后也是个质因数 if(a==0) ans=0; cout<<ans<<endl; return 0; }
3.分形之城
这题就是找规律递归到子问题
n层是可以由n-1层得到的，只不过的经过坐标变化，然后在分别求一下坐标变化需要改变的值即可
get（N,A）表示在第N层获取A这个点的坐标，然后距离直接就两点间距离公式即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct Piont//用来存坐标 { ll x,y; }; Piont get(ll n,ll a) { if(n==0) return {0,0};//假如0层了，说明只有0，0这一个点 ll block=1ll<<2*n-2,len=1ll<<n-1; auto d=get(n-1,a%block);//处理子问题 ll x=d.x,y=d.y; int z=a/block; //图中每种情况 if(z==0) return {y,x}; else if(z==1) return {x,y+len}; else if(z==2) return {x+len,y+len}; else return {len+len-1-y,len-1-x}; } void solve() { ll n,a,b; scanf("%lld%lld%lld",&n,&a,&b); auto da=get(n,a-1),db=get(n,b-1);//获取a,b的坐标，因为数是0开始记的，所以要减1 double dx=da.x-db.x,dy=da.y-db.y; printf("%.0lf\n",sqrt(dx*dx+dy*dy)*10);//输出两点间距离 } int main() { int T; scanf("%d",&T); while(T--) solve(); return 0; }
