这题。。
题意好像就是把一个数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;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114853.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...