【递归专题】【蓝桥杯备考训练】：有序分数、正则问题、带分数、约数之和、分形之城【已更新完成】

目录

1、有序分数（usaco training 2.1）

2、正则问题（第八届蓝桥杯省赛C++ A组 & Java A组）

3、带分数（第四届蓝桥杯省赛Java A组/B组 & C++ B组/C组）

4、约数之和（《算法竞赛进阶指南》）

5、分形之城（《算法竞赛进阶指南》）

1、有序分数（usaco training 2.1）

给定一个整数 N，请你求出所有分母小于或等于 N，大小在 [0,1]范围内的最简分数，并按从小到大顺序依次输出。

例如，当 N=5 时，所有满足条件的分数按顺序依次为：

0/1,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1

输入格式

共一行，包含一个整数 N。

输出格式

按照从小到大的顺序，输出所有满足条件的分数。

每个分数占一行，格式为 a/b，其中 a 为分子， b为分母。

数据范围

1≤N≤160

输入样例：
5
输出样例：
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
思路：

用一个pair对来维护最小值和对应的分子分母，将所有情况枚举，为了避免重复我们要用一个set来确保没有重复的数值

这里要注意进入递归函数要直接进入最里面的一层开始往上递归，这样就可以做到所有分数的都是最简分数式

代码：

#include<bits/stdc++.h>

using namespace std;

int n;

typedef pair<int,int> PII;

typedef pair<double,PII> PDP;

const int N=1e5;

vector<PDP>res;

unordered_set<double>cnt;

void work(int n)
{
    
	if(n==0)return ;
	work(n-1);
	for(int i=n-1;i>0;i--)
	{
		double number=(double)i/n;
		if(cnt.find(number)!=cnt.end())continue;
		cnt.insert(number);
		PII t={i,n};
		res.push_back({number,t});
	}
	
}

bool cmp(PDP a,PDP b)
{
    return a.first<b.first;
}

int main()
{
	cin>>n;
	
	res.push_back({0,{0,1}});
	res.push_back({1,{1,1}});
	
	work(n);
    
	sort(res.begin(),res.end(),cmp);

	for(auto t:res)
	{
		cout<<t.second.first<<"/"<<t.second.second<<endl;
	}
	
	return 0;
}

2、正则问题（第八届蓝桥杯省赛C++ A组 & Java A组）

考虑一种简单的正则表达式：

只由 x ( ) | 组成的正则表达式。

小明想求出这个正则表达式能接受的最长字符串的长度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。

输入格式

一个由x()|组成的正则表达式。

输出格式

输出所给正则表达式能接受的最长字符串的长度。

数据范围

输入长度不超过100，保证合法。

输入样例：
((xx|xxx)x|(x|xx))xx
输出样例：
6
思路：

递归+回溯

代码：
#include<bits/stdc++.h>

using namespace std;

int k=0;

string s; 

//((xx|xxx)x|(x|xx))xx 
//6
int dfs()
{
	int res=0;
	while(k<s.size())
	{
		if(s[k]=='(')
		{
			k++;
			res+=dfs();
			k++;
			
		}
		else if(s[k]==')')
		{
			break;
		}
		else if(s[k]=='|')
		{
			k++;
			res=max(res,dfs());
		}
		else
		{
			k++;
			res++;
		}
	}
	return res;
}

int main()
{
	cin>>s;
	
	int res=dfs();
	cout<<res;
	return 0;
}

3、带分数（第四届蓝桥杯省赛Java A组/B组 & C++ B组/C组）

100可以表示为带分数的形式：100=3+69258/714

还可以表示为：100=82+3546/197

注意特征：带分数中，数字 1∼9分别出现且只出现一次（不包含 0）。

类似这样的带分数，100 有 11种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围

1≤N<1e6

输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6
思路：

由于c++的/并不准确，我们把除法转化为乘法，再进行枚举（n=a+b/c转化为nc=ac+b）

