蓝桥杯带刷题

时间：2023-04-03 07:52:03

A::::::::::::::::::小数第n位

题目描述

我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。

如果我们把有限小数的末尾加上无限多个 0，它们就有了统一的形式。

本题的任务是：在上面的约定下，求整数除法小数点后的第 n 位开始的 3 位数。

输入描述

输入一行三个整数：a b n，用空格分开。a 是被除数，b 是除数，n是所求的小数后位置（0<a,b,n<109）

输出描述

输出一行 3 位数字，表示：a 除以 b，小数后第 n 位开始的 3 位数字。

输入输出样例

示例

输入

1 8 1

输出

125
#include <iostream>
using namespace std;
long long a,b,c;
int main(){
    cin>>a>>b>>c;
    a=a%b;      //求小数所以不影响,现在a<b,a*10/b就是第一个小数位 
  while(c-10>0){
    a=a*1e10;   //每次移动10位，一位乘以10,10位乘以1e10。
    a=a%b;
    c-=10;
  }
    for(int i=1;i<=c+2;i++){
        if(i>=c){
            cout<<a*10/b;   //这一位的小数值 
        } 
        a=a*10%b;           //剩下的 
    } 
    return 0;
}

 B::::::::::::::::::卡片换位（BFS）

题目描述

你玩过华容道的游戏吗？

这是个类似的，但更简单的游戏。

看下面 3 x 2 的格子

+---+---+---+

| A | * | * |

+---+---+---+

| B | | * |

+---+---+---+

在其中放 5 张牌，其中 A 代表关羽，B 代表张飞，* 代表士兵。

还有个格子是空着的。

你可以把一张牌移动到相邻的空格中去(对角不算相邻)。

游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。

输入描述

输入两行 6 个字符表示当前的局面

输出描述

一个整数，表示最少多少步，才能把 A B 换位（其它牌位置随意）

输入输出样例

示例

输入

* A
**B

输出

17

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 256M
#include <iostream>
#include <queue>
#include <map>
using namespace std;
string chushi[2];
int x,y,ax,ay,bx,by;
struct node{
	int x,y;
	int ax,ay;
	int bx,by;
	int ans;
	string lu[2];
};
node one;
queue<node> q;
int g[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool check(int x,int y){
	return x>=0&&x<2&&y>=0&&y<3;
}
map<string,bool> pan;
int main(){
	getline(cin,chushi[0]);
	getline(cin,chushi[1]);
	
	for(int i=0;i<2;i++){
		for(int j=0;j<3;j++){
			if(chushi[i][j]==' '){
				x=i,y=j;
			}
			if(chushi[i][j]=='A'){
				ax=i,ay=j;
			}
			if(chushi[i][j]=='B'){
				bx=i,by=j;
			}
		}
	}
	one.x=x,one.y=y,one.ax=ax,one.ay=ay,one.bx=bx,one.ans=0;
	one.by=by,one.lu[0]=chushi[0],one.lu[1]=chushi[1];
	string mm=chushi[0]+chushi[1];
	pan[mm]=1;

	q.push(one);
	while(!q.empty()){
		node f=q.front();
		q.pop();
		if(f.ax==bx && f.ay==by && f.bx==ax && f.by==ay){
			cout<<f.ans;
			break;
		}
		

		for(int i=0;i<4;i++){
			int tx=f.x+g[i][0];
			int ty=f.y+g[i][1];
		
			if(check(tx,ty)){
				
				string h[2];
				h[0]=f.lu[0];
				h[1]=f.lu[1];
				h[tx][ty]=' ';
				h[f.x][f.y]=f.lu[tx][ty];
			
				string mm=h[0]+h[1];
				
				if(!pan[mm]){
					pan[mm]=1;
					int xx,yy,axx,ayy,bxx,byy;
					for(int i=0;i<2;i++){
						for(int j=0;j<3;j++){
							if(h[i][j]==' '){
								xx=i,yy=j;
							}
							if(h[i][j]=='A'){
								axx=i,ayy=j;
							}
							if(h[i][j]=='B'){
								bxx=i,byy=j;
							}
						}
					}
					node two;
					two.x=xx,two.y=yy,two.ax=axx,two.ay=ayy,two.bx=bxx,two.ans=f.ans+1;
					two.by=byy,two.lu[0]=h[0],two.lu[1]=h[1];
					q.push(two);	
				}		
			}
			
			
		}
	}
	return 0;
}

  C::::::::::::::::::左移右移（双向链表，双指针）

问题描述

小蓝有一个长度为 N 的数组, 初始时从左到右依次是1,2,3,…N 。

之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一:

  1. 左移 x, 即把 x 移动到最左边。

  2. 右移 x, 即把 x 移动到最右边。

请你回答经过 M 次操作之后, 数组从左到右每个数是多少?

输入格式

第一行包含 2 个整数, N 和 M 。

以下 M 行每行一个操作, 其中 “L x "表示左移 x, R   x  "表示右移 x 。

输出格式

输出 NN 个数, 代表操作后的数组。

样例输入

5 3
L 3
L 2
R 1

样例输出

2 3 4 5 1

样例说明

样例中的数组变化如下:

[1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1]

评测用例规模与约定

对于 50% 的评测用例1≤N,M≤10000.

对于 100% 的评测用例, 1≤N,M≤200000,1≤x≤N.

运行限制

  • 最大运行时间：3s
  • 最大运行内存: 512M

双向链表：

#include <iostream>
#include <list>
using namespace std;
list<int> l; 
int n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		l.push_back(i);
	}
	for(int i=0;i<m;i++){
		char a;
		int v;
		cin>>a>>v;
		if(a=='L'){
			l.remove(v);
			l.push_front(v);
		}
		if(a=='R'){
			l.remove(v);
			l.push_back(v);
		}
	}
	for(list<int>::iterator it=l.begin();it!=l.end();it++){
		cout<<*it<<' ';
	}
	return 0;
}

 能过50%

