【刷题】2023年第十四届蓝桥杯大赛软件类省赛C/C++大学A组真题

蓝桥杯2023年第十四届省赛真题-平方差 - C语言网 (dotcpp.com)

 初步想法,x = y2 − z2=(y+z)(y-z)

即x=a*b,a=y+z,b=y-z

2y=a+b

即a+b是2的倍数就好了。

即x存在两个因数之和为偶数就能满足条件。

但时间是(r-l)*x,数据1e9,直接T了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
map<int,int> mp;
int cnt;bool judge(int  x)
{for(int i=1;i<=x;i++)//找两个因数 {if(x%i!=0) continue;int d=x/i+i;if(d%2==0||x==1)//说明是整数 {return true; } }return false;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int l,r;cin>>l>>r; for(int i=l;i<=r;i++){if(judge(i)) cnt++; }cout<<cnt;return 0;
}

运行结果:

进一步分析:

根据题意多写几个,不难发现奇数似乎都能拆成y2 − z2的形式?因此,我们从奇偶的角度来找规律。

(这个地方写错了,是\left ( k+1 \right )^{^{2}}-\left ( k \right )^{^{2}}

那么,在这里就可以得出结论辣。想要数字能表示成y2-z2的形式,只有两种可能:

1.奇数   2.4的倍数

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int cnt;signed main()
{int l,r;cin>>l>>r; for(int i=l;i<=r;i++){if(i%2) cnt++;if(i%4==0) cnt++;}cout<<cnt;return 0;
}

 (这一步还不能过属实有点钻牛角尖了。。。。。

但是好在,已知一个数x,对应的奇数、4的倍数的数的个数是可以算出来的。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int cnt;
signed main()
{int l,r;cin>>l>>r; int d=(l-1)/2;if((l-1)%2==0) d--;int p=l/4;if((l%4)==0) p--;cnt=(r-1)/2-d+r/4-p;cout<<cnt;return 0;
}

蓝桥杯2023年第十四届省赛真题-更小的数 - C语言网 (dotcpp.com)

 暴力

思路:

任取子串起点为i,终点为j。

然后运用双指针算法对子串进行判断。如果两边相等就往中间走。如果左边大了,说明这个子串反转后会变小;如果右边大了,说明这个子串反转后会变大。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
string x;
int cnt;signed main()
{cin>>x;for(int i=0;i<x.length();i++){for(int j=i+1;j<x.length();j++){int l=i,r=j;while(l<=r){if(x[l]<x[r]) break;if(x[l]>x[r]){cnt++;break;}else l++,r--;}}}cout<<cnt;return 0;
}

 暴力做法没想到在这个平台上直接过了,于是换了个平台P2070 - [蓝桥杯2023初赛] 更小的数 - New Online Judge (ecustacm.cn)

果然时间超限。。 

 

DP

上面是三重循环,能想到的就是优化最后那一层while循环。

如果左边大了,说明这个子串反转后会变小;如果右边大了,说明这个子串反转后会变大。如果两边相等就l++,r--,这就意味着这种情况下当前这个字串的状态可以由较小的那一层决定。我们就可以想到DP。

稍微画一下就可以理解,dp[i][j]由dp[i+1][j-1]得到,因此最外面一层循环我们要从大到小,里面一层顺序无所谓,因为先得到dp[i+1][j]还是dp[i+1][j-1]对dp[i][j]没有任何影响。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
string x;
int cnt;
int dp[N][N];signed main()
{cin>>x;for(int i=x.length()-1;i>=0;i--){for(int j=i+1;j<x.length();j++){if(i>=j) continue;if(x[i]>x[j]) dp[i][j]=1;else if(x[i]==x[j]) dp[i][j]=dp[i+1][j-1];cnt+=dp[i][j];}}cout<<cnt;return 0;
}

 蓝桥杯2023年第十四届省赛真题-颜色平衡树 - C语言网 (dotcpp.com)

暂时能力达不到。。。。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【算法挨揍日记】day06——1004. 最大连续1的个数 III、1658. 将 x 减到 0 的最小操作数

1004. 最大连续1的个数 III 1004. 最大连续1的个数 III 题目描述&#xff1a; 给定一个二进制数组 nums 和一个整数 k&#xff0c;如果可以翻转最多 k 个 0 &#xff0c;则返回 数组中连续 1 的最大个数 。 解题思路&#xff1a; 首先题目要我们求出的最多翻转k个0后&#x…

2023华为杯数模C题——大规模创新类竞赛评审方案研究

B题——大规模创新类竞赛评审方案研究 思路&#xff1a;采用数据分析等手段改进评分算法性能 完成情况(1-2问已经完成) 代码下载 问题一 在每个评审阶段&#xff0c;作品通常都是随机分发的&#xff0c;每份作品需要多位评委独立评审。为了增加不同评审专家所给成绩之间的可比…

Android ANR日志分析

会造成ANR的场景&#xff1a; Service Timeout&#xff1a;前台服务在20s内未执行完成&#xff0c;后台为200s&#xff1b; BroadcastQueue Timeout&#xff1a;前台广播在10s内未执行完成&#xff0c;后台为60s&#xff1b; ContentProvider Timeout&#xff1a;内容提供者在…

SAP Oracle表空间扩展技术手册

1、DBACOCKPIT下查看表空间 当表空间不足(达到99%)时,需要按以下步骤扩充表空间(每次扩充20000M,20G): (也可以通过DB13,DB02查看表空间) 新浪博客 Tablespace PSAPSR3 is 100% used | SAP Community Oracle是通过增加数据文件的方式来为表空间扩容。为指定表空间增…

BST搜索二叉树

目录 二叉搜索树概念 ​编辑 1 二叉搜索树的构建 2. 二叉搜索树的删除 3二叉搜索树中放入元素 4. 二叉搜索树中元素的删除 5. 二叉搜索树中元素的遍历 6 二叉搜索树中元素的查找 7二叉搜索树的拷贝构造 二叉搜索树概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一…

WeCanStudio工具套件介绍

直接上视频,在超燃的《天马座幻想》的背景音乐下&#xff0c;再次了解一下该工具套件吧。 WeCanStudio开发套件介绍

LeetCode(力扣)96. 不同的二叉搜索树Python

LeetCode96. 不同的二叉搜索树 题目链接代码 题目链接 https://leetcode.cn/problems/unique-binary-search-trees/description/ 代码 class Solution:def numTrees(self, n: int) -> int:dp [0] * (n 1)dp[0] 1for i in range(1, n 1):for j in range(1, i 1):dp[…

基于华为云云耀云服务器L实例开展性能评测|MySQL性能测评

基于华为云云耀云服务器L实例开展性能评测&#xff5c;MySQL性能测评 1. 测试环境介绍2. 测试环境搭建3. 测试工具3.1. mysqlslap3.2. sysbench 1. 测试环境介绍 随着云计算时代的进一步深入&#xff0c;越来越多的中小企业企业与开发者需要一款简单易用、高能高效的云计算基础…

C++核心编程——P45-52继承

继承 继承是面向对象三大特性之一 有些类与类之间存在特殊的关系&#xff0c;例如下图中: 我们发现&#xff0c;定义这些类的时候&#xff0c;下级别的成员除了拥有上一级的共性&#xff0c;还有自己的特性。 这时候我们就可以考虑利用继承的技术&#xff0c;减少重复代码量…

【一、虚拟机vmware安装】

安装虚拟机 下载 官方下载地址&#xff1a;https://www.vmware.com/cn.html 大概流程就是&#xff0c;最重要的事最后一步

【WSN】基于蚁群算法的WSN路由协议(最短路径)消耗节点能量研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

【初阶数据结构】二叉树全面知识总结

二叉树详解 树的概念及其结构树的概念树的相关概念树的表示方法孩纸兄弟表示法双亲表示法&#xff08;并查集&#xff09; 树的实际应用 二叉树二叉树的概念二叉树的种类二叉树的性质二叉树的存储结构 二叉树顺序结构的实现堆的概念及结构堆向上、向下调整法堆的插入堆的删除堆…

YOLOv5如何训练自己的数据集

文章目录 前言1、数据标注说明2、定义自己模型文件3、训练模型4、参考文献 前言 本文主要介绍如何利用YOLOv5训练自己的数据集 1、数据标注说明 以生活垃圾数据集为例子 生活垃圾数据集&#xff08;YOLO版&#xff09;点击这里直接下载本文生活垃圾数据集 生活垃圾数据集组成&…

[Linux入门]---初识冯诺依曼体系

文章目录 1.背景知识2.冯诺依曼体系结构 1.背景知识 冯诺依曼&#xff08;John von Neumann&#xff09;&#xff0c;被称为“计算机之父”&#xff0c;确定了计算机的体系结构——即“冯诺依曼结构”&#xff1b;我们常见的计算机&#xff0c;如笔记本。我们不常见的计算机&am…

蓝桥杯每日一题2023.9.23

4961. 整数删除 - AcWing题库 题目描述 分析 注&#xff1a;如果要进行大量的删除操作可以使用链表 动态求最小值使用堆&#xff0c;每次从堆中取出最小值的下标然后在链表中删除 注意long long 代码解释&#xff1a; while(k --){auto t q.top();q.pop();res t.first;i…

经典题记录 字符串相加/相乘

1. LeetCode 415 字符串相加 代码一&#xff1a;代码简短&#xff0c;但需要借助额外的一个string来保存结果&#xff0c;更占用内存。 class Solution { public:string addStrings(string num1, string num2) {string ans"";int size1num1.size();int size2num2.si…

qt 6知识集

1.Use multi-arg instead [clazy-qstring-arg] 存在过个arg&#xff0c;连写形式如下&#xff1a; QString("%1 %2").arg(a).arg(b);QString("%1 %2").arg(a, b); // one less temporary heap allocation详见参考文献[1]。 2.widget运行后正常打开却看不…

基于Java的酒店管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…

Three.js后期处理简明教程

后期处理&#xff08;Post Processing&#xff09;通常是指对 2D 图像应用某种效果或滤镜。 在 THREE.js 中我们有一个包含一堆网格物体的场景。 我们将该场景渲染为 2D 图像。 通常&#xff0c;该图像会直接渲染到画布中并显示在浏览器中&#xff0c;但我们可以将其渲染到渲染…

双向链表的实现(增删查改)——最好理解的链表

双向链表的实现 一&#xff0c;双向链表的特点二&#xff0c;双向链表的结构三&#xff0c;双向链表的内容实现3.1创建node节点3.2初始化3.3打印3.4插入3.4.1尾插3.4.2头插3.4.3在pos位置上插入 3.5删除3.5.1尾删3.5.2头删3.5.3删除pos位置上的数据 四&#xff0c;调试技巧&…