数列 （C++代码）

解题思路:





注意事项:





参考代码:

（题目为啥要强调用十进制输出呢,明明就是故意提醒）

分析一下样例

k=3时，数列为：1，3，4，9，10，12，13..

转换成三进制就是：1，10，11，100，101，110，111..

看起来像是二进制，转化成十进制看看

1,2,3,4,5,6,7..

显然,第n项就是n.

程序就把这个过程逆回去，先把n转换成二进制，再把它当成K进制，重新转换为十进制.

#include <iostream>#include <stack>#include <cmath>using namespace std;long long k, n, ans;stack<int> S;int main() {    cin >> k >> n;    while(n) S.push(n & 1), n >>= 1;    while(!S.empty()) ans += S.top() * pow(k, S.size()-1), S.pop();    cout << ans << endl;    return 0;
}

评论

还没有评论

评论

作者: 坚如钻石 更新时间: 2017-11-05 17:15  在Ta的博客查看  0 

什么叫做不看题就直接做的下场，对，说的就是本蒟蒻。本人把2.1*10^9看成了2.1^109，结果——呵呵，高精度！

其实方法很简单，就是把n转换成二进制，把二进制各个位跑一遍，如果这一位是1，那么答案加上以3为底以当前位数-1为指数的值；如果这一位是0，那么什么都不加。

是不是很麻烦，那我就举个例子，就看样例：k=3 n=100。首先把n转换为二进制，就是1100100。第一位是0，则什么都不做，第二位同样如此。到了第三位是1，则答案加上3^（3-1）=9。第四五位不用管，到第六七位分别加3^（6-1）=243和3^（7-1）=729。则最终答案为9+243+729=981。

上代码（特点：高精度）：

#include<stack>#include<cmath>#include<queue>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define N 100005using namespace std;int two[N],ans[N],mul[N];//two存放n的二进制（注意是逆序），ans存放答案，mul存放幂。int main(){    int k,n,i=0,j=1,l=1;//i为two的长度，j为mul的长度，l为ans的长度。
   mul[1]=1;//mul当然一开始为1（3^（1-1））。
   scanf("%d%d",&k,&n);    while(n){
       two[i++]=n%2;
       n/=2;

}//把n转换为二进制。

   i--;//编程习惯，没办法。
   if(two[0])
       ans[1]=1;//特判二进制第一位是否为1，若为1，则答案加3^（1-1）=1。
   for(int m=1;m<=i;m++){        int lea=0;//lea为高精度乘低精度的进位值。
       for(int o=1;o<=j;o++){
           mul[o]=mul[o]*k+lea;
           lea=mul[o]/10;
           mul[o]%=10;

}//高精度乘。 while(lea){

       mul[++j]=lea%10;

       lea/=10;

}//处理剩余的进位。

       if(two[m]){
           n=max(j,l);//因为n已经不需要了，所以用它再来存放j，l的最大值，便于高精度加。
           for(int o=1;o<=n;o++){
               ans[o+1]+=(ans[o]+=mul[o])/10;
               ans[o]%=10;

}//高精度加。

           if(ans[n+1])
               l=n+1;            else
               l=n;//更新答案的长度。
       }
   }    for(int i=l;i;i--)    printf("%d",ans[i]);//输出答案。
   printf("\n");    return 0;
}
翻了一遍题解，好像没有一个人用高精。不过练练手，总是有用的嘛(*￣︶￣)

评论

还没有评论

评论

作者: 弥生 更新时间: 2017-10-18 21:32  在Ta的博客查看  0 

emmm……代码有点短，甚至有点不敢相信这是对的(๑ŐдŐ)b

就是把k转成二进制，再把二进制的每一位转成n进制

（这个仔细看看题目里的3^0，3^1，3^0+3^1，3^2，3^0+3^2，3^1+3^2，3^0+3^1+3^2，…这就和进制转换长得很像了w）

然后是短得要死的代码

#include<bits/stdc++.h>#define LL long longusing namespace std;const int N=1001;int a[N],n,k,l=0;int main(){
   LL ans=0;    scanf("%d%d",&n,&k);    while(k)a[++l]=k%2,k/=2;//先转二进制
   for(int i=l;i>=1;i--)
       ans+=pow(n,i-1)*a[i];//再转n进制
   printf("%lld\n",ans);    return 0;
}

评论

还没有评论

评论

作者: FancyDreams 更新时间: 2017-10-18 21:18  在Ta的博客查看  0 

一开始根本没想到楼下dalao们说的进制，不过也许我的方法和进制在本质上是相同的(???)

考虑有一个位置的数是K^5 ，那么下面就该到K^5+K^0了，然后就是K^5+K^1，K^5+K^0+K^1（注意这里不是K^5+K^2）……

下面建议在纸上画图。

我们假设K^0在位置1，K^1在位置2；

那么位置3的最高次是位置2

位置4(K^2)的最高次是位置4

可是位置5(K^2+K^0)，位置6(K^2+K^1)，位置7(K^2+K^1+K^0)的最高次都是K^2

这能说明什么呢？？每一次最高次的次数加1的时候，都会又以这个最高次项加上前面各个位置的多项式扩展出新的多项式。

那也就将这个数列的长度扩大到原来的两倍，每一次都是这样。

如果到这里还没有发现什么，那我们再看一些数据：

位置7是K^0+K^1+K^2，也就是位置4的数+位置2的数+位置1的数。

位置15是位置:8+4+2+1，也就是K^3+K^2+K^1+K^0

所以实际上这是一种倍增形式的排列组合。

所以直接按照倍增思想做就可以了

#include<cstdio>#include<iostream>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<iterator>#include<utility>using namespace std;long long k,n,sq=0,pos=0;int main(){    scanf("%lld%lld",&k,&n);    if (n==1)
   {        printf("%lld\n",k);        return 0;
   }

   sq=0; pos=1;    while(pos<=n)
   {
       pos+=pow(2,sq);
       sq++;
   }
   pos=0;
   sq--;

   long long result=0;    while (pos<=n)
   {        if (pos==n)
       {            printf("%lld\n",result);            return 0;
       }        if (pos+pow(2,sq)<=n)
       {
           result+=pow(k,sq);
           pos+=pow(2,sq);
           sq--;
       }        else sq--;

   }    return 0;
}

评论

还没有评论

评论

作者: tianbu 更新时间: 2017-10-06 17:04  在Ta的博客查看  0 

简单的题。

可以想到，把这个n^0+n^1+...n0+n1+...转成二进制，每位对应一个指数加上去或不加。这样，在3<= n <=153<=n<=15的时候，就可以保证序列的有序性。

代码就很简单了：

#include<iostream>#include<cstdio>#include<cmath>using namespace std;char cc[10];int l=0;void turn(int a,int b){//    cout<<a<<' '<<b<<endl;
   if(a!=0){
       turn(a/b,b);
       cc[l++]=a%b+'0';
   }
}int main() {//    freopen("sequence.in","r",stdin);//    freopen("sequence.out","w",stdout);
   long long s=0;//有一个点超int了，用long long
   int a,b;    cin>>a>>b;
   turn(b,2);    for(int i=0;i<l;i++){        if(cc[l-i-1]=='1')s+=(long long int)pow(a,i);
   }    cout<<s;    return 0;
}