首页 > 其他分享 >2023南海区区赛模拟(初中组)T1询问"好数"

2023南海区区赛模拟(初中组)T1询问"好数"

时间:2023-12-09 18:55:21浏览次数:51  
标签:输出 好数 int 询问 long T1 整数 2023

第1题     询问"好数" 查看测评数据信息

如果整数a = b^2 或者 a  = b^3,其中正整数b>=1, 那么a就是"好数"。

即:如果a是平方数或者立方数,那么a就是"好数"。

现在有n个询问,第i个询问给出一个整数x[i],表示询问1至x[i]范围内有多少个"好数"。

输入格式

 

第一行,一个整数n。1<=n<=100000。

接下来有n行,第i行有一个整数x[i],1<=x[i]<=10^9 。

 

输出格式

 

共n行,每行一个整数。

 

输入/输出例子1

输入:

6

10

1

25

1000000000

999999999

500000000

 

 

输出:

4

1

6

32591

32590

23125

 

 

样例解释

 

 

 

分析:

先暴力程序,结果70分

#include <bits/stdc++.h>
using namespace std;

int n, x, ans=0;
int main()
{
	scanf("%d", &n);
	while (n--)
	{
		scanf("%d", &x);
		ans=0;
		map<int, int> mp;
		for (int i=1; i*i<=x; i++)
			if (mp[i*i]!=1) mp[i*i]=1, ans++;
		for (int i=1; i*i*i<=x; i++)
			if (mp[i*i*i]!=1) mp[i*i*i]=1, ans++;
		printf("%d\n", ans);
	}
	return 0;
}

  因为数据比较打,10^9,普通数组装不下,所以考虑用map

然后把可能的乘积存起来

 

正解:

这题首先要关注到:X虽然大,但是好数少!!不超过35000个(根号100000000=31622, 1000000000=1000^3, 显然好数最多为32622, 但会出现重复情况)

所以我们预处理好数,然后去重,排序,二分查找

 

 

代码:

注意t也要排序,否则不好去重,调试的时候就是没排序t出问题了(用set检查)

输出R

#include <bits/stdc++.h>
using namespace std;

const int N=35000;
long long n, x;
long long m1=0, t[N], m=0, a[N]; 
int main() 
{
	for (int i=1; i<=31622; i++)
		t[++m1]=i*i;
	for (int i=1; i<=1000; i++)
		t[++m1]=i*i*i;
	
	sort(t+1, t+1+m1);
	for (int i=1; i<=m1; i++)
		if (t[i]!=t[i-1]) a[++m]=t[i];
	sort(a+1, a+1+m);
	
	scanf("%lld", &n);
	while (n--)
	{
		scanf("%lld", &x);
		
		long long L=1, R=m, mid=0;
		while (L<=R)
		{
			mid=(L+R)/2;
			if (a[mid]>x) R=mid-1; // 因为<=都满足情况
			else L=mid+1; //输出结果可以是ans,但是这行要改成 else ans=mid, L=mid+1;
		}
		printf("%lld\n", R);
	}
	return 0;
}

  

为什么输出的是R?分析一下即可

 

 

 

标签:输出,好数,int,询问,long,T1,整数,2023
From: https://www.cnblogs.com/didiao233/p/17891327.html

相关文章

  • 集训队胡策2023-2024补题记录
    CTT结束后发现自己胡策题都没咋补,这下尴尬了。主要原本胡策就打着玩的(怎么CTT平均难度比胡策还要简单啊.jpg。还是随便写几篇题解吧。先来个补全进度表,根据胡策OJ或qoj通过情况来评判:测试赛(10.22)A+BProblem奥林匹克五子棋元旦激光炮Day1(10.23)优惠购......
  • 2023-2024-1 20231403 《计算机基础与程序设计》第十一周学习总结
    作业信息这个作业属于哪个课程<班级的链接>(如2022-2023-1-计算机基础与程序设计)这个作业要求在哪里2023-2024-1计算机基础与程序设计第十一周作业)这个作业的目标自学《计算机科学概论》第15,16章,《C语言程序设计》第10章作业正文https://www.cnblogs.com/lsrmy......
  • 2023-12-09:用go语言,给你两个整数数组 arr1 和 arr2, 返回使 arr1 严格递增所需要的最小
    2023-12-09:用go语言,给你两个整数数组arr1和arr2,返回使arr1严格递增所需要的最小「操作」数(可能为0)。每一步「操作」中,你可以分别从arr1和arr2中各选出一个索引,分别为i和j,0<=i<arr1.length和0<=j<arr2.length,然后进行赋值运算arr1[i]=arr2[j]。如果......
  • 7. 2023-11-20 12:29:32,542 [tornado.general :456 ][WARNING ][3052] Got events f
     这个警告表明Tornado检测到了有事件(events)被发送到一个已经关闭的流(stream)。在Tornado中,一个流代表一个请求或响应的数据流。这个警告可能意味着在请求处理的过程中,尝试向已经关闭的流发送了事件。可能的原因和解决方法:异步操作处理不当:在Tornado中,当你处理异步请求时,需......
  • 2023-2024-1 20232301 《网络》第5周学习总结
    教材学习内容总结教材学习中的问题和解决过程问题1:对于基于语义的海量媒体内容特征快速提取与分类技术,书上暂未举出具体例子,使我在理解上稍有欠缺问题1解决方案:通过不断询问chatgpt,我得到了以具体的体育文章为实例的回答,如下:“当涉及到基于语义的海量媒体内容提取与分类技术......
  • 2023-12
    2023-12*UcupStage11:NaningD.RedBlackTree(QOJ7736)好题。Description给你一颗树,每个节点有一个颜色(红或黑),定义一棵树是好的指这棵树中的所有节点到他子树中的叶子节点路径上的黑色节点数都相等。对每个\(1\lei\len\),求要使以\(i\)为子树是好的,至少要改变多少......
  • 2023年 11月助教总结报告
    一、助教工作的具体职责和任务我每周都会帮助老师批改作业,可以及时了解课程的进度和学生的学习情况。我负责整理学生的问题和反馈。此外,当学生遇到学习问题我可以解决时,我会积极帮助。同时,经过上一次总结,留意到很多同学说会忘记作业截止时间导致没有交上作业,我会提前在qq群里提醒......
  • 2023-2024-1 20231424《计算机基础与程序设计》第11周学习总结
    2023-2024-120231424《计算机基础与程序设计》第11周学习总结作业信息作业属于的课程<班级链接>(2022-2023-1-计算机基础与程序设计)作业要求<作业要求>(2022-2023-1计算机基础与程序设计第一周作业)作业目标《计算机科学概论》第15,16章和《C语言程序设计》第10章......
  • 2023振兴杯-Crypto wp
    crypto1题目fromflagimportflagdefencrypt(x,y):key='zxb'result=''foriinrange(len(x)):result+=chr(ord(x[i])^ord(y[i])^ord(key[i%3]))returnresultx=flagy=flag[1:]+flag[......
  • 2023-2024-1 20232327《网络空间安全导论》第五周学习总结
    2023-2024-120232327《网络空间安全导论》第五周学习总结教材学习内容总结1.信息内容安全是研究利用计算机从包含海量信息并且迅速变化的网络中对特定安全主题相关信息进行自动获取、识别和分析的技术;2.网络爬虫是按照一定规则,自动抓取有互联网信息的程序或脚本;3.信息过滤是......