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='\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账号...

(0)


相关推荐

  • 7000笔记本性价比之王(三千元笔记本性价比之王)

    PC市场的出货量频繁爆低,并不意味着这一市场走衰,其依旧是大部分人日常办公和外出携带办公所不可或缺的电子产品。只是换新欲望不强烈,面对并不了解的产品时过于保守的购买态度,严重影响了消费者在更换笔记本电脑的“快、准、狠”。但若真有购机需求时,看到各个价位的各种机型,又无从下手。说多了都是泪啊…哎…不容易~作为90后编辑和在大城市打拼的各位一样,就是个“小白领”。交了房租水电,买了油米泡面。发现,这个…

  • MiniPCIE打板需要注意的细节[通俗易懂]

    MiniPCIE打板需要注意的细节[通俗易懂]Minipcie可以不用做斜边,重要的是板厚1.0

  • 聊聊系统平均负载_什么是负载敏感系统

    聊聊系统平均负载_什么是负载敏感系统一、什么是平均负载单位时间内,系统处于可运行状态和不可中断状态的进程数,可简单理解为系统平均活跃进程数可运行状态:top命令状态为R,包括Runnable和Running不可中断状态:top命令状态为D,正处于内核态关键流程中的进程,并且这些流程是不可打断的,比如等待硬件设备的I/O响应,这往往是对数据一致性的一种保护机制二、如何查看平均负载$uptime…,loada…

  • java中多态_java之多态

    java中多态_java之多态1.多态的概述:是面向对象的三大特性之一,封装、继承、多态。①一个具体的对象有多种形态,老虎既属于猫科动物(因为子父类是相对的,所以猫科动物也可以看做子类),又属于哺乳动物,所以老虎既可以拥有猫科动物的属性,又有哺乳动物的属性。②Java中多态的代码体现在一个子类对象(实现类对象)既可以给这个子类(实现类对象)引用变量赋值,又可以给这个子类(实现类对象)的父类(接口)变量赋值。普通类与普通类,抽象…

  • windows下php7.1安装redis扩展以及redis测试使用全过程

    windows下php7.1安装redis扩展以及redis测试使用全过程

    2021年10月21日
  • vuethink 配置

    vuethink 配置

    2021年10月11日

发表回复

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

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