🍎 博客主页:🌙@披星戴月的贾维斯
🍎 欢迎关注:👍点赞🍃收藏🔥留言
🍇系列专栏:🌙 蓝桥杯
🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得,但是请相信,世界上总有一些美好值得我们全力以赴,哪怕粉身碎骨!🌙
🍉一起加油,去追寻、去成为更好的自己!
蓝桥杯倒计时 14天
提示:以下是本篇文章正文内容,下面案例可供参考
🍎1、质数问题
🔥1.1题目链接🔥质数问题
🔥1.2题目描述🔥
给定两个整数 n 和 k,请你判断在 [2,n] 的范围内是否存在不少于 k 个质数,满足可以表示为两个相邻质数与 1 的和。
例如,19 满足条件,因为 19=7+11+1。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据占一行,包含两个整数 n 和 k。
输出格式
每组数据输出占一行,如果存在不少于 k 个质数满足条件则输出 YES,否则输出 NO。
数据范围
1≤T≤30,
2≤n≤1000,
0≤k≤1000
输入样例:
5
27 2
45 7
2 0
15 1
17 1
输出样例:
YES
NO
YES
YES
YES
🔥1.3分析题意🔥
根据题意,有T次询问,每次询问输入n, k,分别表示[2 - n]区间的质数是否满足两个质数与1的和不少于k个,很显然,我们需要利用到线性筛这个算法以及枚举区间的值是否满足primes[j - 1] + primes[j] + 1 == i, 满足则ans++,最后判断一下ans是不是大于等于k就行了。
🔥1.4C++代码示例🔥
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
//默写筛质数模板
int primes[N], cnt;//primes[]数组是存每一个质数,cnt是存质数的个数
bool st[N];//判断是是不是质数
int t;
void get_primes(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) primes[cnt ++] = i; //如果i是质数就加进数表里
for(int j = 0; primes[j] <= n / i; j++) //质数值小于n /i
{
st[primes[j] * i] = true;//把prinmes[j] 的合数筛掉
if(i % primes[j] == 0) break;
}
}
}
int main ()
{
cin >> t;
get_primes(N - 1);
while(t --)
{
int n, k;
int ans = 0;
cin >> n >> k;
for(int i = 2; i <= n; i++)
{
if(st[i]) continue; //如果i不是质数继续循环
for(int j = 0; primes[j] <= n; j++)
{
if(primes[j - 1] + primes[j] + 1 == i) ans++;
}
}
if(ans >= k) puts("YES");
else puts("NO");
}
return 0;
}
🍎2、灌溉
🔥2.1题目链接🔥灌溉
🔥2.2题目描述🔥
小蓝负责花园的灌溉工作。
花园可以看成一个 n 行 m 列的方格图形。中间有一部分位置上安装有出水管。
小蓝可以控制一个按钮同时打开所有的出水管,打开时,有出水管的位置可以被认为已经灌溉好。
每经过一分钟,水就会向四面扩展一个方格,被扩展到的方格可以被认为已经灌溉好。即如果前一分钟某一个方格被灌溉好,则下一分钟它上下左右的四个方格也被灌溉好。
给定花园水管的位置,请问 k 分钟后,有多少个方格被灌溉好?
输入描述:
输入的第一行包含两个整数 n,m。
第二行包含一个整数 t,表示出水管的数量。
接下来 t 行描述出水管的位置,其中第 i 行包含两个数 r,c 表示第 r 行第 c 列有一个排水管。
接下来一行包含一个整数 k。
其中,1≤n,m≤100,1≤t≤10,1≤k≤100。
输入输出样例:
输入
3 6
2
2 2
3 4
1
输出
9
🔥2.3分析题意🔥
根据题意,我们有一个n行m列的图,然后读入t次水管的位置,有水管的地方第0分钟就是被灌溉到了,接下来就是每过一分钟,水就会向四面扩展一个方格,我们需要设置一个方向数组,我们设置一个bool数组,被灌溉到的标记为true,注意,第一次被灌溉到,由于我们还在遍历,我们需要先判断这个位置是不是刚刚被灌溉到,被灌溉到我们就置1.
🔥2.4C++代码示例🔥
#include <bits/stdc++.h>
using namespace std;
int st[102][102] = {0};//状态数组
int a[102][102] = {0};
int n, m;
int t, k;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void turn(int x, int y)
{
for(int i = 0; i < 4; i++)
{
int ax = x + dx[i];
int ay = y + dy[i];
if(ax >= 1 && ax <= n && ay >= 1 && ay <= m && st[ax][ay] == 0)
{
st[ax][ay] = 1;
a[ax][ay] = 1;//被覆盖的点标为1
}
}
}
int main()
{
int res = 0;
cin >> n >> m;
cin >> t;
while(t --)
{
int x, y;
cin >> x >> y;
st[x][y] = 1;
}
cin >> k;
while(k --)//K分钟
{
for(int i = 1; i <= 100; i++)
for(int j = 1; j <= 100; j++)
{
if(st[i][j] == 1 && a[i][j] != 1)//如果这个位置有水,并且保证这次不turn刚刚覆盖过的地方
{
turn(i, j);
}
}
}
for(int i = 1; i <= 100; i++)
for(int j = 1; j <= 100; j++)
{
if(st[i][j])
{
res++;
}
}
cout << res << endl;
return 0;
}
🍎3、最大数字
🔥3.1题目链接🔥最大数字
🔥3.2题目描述🔥
给定一个正整数 N 。你可以对 N 的任意一位数字执行任意次以下 2 种操 作:
- 将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。
- 将该位数字减 1 。如果该位数字已经是 0 , 减 1 之后变成 9 。
你现在总共可以执行 1 号操作不超过 A 次, 2 号操作不超过 B 次。 请问你最大可以将 N 变成多少?
输入格式
第一行包含 3 个整数: N, A, B。
输出格式
一个整数代表答案。
样例输入
123 1 2
样例输出
933
样例说明:
对百位数字执行 2 次 2 号操作, 对十位数字执行 1 次 1 号操作。
评测用例规模与约定
对于30% 的数据, 1≤N≤100;0≤A,B≤10。
对于100% 的数据, 1≤N≤10^17 ;0≤A,B≤100
🔥3.3分析题意🔥
根据题目样例,AB都在100以内, N用字符串表示长度也小于20,所以我们这题可以用dfs深搜来做,我们可以来分析一下1和2操作对应的操作数变化,我们的目的是让每一个当前的数x尽量大,到9最好,对于操作数1,针对当前的数来说,他的使用次数最少是a次,如果a比较小,最多是9 - x次,所以我们int t= min(a, 9 - x); 对于操作数2,因为是让数字减小的,如果不能从0 - 9,我们尽量不用,所以在使用时先判断一下操作数b是不是> x。我们在使用完一次操作往下递归时,递归完要注意恢复现场。
🔥3.4代码示例🔥
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ans;
int n, m;
char s[20];
void dfs(int i, LL res)
{
int x = s[i] - '0';
if(s[i])
{
int t = min(n, 9 - x); //对当前位置使用的操作1的次数
n -= t;
dfs(i + 1, res * 10 + t + x);
//回溯
n += t;
if(m > x)//说明能够进行操作2
{
m -= x + 1;
dfs(i + 1, res* 10 + 9);
//恢复现场
m += x + 1;
}
}
else {
ans = max(ans, res);
}
}
int main ()
{
scanf("%s%d%d", s, &n, &m);
dfs(0, 0);
cout << ans << endl;
return 0;
}
🍎4、全排列的价值
🔥4.1题目链接🔥全排列的价值
🔥4.2题目描述🔥
输入格式
输入一行包含一个整数 n 。
输出格式
输出一行包含一个整数表示答案, 由于所有排列的价值之和可能很大, 请 输出这个数除以 998244353 的余数。
样例输入
3
样例输出
9
样例说明
1 至 3 构成的所有排列的价值如下:
0+1+2=3
0+1+1=2
0+0+2=2
0+1+0=1
0+0+1=1
0+0+0=0
故总和为 3+2+2+1+1=9.
评测用例规模与约定
对于40% 的评测用例,n≤20;
对于70% 的评测用例, n≤5000;
对于所有评测用例,2≤n≤10^6
🔥4.3分析题意🔥
*分析题意,就是求出一个数的全排列,求每一个全排列中第i个数前面有多少个数<i的总和,暴力做法:dfs求全排列,然后再两层循环去枚举符合的情况,由于数据量太大,会超时,6 /20。方法2:dp。方法3:找题目的规律,正序排列C最大+逆序排列C=0:这样的对有n!/2,每对的和等于n(n-1)/2。
🔥4.4题目描述🔥
暴力的代码:
#include <bits/stdc++.h>
using namespace std;
int n;
typedef long long LL;
LL ans;
const int N = 1e6 +10;
int a[N];
bool st[N];
void dfs(int u)
{
if(u > n)
{
for(int i = 1; i <= n; i++)
{
for(int j = i - 1; j > 0; j--)
{
if(a[j] < a[i]) ans++;
}
}
return;
}
for(int i = 1; i <= n; i++)
if(!st[i]) //没被用过,是false,就进来
{
a[u] = i;//没用过的填进去
st[i] = true;
dfs(u + 1);
a[u] = 0; //恢复现场
st[i] = false;
}
}
int main()
{
cin >> n;
dfs(1);
cout << ans << endl;
return 0;
}
找规律的代码文章来源:https://www.toymoban.com/news/detail-401790.html
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll mod = 998244353;
ll n,res = 1;
int main()
{
scanf("%ld", &n);
res = (n * (n - 1) / 2) % mod;
for(int i = 3; i <= n; i ++)
{
res = (res * i) % mod;
}
// res = (res * ((n * (n - 1) / 2) % mod)) % mod;
printf("%ld", res);
return 0;
}
🍎4、总结
本文向大家介绍了质数问题、灌溉、最大数字、全排列的价值等,涉及了筛质数,模拟,dfs等算法希望大家读后也能有所收获!文章来源地址https://www.toymoban.com/news/detail-401790.html
到了这里,关于【蓝桥杯】质数问题、灌溉、最大数字、全排列的价值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!