第十三届蓝桥杯C++ B组_C

初赛心得

A: 九进制转十进制

A.1 问题描述

A.2 比赛回顾

B: 顺子日期

B.1 问题描述

B.2 比赛回顾

C: 刷题统计

C.1 问题描述

C.2 比赛回顾

C.3 题解代码

D: 修剪灌木

D.1 问题描述

D.2 比赛回顾

D.3 题解代码

E: X 进制减法

E.1 问题描述

E.2 比赛回顾

E.3 题解代码

F: 统计子矩阵

F.1 问题描述

F.2 比赛回顾

F.3 题解代码

G: 积木画

G.1 问题描述

G.2 比赛回顾

G.3 题解代码

H: 扫雷

H.1 问题描述

H.2 比赛回顾

G.3 题解代码

I: 李白打酒加强版

I.1 问题描述

I.2比赛回顾

I.3 题解代码

J: 砍竹子

J.1 问题描述

J.2比赛回顾

J.3题解代码

初赛心得

2022/4/9，本人于大一下初次参加面向各大高校的编程竞赛，在参赛选拔时，对算法的了解仅为皮毛，学习acwing算法基础课，仅能掌握快速幂、前缀和等初级算法。

经过大约一个月的学习，初步了解二分、前缀和、位运算、STL库(观看数组实现视频，无法独立完成)、暴搜、简单并查集、Kruskal(克鲁斯卡尔)求最短路、快速幂、简单博弈论(Nim游戏)，知道DP(仅观看推导视频，跟抄代码，从未自己实现)，会做简单贪心，并能够做出简单推导，学习了微扰法证明国王游戏(可在算法竞赛进阶指南中查阅)。

A: 九进制转十进制 A.1 问题描述

九进制正整数 (2022) 9 转换成十进制等于多少？

A.2 比赛回顾

简单进制转换(开始的时候还差点算错，后来看到X进制一题，觉得不太对劲，回来才更正了)

B: 顺子日期 B.1 问题描述

小明特别喜欢顺子。

顺子指的就是连续的三个数字： 123 、 456 等。

顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。

例如 20220123 就是一个顺子日期，因为它出现了一个顺子： 123 ；而 20221023 则不是一个顺子日期，它一个顺子也没有。

小明想知道在整个 2022 年份中，一共有多少个顺子日期

B.2 比赛回顾

目前来说题目还有争议(做的时候没想那么多，直接在纸上推)

C: 刷题统计 C.1 问题描述

【问题描述】小明决定从下周一开始努力刷题准备蓝桥杯竞赛。

他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。

请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？【输入格式】输入一行包含三个整数 a , b 和 n . 【输出格式】输出一个整数代表天数。

【样例输入】 10 20 99 【样例输出】 8 【评测用例规模与约定】对于 50 % 的评测用例， 1 ≤ a , b , n ≤ 10 6 . 对于 100 % 的评测用例， 1 ≤ a , b , n ≤ 10 18 .

C.2 比赛回顾

做的时候没想那么多，也不太看数据，最多知道a b要用long long，对于时间复杂度的关注是我在比赛后的这两三天只内，听学长讲，xyc讲才开始的。

C.3 题解代码

#include

using namespace std;
//对于100%的样例，a,b,n为long long
#define int long long
int n;
int a,b;
int ans;