从而我们枚举出a和c就可以算出b，b=nc-ac;

用had_use记录用过的数，ever用来在不影响并行递归的情况下把当前情况递归下去(不破坏原来的记录)

代码：
#include<bits/stdc++.h>

using namespace std;

const int N=600;

//typedef long long LL;

int ever[N],had_use[N];
//数组放在最上面，acwing平台由于放在了ans下面导致输出结果错误 

int ans=0;

int  n;


//n=a+b/c
//nc=ac+b
//b=nc-ac 只要推出来的b满足条件，a和c都满足条件则答案+1 
bool check(int a,int c)
{
	int b=n*c-a*c;
	
	if(!a || !c || !b)return false;
	
	memcpy(ever,had_use,sizeof had_use);//基于现有的情况下，不破坏原来的数组
	//那就拷贝一份，既能在原来之上操作，又能不破坏原来的记录 
	
	while(b)//取出每一位，用来更新用过的数字 
	{
		int t=b%10;
		b/=10;
		if(!t || ever[t])return false;
		ever[t]=1;
	}
	
	for(int i=1;i<=9;i++)if(!ever[i])return false;
	
	return true;
}

void dfs_c(int x,int a,int c)
{
	if(x>=10)return ;
	if(check(a,c))ans++;
	for(int i=1;i<=9;i++)
	{
		if(!had_use[i])
		{
			had_use[i]=1;
			dfs_c(x+1,a,c*10+i);
			had_use[i]=0;//回溯，避免下次的递归中出现错误 
		}
	}
}

void dfs_a(int x,int a)
{
	if(a>=n)return;
	if(a)dfs_c(x,a,0);//如果a满足条件，那么枚举c然后判断是否是成立的
	//0是c的大小 
	for(int i=1;i<=9;i++)//枚举一下当前能用哪些数字
	{
		if(!had_use[i])
		{
			had_use[i]=1;
			dfs_a(x+1,a*10+i);
			had_use[i]=0;//恢复现场，回溯一下 
		}	
	} 
}

int main()
{	
	//cout<<714*97;
	cin>>n;
	dfs_a(0,0);//第一个表示当前用了多少个数字，第二个参数表示当前的a是多少 
	cout<<ans;
	return 0;
}

4、约数之和（《算法竞赛进阶指南》）

假设现在有两个自然数 A 和 B，S 是A的B次方的所有约数之和。

请你求出 S mod9901 的值是多少。

输入格式

在一行中输入用空格隔开的两个整数 A 和 B。

输出格式

输出一个整数，代表 Smod9901 的值。

数据范围

0≤A,B≤5×1e7

输入样例：
2 3
输出样例：
15

注意: A 和 B不会同时为 0。

思路：

分解质因数，把每个质因数的从第0项到最高次数的和乘起来就是约数之和

由于是求A的B次方的约数之和，我们可以先把A分解质因数，次方B可以后来再给到质因数的次方上

代码：
#include<bits/stdc++.h>

using namespace std;

const int MOD=9901;

typedef long long LL;

LL a,b;
LL res=0;

unordered_map<int,int>primes;

LL quickmi(LL a,LL b)
{
	LL res=1;
	while(b)
	{
		if(b&1)res=res*a%MOD;
		a=a*a%MOD;
		b=b>>1;
	}
	return res%MOD;
}

void divide(LL x)
{
	for(int i=2;i<=x/i;i++)
	{
		if(x%i==0)
		{
		    while(x%i==0)
		    {
		        primes[i]++;
		        x/=i;
		    }
		}
	}
	if(x>1)primes[x]++;
}

//求p0+....pk-1 
LL sum(LL p,LL k)
{
	if(k==1)return 1;
	if(k%2==0)return (LL)(quickmi(p,k/2)+1)*sum(p,k/2)%MOD;
	return (LL)(quickmi(p,k-1)+sum(p,k-1))%MOD;
}

