第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-51算法训练 Torry的困惑(基本型)

简介: 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-51算法训练 Torry的困惑(基本型)

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-51算法训练 Torry的困惑(基本型)


前言

       这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍,让大家方便去搜索,所有题目都会有几种语言的写法,帮助大家提供一个思路,当然,思路只是思路,千万别只看着答案就认为会了啊,这个方法基本上很难让你成长,成长是在思考的过程中找寻到自己的那个解题思路,并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练,如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢,这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来,所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式,说着听绕口,但是就是靠量来堆叠思维方式,刷题方案自主定义的话肯定就是从非常简单的开始,稍微对数据结构有一定的理解,暴力、二分法等等,一步步的成长,数据结构很多,一般也就几种啊,线性表、树、图、再就是其它了。顺序表与链表也就是线性表,当然栈,队列还有串都是属于线性表的,这个我就不在这里一一细分了,相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的,例如三分枚举、离散化,图,复杂数据结构还有统计都是不考的,我们找简单题刷个一两百,然后再进行中等题目的训练,当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠,慢慢的就会掌握各种规律,有了规律就能大胆的长一些难度比较高的题目了,再次说明,刷题一定要循序渐进,千万别想着直接就能解决难题,那只是对自己进行劝退处理。加油,平常心,一步步前进。


算法训练 Torry的困惑(基本型)

资源限制

内存限制:512.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s

问题描述

  Torry从小喜爱数学。一天,老师告诉他,像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题,前10、100、1000、10000……个质数的乘积是多少呢?他把这个问题告诉老师。老师愣住了,一时回答不出来。于是Torry求助于会编程的你,请你算出前n个质数的乘积。不过,考虑到你才接触编程不久,Torry只要你算出这个数模上50000的值。

输入格式

  仅包含一个正整数n,其中n<=100000。

输出格式

  输出一行,即前n个质数的乘积模50000的值。

样例输入

1

样例输出

2

题解:这个题目难度在于超大数的处理。

C语言

#include<stdio.h>
int pr[100010];
int top;
int isPrime(int n)
{
  int i;
  for(i = 0; i < top; i++)
  {
    if(n % pr[i] == 0)
    {
      return 0;
    }
  }
  return 1;
}
int findNextPrime(void)
{
  int n = pr[top - 1] + 1;
  while(!isPrime(n))
  {
    n++;
  }
  pr[top++] = n;
  return n;
}
int main(void)
{
  int i, n;
  int result = 2;
  scanf("%d", &n);
  pr[0] = 2;
  top = 1;
  for(i = 1; i < n; i++)
  {
    int x = findNextPrime();
    result *= x;
    result %= 50000;
  }
  printf("%d", result);
  return 0;
}

C++语言

#include <iostream>
using namespace std;
int a[100005];
int main()
{
  unsigned int i, j, n, cnt = 1, cj = 2;
  cin >> n;
  if (n == 1)
  {
    cout << 2 << endl;
    return 0;
  }
  a[0] = 2;
  for (i = 3; i < 2000000; i++)
  {
    for (j = 0; j < cnt; j++)
    {
      if (a[j] * a[j] > i)
      {
        break;
      }
      else
      {
        if (!(i % a[j]))
        {
          break;
        }
      }
    }
    if (a[j] * a[j] > i)
    {
      a[cnt++] = i;
      cj = (cj % 50000) * (i % 50000) ;
      if (cnt == n)
      {
        break;
      }
    }
  }
  cout << cj % 50000 << endl;
  return 0;
}

Java语言

计算起来还是非常的麻烦。

