这题。。

L. Digit sum (ICPC 2019 上海网络赛)

题意好像就是把一个数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