int main()
{
	cin>>a>>b;
	
	divide(a);
	
	LL res=1;
	
	for(auto prime :primes)
	{
		int p=prime.first;
		int k=prime.second*b;//p的次数 

		res=(LL)res*sum(p,k+1)%MOD;//求约数之和 
	}
	if(!a)res=0;
	cout<<res<<endl; 
	
	return 0;
}

5、分形之城（《算法竞赛进阶指南》）

城市的规划在城市建设中是个大问题。

不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。

而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：

city.png

当城区规模扩大之后，Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围，提升城市的等级。

对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。

虽然这个方案很烂，Fractal 规划部门的人员还是想知道，如果城市发展到了等级 N，编号为 A 和 B 的两个街区的直线距离是多少。

街区的距离指的是街区的中心点之间的距离，每个街区都是边长为 10 米的正方形。

输入格式

第一行输入正整数 n，表示测试数据的数目。

以下 n 行，输入 n 组测试数据，每组一行。

每组数据包括三个整数 N,A,B表示城市等级以及两个街区的编号，整数之间用空格隔开。

输出格式

一共输出 n 行数据，每行对应一组测试数据的输出结果，结果四舍五入到整数。

数据范围

1≤N≤31
1≤A,B≤2**2N
1≤n≤1000

输入样例：
3 
1 1 2 
2 16 1 
3 4 33
输出样例：
10 
30 
50
思路：

我们要知道第n等级城市的信息就要知道n-1等级的（n-1等级的城市可以通过旋转变换得出n等级城市的坐标信息），递归下去，最后算出街区中心坐标然后进行勾股定理即可，注意要乘上单位长度（本代码为5）

代码：
#include<bits/stdc++.h>

typedef long long LL;

using namespace std;

typedef pair<LL,LL> PLL;

#define x first

#define y second

PLL calc(LL n,LL m)
{
	//n代表城市等级 
	//m代表坐标，从0开始计数 
	if(n==0)return {0,0};
	LL len = 1ll <<(n-1);//本等级内象限的边长/2 
	LL cnt=1ll<<(2*n-2);//上一等级的容量
	PLL pos = calc(n - 1, m % cnt);  // 上一等级的坐标信息 
	LL x=pos.x,y=pos.y;
	int z=m/cnt;//处于哪个象限 
	 if (z == 0)
        return { - y - len, - x + len };
    // 右上象限更换原点（x+len,y+len）
    else if (z == 1)
        return { x + len, y + len };
    // 右下象限更换原点（x+len,y-len）
    else if (z == 2)
        return { x + len, y - len };
    // 左下象限逆转90°（-y,x）沿y对称（y,x）更换原点（y-len,x-len）
    return { y - len, x - len };
}

int main()
{
	 int N;
    cin >> N;
    while (N --)
    {
        LL n, m1, m2;
        cin >> n >> m1 >> m2;
        PLL pos1 = calc(n, m1 - 1);
        PLL pos2 = calc(n, m2 - 1);

        double x = (double) (pos1.first - pos2.first);
        double y = (double) (pos1.second - pos2.second);
        //单位长度要乘五
        printf("%.0lf\n", sqrt(x * x + y * y) * 5);
	}
	return 0;
}

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

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

相关文章

面试笔记——Redis（使用场景、面临问题、缓存穿透）

面试笔记——Redis（使用场景、面临问题、缓存穿透）

Redis的使用场景 Redis&#xff08;Remote Dictionary Server&#xff09;是一个内存数据结构存储系统&#xff0c;它以快速、高效的特性闻名&#xff0c;并且它支持多种数据结构&#xff0c;包括字符串、哈希表、列表、集合、有序集合等。它主要用于以下场景&#xff1a; 缓…
阅读更多...
虹科技术|PCAN系列网关内部存储空间解析：EEPROM与Flash的集成应用

虹科技术|PCAN系列网关内部存储空间解析：EEPROM与Flash的集成应用

