算法竞赛入门【码蹄集进阶塔335题】(MT2271-2275)

这篇具有很好参考价值的文章主要介绍了算法竞赛入门【码蹄集进阶塔335题】(MT2271-2275)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法竞赛入门【码蹄集进阶塔335题】(MT2271-2275)



前言

个数,如果这个数是他喜欢的数,那么告诉他下一个他喜欢的数是多少(即大于这个数的,云曦算法,算法,c++,数据结构,码蹄集

为什么突然想学算法了?

> 用较为“官方”的语言讲,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言,是因为当下快到了考研和找工作的年纪(ಥ_ಥ),无论走哪一条路,都不免需要一些相对丰富的算法知识,是故,便产生了一个暑假速成算法的计划,可能对于像我这种算法竞赛小白而言,几乎很难,但我仍然还是想尝试一下,毕竟,梦想还是要有的,万一实现了呢?~( ̄▽ ̄~)~

个数,如果这个数是他喜欢的数,那么告诉他下一个他喜欢的数是多少(即大于这个数的,云曦算法,算法,c++,数据结构,码蹄集


为什么选择码蹄集作为刷题软件?

码蹄集,是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的,其依托全国各大名校计算机系和清华大学出版社等单位的强大资源,旨在为计算机学习爱好者提供全面和权威的计算机习题。
个数,如果这个数是他喜欢的数,那么告诉他下一个他喜欢的数是多少(即大于这个数的,云曦算法,算法,c++,数据结构,码蹄集


目录

1. MT2271 完全立方数3

(1)题目描述
给定n,求不大于n的所有素数的立方和。

格式

输入格式: 一个整数n 。
.
输出格式: 一个数表示答案。

样例1

输入: 3
.
输出: 8

备注:

其中: n≤100000。

(2)参考代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

bool isprime(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0)  return false;
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    long long ans = 0;
    for(int i=2;i<=n;i++){
        if(isprime(i)){
            ans += (long long)(i)*i*i;
        }
    }
    printf("%lld\n",ans);

    return 0;
}


2. MT2272 质数率

(1)题目描述

请你求出[1,n]范围内质数占比率。

格式

输入格式: 只有一行,一个整数n,含义如题目描述。
.
输出格式: 输出[1, n]范围内质数占比,保留3位小数。

样例1

输入: 10
.
输出: 0.400

备注:

保证:对于100%的数据:0≤n≤108。

(2)参考代码

#include<bits/stdc++.h> 

using namespace std;

int prime[100000000],cnt,n;
bool vis[100000000];

void init(){
    for(int i=2;i<=n;++i){
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt;++j){
            if(prime[j]*i>n) break;
            vis[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }
}
int main( )
{
    cin>>n;
    init();
    cout<<fixed<<setprecision(3)<<(1.0*cnt/n);
    return 0;
}

3. MT2273 元素共鸣

(1)题目描述
遥远的大陆上存在着元素共鸣的机制。

建立一个一维坐标系,其中只有素数对应的点的坐标存在着元素力,而相距为k的两个元素力之间能形成元素共鸣。现在,需要求出n范围内所有能元素共鸣的点对,并将他们以第一个点的坐标大小为关键字排序后输出(小的在前)


格式

输入格式: 一行两个整数n, k
.
输出格式: 所有小于等于n的素数对。每对素数对输出一行,中间用单个空格隔开。若没有找到任何素数对,输出empty

样例1

输入格式: 6924 809
.
输出格式: 2 811

(2)参考代码

#include<bits/stdc++.h> 

using namespace std;
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int ,int>pii;
const int inf32 = 0x3f3f3f3f;
const ll inf64 = 0x3f3f3f3f3f3f3f3f;

void read(__int128_t &num){
    int f=1;
    num=0;
    char c = getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c = getchar();
    }
    while(c>='0' && c<='9'){
        num = num*10 + (c-'0');
        c=getchar();
    }
    num*=f;
}

void write(__int128_t num){
    if(num<0) putchar('-'),num=-num;
    if(num>9) write(num/10);
    putchar(num%10+'0');
}

const int N = 100000;
bool vis[N+1];
vector<int> primes;
void get_primes(){
    for(int i=2;i<=N;++i){
        if(!vis[i]) primes.emplace_back(i);
        for(int j=0;primes[j] <=N/i;++j){
            vis[primes[j]*i]=true;
            if(!(i%primes[j])) break;
        }
    }
}

void solve(){
    int n,k;
    cin>>n>>k;
    get_primes();
    bool sec = true;
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            if(!vis[i+k]&&i+k<=n){
                sec = false;
                cout<<i<<' '<<i+k<<endl;
            }
        }
    }
    if(sec) cout<<"empty"<<endl;
}
int main( )
{
    solve();
    return 0;
}

4. MT2274 第k小素数

(1)题目描述
已知,自然数范围内,最小的素数是2。现在给定一个正整数k,请问第k 小的素数是多少?请编写函数IsPrime来求解第k小的素数,传入参数k,最后返回第k 小的素数。

提示:由于k会比较大,单纯的使用O(n√n)算法会超时,建议在IsPrime函数中完成素数的线性筛,然后直接返回第k小的素数。


格式

输入格式: 第一行一个整数k(1≤k ≤3000000)。
.
输出格式: 输出第k小的素数。

样例1:

输入: 1
.
输出:2

备注:

