程序员经验分享-hwhale

【2022年第十三届蓝桥杯省赛个人题解】

2023-11-12

A: 九进制转十进制（5分）

题目描述:
九进制正整数 ( 2022 ) 9 (2022)_9 (2022)9​ 转换成十进制等于多少？

AC代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
int main()
{
    // IOS;
    int k = 9;           //进制
    string num = "2022"; //数字
    int ans = 0;
    ll temp = 1;
    int len = num.size();
    for (int i = len - 1; i >= 0; --i)
    {
        ans += temp * (num[i] - '0');
        temp *= k;
    }
    cout << ans;
    return 0;
}

B: 顺子日期（5分）

题目描述:
小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123；而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022
年份中，一共有多少个顺子日期。

思路
不清楚0开头算不算顺子，算的话就是14，不算为4。

C: 刷题统计（10分）

题目描述:
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a a a 道题目，周六和周日每天做 b b b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n n n 题？

输入格式：
输入一行包含三个整数 a , b a, b a,b 和 n n n.

输出格式：
输出一个整数代表天数。

输入样例：

10 20 99

输出样例：

8

评测用例规模与约定
对于 50% 的评测用例， 1 ≤ a , b , n ≤ 1 0 6 1 ≤ a, b, n ≤ 10^6 1≤a,b,n≤106
对于 100% 的评测用例， 1 ≤ a , b , n ≤ 1 0 18 1 ≤ a, b, n ≤ 10^{18} 1≤a,b,n≤1018

思路
略

AC代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;

int main()
{
    IOS;
    ll a, b, n;
    cin >> a >> b >> n;
    ll ans = n / (5 * a + 2 * b) * 7;
    ll t = ans / 7 * (5 * a + 2 * b);
    for (int i = 1; i <= 7; i++)
    {
        if (t >= n)
            break;
        if (i < 6)
            t += a, ans++;
        else
            t += b, ans++;
    }
    cout << ans << endl;

    return 0;
}

D: 修剪灌木（10分）

题目描述:
爱丽丝要完成一项修剪灌木的工作。
有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

输入格式：
一个正整数 N N N ，含义如题面所述。

输出格式：
输出 N N N 行，每行一个整数，第行表示从左到右第 i i i 棵树最高能长到多高。

输入样例：

3

输出样例：

4
2
4

评测用例规模与约定
对于 30% 的数据， N ≤ 10 N ≤ 10 N≤10.
对于 100% 的数据， 1 < N ≤ 10000 1 < N ≤ 10000 1<N≤10000.

思路
略

AC代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;

int main()
{
    IOS;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cout << 2 * max(n - i, i - 1) << endl;
    return 0;
}

E: X 进制减法（15分）

题目描述:
进制规定了数字在数位上逢几进一。
X X X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某
种 X X X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则
X X X 进制数 321 321 321 转换为十进制数为 65 65 65。
现在有两个 X X X 进制表示的整数 A A A 和 B B B，但是其具体每一数位的进制还不确
定，只知道 A A A 和 B 是同一进制规则，且每一数位最高为 N N N 进制，最低为二进
制。请你算出 A − B A − B A−B 的结果最小可能是多少。
请注意，你需要保证 A A A 和 B B B 在 X X X 进制下都是合法的，即每一数位上的数
字要小于其进制。

输入格式：
第一行一个正整数 N N N，含义如题面所述。
第二行一个正整数 M a M_a Ma​，表示 X X X 进制数 A A A 的位数。
第三行 M a M_a Ma​ 个用空格分开的整数，表示 X X X 进制数 A A A按从高位到低位顺序各
个数位上的数字在十进制下的表示。
第四行一个正整数 M b M_b Mb​，表示 X X X 进制数 B B B 的位数。
第五行 M b M_b Mb​ 个用空格分开的整数，表示 X X X 进制数 B B B 按从高位到低位顺序各
个数位上的数字在十进制下的表示。
请注意，输入中的所有数字都是十进制的。

