蓝桥杯倒计时 | 倒计时17天

作者🕵️‍♂️:让机器理解语言か

专栏🎇:蓝桥杯倒计时冲刺

描述🎨:蓝桥杯冲刺阶段,一定要沉住气,一步一个脚印,胜利就在前方!

寄语💓:🐾没有白走的路,每一步都算数!🐾

 题目一:22年省赛A题——小兰做实验 (难度:★★)

小蓝做实验 - 蓝桥云课 (lanqiao.cn)

问题描述

小蓝很喜欢科研, 他最近做了一个实验得到了一批实验数据, 一共是两百 万个正整数。

如果按照预期, 所有的实验数据 x 都应该满足 10^7\leqslant x \leqslant 10^8。但是做实验都会有一些误差, 会导致出现一些预期外的数据, 这种误差数据 y 的 范围是 110^3\leq y\leq10^{12} 。由于小蓝做实验很可靠, 所以他所有的实验数据中 99.99% 以上都是符合预期的。小蓝的所有实验数据都在 primes.txt 中, 现 在他想统计这两百万个正整

数中有多少个是质数, 你能告诉他吗?

答案提交

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

【思路】 

三个考点:

  1. 读文件。文件有200万个整数,只能读文件,不能复制到代码中。
  2. 素数判断。判断x是否为素数,可以把它除以[2, sqrt(x)]内的素数,如果能整除就不是素数。
  3. 素数筛,预处理出素数。文件里99.99%的整数都< 10^8,所以只要得到10^4内的素数即可。约1300个素数。其他0.01%的大于10^8的数,数量很少,可以单独判断。

 计算量:1300×200万。
Python代码实际运行时间:约1分钟。

【代码】

注意:在IDLE运行时,代码和文件必须在同一个文件夹内。

from math import *

def E_sieve(n):     # 得到10^4以内的素数
  for i in range (2,int (sqrt (n)+1)):
    if not vis[i]:
      for j in range(i*i, n+1,i):
        vis[j] =1
  k = 0 
  for i in range(2,n+1):#存素数
    if not vis[i]:
      prime[k] = i
      k += 1
    return k

def is_prime(x):  # 判断素数:若n是素数,返回true
  if x == 1: return False #1不是素数
  for i in range(k):
    if x % prime[i] == 0: return False #不是素数
  return True     #是素数

cnt = 0
N = int(1e4)
prime =[0]*N
vis =[0]*N
n = int(1e4)
k = E_sieve(n-1)
print(k)    #质数个数
with open ('primes.txt','r') as f:    # 读取文件
  for a in f:
    b=int(a.rstrip())                 #去掉末尾的\n,转为整数
    if b<=int(1e8):
      if is_prime(b)==True:cnt +=1
      #else:#单独判断大于1e8的数字
print(cnt)

题目二:22年省赛B题——火柴棒数字 (难度:★★★) 

火柴棒数字 - 蓝桥云课 (lanqiao.cn)

问题描述

小蓝最近迷上了用火柴棒拼数字字符, 方法如下图所示:

他只能拼 0 至 9 这十种数字字符, 其中每个数字字符需要的火柴棒的数目 依次是: 6,2,5,5,4,5,6,3,7,6 。他不喜欢重复拼同一个数字字符, 所以对于每个 数字字符他最多拼十个。小蓝会把拼出来的数字字符组合在一起形成一个整数, 例如对于整数 345 , 需要的火柴棒的数目为 5+4+5=14 根。小蓝有 300 根 火柴棒, 他想知道自己能拼出的最大整数是多少? 可以不使用完这 300 根火柴 棒, 可以有多余的火柴棒剩下。

答案提交

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

【思路】 

将数字看成价值为1各有10个的物品需要的火柴棒看成重量,这是多重背包问题。因为是填空题,没有用滚动数组优化和二进制优化。

  • 为什么每个数字价值都为1?

答:因为位数越大,这个整数就越大,最大的整数肯定是位数最多的。(例如:9999<10000),每个数字都相当于给你增加了一位数, 所以每个数字价值都为1。

  •  位数相同(价值相同)时,怎么选择?

