猫史档案馆

[C++]能力测试“丑数”

用户:进阶的柯南进阶的柯南查看:59 回复:17 评论:59 创建时间:2024-08-16T19:34:32

题目描述

丑数是一些质因子只有2,3,5的数。数列1,2,3,4,5,6,8,9,10,12,15……写出了从小到大的前11个丑数，1属于丑数。现在请你编写程序，找出第N个丑数是什么。

输入

1行1个整数N（1<=N<=1500)

输出

一个整数，你找到的第1500个丑数。

 

PS：共10个测试点，1点10分，满分100分，你可以在评论区发代码，我会在线上测评

0分：c++小白

10~30分：c++新手

40~70分：c++普及组高手

80~90分：c++普及组顶尖人物

100分：c++普及组大佬

我的原则是：禁止打表，禁止在网络上抄代码，我是能力测试，你测了不属于自己的能力是对你无用的

回复

上一页第 1 页 / 共 1 页下一页
进阶的柯南进阶的柯南

输出处“1500”为错字，修改为“N”

点赞0

评论

进阶的柯南进阶的柯南

d'd'd

点赞0

评论

进阶的柯南进阶的柯南

d'd'd

点赞0

评论

进阶的柯南进阶的柯南

d'd'd

点赞0

评论

稗田阿Q_Official稗田阿Q_Official

致敬传奇暴搜哥我

点赞0

评论

该用户不再实名上网该用户不再实名上网

辅助（不喜之处可删）

点赞0

评论

该用户不再实名上网该用户不再实名上网

楼主，我有3个问题

1，运行时间限制是多少？

2，能不能公布测试点数据？

3，打表的判定依据是什么？

点赞0

评论

10cKYouse1f10cKYouse1f

#include <iostream>
using namespace std;
bool passList[6] = { 0,0,1,1,0,1 };
int n = 0;

bool isOk2(int y) {
	if (y < 3) {
		return false;
	}
	int i = 2;
	while (i * i <= y) {
		if (!(y % i * i)) {
			return false;
		}
		i++;
	}
	return true;
}

bool isOk(int z) {
	int num1 = z;
	int num2 = 1;
	for (; num2 < z; num2++) {
		if (!(z % num2)) {
			num1 = z / num2;
			if (isOk2(num1) && !passList[num1]) {
				return false;
			}
			if (isOk2(num2) && !passList[num2]) {
				return false;
			}
		}
	}
	return true;
}


int main() {
	cin >> n;
	int okNum = 0;
	int ans = 0;
	while (okNum < n) {
		ans++;
		if (isOk(ans) and !isOk2(ans) || passList[ans]) {
			okNum++;
		}
	}
	cout << ans;
}

点赞0

评论

进阶的柯南进阶的柯南

现在要交的快点（）我23点要去睡觉不然被我爸制裁（

点赞0

评论

进阶的柯南进阶的柯南

当出现80分以上的人或者提交人数达到6~7人时公布AC答案

点赞0

评论

10cKYouse1f10cKYouse1f

#include <iostream>
#include <vector>
using namespace std;
int passList[3] = {2,3,5};
int n = 0;
vector<int> ansList;


int main() {
	cin >> n;
	double start = clock();
	int Count = 1;
	int 喵 = 1;
	while (Count < n) {
		int min = INT_MAX;
		ansList.push_back(喵);
		for (int y = 0; y < 3; y++)  {
			for (int x = 0; x < Count; x++) {
				int nextUgly = ansList[x] * passList[y];
				if (ansList[Count - 1] < nextUgly){
					if (nextUgly < min) {
						min = nextUgly;
					}
					break;
				}
			}
		}
		喵 = min;
		Count++;
	}
	cout << 喵;
}

点赞0

评论

浮躁的小黄鸡1浮躁的小黄鸡1

#include<bits/stdc++.h>
using namespace std;
int a[1000005],b[1000005];
queue<int> x;
int main(){
    int n;
    cin>>n;
    for(int i=2;i<=1000000;i++){
        if(a[i]==0){
            x.push(i);
            for(int j=i*2;j<=1000000;j+=i)
                a[j]=1;
        }
    }
    while(!x.empty()){
        int max1=x.front();
        if(max1>5){
            for(int i=max1;i<=1000000;i+=max1)
                b[i]=1;
        }
        x.pop();
    }
    int max2=0;
    for(int i=1;i<=1000000;i++){
        if(b[i]==0){
            max2++;
            if(max2==n){
                cout<<i;
                return 0;
            }
        }
    }
    return 0;
}