导读&#xff1a;网关设备是确保数据流畅通信的关键。虹科PCAN系列网关凭借卓越性能和创新技术&#xff0c;为众多应用提供了高效稳定的解决方案。本文将深入探讨虹科PCAN系列网关内部存储空间&#xff0c;特别是EEPROM和SPI Flash的配置与利用&#xff0c;并解析如何通过C编程…
阅读更多...
每日一题——LeetCode1694.重新格式化电话号码

每日一题——LeetCode1694.重新格式化电话号码

方法一 模拟&#xff1a; 首先去除number里面的破折号和空格&#xff0c;取出纯数字组成的字符串str。 对于str每三个数分成一组&#xff0c;加一个破折号&#xff0c;当str的长度小于等于4时再分情况讨论&#xff0c;如果等于4就分为22形式&#xff0c;如果小于4&#xff0c…
阅读更多...
flask之ssti [WesternCTF2018]shrine1

flask之ssti [WesternCTF2018]shrine1

打开题目 整理一下&#xff0c;代码: import flask import osapp flask.Flask(__name__) app.config[FLAG] os.environ.pop(FLAG) app.route(/)def index():return open(__file__).read()app.route(/shrine/)def shrine(shrine):def safe_jinja(s):s s.replace((, ).replac…
阅读更多...
基于springboot+vue的乡政府管理系统

基于springboot+vue的乡政府管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…
阅读更多...
奇数乘积（C语言）

奇数乘积（C语言）

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int i 1;int j 3;//循环运算&#xff1b;while (j < 12){//运算&#xff1b;i i * j;//改变数值&#xff1b;j 2…
阅读更多...
多线程服务器适用场合

多线程服务器适用场合

前提 进程”指的是fork(2)系统调用的产物 线程”指的是pthread_create()的产物,因此是宝贵的那种原生线程。而且Pthreads是NPTL的,每个线程由clone(2)产生,对应一个内核的task_struct。 Pthreads是一组线程操作的标准&#xff0c;NPTL是 Native POSIX Thread Library 的缩写&…
阅读更多...
成都规模最大的直播基地在哪里

成都规模最大的直播基地在哪里

天府锋巢直播产业基地&#xff0c;位于成都这座历史文化与现代气息交织的城市&#xff0c;不仅是成都规模最大的直播产业园&#xff0c;更是西南地区乃至全国范围内具有影响力的直播产业聚集地。在这里&#xff0c;直播产业与科技创新、文化创意、教育培训等多个领域深度融合&a…
阅读更多...
工业AMR机器人如何实现规模化的柔性生产

工业AMR机器人如何实现规模化的柔性生产

在当下高度复杂的工业生产环境中&#xff0c;机器人如何实现规模化的柔性生产&#xff0c;已成为业界关注的焦点。特别是在追求高效率、高质量的生产过程中&#xff0c;团队协作的重要性愈发凸显。富唯智能一体化AMR控制系统&#xff0c;作为机器人的核心指挥部&#xff0c;犹如…
阅读更多...
Android基础开发-读写短信

Android基础开发-读写短信

1、利用ContentObserver监听短信 内容观察器ContentObserver给目标内容注册一个观察器&#xff0c;目标内容的数据一旦发生改变&#xff0c;观察器规定好的动作马上触发&#xff0c;从而执行开发者预定义的代码。 参数原理&#xff1a; notifyForDescendents 通知子孙后代 …
阅读更多...
C++ 万物起源：类与对象（一）

C++ 万物起源：类与对象（一）

目录 一、C与C语言的区别 1.1类的引入 二、C类 2.1类的概念与定义 2.2类的访问限定符与封装 2.2.1C中struct和class的区别 2.3封装 2.4类的作用域与实例化 三、类对象模型 3.1类对象的存储模式 3.2结构体内存对齐规则 一、C与C语言的区别 C语言是面向过程的&#xf…
阅读更多...
毕设学习进展周报

毕设学习进展周报