import java.io.*;
public class Main {
  public static void main(String[] args) {
    try{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in),1);
      String line = br.readLine();
      int n = Integer.parseInt(line);
      getans(n);
    }catch(Exception e){
      System.out.println("Message:"+e.getMessage());
    }   
  }
  
  public static void getans(int n){
    if(n<1);
    else if(n==1)System.out.println(2);
    else if(n<7){
      long ans = 6,nowp = 3;
      for(int i=0;i<n-2;i++){
        nowp=nextprime(nowp);
        ans*=nowp;
      }
      System.out.println(ans);
    }else if(n==7)System.out.println(10510);
    else if(n<100){
      long ans = 10510,nowp = 17;
      for(int i=0;i<n-7;i++){
        nowp=nextprime(nowp);
        ans=ans*nowp%50000;
      }
      System.out.println(ans);
    }else if(n==100)System.out.println(31090);
    else if(n<1000){
      long ans = 31090,nowp = 541;
      for(int i=0;i<n-100;i++){
        nowp=nextprime(nowp);
        ans=ans*nowp%50000;
      }
      System.out.println(ans);
    }else if(n==1000)System.out.println(1570);
    else if(n<=10000){
      long ans = 1570,nowp = 7919;
      for(int i=0;i<n-100;i++){
        nowp=nextprime(nowp);
        ans=ans*nowp%50000;
      }
      System.out.println(ans);
    }else if(n==10000)System.out.println(48410);
    else if(n<100000){
      long ans = 48410,nowp = 115321;
      for(int i=0;i<n-100;i++){
        nowp=nextprime(nowp);
        ans=nowp%50000*ans%50000;
      }
      System.out.println(ans);
    }else if(n==100000)System.out.println(20710);
    else{
      long ans = 20710,nowp = 1452433;
      for(int i=0;i<n-100;i++){
        nowp=nextprime(nowp);
        ans=nowp%50000*ans%50000;
      }
      System.out.println(ans);
    }
  }
  
  public static long nextprime(long now){
    now+=2;
    int check = 0;
    while(true){
      check = checkprime(now);
      if(check==0)
        now+=2;
      else
        break;
    }
    return now;
  }
  
  public static int checkprime(long n){
    for(int i=3;i<=Math.sqrt(n);i+=2)
      if(n%i==0)return 0;
    return 1;
  }
  
}

Python语言

Python去掉了数据类型的处理,相对来说还是代码简洁一些的。

n=eval(input())
num=1
i=2
count=0
while True:
    flag=0
    for j in range(2,i):
        if i%j==0:
            flag=1
            break
    if flag==0:
        count+=1
        if num>50000:
            num%=50000
        num*=i
    if count==n:
        print(num%50000)
        break
    i+=1

总结

没有什么不付出就能拿到的结果,我们都是在负重前行,最终结果与自身先天的脑力有一定的关系,但是还是有很大一部分看自己后天的努力,其实从报名到比赛也就5个月左右,真正刷题的事件也就2个月,2个月回忆一下你真正的认真刷过题吗,如果你真的用尽所有的精力去努力了,那么我相信你最终的成绩一定会让你满意的,加油。

没有什么不付出就能拿到的结果,我们都是在负重前行,最终结果与自身先天的脑力有一定的关系,但是还是有很大一部分看自己后天的努力,其实从报名到比赛也就5个月左右,真正刷题的事件也就2个月,2个月回忆一下你真正的认真刷过题吗,如果你真的用尽所有的精力去努力了,那么我相信你最终的成绩一定会让你满意的,加油。


相关文章
|
5月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
94 0
|
3天前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
4月前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
42 3
|
3天前
|
算法 C++
【算法解题思想】动态规划+深度优先搜索(C/C++)
【算法解题思想】动态规划+深度优先搜索(C/C++)
|
4月前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
37 2
|
5月前
|
存储 算法 Java
蓝桥杯递归算法
蓝桥杯中的递归算法涉及将问题分解为子问题,通过函数自身调用来求解。优点是简洁易懂,但效率低且可能引发栈溢出。示例包括:数组求和、数的阶乘、斐波那契数列及最大公约数计算,以及字符串翻转。代码展示了各种递归场景的Java实现,如`f3`计算数组和,`f`求阶乘,`f1`计算斐波那契数,`f2`找最大公约数,和`f1`字符串反转。
33 1
|
4月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
5月前
|
算法 安全
死锁相关知识点以及银行家算法(解题详细步骤)
死锁相关知识点以及银行家算法(解题详细步骤)
125 2
|
4月前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
31 0
|
5月前
|
算法 安全 定位技术
【刷题】备战蓝桥杯 — dfs 算法
dfs算法在数据较小的情况下可以使用。 一定一定要确定好终止条件,避免栈溢出。 相应做好回溯,保证每次的遍历都是不一样的选择,避免少结果。 针对题目进行对应细节处理,有能力的话可以进行剪枝优化!!!
45 0