signed main()
{
    cin>>a>>b>>n;
    
    int t=n/(a*5+b*2);//算出每周做题，总题数/周，下取整
    int T=n%(a*5+b*2);//计算剩余题目
    int cnt=0;//统计天数
    for(int i=0;i<7;i++)
    {//i不会超过7，即如果超过7天，则会被算入t
        if(T<=0)break;//如果T减到零以后结束循环，可能半天做完，也得算一天
        if(i==5&&i==6)T-=b;
        else T-=a;
        cnt=i+1;
    }
    cout<

 
c题，对于全部数据n要超1e8的，如果按天计算，必超时。

 
 
D: 修剪灌木 
D.1 问题描述 
 
 
  【问题描述】
  
 
  爱丽丝要完成一项修剪灌木的工作。

 
  
 
  有 
  N 
  棵灌木整齐的从左到右排成一排。

爱丽丝在每天傍晚会修剪一棵灌 
  
 
  木，让灌木的高度变为 
  0 
  厘米。

爱丽丝修剪灌木的顺序是从最左侧的灌木开始， 
  
 
  每天向右修剪一棵灌木。

当修剪了最右侧的灌木后，她会调转方向，下一天开 
  
 
  始向左修剪灌木。

直到修剪了最左的灌木后再次调转方向。

然后如此循环往复。

 
  
 
  灌木每天从早上到傍晚会长高 
  1 
  厘米，而其余时间不会长高。

在第一天的 
  
 
  早晨，所有灌木的高度都是 
  0 
  厘米。

爱丽丝想知道每棵灌木最高长到多高。

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

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

 
  
  
 
  【样例输入】 
  
 
  3 
  
  
 
  【样例输出】 
  
 
  4
  
 
  2
  
 
  4 
  
  
 
  【评测用例规模与约定】 
  
 
  对于 
  30
  % 
  的数据，
  N 
  ≤ 
  10
  . 
  
 
  对于 
  100
  % 
  的数据，
  1 
  < 
  N 
  ≤ 
  10000
  . 
  
 
D.2 比赛回顾 
当时做的时候脑子已经想不了太多了，直接暴力模拟，来回砍三次即可，我还算了一下时间复杂度，不是嵌套循环，应该是3*n，结果不会超时。

 
D.3 题解代码 
#include

using namespace std;
int n;

int main()
{
    cin>>n;
    
    for(int i=0;i
 
经推导可得，第k棵树(k为1~n)的最大高度为，k-1 或 n-k 的最大值*2 
 
E: X 进制减法  
E.1 问题描述 
 
 
  【问题描述】
  
 
  进制规定了数字在数位上逢几进一。

 
  
 
  X 
  进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某 
  
 
  种 
  X 
  进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 
  
 
  X 
  进制数 
  321 
  转换为十进制数为 
  65
  。

 
  
 
  现在有两个 
  X 
  进制表示的整数 
  A 
  和 
  B
  ，但是其具体每一数位的进制还不确 
  
 
  定，只知道 
  A 
  和 
  B 
  是同一进制规则，且每一数位最高为 
  N 
  进制，最低为二进 
  
 
  制。

请你算出 
  A 
  − 
  B 
  的结果最小可能是多少。

 
  
 
  请注意，你需要保证 
  A 
  和 
  B 
  在 
  X 
  进制下都是合法的，即每一数位上的数 
  
 
  字要小于其进制。

 
  
  
 
  【输入格式】 
  
 
  第一行一个正整数 
  N
  ，含义如题面所述。

 
  
 
  第二行一个正整数 
  M
  a
  ，表示 
  X 
  进制数 
  A 
  的位数。

 
  
 
  第三行 
  M
  a 
  个用空格分开的整数，表示 
  X 
  进制数 
  A 
  按从高位到低位顺序各 
  
 
  个数位上的数字在十进制下的表示。

 
  
 
  第四行一个正整数 
  M
  b
  ，表示 
  X 
  进制数 
  B 
  的位数。

 
  
 
  第五行 
  M
  b 
  个用空格分开的整数，表示 
  X 
  进制数 
  B 
  按从高位到低位顺序各 
  
 
  个数位上的数字在十进制下的表示。

 
  
 
  请注意，输入中的所有数字都是十进制的。

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


  
  
   
  
   【样例输入】 
   
  
   11 
   
  
   3 
   
  
   10 4 0 
   
  
   3 
   
  
   1 2 0 
   
   
  
   【样例输出】 
   
  
   94 
   
   
  
   【样例说明】 
   
  
   当进制为：最低位 
   2 
   进制，第二数位 
   5 
   进制，第三数位 
   11 
   进制时，减法 
   
  
   得到的差最小。

此时 
   A 
   在十进制下是 
   108
   ，
   B 
   在十进制下是 
   14
   ，差值是 
   94
   。

 
   
   
  
   【评测用例规模与约定】 
   
  
   对于 
   30
   % 
   的数据，
   N 
   ≤ 
   10; 
   M
   a
   , 
   M
   b 
   ≤ 
   8
   . 
   
  
   对于 
   100
   % 
   的数据，
   2 
   ≤ 
   N 
   ≤ 
   1000; 1 
   ≤ 
   M
   a
   , 
   M
   b 
   ≤ 
   100000; 
   A 
   ≥ 
   B
   
  
 
E.2 比赛回顾 
做到这个地方，理解题意已经开始困难了，开始没搞懂他给的样例是怎么转换的，就先看了后面的二维前缀和，读懂题目之后，其实当时的我并不知道这会是一个贪心题目，只是能够感觉到，X应该是a[i]+1,b[i]+1中的最大值，想到这里就很明晰了，先算出X，再用该位进制*(a[i]-b[i])即可 
E.3 题解代码 
#include

using namespace std;

const int mod=1000000007;
const int N=1e5+10;
int n,A,B;
int a[N],b[N],x[N];
long long ans;
signed main()
{
    cin>>n;//n用不到
    cin>>A;//A的位数
    for(int i=A-1;i>=0;i--)cin>>a[i];
    cin>>B;//B的位数
    for(int i=B-1;i>=0;i--)cin>>b[i];
    //比较算出x，注意x最小为2
    for(int i=0;i
 
(ans+mod)%mod是一个很神奇的运算，可以消除负数取模运算规律的影响。

 
 
F: 统计子矩阵 
F.1 问题描述 
 
 
  【问题描述】 
  
 
  给定一个 
  N 
  × 
  M 
  的矩阵 
  A
  ，请你统计有多少个子矩阵 
  (
  最小 
  1 
  × 
  1
  ，最大 
  
 
  N 
  × 
  M
  ) 
  满足子矩阵中所有数的和不超过给定的整数 
  K
  ? 
  
  
 
  【输入格式】 
  
 
  第一行包含三个整数 
  N
  , 
  M 
  和 
  K
  . 
  
 
  之后 
  N 
  行每行包含 
  M 
  个整数，代表矩阵 
  A
  . 
  
  
 
  【输出格式】 
  
 
  一个整数代表答案。

 
  
  
 
  【样例输入】 
  
 
  3 4 10 
  
 
  1 2 3 4 
  
 
  5 6 7 8 
  
 
  9 10 11 12 
  
  
 
  【样例输出】 
  
 
  19 
  
  
 
  【样例说明】 
  
 
  满足条件的子矩阵一共有 
  19
  ，包含： 
  
 
  大小为 
  1 
  × 
  1 
  的有 
  10 
  个。

 
  
 
  大小为 
  1 
  × 
  2 
  的有 
  3 
  个。


  
  
  
   大小为 
   1 
   × 
   3 
   的有 
   2 
   个。

 
   
  
   大小为 
   1 
   × 
   4 
   的有 
   1 
   个。

 
   
  
   大小为 
   2 
   × 
   1 
   的有 
   3 
   个。

 
   
   
  
   【评测用例规模与约定】 
   
  
   对于 
   30
   % 
   的数据，
   N
   , 
   M 
   ≤ 
   20
   . 
   
  
   对于 
   70
   % 
   的数据，
   N
   , 
   M 
   ≤ 
   100
   . 
   
  
   对于 
   100
   % 
   的数据，
   1 
   ≤ 
   N
   , 
   M 
   ≤ 
   500; 0 
   ≤ 
   A
   i j 
   ≤ 
   1000; 1 
   ≤ 
   K 
   ≤ 
   250000000
   . 
   
  
 
F.2 比赛回顾 
F.3 题解代码  
 
G: 积木画  
G.1 问题描述 
G.2 比赛回顾 
G.3 题解代码 
 
H: 扫雷  
H.1 问题描述 
H.2 比赛回顾 
G.3 题解代码 
 
I: 李白打酒加强版 
I.1 问题描述 
I.2比赛回顾 
I.3 题解代码 
J: 砍竹子 
J.1 问题描述 
J.2比赛回顾 
J.3题解代码					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/607242.html

第十三届蓝桥杯C++ B组

发表评论

评论列表（0条）