文章目录 3.11-3.18 3.11-3.18 1.阅读ACL文献并记录 2.查找相关资料学习在阿里云部署ChatGLM3-6B 参考&#xff1a;https://blog.csdn.net/H66778899/article/details/135630030 # 运行 streamlit run /mnt/workspace/ChatGLM3/conposite_demo/main.py可以得到&#xff1a;…
阅读更多...
jscpd对项目进行查重（支持150+类语言）

jscpd对项目进行查重（支持150+类语言）

jscpd jscpd 查重时能够跳过标记为忽略的块和新行以及空符号和注释&#xff08;不支持尖括号注释<!-- --&#xff01;>&#xff09;&#xff0c;重复率判定依据为一定长度标识符的MD5值是否相同。 安装 npm install -g jscpd配置参数(查看更多) OptionTypeDefaultDes…
阅读更多...
Windows系统安装GeoServe结合内网穿透实现公网访问本地位置信息服务

Windows系统安装GeoServe结合内网穿透实现公网访问本地位置信息服务

文章目录 前言1.安装GeoServer2. windows 安装 cpolar3. 创建公网访问地址4. 公网访问Geo Servcer服务5. 固定公网HTTP地址 前言 GeoServer是OGC Web服务器规范的J2EE实现&#xff0c;利用GeoServer可以方便地发布地图数据&#xff0c;允许用户对要素数据进行更新、删除、插入…
阅读更多...
抖音视频批量下载工具|无水印视频提取软件

抖音视频批量下载工具|无水印视频提取软件

抖音视频批量下载工具安装教程 一&#xff1a;双击安装包 二&#xff1a;进入安装主界面 然后点击接收Q:290615413 三&#xff1a;接受后进入安装模式 设置好安装路径 系统默认的是D盘然后点击解压 四&#xff1a;点击解压后安装等待安装 安装成功后桌面会有 抖音视频批量提取工…
阅读更多...
Python进程与线程开发

Python进程与线程开发

目录 multiprocessing模块 线程的开发 threading模块 setDaemon 死锁 线程间的通信 multiprocessing模块 运行python的时候&#xff0c;我们都是在创建并运行一个进程&#xff0c;(linux中一个进程可以fork一个子进程&#xff0c;并让这个子进程exec另外一个程序)。在pyt…
阅读更多...
算法设计与分析（贪心法）

算法设计与分析（贪心法）

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入学习某技术知识点… 一个人摸索学习很难坚持&#xff0c;想组团高效学习… 想写博客但无从下手&#xff0c;急需…
阅读更多...
Vulnhub - Symfonos

Vulnhub - Symfonos

希望和各位大佬一起学习&#xff0c;如果文章内容有错请多多指正&#xff0c;谢谢&#xff01; 个人博客链接&#xff1a;CH4SER的个人BLOG – Welcome To Ch4sers Blog Symfonos 靶机下载地址&#xff1a;https://www.vulnhub.com/entry/symfonos-1,322/ 0x01 信息收集 …
阅读更多...
[保姆级教程]Windows安装MongoDB教程

[保姆级教程]Windows安装MongoDB教程

文章目录 MongoDB安装包下载1.点击进入mongodb官网2.点击MongoDB Community Edition&#xff08;社区版&#xff09;&#xff0c;进入下图界面3.选择版本4.下载5.安装6.勾选同意协议&#xff0c;点击“Next"7.选择自定义安装8.点击“Next"9.修改到合适的地址10.点击i…
阅读更多...
影响汇率的因素？fpmarkets澳福总结几个

影响汇率的因素？fpmarkets澳福总结几个

汇率对于刚刚开始外汇交易的新手来说非常重要&#xff0c;这不是没有道理的&#xff0c;了解汇率如何变化以及怎么变化有助于在外汇交易中获得稳定的利润。那么影响汇率的因素有哪些&#xff1f;fpmarkets澳福总结几个。 任何国家货币的汇率都是由市场决定的。主要的市场因素是…
阅读更多...
最新文章

Copyright @ 2022~2023