输出格式：
输出一行一个整数，表示 X X X 进制数 A − B A − B A−B 的结果的最小可能值转换为十进
制后再模 1000000007 1000000007 1000000007 的结果。

输入样例：

11
3
10 4 0
3
1 2 0

输出样例：

94

评测用例规模与约定
对于 30% 的数据， N ≤ 10 ; M a , M b ≤ 8 N ≤ 10; Ma, Mb ≤ 8 N≤10;Ma,Mb≤8.
对于 100% 的数据， 2 ≤ N ≤ 1000 ; 1 ≤ M a , M b ≤ 100000 ; A ≥ B 2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B 2≤N≤1000;1≤Ma,Mb≤100000;A≥B.

F: 统计子矩阵（15分）

题目描述:
给定一个 N × M N × M N×M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1 1 × 1 1×1，最大
N × M N × M N×M) 满足子矩阵中所有数的和不超过给定的整数 K K K?

输入格式：
第一行包含三个整数 N , M 和 K N, M 和 K N,M和K.
之后 N N N行每行包含 M M M个整数，代表矩阵 A A A

输出格式：
一个整数代表答案。

输入样例：

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

输出样例：

19

评测用例规模与约定
对于 30% 的数据， N , M ≤ 20 N, M ≤ 20 N,M≤20.
对于 70% 的数据， N , M ≤ 100 N, M ≤ 100 N,M≤100.
对于 100% 的数据， 1 ≤ N , M ≤ 500 ; 0 ≤ A i j ≤ 1000 ; 1 ≤ K ≤ 250000000 1 ≤ N, M ≤ 500; 0 ≤ A_{ij} ≤ 1000; 1 ≤ K ≤ 250000000 1≤N,M≤500;0≤Aij​≤1000;1≤K≤250000000.

思路
先建立二维前缀和数组。
先枚举两条竖着的直线，为矩阵的左边和右边，然后从上到下双指针扫描，把二维问题变成一维问题。即给定一个一维数组，求连续一段区间和小于等于k的区间数量

