目前做的一些蓝桥杯算法训练题目

1.传球游戏-DP

【问题描述】

上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
　　游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。
　　聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。

输入格式

共一行，有两个用空格隔开的整数n，m（3<=n<=30，1<=m<=30）。

输出格式

t共一行，有一个整数，表示符合题意的方法数。

样例输入

3 3

样例输出

数据规模和约定

40%的数据满足：3<=n<=30，1<=m<=20
　　100%的数据满足：3<=n<=30，1<=m<=30

代码

#include <iostream>
#include <queue>
using namespace std;
int n, m;
int all = 0;
void dfs(int i, int cnt)   //递归会超时，得用dp，dp理解为左右两边就可以
{
	if (cnt == m)
	{
		if (i == 1)
			all++;
		return;
	}
	if (i - 1 > m - cnt && n - i + 1 > m - cnt)
	{
		return;
	}
	int zuochuan = i - 1;
	int youchuan = i + 1;
	if (i == 1)
	{
		zuochuan = n;
	}
	if (i == n)
	{
		youchuan = 1;
	}
	dfs(zuochuan, cnt + 1);
	dfs(youchuan, cnt + 1);
}


int dp[40][40];

int main()
{
	cin >> n >> m;
	//dfs(1,0); 
	dp[0][1] = 1;   //这里不理解  
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int zuobian = j - 1;
			int youbian = j + 1;
			if (j == 1)
				zuobian = n;
			if (j == n)
				youbian = 1;
			dp[i][j] = dp[i - 1][zuobian] + dp[i - 1][youbian];
		}
	}
	cout << dp[m][1] << endl;
	//cout<<all<<endl;
}

2.乘积最大 -用的dfs

问题描述

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：312，当N=3，K=1时会有以下两种分法：

312=36
　　312=62

这时，符合题目要求的结果是：31*2=62

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

输入格式

程序的输入共有两行：
　　第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）
　　第二行是一个长度为N的数字串。

输出格式

输出所求得的最大乘积（一个自然数）。

样****例输入

4 2
　　1231

样例输出

代码

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
int a[100];
int maxx = 0;
int n, k;
int su(int kaishi, int jiewei)
{
	int sum = 0; //里面定义记得 = 0  
	int chen = pow(10, jiewei - kaishi);
	for (int i = kaishi; i <= jiewei; i++)
	{
		sum += a[i] * chen;
		chen /= 10;
	}
	return sum;
}

int dfs(int kaishi, int jiewei, int k)
{
	if (k == 0)
	{
		return su(kaishi, jiewei);
	}
	int ma = 0;
	for (int i = kaishi; i <= jiewei; i++)
	{
		int ans = su(kaishi, i) * dfs(i + 1, jiewei, k - 1);
		ma = max(ans, ma);
	}
	return ma;
}

int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		char x;
		cin >> x;
		a[i] = x - '0';
	}
	cout << dfs(1, n, k) << endl;
}

3.[蓝桥杯2019初赛]迷宫

题目描述

下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可
以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这
个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，
一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式，
其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。

输入

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

代码

#include<iostream>
using namespace std;
#define maxq 1000000
int mp[60][60];
int vis[60][60];
int dp[60][60];
char yf[maxq];
char yl[maxq];
int maxx = 100000;
char fx[] = { 'D','L','R','U' };
int xx[] = { 0,-1,1,0 };   //照题目最小排序来！~ 
int yy[] = { 1,0,0,-1 };

void dfs(int y, int x, int t)
{
	if (t >= maxx)
	{
		return;
	}
	if (y == 30 && x == 50)
	{
		if (t < maxx)
		{
			maxx = t;
			for (int i = 0; i < t; i++)
			{
				yl[i] = yf[i];
			}
		}
	}

	for (int i = 0; i < 4; i++)
	{
		int dy = y + yy[i];
		int dx = x + xx[i];
		if (t + 1 > dp[dy][dx])
		{
			continue;
		}
		if (dy <= 30 && dy >= 1 && dx <= 50 && dx >= 1 && vis[dy][dx] == 0 && mp[dy][dx] != 1)
		{
			dp[dy][dx] = t + 1;  //记录最短步数！！！nice！
			vis[dy][dx] = 1;
			yf[t] = fx[i];
			dfs(dy, dx, t + 1);
			vis[dy][dx] = 0;
		}
	}
}