数字是从小到大装进dp[ ][ ],为了拼出最大的整数,所以输出最大整数时应该按数字i从大到小考虑。当位数相同的时候就选择装了更多数字i的dp,因为装了更多数字i的dp肯定比装了较少的数字i的dp,最后拼出的整数更大。

  • 定义状态dpli][j]:表示把前i个数字装进容量j的背包,能装进背包的最大价值。

【代码】 

N = 300                           # 背包容量
W =[0,6,2,5,5,4,5,6,3,7,6]        # 每种火柴的重量
dp = [[0]*301 for i in range(11)]
for i in range(1,11):             # 遍历所有数字:数字0为1,数字1为2,以此类推。
  for k in range(0,11):           # 每个数字最多有10个,每个价值为1
    for j in range(k * W[i],301): # 枚举背包容量
      dp[i][j] = max(dp[i-1][j], dp[i - 1][j - k * W[i]] + k) # 不装或装第i个数的两种情况取最大值
j=300
for i in range(10,0,-1):    # 遍历所有数字,数字9为10,数字8为9,以此类推
  k= 0 
  # 在最大价值下(dp[i][j])最多能装k个数字i
  for g in range(0,11):     # 遍历每种数字的数量
    if j-g*W[i]>=0:         # 背包放得下
      if (dp[i][j] == dp[i - 1][j - g * W[i]] + g): # 位数(最大价值)相同时,能否装下g个数字i
        k = g         # 记录最多能装k个
  j = j - k * W[i]    # 背包剩余容量
  while k > 0:        # 装了这个数字k个,就输出k个这个数字
    k -= 1
    print(i - 1, end='') 
# 答案:9999999999777777777755555555554444444444333333333322222222221111

题目三:22年省赛C题——近似GCD (难度:★★★)

问题描述

小蓝有一个长度为 n 的数组 A=(a1​,a2​,⋯,an​), 数组的子数组被定义为从原数组中选出连续的一个或多个元素组成的数组数组的最大公约数指的是数组中所有元素的最大公约数。如果最多更改数组中的一个元素之后, 数组的最大公约数为 g, 那么称 g 为这个数组的近似 GCD。一个数组的近似 GCD 可能 有多种取值

具体的, 判断 g 是否为一个子数组的近似 GCD 如下:

  1. 如果这个子数组的最大公约数就是 g, 那么说明 g 是其近似 GCD。

  2. 在修改这个子数组中的一个元素之后 (可以改成想要的任何值), 子数组的最大公约数为 g, 那么说明 g 是这个子数组的近似 GCD。

小蓝想知道, 数组 A 有多少个长度大于等于 2 的子数组满足近似 GCD 的 值为 g 

输入格式

输入的第一行包含两个整数 n,g, 用一个空格分隔, 分别表示数组 A 的长 度和 g 的值。

第二行包含 n 个整数 a1​,a2​,⋯,an​, 相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数表示数组 A 有多少个长度大于等于 2 的子数组的近 似 GCD 的值为 g 。

样例输入

5 3
1 3 6 4 10

样例输出

5

样例说明

满足条件的子数组有 5 个:

[1,3]: 将 1 修改为 3 后, 这个子数组的最大公约数为 3 , 满足条件。

[1,3,6]: 将 1 修改为 3 后, 这个子数组的最大公约数为 3 , 满足条件。

[3,6]:这个子数组的最大公约数就是 3 , 满足条件。

[3,6,4] : 将 4 修改为 3 后, 这个子数组的最大公约数为 3 , 满足条件。

[6,4] : 将 4 修改为 3 后, 这个子数组的最大公约数为 3 , 满足条件。

评测用例规模与约定

对于 20%20% 的评测用例, 2≤n≤10^2 ;

对于 40%40% 的评测用例, 2≤n≤10^3;

对于所有评测用例, 2≤n≤10^51≤g,ai​≤10^9 。

n最大是 10^5,所以最多只能用O(nlogn)的算法。

【思路】 

题解
一个子数组a:

  • 若a中每一项都是g的倍数,只需要将a中某个元素改为g,满足要求。
  • 若a中存在一个不是g的倍数,把它改为g,满足要求。
  • 若a中存在至少2个不是g的倍数,无法满足要求。

问题变成:求原数组有多少个子数组满足这个数组里最多只有一个元素不是g的倍数编码

用双指针遍历原数组                        双指针复杂度:O(n)

