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

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

这题。。

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='
#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;
}
}
'; 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账号...

(0)
blank

相关推荐

  • mybatis log plugin 激活码[最新免费获取][通俗易懂]

    (mybatis log plugin 激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html1M3Q9SD5XW-eyJsa…

  • 原生js添加元素

    原生js添加元素今天做页面使用的mui,因为使用mui情况下无法使用jquery,于是在ajax请求完毕添加元素的时候发现自己竟然对原生js添加元素的方法有点模糊了,真是越活越倒退了,赶紧整理一波。首先最简单的innerHTML,这个不想多说,入门新手喜欢这么用,但他的缺点也很明显:不管你渲染部分还是全部,始终需要替换原先所有的子元素,也就是需要重复渲染,会增加浏览器压力。接下来就是正题了,js推荐是这样…

  • 请简述什么是Vue组件化开发_vuecli和webpack

    请简述什么是Vue组件化开发_vuecli和webpack前言真实项目开发过程中,我们都是使用组件化的去开发vue的项目,但是组件化的思想又是如何来的呢?下面就从开始讲解演变过程演变过程1.0一般情况下vue都是单页面开发,所以项目中只会有一个inde

  • 全面了解 Nginx 到底能做什么

    全面了解 Nginx 到底能做什么

  • windws7下Loadrunner12的使用教程详解「建议收藏」

    windws7下Loadrunner12的使用教程详解「建议收藏」一.初识LoadRunner( 点击链接跳转到LoadRunner的安装步骤)1.简介:(1)从LoadRunner英语字面上进行理解就是负载跑步者,为什么这么说呢?对于从事IT软件行业的工作者如开发人员和测试人员来说一定不会感到陌生就是在承受负载的条件下运行软件或者网页的业务。从另一个比较形象的理解就是“压死骆驼的最后一根稻草”这里的稻草就是软件的事务,LoadRunner这款软件…

    2022年10月14日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号