2017zzuli校赛_2134: 维克兹的进制转换
题意就最后的一句话
看到数据范围，n最大1e7，很明显是个O（n）的打表题
那我们需要找到递推关系，因为末尾只可能是0，1，2三个数字，那我们先按照末尾的情况分类
设ans【i】【0】为能够组成i的，末尾数字为0的方案数，ans【i】【1】，ans【i】【2】同理
当i是偶数的时候，末尾数字为1必然方案数是0，即ans【i】【1】=0
末尾数字为0的方案数与i/2的方案数有关
当i是奇数的时候同理分析
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7;
int ans[maxn+50][3];
int T,n;
int main(){
memset(ans,0,sizeof(ans));
ans[0][0]=1;
for(int i=1;i<=maxn;i++)
if (i%2==0){
ans[i][1]=0;
ans[i][0]=ans[i/2][0]+ans[i/2][1]+ans[i/2][2];
ans[i][2]=ans[(i-2)/2][0]+ans[(i-2)/2][1]+ans[(i-2)/2][2];
}
else{
ans[i][0]=ans[i][2]=0;
ans[i][1]=ans[(i-1)/2][0]+ans[(i-1)/2][1]+ans[(i-1)/2][2];
}
scanf("%d",&T);
while(T--){
scanf("%d",&n);
printf("%d\n",ans[n][0]+ans[n][1]+ans[n][2]);
}
return 0;
}
查看30道真题和解析