【代码】 

        技巧1:用last标记当前的不满足g的倍数的点,下次a[i]再次不满足g的倍数时,j直接跳到last往后一点,确保只有一个不是g的倍数

        技巧2: 每次i移动一步就记录一下双指针的距离(即满足要求的子数组个数),然后将它们累加起来,就是所有满足要求的子数组个数

n,g=map(int,input().split())
a=[0]+list(map(int,input().split()))
ans=0
last=0
j=1
for i in range(1, n+1):    # 前指针往前走
  if a[i]%g != 0:          # 不满足g的倍数
    j = last+1             # 后指针往前走
    last = i               # last标记不满足点,下次a[i]再次不满足g的倍数,j直接跳到last往后一点
  if i-j+1 >= 2:ans += i-j    # 长度大于2就开始累加
print(ans)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/3857.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

将一段数字转为字符串

将一段数字转为字符串 string turn(long long x){string str;while(x){int tx%10;// 数字0的ascii码为48&#xff01;char ct48;strc;// string类拼接方式x/10;}reverse(str.begin(),str.end()); // 不要忘了反转字符串return str; }例: #include<iostream> #include&l…

使用VS Code 配置Ubuntu远程C++开发环境

使用VS Code 配置Ubuntu远程C开发环境 环境准备 VS CodeWSL Ubuntu 虚拟机 配置步骤 在Ubuntu 中配置ssh远程登录 Ubuntu 配置远程登录 VsCode 安装 Remote-ssh 插件 打开vscode ssh configure ,填入相关信息 ​ Host : 主机名称&#xff0c;在左侧列表中显示的名称 ​ …

【Linux】[万字] Linux下的文件操作 及 Linux文件描述符fd 详解

在Linux操作系统中, 文件描述符是一个至关重要的概念. 理解了文件描述符, 其实就可以相当于理解了Linux系统的关于内存文件系统的整个大致框架和逻辑 但是在介绍文件描述符之前, Linux关于文件还存在许多 概念和文件操作 的知识需要介绍一下, 就当作是为解释文件描述符所做的…

IDEA连接Linux服务器进行文件操作

IDEA连接Linux服务器进行文件操作 文章目录IDEA连接Linux服务器进行文件操作连接的作用和意义安装openssh开启openssh服务验证是否开启服务安装网络工具包查看虚拟机IP地址Idea连接Linux虚拟机打开配置页面配置SFTP配置SSH完成后出现的配置文件安装big data tools插件连接的作用…

【RV1126】调试GT911,1024x600 7寸 MIPI 电容触摸屏

文章目录一、驱动注册失败二、触摸屏可以触摸&#xff0c;但是x轴数据反了三、可以触摸了&#xff0c;但是Y轴数据跳变&#xff0c;几乎只有一半的屏幕是可以正常滑动的三、汇顶触摸屏配置文件解析四、使用新的配置文件4.1 新配置解决问题4.2 测试触摸的方法在kernel增加frame …

【学习经验分享NO.21】学习资料分享(持续更新)

本博客将收集整理人工智能深度学习相关资料&#xff0c;进行整理&#xff0c;供大家学习使用。如果有需要帮忙整理的请留言。将不断更新&#xff0c;请持续关注。 一、深度学习论文资料 链接&#xff1a;https://pan.baidu.com/s/18LO5df0dp9-IE8Z3aFyrPg 提取码&#xff1a;c…

记录springboot+vue+fastdfs实现简易的文件(上传、下载、删除、预览)操作

前言说明&#xff1a;springboot vue FastDFS实现文件上传&#xff08;支持预览&#xff09;升级版 FASTDFS部分 FASTDFS安装过程&#xff1a;基于centos 7安装FastDFS文件服务器 SpringBoot部分 springboot源码实现 package com.core.doc.controller;import com.baomid…

【多线程】CAS

✨个人主页&#xff1a;bit me&#x1f447; ✨当前专栏&#xff1a;Java EE初阶&#x1f447; 目 录&#x1f40d;一. 什么是 CAS&#x1f98e;二. CAS 是怎么实现的&#x1f996;三. CAS 典型应用场景&#x1f436;1. 实现原子类&#x1f431;2. 实现自旋锁&#x1f995;四. …

进程间通信----信号量

文章目录信号量1. 问题2. 什么是信号量3. 信号量的使用4. 信号量的控制6. 实例信号量 1. 问题 程序中&#xff0c;有时存在一种特殊代码&#xff0c;最多只允许一个进程执行该部分代码。这部分区域&#xff0c;称为“临界区” 然而在多进程并发执行时&#xff0c;当一个进程进…

Pseudo-completeness(前中序遍历确定后序遍历)

题目链接&#xff1a;题目详情 - 7-16 Pseudo-completeness (pintia.cn) 样例1输入&#xff1a; 7 4 2 5 1 6 3 7 1 2 4 5 3 6 7样例1输出&#xff1a; 1 4 5 2 6 7 3 1样例2输入&#xff1a; 10 8 4 9 2 10 5 1 6 3 7 1 2 4 8 9 5 10 3 6 7样例2输出&#xff1a; 2 8 9 4…

启动容器(后台模式)

使用以下命令创建一个以进程方式运行的容器 rootLAPTOP-B38J348H:~# docker run -d ubuntu:15.10 /bin/sh -c "while true; do echo hello world ; sleep 1; done" 在输出中&#xff0c;我们没有看到期望的 "hello world"&#xff0c;而是一串长字符 f7…

IDEA的全新UI可以在配置里启用了,快来试试吧!

刚看到IDEA官方昨天发了这样一条推&#xff1a;IDEA的新UI可以在2022.3版本上直接使用了&#xff01;开启方法如下&#xff1a;打开IDEA的Setting界面&#xff0c;在Appearance & Behavior下有个被标注为Beta标签的New UI菜单&#xff0c;具体如下图&#xff1a;勾选Enable…

ChartGPT多重插补法 填充缺失点

问题描述已知时间戳与对应的值&#xff0c;需要根据时间戳找到缺失的点&#xff0c;然后进行值的填充。例如&#xff1a;源码<!-- https://mvnrepository.com/artifact/org.apache.commons/commons-math3 --><dependency><groupId>org.apache.commons</gr…

【微信小程序】-- uni-app 项目-- 配置 tabBar 效果(五十一)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…

【C++进阶】智能指针

文章目录为什么需要智能指针&#xff1f;内存泄漏什么是内存泄漏&#xff0c;内存泄漏的危害内存泄漏分类&#xff08;了解&#xff09;如何避免内存泄漏智能指针的使用及原理smart_ptrauto_ptrunique_ptrshared_ptr线程安全的解决循环引用weak_ptr删除器为什么需要智能指针&am…

HJZS电源监视继电器HJZS-E202 AC220V

系列型号&#xff1a; HJZS-E202断电延时继电器 HJZS-E002断电延时继电器 一 应用 HJZS-E202电源监视继电器用于直流或交流操作的各种保护和自动控制的装置中&#xff0c;用以增加触点数量。 二 安装结构 导轨安装9壳体结构&#xff0c;具体尺寸参阅外型尺寸图。 三 产品型号…

蓝桥杯刷题冲刺 | 倒计时14天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.最长递增2.走迷宫3.解立方根4.回文特判5.修改数组1.最长递增 题目 链接&#xff1a; 最长递增…

【Java版oj 】 day17杨辉三角形的变形、计算某字符出现次数

目录 一、杨辉三角形的变形 &#xff08;1&#xff09;原题再现 &#xff08;2&#xff09;问题分析 &#xff08;3&#xff09;完整代码 二、计算某字符出现次数 &#xff08;1&#xff09;原题再现 &#xff08;2&#xff09;问题分析 &#xff08;3&#xff09;完整代…

Python调用GPT3.5接口的最新方法

GPT3.5接口调用方法主要包括openai安装、api_requestor.py替换、接口调用、示例程序说明四个部分。 1 openai安装 Python openai库可直接通过pip install openai安装。如果已经安装openai&#xff0c;但是后续提示找不到ChatCompletion&#xff0c;那么请使用命令“pip instal…

【ArcGIS Pro二次开发】(18):地理处理工具类【Geoprocessing】补遗

ArcGIS Pro SDK 3.0中的Geoprocessing类是用于执行地理处理工具的核心类。地理处理工具是用于执行空间分析、数据转换、数据管理等任务的工具集&#xff0c;包括常见的空间分析工具、栅格处理工具、矢量处理工具、地图制图工具等。 之前有简单记录了下Geoprocessing工具的用法…