蓝桥杯第十四届C++A组(未完)

【规律题】平方差

题目描述

给定 L, R,问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 x=y^{2}-z^{2}

输入格式

输入一行包含两个整数 L, R,用一个空格分隔。

输出格式

输出一行包含一个整数满足题目给定条件的 x 的数量。

样例输入

1 5

样例输出

4

提示

1=1^{2}-0^{2}

3=2^{2}-1^{2}

4=2^{2}-0^{2}

5=3^{2}-2^{2}

对于 40% 的评测用例,LR ≤ 5000 ;

对于所有评测用例,1 ≤ L ≤ R ≤ 10^9 。


x=y^{2}-z^{2}x=(y+z)*(y-z)

m=(y+z),n=(y-z) ,则x=m*n,解得:y=\frac{m+n}{2},z=\frac{m-n}{2}

要使y和z有整数解,那么(m+n),(m-n) 为偶数,

(1)偶数+偶数=偶数,偶数-偶数=偶数;

(2)奇数+奇数=偶数,奇数-奇数=偶数;

则m和n奇偶性相同,即如果x有一对因子奇偶性相同,那么一定可以找到y,z满足x=y^{2}-z^{2}

(1)若m,n都为偶数,那么m是2的倍数,n是2的倍数,那么m*n一定是4的倍数。

(2)若m,n都为奇数,那么由性质 奇数*奇数=奇数 得,m*n也一定为奇数。

综上 x 是四的倍数或者奇数。


#include<iostream>
#include<cstring>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=10010;
int main(){
	LL L,R;
	cin>>L>>R;
	int cnt=0;
	for(LL i=L;i<=R;i++){
		if(i%4==0||i%2){
			cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}

更小的数

题目描述

蓝桥杯2023年第十四届省赛真题-更小的数

小蓝有一个长度均为 n 且仅由数字字符 0 ∼ 9 组成的字符串,下标从 0 到 n − 1,你可以将其视作是一个具有 n 位的十进制数字 num,小蓝可以从 num 中选出一段连续的子串并将子串进行反转,最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew 满足条件 numnew < num,请你帮他计算下一共有多少种不同的子串选择方案,只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。

注意,我们允许前导零的存在,即数字的最高位可以是 0 ,这是合法的。

输入格式

输入一行包含一个长度为 n 的字符串表示 num(仅包含数字字符 0 ∼ 9),

从左至右下标依次为 0 ∼ n − 1。

输出格式

输出一行包含一个整数表示答案。

样例输入

210102

样例输出

8

提示

一共有 8 种不同的方案:

1)所选择的子串下标为 0 ∼ 1 ,反转后的 numnew = 120102 < 210102 ;

2)所选择的子串下标为 0 ∼ 2 ,反转后的 numnew = 012102 < 210102 ;

3)所选择的子串下标为 0 ∼ 3 ,反转后的 numnew = 101202 < 210102 ;

4)所选择的子串下标为 0 ∼ 4 ,反转后的 numnew = 010122 < 210102 ;

5)所选择的子串下标为 0 ∼ 5 ,反转后的 numnew = 201012 < 210102 ;

6)所选择的子串下标为 1 ∼ 2 ,反转后的 numnew = 201102 < 210102 ;

7)所选择的子串下标为 1 ∼ 4 ,反转后的 numnew = 201012 < 210102 ;

8)所选择的子串下标为 3 ∼ 4 ,反转后的 numnew = 210012 < 210102 ;

对于 20% 的评测用例,1 ≤ n ≤ 100 ;

对于 40% 的评测用例,1 ≤ n ≤ 1000 ;

对于所有评测用例,1 ≤ n ≤ 5000 。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
int main(){
	string s;
	cin>>s;
	int n=s.size();
	int cnt=0;
	for(int i=0;i<n-1;i++){
		for(int j=n-1;j>i;j--){
			if(s[i]>s[j]) cnt++;
			else if(s[i]==s[j]){
				for(int x=i,y=j;x<y;x++,y--){
					if(s[x]>s[y]){
						cnt++;
						break;
					}else if(s[x]<s[y]) break;
				}
			}
		}
	}
	cout<<cnt<<endl;
	return 0;
}

【DFS】颜色平衡树

题目描述

给定一棵树,结点由 1 至 n 编号,其中结点 1 是树根。树的每个点有一个颜色 Ci。

如果一棵树中存在的每种颜色的结点个数都相同,则我们称它是一棵颜色平衡树。

求出这棵树中有多少个子树是颜色平衡树。

输入格式

输入的第一行包含一个整数 n ,表示树的结点数。

