这题。。
题意好像就是把一个数n转化为b进制，然后从n=1开始，一直加到这个数的二进制的位数的和。然后我想到函数库#include<stdlib.h>里面一个求进制的函数itoa，然后打出来了，测试的时候发现，这个oj评判系统竟然没有这个函数，无奈自己只能自己写，然后就是下面这个
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
char str[maxn];
char *itoa_my(int value,char *string,int radix)
{
char zm[37]="0123456789abcdefghijklmnopqrstuvwxyz";
char aa[100]={0};
int sum=value;
char *cp=string;
int i=0;
if(radix<2||radix>36)
{
cout<<"error data!"<<endl;
return string;
}
if(value<0)
{
cout<<"error data!"<<endl;
return string;
}
while(sum>0)
{
aa[i++]=zm[sum%radix];
sum/=radix;
}
for(int j=i-1;j>=0;j--)
{
*cp++=aa[j];
}
*cp='\0';
return string;
}
int shuhe(int n,int b)
{
int sum = 0;
itoa_my( n, str, b );
int h = strlen(str);
for(int i=0;i<h;i++)
{
sum+=str[i]-'0';
}
return sum;
}
int main()
{
int t, n, b;
scanf("%d",&t);
for(int j = 1;j<=t;j++ )
{
int ans=0;
scanf("%d%d",&n,&b);
for(int i=1;i<=n;i++)
{
ans += shuhe(i,b);
}
cout<<"Case #"<<j<<": "<<ans<<endl;
}
}样例啥的都没问题，就是超时，然后超时你要超多点，也就算了，然后题目要求是2000ms我这是2010到2030ms就超那么一点
然后，一直过不去，然后我们队就我一个做，实在不想怼了。这个超了12ms，，，。
然后网上的题解是这样的
思路：二维树状数组+区间求和
#include<iostream>
using namespace std;
const int MAXN = 1000001;
int c[11][MAXN];
int calc(int n,int b)
{
int res=0;
while(n)
{
res += (n%b);
n/=b;
}
return res;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y,int val)
{
while(y<MAXN)
{
c[x][y]+=val;
y+=lowbit(y);
}
}
int Sum(int x,int y)
{
int sum = 0;
while(y>0)
{
sum+=c[x][y];
y-=lowbit(y);
}
return sum;
}
void init() //将二到十进制的所有数的情况计算出来，且对每个进制建立一个树状数组
{
for(int i=2;i<=10;i++)
{
for(int j=1;j<MAXN;j++)
{
int val = calc(j,i);
add(i,j,val);
}
}
}
int main()
{
int T,id=1;
init();
scanf("%d",&T);
while(T--)
{
int n,b;
scanf("%d%d",&n,&b);
printf("Case #%d: %d\n",id++,Sum(b,n));
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/114853.html原文链接：https://javaforall.net