1≤k ≤3000000(提示:k取最大时,数组开到50,000,000)。

(2)参考代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxn 50000000
#define false 0
#define true 2
int notprim[maxn];
int prim[maxn];
void init() {
    memset(notprim, false, sizeof(notprim));
    int cnt = 0;
    for (int i = 2; i <= maxn; i++) {
        if (!notprim[i]) prim[cnt++] = i;        //如果是素数直接赋值
        for (int j = 0; j < cnt && i * prim[j] <= maxn; j++) { //如果是合数,将前面所有的素数乘当前i筛去
            notprim[i * prim[j]] = true;
            if (i % prim[j] == 0)    //关键处:如果当前合数中出现前面已经出现的素数就跳出
                break;
        }
    }
}
int main() {
    int k;
    scanf("%d", &k);
    init();
    
    printf("%d", prim[k-1]);
    return 0;
}
/*
简化版的线性筛
*/


5. MT2275 小码哥喜欢的数

(1)题目描述
小码哥不喜欢以下情况的数:
1.是7的倍数(包括7) ;
⒉数字的某一位是7,这种数字的倍数,小码哥也不喜欢。

小码哥会给你t个数,如果这个数是他喜欢的数,那么告诉他下一个他喜欢的数是多少(即大于这个数的下一个他喜欢的数)。如果这个数他不喜欢,那你要告诉他。


格式

输入格式:
第1行,一个正整数T表示小码哥给你的数。
接下来T行,每行1个整数a ,表示这一次小码哥给的数。
.
输出格式:
输出共T行,每行一个整数。如果这个数是他喜欢的数,那么告诉他下一个他喜欢的数是多少(即大于这个数的下一个他喜欢的数);如果这个数他不喜欢,那你要输出-1 ;注:定义0不为小码哥喜欢的数。

样例1

输入格式: 2 3
.
输出格式: 6

备注:

其中: 1≤m ≤le8,1 ≤n ≤1e10

(2)参考代码

#include<bits/stdc++.h> 
/*
思路:不越狱的状态好计算所以:越狱数=总的状态数-不越狱的状态数
其中 总的状态数为:m^n
    不越狱的状态数: m*(m-1)^(n-1) :只有第一个可以选择m个宗教,其他的只能选和前一个不同的宗教所以是m-1种情况
这里计算用了快速幂的方法。
*/
using namespace std;
long long p=1007;
long long qpow(long long x, long long y){
    if(y==0)
        return 1;
    if(y%2==1){
        return qpow(x, y - 1) * x % p;
    }else{
        long long t = qpow(x, y/2) % p;
        return t*t % p;
    }
}
int main( )
{
    long long m,n;
    cin>>m>>n;
    long long ans = qpow(m,n)-(m*qpow(m-1,n-1)%p);
    cout<<(ans+p)%p<<endl;//注意需要+p之后再取 %p,防止有负数
    return 0;
}

结语

感谢大家一直以来的不断支持与鼓励,码题集题库中的进阶塔350题正在逐步更新,之后会逐步跟进星耀,王者的题,尽请期待!!!
同时,也希望这些题能帮助到大家,一起进步,祝愿每一个算法道路上的“苦行僧”们,都能够历经磨难,终成正果,既然选择了这条路,走到了这里,中途放弃,岂不是太过可惜?

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0,供大家更好的进行学习与刷题~( ̄▽ ̄~)~

愿你的结局,配得上你一路的颠沛流离。文章来源地址https://www.toymoban.com/news/detail-724190.html

到了这里,关于算法竞赛入门【码蹄集进阶塔335题】(MT2271-2275)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法竞赛入门【码蹄集进阶塔335题】(MT2126-2150)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2023年04月19日
    浏览(35)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2201-2225)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月08日
    浏览(31)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月06日
    浏览(31)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2076-2100)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2023年04月19日
    浏览(47)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2226-2250)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月11日
    浏览(35)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2291-2295)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月06日
    浏览(31)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2151-2175)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月02日
    浏览(50)
  • 算法竞赛入门【码蹄集新手村600题】(MT1020-1040)

    码蹄集网站地址:https://www.matiji.net/exam/ojquestionlist (1)题目 输入一个实数,第一次按实型输出;第二次保留2位小数输出;第三次保留3位小数但最小列宽8列输出,空格分隔。 格式 样例1 (2)参考代码 (1)题目 输出3.1415926、12345678.123456789的小数、指数形式。 格式 样例1 (

    2024年02月16日
    浏览(42)
  • 算法竞赛入门【码蹄集新手村600题】(MT1280-1300)C语言

    码蹄集网站地址:https://www.matiji.net/exam/ojquestionlist (1)题目 输入正整数N(1500),首先计算其逆序数M(比如12逆序后是21)。然后输出N的M次方的最后3位数。 格式 样例1 (2)参考代码 (1)题目 一个自然数,如果每一位数的位数次幂之和等于该自然数,则称之为Disarium数。 比如

    2024年02月07日
    浏览(41)
  • 供水管线 码蹄集

    首先,题目要求我们去掉一些管道,使得总的管道管理费用最小。在去掉部分管道的情况下,城市之间不再形成一个回路,即城市之间构成了一棵树。因此,我们需要找到一棵生成树,使得所有管道管理费用之和最小。 接下来,我们需要选择合适的算法来寻找最小生成树。常

    2024年02月06日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包