int main()
{
	for (int i = 1; i <= 30; i++)
	{
		for (int j = 1; j <= 50; j++)
			dp[i][j] = 99999;//初始化 
	}
	for (int i = 1; i <= 30; i++)
	{
		for (int j = 1; j <= 50; j++)
		{
			char a;
			cin >> a;
			mp[i][j] = a - '0';
		}
	}
	vis[1][1] = 1;
	//	dfs(1,1,0);
	//	for(int i=0;i<maxx;i++)
	//	{
	//		cout<<yl[i];
	//	}
	cout << "DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR";
}

4.历届试题分考场 - 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

样例输出

代码

# include<iostream>
# include<bits/stdc++.h>

using namespace std;

int fs[110][110];     //关系表
int n, m;
int seat[110][110];  //座位表
int minn = 110;

void dfs(int x, int kc)
{
	if (kc >= minn || kc > n)
	{
		return;
	}


	if (x == n + 1)
	{
		if (kc < minn)
		{
			minn = kc;
		}
		return;
	}

	for (int i = 1; i <= kc; i++)
	{
		int k = 1;
		while (seat[i][k] != 0 && fs[x][seat[i][k]] == 0)
		{
			k++;
		}
		if (seat[i][k] == 0)
		{
			seat[i][k] = x;
			dfs(x + 1, kc);
			seat[i][k] = 0;
		}
	}

	seat[kc + 1][1] = x;
	dfs(x + 1, kc + 1);
	seat[kc + 1][1] = 0;

}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		fs[a][b] = fs[b][a] = 1;     //关系表
	}
	dfs(1, 1);
	cout << minn << endl;
}

5.算法提高天天向上

问题描述

A同学的学习成绩十分不稳定，于是老师对他说：“只要你连续4天成绩有进步，那我就奖励给你一朵小红花。”可是这对于A同学太困难了。于是，老师对他放宽了要求：“只要你有4天成绩是递增的，我就奖励你一朵小红花。”即只要对于第i、j、k、l四天，满足i<j<k<l并且对于成绩wi<wj<wk<wl，那么就可以得到一朵小红花的奖励。现让你求出，A同学可以得到多少朵小红花。

输入格式

第一行一个整数n，表示总共有n天。第二行n个数，表示每天的成绩wi。

输出格式

一个数，表示总共可以得到多少朵小红花。

样例输入

6
1 3 2 3 4 5

样例输出

代码

#include <iostream>

using namespace std;

long long dp[2002][5];

long long a[2002];

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	
	for (int i = n - 1; i >= 0; i--)
	{
		dp[i][1] = 1;
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] > a[i])
			{
				int k = 2;
				while (k <= 4)
				{
					if (dp[j][k - 1] == 0)
						break;
					dp[i][k] += dp[j][k - 1];
					k++;
				}
			}
		}
	}
	
	long long  sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += dp[i][4];
	}
	cout << sum << endl;

}

6.算法提高日期计算

问题描述

已知2011年11月11日是星期五，问YYYY年MM月DD日是星期几？注意考虑闰年的情况。尤其是逢百年不闰，逢400年闰的情况。

输入格式

输入只有一行
　　YYYY MM DD

输出格式

输出只有一行
　　W

数据规模和约定

1599 <= YYYY <= 2999
　　1 <= MM <= 12
　　1 <= DD <= 31，且确保测试样例中YYYY年MM月DD日是一个合理日期
　　1 <= W <= 7，分别代表周一到周日

样例输入

2011 11 11

样例输出

代码

#include <iostream>

using namespace std;
int days[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };//平年365
int days2[13] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };//闰年366

bool islunar(int y)
{
    if (y % 4 == 0 && y % 100 != 0)
    {
        return true;
    }
    else if (y % 400 == 0)
    {
        return true;
    }
    return false;
}