接下来 n 行,每行包含两个整数 Ci , Fi,用一个空格分隔,表示第 i 个结点的颜色和父亲结点编号。

特别地,输入数据保证 F1 为 0 ,也即 1 号点没有父亲结点。保证输入数据是一棵树。

输出格式

输出一行包含一个整数表示答案。

样例输入

6
2 0
2 1
1 2
3 3
3 4
1 4

样例输出

4

提示

编号为 1, 3, 5, 6 的 4 个结点对应的子树为颜色平衡树。

对于 30% 的评测用例,n ≤ 200,Ci ≤ 200 ;

对于 60% 的评测用例,n ≤ 5000,Ci ≤ 5000 ;

对于所有评测用例,1 ≤ n ≤ 200000,1 ≤ Ci ≤ 200000,0 ≤ Fi < i 。

#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
const int N=2e5+10;
int c[N];
int ans=0;
int n;
vector<int> g[N];
void add(map<int,int> &cnt,map<int,int> &cnt_nb){
	for(auto mp:cnt_nb){
		int x=mp.first;
		int y=mp.second;
		cnt[x]+=y;
	}
}
map<int,int> dfs(vector<int> *g,int *c,int i){
	int sz=g[i].size();
	map<int,int> cnt;
	if(sz==0){
		cnt[c[i]]=1;
		ans++;
		return cnt;
	}
	cnt[c[i]]=1;
	for(int j=0;j<sz;j++){
		int nb=g[i][j];
		map<int,int> cnt_nb=dfs(g,c,nb);
		add(cnt,cnt_nb);
	}
	int num=cnt[c[i]];
	for(auto mp:cnt){
		int count=mp.second;
		if(count!=num) return cnt;
	}
	ans++;
	return cnt;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int f;
		cin>>c[i]>>f;
		if(f>=1) g[f-1].push_back(i);
	}
	dfs(g,c,0);
	cout<<ans<<endl;
	return 0;
}

【DFS】(选不选)买瓜

题目描述

小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜,每个瓜的重量为 Ai 。

小蓝刀功了得,他可以把任何瓜劈成完全等重的两份,不过每个瓜只能劈一刀。

小蓝希望买到的瓜的重量的和恰好为 m 。

请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜,请输出 −1 。

输入格式

输入的第一行包含两个整数 n, m,用一个空格分隔,分别表示瓜的个数和小蓝想买到的瓜的总重量。

第二行包含 n 个整数 Ai,相邻整数之间使用一个空格分隔,分别表示每个瓜的重量。

输出格式

输出一行包含一个整数表示答案。

样例输入

3 10
1 3 13

样例输出

2

提示

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

对于 60% 的评测用例,∑n≤20;

对于所有评测用例,1 ≤n≤30,1≤ Ai ≤ 10^9 ,1 ≤ m ≤ 10^9

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=35,INF=0x3f3f3f3f;
LL p[N];
LL a[N];
int n;
LL m;
int ans=INF;
void dfs(int u,LL sum,int cnt){
	if(sum==m){
		ans=min(ans,cnt);
		return ;
	}
	if(cnt>=ans||u>n||sum+p[u]<m||sum>m) return ;
	dfs(u+1,sum+a[u],cnt);
	dfs(u+1,sum+a[u]/2,cnt+1);
	dfs(u+1,sum,cnt);
}
int main(){
	cin>>n>>m;
	m*=2;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]*=2;
	}
	sort(a+1,a+1+n,greater<int>());
	for(int i=n;i>=1;i--) p[i]=p[i+1]+a[i];
	dfs(1,0,0);
	if(ans==INF) cout<<"-1"<<endl;
	else cout<<ans<<endl;
	return 0;
}

网络稳定性(X)

异或和之和

题目描述

给定一个数组 Ai,分别求其每个子段的异或和,并求出它们的和。或者说,对于每组满足 1 ≤ L ≤ R ≤ n 的 L, R ,求出数组中第 L 至第 R 个元素的异或和。然后输出每组 L, R 得到的结果加起来的值。

输入格式

输入的第一行包含一个整数 n 。

第二行包含 n 个整数 Ai ,相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

5
1 2 3 4 5

样例输出

39

提示

对于 30% 的评测用例,n ≤ 300 ;
对于 60% 的评测用例,n ≤ 5000 ;
对于所有评测用例,1 ≤ n ≤ 105,0 ≤ Ai ≤ 2^20 。

区间[l,r]的异或和可以表示为S_{r}\bigoplus S_{l-1},这样原问题就变成了:求n+1个数两两异或之和,如果S_{i}的二进制第 j 位为1(0),我们只需知道 [0,i-1] 这个区间内的数二进制第 j 位为0(1)的个数x,这样s[i]的第 j 位的贡献值为x*2^j;