双指针：

#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int a[200005];
struct node{
	long long zuobiao;
	int zhi;
	bool operator<(const node &rhs)const{
		return zuobiao<rhs.zuobiao;
	}
};
node b[1000000];
int main(){
	cin>>n>>m;
	long long l=-100;
	long long r=1e6;
	for(int i=1;i<=n;i++){
		b[i].zhi=i;
		b[i].zuobiao=i;
	}
	for(int i=0;i<m;i++){
		char a;
		int v;
		cin>>a>>v;
		if(a=='L'){
			b[v].zuobiao=l;
			l--;
		}else{
			b[v].zuobiao=r;
			r++;
		}
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
		cout<<b[i].zhi<<' ';
	}
	return 0;
}

  D::::::::::::::::::数数（思维）

问题描述

任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 28=2×2×7 被分解为了三个质数相乘。请问在区间 [2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘?

答案提交

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

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 512M

 上千万的数据量，不可能12个循环吧

#include <iostream>
#include <vector>
using namespace std;
int ans;
bool sushu(int x){
	if(x==1){
		return false;
	}
	if(x==2){
		return true;
	}
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}
int su[23333339];
vector<int> p;
int main(){
	long long a=2333333;
	long long b=23333333;
	for(int i=2;i<=b;i++){
		if(!su[i]&&sushu(i)){
			su[i]=1;             //su[i]=1，代表i由一个数的值 
			p.push_back(i);      //素数压入动态数组 
		}

		if(i>=a&&su[i]==12){   //判断是否是12个数的乘积 
			ans++;
		}                     //当i==a时,p中是2到a的所有素数 

		for(vector<int>::iterator it=p.begin();it!=p.end();it++){
			if(i* *it>b){
				break;
			}else{
				su[i* *it]=su[i]+1;   //i* *it两个乘积，再i的基础上乘以*it，所以值加一； 
			}
		}
	}
	cout<<ans;
	return 0;
}

 半分钟出答案，还是慢点，填空题无所谓了

  E::::::::::::::::::约瑟夫杯（队列，循环列表）

题目描述

设有 nn 个人围坐在圆桌周围，现从某个位置 kk 上的人开始报数，报数到 m 的人就站出来。下一个人，即原来的第 m+1 个位置上的人，又从 11 开始报数，再报数到 m 的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这 n 个人的出列顺序。

蓝桥杯带刷题

要求一：采用循环链表解决。

要求二：可以使用模拟法，模拟循环链表。

要求三：可以不使用循环链表类的定义使用方式。

输入描述

输入只有一行且为用空格隔开的三个正整数 n,k,m，其含义如上所述。

输出描述

共 n 行，表示这 n 个人的出列顺序。

输入输出样例

示例 1

输入

3 5 8

输出

3
2
1

队列方法：

#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int n,k,m;     //n个人，k开始，m出 
int main(){
	cin>>n>>k>>m;
	k=k%n; 
	for(int i=k;i<=n;i++){
		q.push(i);
	}
	for(int i=1;i<k;i++){
		q.push(i);
	}
	while(!q.empty()){
		for(int i=1;i<m;i++){
			int c=q.front();
			q.pop();
			q.push(c); 
		}
		int c=q.front();
		cout<<c<<endl;
		q.pop();
	}
	return 0;
}

 循环链表方法：

#include <iostream>
using namespace std;


typedef struct node
{
  int data;
  struct node* next;
}LNode, *Linklist;


void initlink(Linklist &head, int n)
{
  head = new LNode;
  LNode * p = head;
  p->data = 1;
  for (int i = 2; i <= n; i++)
  {
    p->next = new LNode;
    p = p->next;
    p->data = i;
    }
  p->next = head;       
}


void baoshu(Linklist &head, int k, int m)
{
  LNode *p = head;
  for (int i = 1; i < k; i++)
      p = p->next;
  while (p->next != p)
  {
    for (int j = 1; j < m - 1; j++)  p = p->next;
    cout << p->next->data << endl;
    p->next = p->next->next;
    p = p->next;
  }
  cout << p->data;
}

int main()
{
    int n, k, m;
    cin >> n >> k >> m;
    Linklist head;
    initlink(head, n);
    baoshu(head, k, m);
}

  F::::::::::::::::::移动字母（DFS,BFS）

题目描述

2x3=6 个方格中放入 ABCDE 五个字母，右下角的那个格空着。如下图所示。

蓝桥杯带刷题

和空格子相邻的格子中的字母可以移动到空格中，比如，图中的 C 和 E 就可以移动，移动后的局面分别是：

A B

D E C

A B C

D E

为了表示方便，我们把 6 个格子中字母配置用一个串表示出来，比如上边的两种局面分别表示为：

AB*DEC

ABCD*E

题目的要求是：请编写程序，由用户输入若干表示局面的串，程序通过计算，输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出 1,否则输出 0。初始状态为：ABCDE*。

输入描述

先是一个整数 nn，表示接下来有 nn 行状态。

输出描述

程序输出 nn 行 1 或 0。

输入输出样例

示例

输入

7 BCDEA* DAECB* ECABD* BCDAE* DAEBC* ECADB* EDCAB*

输出

1 1 1 0 0 0 0

#include <iostream>
#include <map>
using namespace std;
int n;
string a[2];
string b[2];
int bb[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool res;
map<string,bool> vis;
bool check1(){
	for(int i=0;i<2;i++){
		for(int j=0;j<3;j++){
			if(a[i][j]!=b[i][j]){
				return false;
			}
		}
	}
	return true;
}
bool check2(int x,int y){
	return x>=0&&x<2&&y>=0&&y<3;
}
void dfs(int x,int y){

	if(res){
		return;
	}
	if(check1()){
		res=true;
		return;
	}
	for(int i=0;i<4;i++){
		int tx=x+bb[i][0];
		int ty=y+bb[i][1];
		if(check2(tx,ty) ){
			char c=a[x][y];
			a[x][y]=a[tx][ty];
			a[tx][ty]=c;
			
			if(!vis[a[0]+a[1]]) {
				vis[a[0]+a[1]]=1;
				dfs(tx,ty);

			}
			c=a[x][y];
			a[x][y]=a[tx][ty];
			a[tx][ty]=c;
	
		}
	}
}
int main(){
	cin>>n;
	
	for(int i=0;i<n;i++){
		a[0]="ABC";
		a[1]="DE*";
		for(int i=0;i<2;i++){
			for(int j=0;j<3;j++){
				cin>>b[i][j];
			}
		}
		res=false;
		vis.clear();
		dfs(1,2);
		if(res){
			cout<<1<<endl;
		}else{
			cout<<0<<endl;
		}
	}
	return 0;
}

  G::::::::::::::::::路径之迷（DFS）

题目描述

小明冒充 XX 星球的骑士，进入了一个奇怪的城堡。

城堡里边什么都没有，只有方形石头铺成的地面。

假设城堡地面是 n×n 个方格。如下图所示。

蓝桥杯带刷题

按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 n 个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。

本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

输入描述

第一行一个整数 N (0≤N≤20)，表示地面有N×N 个方格。

第二行 N 个整数，空格分开，表示北边的箭靶上的数字（自西向东）

第三行 N 个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出描述

输出一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3 ⋯

比如，上图中的方块编号为：

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

输入输出样例

示例

输入

4
2 4 3 4
4 3 3 3

输出

0 4 5 1 2 3 7 11 10 9 13 14 15

#include <iostream>
using namespace std;
int n;
int g[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int shang[25];
int zuo[25];
int shang1[25];
int zuo1[25];
bool falge;
struct node{
    int x,y;
};
node lu[405];
bool vis[25][25];
int m=1;
bool check1(){
    for(int i=0;i<n;i++){
        if(shang[i]!=shang1[i] || zuo[i]!=zuo1[i]){
            return false;
        }
    }
    return true;
}
bool check2(int x,int y){
    return x>=0&&y>=0&&x<n&&y<n;
}
bool check3(){
    for(int i=0;i<n;i++){
        if(shang1[i]>shang[i] || zuo1[i]>zuo[i]){
            return false;
        }
    }
    return true;
}
void dfs(int x,int y){
    if(!check3()|| falge){     //剪枝
        return;
    }
    if(x==n-1&&y==n-1 && check1()){
        for(int i=0;i<m;i++){
            cout<<lu[i].x*n+lu[i].y<<' ';
        }
        falge=1;
        return;
    }

    for(int i=0;i<4;i++){
        int tx=x+g[i][0];
        int ty=y+g[i][1];
        if(check2(tx,ty) && !vis[tx][ty]){
            vis[tx][ty]=1;
            lu[m].x=tx;
            lu[m].y=ty;
            shang1[ty]+=1;
            zuo1[tx]+=1;
            m++;
            dfs(tx,ty);
            lu[m].x=0;
            lu[m].y=0;
            shang1[ty]-=1;
            zuo1[tx]-=1;
            m--;
            vis[tx][ty]=0;
        }
    }
    
}
int main(){
    zuo1[0]=1;
    shang1[0]=1;
    lu[0].x=0;
    lu[0].y=0;
    vis[0][0]=1;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>shang[i];
    } 
    for(int i=0;i<n;i++){
        cin>>zuo[i];
    }
    dfs(0,0);
    return 0;
}

  H::::::::::::::::::分考场(DFS)

题目描述

n 个人参加某项特殊考试。

为了公平，要求任何两个认识的人不能分在同一个考场。

求最少需要分几个考场才能满足条件。

输入描述

输入格式：

第一行，一个整数 n (1≤n≤100)，表示参加考试的人数。

第二行，一个整数 m，表示接下来有 m 行数据。

以下 m 行每行的格式为：两个整数 a,b，用空格分开 ( 1≤a,b≤n )表示第 a 个人与第 b 个人认识。

输出描述

输出一行一个整数，表示最少分几个考场。

输入输出样例

示例

输入

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

输出

4

#include <iostream>
using namespace std;
int n,m;
bool xi[105][105];
int ans=1e8;
int cher[105][105];
void dfs(int p,int room){

	if(room>=ans){
		return;
	}
	if(p>n){
		ans=min(ans,room); 
		return;
	}
	for(int i=1;i<=room;i++){
		int j=0;
		while(cher[i][j] && !xi[cher[i][j]][p]) j++;
		if(!cher[i][j]){
			cher[i][j]=p;
			dfs(p+1,room);
			cher[i][j]=0;
		}
	}
	
	cher[room+1][0]=p;
	dfs(p+1,room+1);
	cher[room+1][0]=0;
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		xi[a][b]=xi[b][a]=1;
	}
	dfs(1,1);   //第一个人，1个教室； 
	cout<<ans;  
	return 0;
}

  I::::::::::::::::::质数拆分(DP,01背包)

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？

注意交换顺序视为同一种方法，例如 2+2017=2019 与 2017+2=2019 视为同一种方法。

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 128M
#include <iostream>
using namespace std;
long long f[2020][2020];    //前i个数组成j的方案数 

bool check(int x){
	if(x==1){
		return false;
	}
	if(x==2){
		return true;
	}
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}
int zhi[2020];
int main(){
	int len=1;
	for(int i=1;i<2019;i++){
		if(check(i)){
			zhi[len++]=i;
		}
	}
	f[0][0]=1;
	for(int i=1;i<len;i++){
		for(int j=0;j<=2019;j++){
			f[i][j]=f[i-1][j];
			if(j>=zhi[i]){
				f[i][j]+=f[i-1][j-zhi[i]];
			}
		}
	}
	cout<<f[len-1][2019];
	return 0;
}

 for(int i=1;i<len;i++){
        for(int j=0;j<=2019;j++){
            f[i][j]=f[i-1][j];
            if(j>=zhi[i]){
                f[i][j]+=f[i-1][j-zhi[i]];
            }
        }
    }

状态1：目标:值小于该质数时  f[i][j]=f[i-1][j];

状态2：目标:值不小于该质数时 要加上前i-1质数构成该指数的方案数f[i][j]+=f[i-1][j-zhi[i]];

    

J::::::::::::::::::修改数组（并查集）

题目描述

给定一个长度为 N 的数组 A=[A1​,A2​,⋅⋅⋅,AN​]，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2​,A3​,⋅⋅⋅,AN​。

当修改 Ai​ 时，小明会检查 Ai​ 是否在 A1​ ∼ Ai​−1 中出现过。如果出现过，则小明会给 Ai​ 加上 1 ；如果新的 Ai​ 仍在之前出现过，小明会持续给 Ai​ 加 1 ，直 到 Ai​ 没有在 A1​ ∼ Ai​−1 中出现过。

当 AN​ 也经过上述修改之后，显然 A 数组中就没有重复的整数了。

现在给定初始的 A 数组，请你计算出最终的 A 数组。

输入描述

第一行包含一个整数 N。

第二行包含 N 个整数 A1​,A2​,⋅⋅⋅,AN​。

其中，1≤N≤105，1≤Ai​≤106。

输出描述

输出 N 个整数，依次是最终的 A1​,A2​,⋅⋅⋅,AN​。

输入输出样例

示例

输入

5
2 1 1 3 4

输出

2 1 3 4 5

 建立一个并查集，初始化根节点都是自己，当第一次出现时，返回根节点也就是自己，然后根节点加一，下次再次查找该数时，发现自己不是大boss，然后找boss，若是下一个boss也不是大boss，就继续找，直到找到大boss。

#include <iostream>
using namespace std;
int a[10000005];
int find(int x){
	if(a[x]!=x) a[x]=find(a[x]);
	return a[x];  //不是大boss去找大boss 
}
void jiaru(int x,int y){
	int tx=find(x);
	int ty=find(y);
	if(tx!=ty){             //不是一个大boss建立新的树 
		a[x]=y;
	}
} 
int n; 
int main(){
	cin>>n;
	for(int i=1;i<=10000005;i++){
		a[i]=i;                 //初始化根节点都是自己 
	}
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		x=find(x);
		cout<<x<<' ';
		a[x]=x+1;
	} 
	return 0;
}

标签：

相关文章