int main()
{
    int y, m, d;
    int s = 0;
    scanf("%d%d%d", &y, &m, &d);
    if (y == 2011)
    {
        if (m > 11)
        {
            s += 19 + d;
        }
        else if (m == 11)
        {
            if (d > 11)
            {
                s += d - 11;
            }
            else if (d <= 11)
            {
                s += 11 - d;
            }
        }
        else if (m < 11)
        {
            for (int i = m + 1; i < 11; i++)
            {
                s += days[i];
            }
            s += days[m] - d + 11;
        }
    }
    else if (y > 2011)
    {
        for (int i = 2012; i < y; i++)
        {
            if (islunar(i))
            {
                s += 366;
            }
            else
            {
                s += 365;
            }
        }
        if (islunar(y))
        {
            for (int i = 1; i < m; i++)
            {
                s += days2[i];
            }
        }
        else
        {
            for (int i = 1; i < m; i++)
            {
                s += days[i];
            }
        }
        s += d + 50;
    }
    else if (y < 2011)
    {
        for (int i = y + 1; i < 2011; i++)
        {
            if (islunar(i))
            {
                s += 366;
            }
            else
            {
                s += 365;
            }
        }
        if (islunar(y))
        {
            for (int i = m + 1; i <= 12; i++)
            {
                s += days2[i];
            }
            s += days2[m] - d + 315;
        }
        else
        {
            for (int i = m + 1; i <= 12; i++)
            {
                s += days[i];
            }
            s += days[m] - d + 315;
        }
    }
    s %= 7;
    if (y > 2011 || (y == 2011 && m > 11) || (y == 2011 && m == 11 && d > 11))
    {
        if (s <= 2) {
            cout << s + 5 << endl;
        }
        else {
            cout << s - 2 << endl;
        }
    }
    else
    {
        if (s < 5) {
            cout << 5 - s << endl;
        }
        else {
            cout << 12 - s << endl;
        }
    }
    return 0;
}

7.算法提高现代诗如蚯蚓

问题描述

现代诗如蚯蚓
　　断成好几截都不会死
　　字符串断成好几截
　　有可能完全一样
　　请编写程序
　　输入字符串
　　输出该字符串最多能断成多少截完全一样的子串

输入格式

一行，一个字符串

输出格式

一行，一个正整数表示该字符串最多能断成的截数

样例输入

abcabcabcabc

样例输出

样例说明

最多能断成四个”abc”，也就是abc重复四遍便是原串
　　同时也能断成两个”abcabc”
　　最坏情况是断成一个原串”abcabcabcabc”

代码

#include <iostream>

using namespace std;

int main()
{
    string str;
    cin >> str;
    int len = str.size();
    int maxx = 1;
    for (int i = len; i > 0; i--)
    {
        if (str.size() % i == 0)
        {
            int flag = 1;
            for (int k = 0; k < i; k++)
            {
                for (int l = i; l < str.size(); l += i)
                {
                    if (str[k] != str[k + l])
                    {
                        flag = 0;
                    }
                }
            }
            if (flag == 1)
            {
                if (str.size() / i > maxx)
                {
                    maxx = str.size() / i;
                }
            }
        }
    }
    cout << maxx << endl;
    return 0;
}

8. [蓝桥杯2019初赛]数列求值

题目描述

给定数列1, 1, 1, 3, 5, 9, 17, …，从第4 项开始，每项都是前3 项的和。求
第20190324 项的最后4 位数字。

代码

#include <iostream>

using namespace std;

int main()
{
    long long int a[4];
    a[0] = 1;
    a[1] = 1;
    a[2] = 1;
    int i;
    for (i = 3; i < 100000000; i++)
    {
        a[3] = a[2] + a[1] + a[0];
        a[0] = a[1] % 10000;
        a[1] = a[2] % 10000;
        a[2] = a[3] % 10000;
        if (i == 20190323)
            break;
    }
    cout << a[3] % 10000 << endl;
    return 0;
}

9.算法提高快速幂+取模

问题描述

给定A, B, P，求(A^B) mod P。

输入格式

输入共一行。
　　第一行有三个数，N, M, P。

输出格式

输出共一行，表示所求。

样例输入

2 5 3

样例输出

数据规模和约定