#include<iostream>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N][30];
signed main(){
	int n;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>x;
		for(int j=0;j<=20;j++){
			a[i][j]=(x>>j)&1;
			a[i][j]^=a[i-1][j];
		}
	}
	int ans=0;
	for(int j=0;j<=20;j++){
		map<int,int> mp;
		mp[0]++;
		for(int i=1;i<=n;i++){
			int x=mp[a[i][j]^1];//与第i个数第j位不同的个数
			ans+=(1<<j)*x;
			mp[a[i][j]]++;
		}
	}
	cout<<ans<<endl;
	return 0;
}
#include<iostream>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
int s[N];
int cnt[N][30];
signed main(){
	int n;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]^a[i];
	}
//求n+1个数第j位0和1的个数
	for(int j=0;j<=20;j++){
		for(int i=0;i<=n;i++){
			if(s[i]>>j&1) cnt[j][1]++;
			else cnt[j][0]++;
		}
	}
	int ans=0;
	for(int i=0;i<=20;i++){
//每个1都可以和每个0异或等于1,总数为cnt[i][0]*cnt[i][1],每个1的贡献值为2^i
		ans+=cnt[i][0]*cnt[i][1]*(1<<i);
	}
	cout<<ans<<endl;
	return 0;
}

像素放置(X)

翻转硬币(X)

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

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

相关文章

Redis中的Sentinel(二)

Sentinel 初始化Sentinel状态。 在应用了Sentinel的专用代码之后&#xff0c;接下来&#xff0c;服务器会初始化一个sentinel.c/sentinelState结构(简称Sentinel状态),这个结构 保存了服务器中所有和Sentinel功能有关的状态(服务器的一般状态仍然由redis.h/redisServer保存);…

【java数据结构-二叉树(上)】

java数据结构-二叉树&#xff08;上&#xff09; 二叉树的概念二叉树的节点介绍 二叉树构造如何使用兄弟表示法构造二叉树两种特别的二叉树二叉树的基本性质&#xff1a; 二叉树的存储二叉树的遍历&#xff1a;前序遍历&#xff1a;中序遍历&#xff1a;后序遍历&#xff1a;层…

最新ChatGPT4.0工具使用教程:GPTs,Midjourney绘画,AI换脸,GPT语音对话,文档分析一站式系统

一、前言 ChatGPT3.5、GPT4.0、相信对大家应该不感到陌生吧&#xff1f;简单来说&#xff0c;GPT-4技术比之前的GPT-3.5相对来说更加智能&#xff0c;会根据用户的要求生成多种内容甚至也可以和用户进行创作交流。 然而&#xff0c;GPT-4对普通用户来说都是需要额外付费才可以…

基于RDMA的云服务能力实践与探索

01 背景 随着基于大数据大模型构建的数据系统越来越有商业价值&#xff0c;机器学习的玩家也越来越多&#xff0c;数据量越来越大。为解决海量数据在服务器之间的同步效率问题&#xff0c;RDMA(Remote Direct Memory Access) 技术逐渐走进了网络技术人员的视野。RDMA为什么…

yolov8多分支任务头训练

目前已知的yolov8可以针对多个任务进行单独训练,但是暂时还没有开放针对多个任务头同时进行训练的教程,本文章针对yolov8的多任务训练进行详细介绍。 先放上效果图: 三个任务,分别是目标检测、可行驶区域、车道线,具体步骤请往下看。 一、环境配置 从如下github下载代码…

Flutter Don‘t use ‘BuildContext‘s across async gaps.

Flutter提示Don‘t use ‘BuildContext‘s across async gaps.的解决办法—flutter里state的mounted属性

10-热点文章-定时计算

xxl-Job分布式任务调度 1 今日内容 1.1 需求分析 目前实现的思路&#xff1a;从数据库直接按照发布时间倒序查询 问题1&#xff1a; 如何访问量较大&#xff0c;直接查询数据库&#xff0c;压力较大 问题2&#xff1a; 新发布的文章会展示在前面&#xff0c;并不是热点文章 …

交叉验证(Cross-Validation)

交叉验证的基本概念 交叉验证通常用于评估机器学习模型在未知数据上的性能。它将数据集分成k个不同的子集&#xff0c;然后进行k次训练和验证。在每次迭代中&#xff0c;选择一个子集作为测试集&#xff0c;其余的子集作为训练集。这样&#xff0c;每个子集都用作过测试集&…

Debian安装1panel管理面板教程-最新

