【蓝桥杯】质数问题、灌溉、最大数字、全排列的价值

这篇具有很好参考价值的文章主要介绍了【蓝桥杯】质数问题、灌溉、最大数字、全排列的价值。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍎 博客主页:🌙@披星戴月的贾维斯
🍎 欢迎关注:👍点赞🍃收藏🔥留言
🍇系列专栏:🌙 蓝桥杯
🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得,但是请相信,世界上总有一些美好值得我们全力以赴,哪怕粉身碎骨!🌙
🍉一起加油,去追寻、去成为更好的自己!

蓝桥杯倒计时 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. 将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。
  2. 将该位数字减 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;
}

找规律的代码

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode 第 380 场周赛 Problem C 价值和小于等于 K 的最大数字(Java + 二分答案 + 规律)

    Problem: 100160. 价值和小于等于 K 的最大数字 给你一个整数 k 和一个整数 x 。 令 s 为整数 num 的下标从 1 开始的二进制表示。我们说一个整数 num 的 价值 是满足 i % x == 0 且 s[i] 是 设置位 的 i 的数目。 请你返回 最大 整数 num ,满足从 1 到 num 的所有整数的 价值 和小于等于 k 。

    2024年01月19日
    浏览(41)
  • 【动态规划】07路径问题_礼物的最大价值_C++(medium)

    题目链接:leetcode礼物的最大价值 目录 题目解析: 算法原理 1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值 编写代码 题目让我们求怎样走才能可以拿到最高价值的珠宝 由题可得: 只能从架子的 左上角 开始拿珠宝 每次可以移动到 右侧或下侧 的相邻位置 到达珠宝

    2024年02月03日
    浏览(39)
  • 题目3180:蓝桥杯2023年第十四届省赛真题-互质数的个数======及探讨互质专题

    https://www.dotcpp.com/oj/problem3162.html 已AC。 (1)首先大家要知道什么叫互质: 以及它们的性质: 在数论中,对正整数n,欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数(由高斯所命名)或是欧拉总计函数(totient fu

    2023年04月24日
    浏览(47)
  • 蓝桥杯备赛|成绩统计|排列字母|纸张尺寸

    目录   1 成绩统计 题目描述 输入描述 输出描述 输入输出样例 示例 1.1 解题思路 1.2 AC_Code Python 标程 2 排列字母 问题描述 2.1 解题思路 2.2 AC_Code Python 标程 3 纸张尺寸 问题描述 输入格式 输出格式 样例输入1 样例输出1 样例输入 2 样例输出 2 运行限制 3.1 解题思路 3.2 AC_Code P

    2023年04月09日
    浏览(44)
  • 【C语言蓝桥杯每日一题】——排列字母

    TOC     😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话

    2023年04月09日
    浏览(47)
  • 【学会动态规划】礼物的最大价值(7)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:剑指 Offer 47. 礼物的最大价值

    2024年02月16日
    浏览(39)
  • 【SQL开发实战技巧】系列(二十三):数仓报表场景☞ 如何对数据排列组合去重以及通过如何找到包含最大值和最小值的记录这个问题再次用执行计划给你证明分析函数性能不一定高

    【SQL开发实战技巧】系列(一):关于SQL不得不说的那些事 【SQL开发实战技巧】系列(二):简单单表查询 【SQL开发实战技巧】系列(三):SQL排序的那些事 【SQL开发实战技巧】系列(四):从执行计划讨论UNION ALL与空字符串UNION与OR的使用注意事项 【SQL开发实战技巧】系列

    2023年04月10日
    浏览(72)
  • [Go版]算法通关村第十三关黄金——数字数学问题之数论问题(最大公约数、素数、埃氏筛、丑数)

    题目链接:LeetCode-1979. 找出数组的最大公约数 辗转相除法其核心部分为:若r 是a ÷ b的余数,则 gcd(a, b)=gcd(b, r) 题目链接:LeetCode-204. 计数质数 如果 x 是质数,那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数。 时间复杂度分析: 外层循环的迭代次数是 n-2,即 O ( n ) O(n) O ( n ) 次

    2024年02月11日
    浏览(39)
  • 【C++】无重复数字全排列(三种方法)和有重复数字全排列

     把 1 ∼ n 1∼n 1 ∼ n 这 n n n 个整数排成一行后随机打乱顺序,输出所有可能的次序。 输入格式: 一个整数 n n n 。 1 ≤ n ≤ 9 1≤n≤9 1 ≤ n ≤ 9 。 输出格式: 按照从小到大的顺序输出所有方案,每行 1 1 1 个。 首先,同一行相邻两个数用一个空格隔开。 其次,对于两个不

    2024年02月06日
    浏览(49)
  • 华为OD机试真题【寻找最大价值的矿堆】

    1、题目描述 【寻找最大价值的矿堆】 给你一个由 ‘0’(空地)、’1’(银矿)、’2’(金矿)组成的的地图, 矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿价值1 ,金矿价值2,请你找出地图中最大价值的矿堆并输出该矿堆的

    2024年02月09日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包