AC代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const int N = 510;
int a[N][N], b[N][N];
int main()
{
    IOS;
    int n, m, k;
    ll ans = 0;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
        }
    }
    for (int l = 1; l <= m; l++) //枚举矩阵的左边
    {
        for (int r = l; r <= m; r++) //枚举矩阵的右边
        {
            for (int i = 1, j = 1; i <= n; i++) //有了左右边界，从上到下扫描
            {
                while (j <= i && (b[i][r] - b[i][l - 1] - b[j - 1][r] + b[j - 1][l - 1]) > k)
                    j++;
                if (j <= i) //有可能最小的矩阵都不满足，此时j>i
                    ans += (i - j + 1);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

G: 积木画（20分）

题目描述:
小明最近迷上了积木画，有这么两种类型的积木，分别为 I I I 型（大小为 2个单位面积）和 L L L 型（大小为 3 个单位面积）
同时，小明有一块面积大小为 2 × N 2 × N 2×N 的画布，画布由 2 × N 个 1 × 1 2 × N 个 1 × 1 2×N个1×1 区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？积木可以任意旋转，且画布的方向固定。

输入格式：
输入一个整数 N N N，表示画布大小。

输出格式：
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 1000000007 1000000007 取模后的值

输入样例：

3

输出样例：

5

在这里插入图片描述

评测用例规模与约定
对于所有测试用例， 1 ≤ N ≤ 10000000 1 ≤ N ≤ 10000000 1≤N≤10000000.

思路：
线性DP。

AC代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const int N = 1e7 + 10;
const int mod = 1e9 + 7;

ll dp[N][4];
// 1填上面   2填下面  3全填

int main()
{
    int n;
    cin >> n;
    dp[0][3] = 1;
    for (int i = 1; i <= n; i++)
    {
        dp[i][1] = (dp[i - 1][2] + dp[i - 2][3]) % mod;
        dp[i][2] = (dp[i - 1][1] + dp[i - 2][3]) % mod;
        dp[i][3] = ((dp[i - 1][3] + dp[i - 1][1]) % mod + (dp[i - 1][2] + dp[i - 2][3]) % mod) % mod; //不分开求和会超int，1e7没法用LL
    }

    cout << dp[n][3] % mod;
}

I: 李白打酒加强版（25分）

题目描述:
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：
无 事 街 上 走 ， 提 壶 去 打 酒 。 逢 店 加 一 倍 ， 遇 花 喝 一 斗 。 无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。 无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 N N N 次，遇到花 M M M 次。已知最后一次遇到的是花，
他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇
花是不合法的。

输入格式：
第一行包含两个整数 N N N和 M M M.

输出格式：
输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。

输入样例：

5 10

输出样例：

14

评测用例规模与约定
对于 40% 的评测用例： 1 ≤ N , M ≤ 10 1 ≤ N, M ≤ 10 1≤N,M≤10。
对于 100% 的评测用例： 1 ≤ N , M ≤ 100 1 ≤ N, M ≤ 100 1≤N,M≤100。

思路
一眼dp，dp方案为

如果最后一步是到店，那么j应该大于0，因为至少有最后一步到店，到花同理，
如果最后一步是到店，那么上一步手里有的酒应该是k / 2，也是因此我们的k应该整除于2
如果最后一步是到花，那么上一步手里有的酒应该是k + 1。
打印答案的时候不是打印 dp[n][m][0] ,因为这么打印是无法区分最后是到花还是到店，
所以往前推一步，如果最后到花，那么喝完的上一步应该是dp[n - 1][m][1]。

AC代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const int mod = 1e9 + 7;
const int N = 110;
int dp[N][N][N]; //三维分别为店、花、酒
int main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    dp[0][0][2] = 1; //初始状态
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            for (int k = 0; k <= m; k++)
            {

                if (i && k % 2 == 0)
                    dp[i][j][k] += dp[i - 1][j][k / 2] % mod; //遇到店
                if (j)
                    dp[i][j][k] += dp[i][j - 1][k + 1] % mod; //遇到花
            }
        }
    }
    cout << dp[n][m - 1][1] << endl; //最后遇到的一个一定是花
    return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

题解

蓝桥杯

算法

c

【2022年第十三届蓝桥杯省赛个人题解】 的相关文章

随机推荐

  • FPGA微型板Verilog简单音频

    简单音调生成 该模块通过使用一个计数器生成一个1 kHz的信号 该计数器在CLK的每个刻度上都递增 当计数器达到32 000时 将切换输出BUZZER 并将计数器重置为0 音频输出 使用一个1 k 电阻器和一小段实心线将GPIO引脚P97和

  • Nginx多条件IF逻辑运算（与、或操作）不支持问题解决方法

    原文地址 Nginx多条件IF逻辑运算 与 或操作 不支持问题 BIGTREE Nginx配置不支持if条件的逻辑与 逻辑或运算 而且也不支持if嵌套 例如 if e request filename request uri apple b

  • 5 建立业务需求

    业务需求代表的是需求链的顶部 它们定义解决方案的愿景和实现该方案的项目范围 用户需求和功能需求和功能需求必须与业务需求建立的背景和目标保持一致 任何无助于项目达成业务目标的需求都不宜实现 如果项目没有清晰的定义和充分沟通方向 肯定会带来灾难

  • IDEA配置tomcat服务器

    需求背景 从Eclipse转IDEA后面对的第一个问题 就是要为IDEA配置tomcat服务 否则不可用 那么 功能需求 那么 该如何配置呢 1 点击 Edit Configurations 进入tomcat服务编辑页面 如下图所示 2 点

  • 漫谈数据库表设计及索引设计

    一 数据库表设计 在数据库表设计上有个很重要的设计准则 称为范式设计 什么是范式设计 范式来自英文Normal Form 简称NF MySQL是关系型数据库 但是要想设计 个好的关系 必须使关系满足一定的约束条件 此约束已经形成了规范 分成

  • 一阶RC低通滤波器（二）

    这篇文章补充下前面讲的一阶低通滤波器 在母线电压采样或是在电机的三相端电压采样时 往往是先分压 再经过RC低通滤波器 电路图如下 1 先求输出和输入的关系 Uao Ua 从上式可以看出系统相当于一个典型的一阶低通滤波器串联了一个R2 R1

  • python-opencv之形态学操作（腐蚀和膨胀）原理详解

    形态学操作作用 Removing noise Isolation of individual elements and joining disparate elements in an image Finding of intensity

  • frp login to server failed: i/o deadline reached

    使用kcp协议有时会出现这个问题 配置改为tcp即可

  • 【科研入门】会议、期刊、出版社、文献数据库、引文数据库、SCI分区、影响因子等基础科研必备知识

    大家好 我是洲洲 欢迎关注 一个爱听周杰伦的程序员 关注公众号 程序员洲洲 即可获得10G学习资料 面试笔记 大厂独家学习体系路线等 还可以加入技术交流群欢迎大家在CSDN后台私信我 本文目录 一 会议与期刊 二 如何辨别是否正规期刊or会

  • 进阶题解：链表相交，吊打代码随想录

    随想录解法 class Solution public ListNode getIntersectionNode ListNode headA ListNode headB ListNode curA headA ListNode curB

  • #pragma data_seg共享数据使用说明

    用 pragma data seg建立一个新的数据段并定义共享数据 其具体格式为 pragma data seg shareddata HWND sharedwnd NULL 共享数据 pragma data seg 1 pragma da

  • 样本方差为何除以n-1而不是n？

    很多人可能都会有疑问 为什么要除以n 1 而不是n 如果除以n 对样本方差的估计不是无偏估计 比总体方差要小 要想是无偏估计就要调小分母 所以除以n 1 那么问题来了 为什么不是除以n 2 n 3等 所以在这里彻底总结一下 首先交代一下无偏

  • wangEditor富文本编辑器+react+antd的使用

    1 github上发现富文本编辑器 官网地址及github地址 2 结合react antd的具体使用 案例使用场景 MyModal为弹窗 弹窗显示 编辑名称及描述 描述使用wangeditor富文本编辑器实现 MyModal js imp

  • 免费的HTML5连载来了《HTML5网页开发实例详解》连载（六）媒体查询

    响应式设计的另一个重要技术手段是媒体查询 如果只是简单的设计一个流式布局系统 那么可以保证每个网格按比例的放大和缩小 但有可能会使得在小屏幕下 如手机设备 网格太小而严重影响阅读 这样的设计称不上响应式设计 媒体查询可以来解决这一问题 媒体

  • VMware workstation 14.1.8 pro 下载地址 14最新版

    VMware Workstation 14 1 8 Pro 发布于2019年11月12日 官网下载地址如下 https download3 vmware com software wkst file VMware workstation f

  • linux如何查看安装了哪些软件

    linux查看安装了哪些软件的方法 1 利用 rpm qa 命令查看rpm方法安装的软件 2 利用 dpkg l 命令查看deb方法安装的软件 3 利用 yum list installed 命令查看yum方法安装的软件 本教程操作环境 l

  • python爬虫笔记

    python爬虫笔记 找到了一个网址 https blog csdn net belalds article details 80694126 1 使用requests库 import requests 导入requests库 respon

  • MetaMask 添加BSC、Polygon网络配置

    打开浏览器 点击MetaMask插件 选择网络 点击弹窗中的 Add Network 按钮 添加各网络配置如下 1 BSC Binance Smart Chain 主网 key value 网络名称 Network Name Binance

  • python3爬虫 selenium+pyquery爬取人才网简历实战

    不废话 直接贴代码 各位看官要是觉得可以的话 麻烦点个赞 import requests pymysql pyquery time from bs4 import BeautifulSoup from selenium import web

  • 【2022年第十三届蓝桥杯省赛个人题解】

    A 九进制转十进制 5分 题目描述 九进制正整数 2022 9 2022 9 2022 9 转换成十进制等于多少 AC代码 include

热门标签