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;
}