共10组数据
　　对100%的数据，A, B为long long范围内的非负整数，P为int内的非负整数。

代码

参考 https://www.bilibili.com/video/BV12r4y1w7tx?from=search&seid=7396560337832777912

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4veLJXdO-1618673654550)(C:\Users\HP\AppData\Roaming\Typora\typora-user-images\image-20210410154043709.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Y8uK67dx-1618673654553)(C:\Users\HP\AppData\Roaming\Typora\typora-user-images\image-20210410154051135.png)]

#include<iostream>
using namespace std;

int main()
{
	long long a, b;
	int p;
	cin >> a >> b >> p;
	long long ans = 1;
	a %= p;
	while (b != 0)
	{
		if (b & 1)  //即 b%2==1   ,可以加快速度 
		{
			ans = (ans * a) % p;
		}
		a = (a * a) % p;
		b >>= 1; //	即 b /= 2;
	}
	cout << ans << endl;
}

10. 麦森数

题目描述

形如2^{P-1的素数称为麦森数，这时P*P*一定也是个素数。但反过来不一定，即如果P*P*是个素数，2}P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。

任务：从文件中输入P（1000<P<3100000），计算2^P-1的位数和最后500位数字（用十进制高精度数表示）

输入格式

文件中只包含一个整数P（1000<P<3100000）

输出格式

第一行：十进制高精度数2^P-1的位数。

第2-11行：十进制高精度数2^P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）

不必验证2^P-1与P是否为素数。

输入输出样例

输入 #1复制

输出 #1

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int m[1010];
int a[1010];
int temp[1010];   //要有个临时保存的 

void xianchen()
{
	memset(temp, 0, sizeof(temp));
	for (int i = 1; i <= 500; i++)  //直接500给他 
	{
		for (int j = 1; j <= 500; j++)
		{
			temp[i + j - 1] += m[i] * a[j];
			temp[i + j] += temp[i + j - 1] / 10;
			temp[i + j - 1] %= 10;
		}
	}
	memcpy(m, temp, sizeof(m));  //把 temp 的值传给 m 
}

void zichen()
{
	memset(temp, 0, sizeof(temp));
	for (int i = 1; i <= 500; i++)
	{
		for (int j = 1; j <= 500; j++)
		{
			temp[i + j - 1] += a[i] * a[j];
			temp[i + j] += temp[i + j - 1] / 10;
			temp[i + j - 1] %= 10;
		}
	}
	memcpy(a, temp, sizeof(a));
}

int main()
{
	long long p;
	cin >> p;
	cout << int((p * log10(2)) + 1) << endl;   //求位数可以通过 log10()+1 解决 
	a[1] = 2;
	m[1] = 1;
	while (p != 0)
	{
		if (p % 2 == 1)
		{
			xianchen();
		}
		p /= 2;
		zichen();
	}
	m[1]--;
	for (int i = 500; i >= 1; i--)
	{
		if (i % 50 == 0 && i != 500)
		{
			cout << endl;
		}
		cout << m[i];
	}
}

目前做的一些蓝桥杯算法训练题目

1.传球游戏-DP

【问题描述】

输入格式

输出格式

样例输入

样例输出

数据规模和约定

代码

2.乘积最大 -用的dfs

样例输出

代码

3.[蓝桥杯2019初赛]迷宫

题目描述

输入

代码

4.历届试题 分考场 - dfs

问题描述

输入格式

输出格式

样例输入

样例输出

代码

5.算法提高 天天向上

问题描述

输入格式

输出格式

样例输入

样例输出

代码

6.算法提高 日期计算

问题描述

输入格式

输出格式

数据规模和约定

样例输入

样例输出

代码

7.算法提高 现代诗如蚯蚓

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

代码

8. [蓝桥杯2019初赛]数列求值

题目描述

代码

9.算法提高 快速幂+取模

问题描述

输入格式

输出格式

样例输入

样例输出

数据规模和约定

代码

10. 麦森数

题目描述

输入格式

输出格式

输入输出样例

代码

热门文章

4.历届试题分考场 - dfs

5.算法提高天天向上

6.算法提高日期计算

7.算法提高现代诗如蚯蚓

9.算法提高快速幂+取模