点赞0

评论

该用户不再实名上网该用户不再实名上网

#include<iostream> using namespace std; int f(int x) {     if(x==1)     {         return 1;//1也算丑数     }     while(x%2==0)     {         x/=2;         if(x==1)         {             return 1;         }     }     while(x%3==0)     {         x/=3;         if(x==1)         {             return 1;         }     }     while (x%5==0)     {         x/=5;         if(x==1)         {             return 1;         }     }     return 0;

 

} int main() {     int t;     cin>>t;     int a,y=0;     while (t!=0)     {         if(f(y)==0)             t--;

 

        y++;     }     cout<<f(y); } 
#include<iostream>
using namespace std;
int f(int x)
{
    if(x==1)
    {
        return 1;//1也算丑数
    }
    while(x%2==0)
    {
        x/=2;
        if(x==1)
        {
            return 1;
        }
    }
    while(x%3==0)
    {
        x/=3;
        if(x==1)
        {
            return 1;
        }
    }
    while (x%5==0)
    {
        x/=5;
        if(x==1)
        {
            return 1;
        }
    }
    return 0;

}
int main()
{
    int t;
    cin>>t;
    int a,y=0;
    while (t!=0)
    {
        if(f(y)==0)
            t--;

        y++;
    }
    cout<<f(y);
}​

点赞0

评论

_VirtualPoint__VirtualPoint_

这……100了也不算大佬啊，才CSP-J第二题难度

点赞0

评论

OLEEEEEEEEEEEEEEEEEEOLEEEEEEEEEEEEEEEEEE

使用集合set，自动排序、去重：

#include<bits/stdc++.h>
using namespace std;
int n,t=1;
set<long long>s;
int main(){
	scanf("%d",&n);
	s.insert(1);
	if(n>1)
		for(set<long long>::iterator it=s.begin(); it!=s.end(); it++){
			s.insert((*it)<<1);
			if(s.size()==n) break;
			s.insert((*it)*3);
			if(s.size()==n) break;
			s.insert((*it)*5);
			if(s.size()==n) break;
		}
	for(set<long long>::iterator it=s.begin(); it!=s.end(); it++)
		printf("%lld ",*it);
    return 0;
}

点赞0

评论

OLEEEEEEEEEEEEEEEEEEOLEEEEEEEEEEEEEEEEEE

愺！不是输出前N个！

#include<bits/stdc++.h>
using namespace std;
int n,t=0;
set<long long>s;
int main(){
	scanf("%d",&n);
	s.insert(1);
	if(n>1)
		for(set<long long>::iterator it=s.begin(); it!=s.end(); it++){
			s.insert((*it)<<1);
			if(s.size()==n<<2) break;
			s.insert((*it)*3);
			if(s.size()==n<<2) break;
			s.insert((*it)*5);
			if(s.size()==n<<2) break;
		}
	for(set<long long>::iterator it=s.begin(); it!=s.end(); it++){
		t++;
		if(t==n){
			printf("%lld\n",*it);
			break;
		}
	}
    return 0;
}

点赞0

评论

进阶的柯南进阶的柯南

AC做法：

#include <bits/stdc++.h>
using namespace std;
int p2=1,p3=1,p5=1,a[1505]={0,1},x,n;
int min3(int a,int b,int c){
	if (a<=b)
	  if (a<=c)
	    return a;
	  else
	    return c;
   else if (b<=c) 
          return b;
        else  return c;	    
}
int main(){
    cin>>n;
	for (int i=2;i<=n;i++){
		x=min3(2*a[p2],3*a[p3],5*a[p5]);
		a[i]=x;
		if (x==2*a[p2])  p2++; 
		if (x==3*a[p3])  p3++;
		if (x==5*a[p5])  p5++;
	}
	printf("%d",a[n]);
	return 0;
}

点赞0

评论