1Panel 是一个现代化、开源的 Linux 服务器运维管理面板。 1Panel面板是一个强大的服务器管理工具&#xff0c;它通过提供一站式管理、易于使用的界面、高度的可定制性、安全可靠的性能、强大的扩展性以及活跃的社区支持&#xff0c;为用户提供了一个高效、便捷的管理解决方案…

华为云1核2G免费使用一年

个人用户专享云服务器、云数据库产品每天上午9:30开抢&#xff0c;其他产品每天0点开放领取&#xff0c;企业用户所有产品每天0点开放领取&#xff1b; 云产品体验名额有限&#xff0c;领完即止。详情&#xff1a;https://www.vpspick.com/vps/591.html 通用入门型 T6 云服务…

实验06_IPv6实验

目录 实验拓扑 实验需求 实验配置及其现象验证&#xff1a; (1)R1---R4的IPv6的地址配置&#xff0c;根据设备编码配置IPv6 (2)R6 通过无状态自动获取 IPv6 地址 (3)OSPFv3 配置&#xff0c;通过 OSPFv3 实现全网通&#xff08;区域划分根据拓扑图&#xff09; 实验拓扑 …

Linux存储的基本管理

实验环境&#xff1a; 系统里添加两块硬盘 ##1.设备识别## 设备接入系统后都是以文件的形式存在 设备文件名称&#xff1a; SATA/SAS/USB /dev/sda,/dev/sdb ##s SATA, dDISK a第几块 IDE /dev/hd0,/dev/hd1 ##h hard VIRTIO-BLOCK /de…

蓝桥杯(5):python动态规划DF[2:背包问题]

1 0-1背包介绍【每件物品只能拿1件或者不拿】 1.1 简介 贪心是不可以的&#xff01;&#xff01;&#xff01; 1.2 状态 及状态转移 转移解释&#xff1a;要么不选 则上一个直接转移过来【dp[i-1][j]】&#xff0c;要么是选这个之后体积为j 则上一个对应的就是【dp[i-1][j-wi]…

Vue 样式技巧总结与整理[中级局]

SFC&#xff08;单文件组件&#xff09;由 3 个不同的实体组成&#xff1a;模板、脚本和样式。三者都很重要&#xff0c;但后者往往被忽视&#xff0c;即使它可能变得复杂&#xff0c;且经常导致挫折和 bug。 更好的理解可以改善代码审查并减少调试时间。 这里有 7 个奇技淫巧…

CSS设置网页颜色

目录 前言&#xff1a; 1.颜色名字&#xff1a; 2.十六进制码&#xff1a; 3.RGB&#xff1a; 4.RGBA&#xff1a; 5.HSL&#xff1a; 1.hue&#xff1a; 2.saturation&#xff1a; 3.lightness&#xff1a; 6.HSLA&#xff1a; 前言&#xff1a; 我们在电脑显示器&…

高血压的常见症状,你是否了解并警惕?

高血压是一种慢性心血管疾病&#xff0c;它的形成和发展与很多种因素密切相关。导致高血压的重要因素之一就是不良的生活饮食习惯。 高血压严重危害着人的心脏、肾脏、大脑等这些人体重要的器官&#xff0c;会容易带来心脏病、肾功能衰竭等一系列疾病。今天我在来为大家讲解一…

CorelDRAW2024序列号破解版下载以及CorelDRAW新功能介绍

CorelDRAW Graphics Suite 2024破解版介绍 CorelDRAW Graphics Suite 2024 破解版是领先的专业图形设计软件套件&#xff0c;旨在提供多个精心设计的工具和丰富的功能&#xff0c;轻松提高您的技能睡哦平&#xff0c;您可以更好的完成矢量插图、完美的布局、高级的照片编辑和高…

Jeecg commonController 任意文件上传漏洞复现

0x01 产品简介 Jeecg(J2EE Code Generation)是一款基于代码生成器的低代码开发平台,使用JEECG可以简单快速地开发出企业级的Web应用系统。 0x02 漏洞概述 JEECG(J2EE Code Generation) 是开源的代码生成平台,目前官方已停止维护。由于 /api 接口鉴权时未过滤路径遍历,攻…

中高级前端? 这些一元运算符,你真的搞清楚了吗

前言 一元运算符&#xff0c;不太起眼&#xff0c;作用很大&#xff0c;请别忽视她&#xff01; 走近她&#xff0c;爱上她&#xff01; 定义 只需要一个操作数的运算符称为一元运算符。 还是代码容易懂&#xff1a; 1 // 一个操作数1 2 // 两个操作数一元运算符清单 运…

基于Springboot的学校防疫物资管理平台(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的学校防疫物资管理平台&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系…