投稿
  1. 首页
  2. C

第十三届蓝桥杯大赛软件赛省赛cc++ CB组赛后记录&题解

code • 2022-4-12 • C • 阅读 77

第十三届蓝桥杯大赛软件赛省赛cc++ CB组赛后记录&题解,第1张

文章目录
    • 试题 A: 九进制转十进制
      • 问题描述
      • 问题答案
    • 试题 B: 顺子日期
      • 问题描述
      • 问题答案
    • 试题 C: 刷题统计
      • 问题描述
      • 问题答案(正解)
    • 试题 D: 修剪灌木
      • 问题描述
      • 问题答案(正解)
    • 试题 E: X 进制减法
      • 问题描述
      • 问题答案(正解)
    • 试题 F: 统计子矩阵
      • 问题描述
      • 问题答案(暴力百分之70)
    • 试题 G: 积木画
      • 问题描述
      • 问题答案(g了)
    • 试题 H: 扫雷
      • 问题描述
      • 问题答案(暴力骗分)
    • 试题 I: 李白打酒加强版
      • 问题描述
      • 问题答案(暴力百分之40 & 正解)
    • 试题 J: 砍竹子(暴力百分之20 & 堆优化 & 性质方法（最快）正解)
      • 问题描述
      • 问题答案

试题 A: 九进制转十进制 问题描述

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

问题答案

答案为： 1478

试题 B: 顺子日期 问题描述

小明特别喜欢顺子。


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


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


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


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


问题答案

答案为：4 或者是 14 （我填的是4以为不包含012这种情况）

试题 C: 刷题统计 问题描述

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


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


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



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

问题答案(正解)

数据范围为1e18,所以写法首先对一周进行取余，然后再进行判断7天就可以了。


#include 

using namespace std;

typedef long long LL;
const int N = 1e5+10;
LL a,b,n;
LL day;
void solve()
{
    cin>>a>>b>>n;
    LL sum = a*5+2*b;
    if(n%sum==0)
    {
        day = n/sum*7;
    }
    else
    {
         day = n/sum*7; n%=sum;
         for(int i=1; i<=5; i++)
         {
             if(n>0) n-=a,day++;
         }
         for(int i=1; i<=2; i++)
         {
             if(n>0) n-=b,day++;
         }
    }
    cout<<day<<"\n";


}

int main()
{

    solve();
    return 0;
}
试题 D: 修剪灌木 问题描述

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



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


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


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


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


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


然后如此循环往复。



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


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


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



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



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



【样例输入】
3
【样例输出】
424
【评测用例规模与约定】
对于 30% 的数据，N ≤ 10.
对于 100% 的数据，1 < N ≤ 10000

问题答案(正解)

我采用的方法是打表找规律，模拟一下这个 *** 作打表一下找规律。


#include 


using namespace std;

typedef long long LL;

const int N = 1e5+10;
LL w[N];
int n;

void solve()
{
    scanf("%d",&n);
    if(n==1) printf("1\n");
    else if(n==2)
    {
        printf("2\n2\n");
    }
    else
    {
        int m;
        if(n%2==1)
        {
            m = n-1,m+=n/2*2;
            for(int i=1; i<=n/2; i++)
            {
                printf("%d\n",m);
                m-=2;
            }
            for(int i=1; i<=n/2+1; i++)
            {
                printf("%d\n",m);
                m+=2;
            }
        }
        else
        {
            m = n,m+=(n/2-1)*2;
            for(int i=1; i<=n/2; i++)
            {
                printf("%d\n",m);
                m-=2;
            }
            for(int i=1; i<=n/2; i++)
            {
                m+=2;
                printf("%d\n",m);
            }
        }

    }

}

int main()
{
    solve();
    return 0;
}
试题 E: X 进制减法 问题描述

【问题描述】
进制规定了数字在数位上逢几进一。



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



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


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



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



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



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



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



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



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



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



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


问题答案(正解)

本质就是贪心，从低位到高位枚举max（{a+1,b+1，2}）的进制，并把进制乘进去。



举一个例子，就是你求2的1次方到2的10次方的和一样，不过这个乘的进制不是固定的变化而已。


题意比较坑，看懂了还是好理解的。


#include 


using namespace std;

typedef long long LL;

const int N = 1e5+10,mod = 1000000007;
LL ar[N],br[N];
LL n,a,b;

void solve()
{
    scanf("%lld",&n);

    scanf("%lld",&a);
    for(int i=1; i<=a; i++) scanf("%lld",&ar[i]);
    reverse(ar+1,ar+1+a);

    scanf("%lld",&b);
    for(int i=1; i<=b; i++) scanf("%lld",&br[i]);
    reverse(br+1,br+1+b);

    int i = 1,j = 1;
    LL res = 1,sum = 0;
    while(i<=a||j<=b)
    {
        LL x=0,y=0,cnt=2;
        if(i<=a) x = ar[i],i++;
        if(j<=b) y = br[j],j++;

        cnt = max(max(x,y)+1,cnt);
        sum = (sum+(x-y)*res)%mod;
        res = res*cnt%mod;
    }
    sum = (sum%mod+mod)%mod;
    printf("%lld\n",sum);

}

int main()
{
    solve();
    return 0;
}
试题 F: 统计子矩阵 问题描述

【问题描述】
给定一个 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

问题答案(暴力百分之70)

是一个二维前缀和，不过需要优化，我没有想到直接4维暴力，骗百分之70的分。


#include 


using namespace std;

typedef long long LL;

const int N = 1e3+10,mod = 1000000007;
LL ar[N][N];
LL s[N][N];
LL n,m,k,ans;

void check(int x,int y)
{
    for(int i=x; i<=n; i++)
    {
        for(int j=y; j<=m; j++)
        {
            LL sum = ar[i][j] - ar[i-x][j] - ar[i][j-y]+ar[i-x][j-y];
            if(sum<=k) ans++;

        }

    }
}



void solve()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            scanf("%lld",&ar[i][j]);
            ar[i][j] = ar[i][j]+ar[i-1][j]+ar[i][j-1]-ar[i-1][j-1];
        }
    }

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            check(i,j);

        }
    }
    printf("%lld",ans);

}

int main()
{
    solve();
    return 0;
}
试题 G: 积木画 问题描述

【问题描述】
小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2
个单位面积）和 L 型（大小为 3 个单位面积）：
同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构
成。


小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？
积木可以任意旋转，且画布的方向固定。



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



【输出格式】
输出一个整数表示答案。


由于答案可能很大，所以输出其对 1000000007 取
模后的值
【样例输入】
3
【样例输出】
5

问题答案(g了)

没有想出来，g了，状态压缩dp忘完了。


试题 H: 扫雷 问题描述

【问题描述】
小明最近迷上了一款名为《扫雷》的游戏。


其中有一个关卡的任务如下，
在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 (xi, yi,ri) 表示在坐标 (xi, yi) 处
存在一个炸雷，它的爆炸范围是以半径为 ri 的一个圆。



为了顺利通过这片土地，需要玩家进行排雷。


玩家可以发射 m 个排雷火
箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (xj, yj,rj) 表
示这个排雷火箭将会在 (xj, yj) 处爆炸，它的爆炸范围是以半径为 rj 的一个圆，
在其爆炸范围内的炸雷会被引爆。


同时，当炸雷被引爆时，在其爆炸范围内的
炸雷也会被引爆。


现在小明想知道他这次共引爆了几颗炸雷？
你可以把炸雷和排雷火箭都视为平面上的一个点。


一个点处可以存在多个
炸雷和排雷火箭。


当炸雷位于爆炸范围的边界上时也会被引爆。



【输入格式】
输入的第一行包含两个整数 n、m.
接下来的 n 行，每行三个整数 xi, yi,ri，表示一个炸雷的信息。



再接下来的 m 行，每行三个整数 xj, yj,rj，表示一个排雷火箭的信息。



【输出格式】
输出一个整数表示答案。



【样例输入】
2 1
2 2 4
4 4 2
0 0 5
【样例输出】
2

问题答案(暴力骗分)

想用队列入射发射的炮d，然后如果可以炸到某个雷然后将雷在进行入队，进行暴力，可能我实现的有问题，在代码源上只对了一个样例。


#include 

using namespace std;

typedef long long LL;
const int N = 1e5+10,mod = 1000000007;
vector<vector<int> > p;
int n,m;
struct node
{
    int a,b,c;
}ar[N];
void solve()
{
    scanf("%d%d",&n,&m);
    int ans = 0;
    for(int i=1; i<=n; i++)
    {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        ar[i] = {a,b,c};
    }
    queue<node> q;
    for(int i=1; i<=m; i++)
    {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        node z = {a,b,c};
        q.push(z);
    }

    while(!q.empty())
    {
      node x = q.front(); q.pop();
      for(int i=1; i<=n; i++)
      {
          if(ar[i].c>10) continue;
          double x1 = x.a,y1 = x.b;
          double x2 = ar[i].a,y2 = ar[i].b;
          double r1 = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
          int r2 = sqrt(r1);
          if(r2<=x.c) q.push(ar[i]),ar[i].c = 11,ans++;
      }
    }

    printf("%d\n",ans);

}

int main()
{

    solve();
    return 0;
}
试题 I: 李白打酒加强版 问题描述

【问题描述】
话说大诗人李白，一生好饮。


幸好他从不开车。



一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。


他边走边唱：
无事街上走，提壶去打酒。



逢店加一倍，遇花喝一斗。



这一路上，他一共遇到店 N 次，遇到花 M 次。


已知最后一次遇到的是花，
他正好把酒喝光了。



请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇
花是不合法的。



【输入格式】
第一行包含两个整数 N 和 M.
【输出格式】
输出一个整数表示答案。


由于答案可能很大，输出模 1000000007 的结果。



【样例输入】
5 10
【样例输出】
14

问题答案(暴力百分之40 & 正解)

当时做题没时间了，暴力骗分百分之四十。


#include 

using namespace std;

typedef long long LL;
const int N = 1e5+10,mod = 1000000007;
int n,m;
LL ans=0;

void solve()
{
    cin>>n>>m;
    m--;
    for(int i=0; i<1<<n+m; i++)
    {
        int flag = 0;
        int dian = n,hua = m;
        LL res = 2;
        for(int j=0; j<n+m; j++)
        {
            if(i>>j&1)
            {
                if(dian<=0) {flag = 1;break;}
                else dian--,res*=2;
            }
            else
            {
                if(hua<=0) {flag=1; break;}
                else hua--,res--;
                if(res<0) {flag =1; break;}
            }
        }
        if(!flag&&res==1) ans++;
    }
    cout<<ans<<"\n";
}

int main()
{

    solve();
    return 0;
}

赛后写的正解，简单的线性转移dp，状态方程还是很好写的。


#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 110,mod = 1e9+7;
LL f[N][N][N];
int main()
{
    int n,m; cin>>n>>m;
    f[0][0][2] = 1; m--;
    for(int i=0; i<=n; i++)
        for(int j=0; j<=m; j++)
            for(int k=0; k<=m; k++)
            {
                if(i>=1)
                {
                    if(k%2==0)
                    {
                        f[i][j][k] += f[i-1][j][k/2];
                        f[i][j][k] %= mod;
                    }
                }
                if(j>=1)
                {
                    f[i][j][k] += f[i][j-1][k+1];
                    f[i][j][k] %= mod;
                }
            }
    cout<<f[n][m][1]<<"\n";
    return 0;
}
试题 J: 砍竹子(暴力百分之20 & 堆优化 & 性质方法（最快）正解) 问题描述

【问题描述】
这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的
高度为 hi.
他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。


魔法可以对连续的一
段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以
把这一段竹子的高度都变为 ⌊ √⌊ H2 ⌋ + 1⌋，其中 ⌊x⌋ 表示对 x 向下取整。


小明想
知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。



【输入格式】
第一行为一个正整数 n，表示竹子的棵数。



第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。



【输出格式】
一个整数表示答案。



【样例输入】
6
2 1 4 2 6 7
【样例输出】
5

问题答案

这道题的思路还是比较好想的，就是先从高到底进行砍竹子，数据范围是2*1e5，如何优化到logn级别，由于我前面做题较慢，我后面都是直接暴力骗分，本题我直接用优先队列维护区间最大进行暴力，可以骗百分之20的分。


#include 

using namespace std;

typedef long long LL;
const int N =2e5+10,mod = 1000000007;
int n;
LL ar[N],br[N],ans;
priority_queue<LL> q;
void solve()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld",&ar[i]);
        if(ar[i]>1) q.push(ar[i]);
    }
    while(!q.empty())
    {
        LL x = q.top(); q.pop();
        LL z = sqrt(x/2+1);
        if(z>1) q.push(z);
        for(int i=1; i<=n; i++)
        {
            if(ar[i]==x&&ar[i]==ar[i-1]) continue;
            if(ar[i]==x) ans++;
        }
        for(int i=1; i<=n; i++) if(ar[i]==x) ar[i]=z;
    }


    printf("%lld\n",ans);

}

int main()
{

    solve();
    return 0;
}

解法我们用优先队列维护期区间时间复杂度为 21e510*logn。



为什么是10 左右的，极限为1e18的时候其实我们假设都是开平方
1e18，1e9,1e5,1e3,1e2,1e1,5,2,1。


这里直接随便算的，理解了都可以了

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 2e5+10;
typedef long long LL;

struct node 
{
    LL l,r,w;    
};
bool operator< (node a,node b) 
{  
    if(a.w==b.w) return a.l>b.l; 
    return a.w<b.w;
}
priority_queue<node> q;
int n;
LL w[N],ans;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>w[i];
    for(int i=1,j = 1; i<=n; i++)
    {
        while(w[j]==w[i]) j++;
        if(w[i]<=1) 
        {
            i = j-1; continue;
        }
        node s = {i,j-1,w[i]};
        q.push(s);
        i = j-1;
    }
    
    LL l1 = 0,r1 = 0,cnt = -1,z = 0;
    while(!q.empty())
    {
        node t = q.top(); q.pop();
        if(cnt!=t.w)
        {
            ans++;
            l1 = t.l,r1 = t.r,cnt = t.w;
            z = sqrt(cnt/2+1);
            if(z>1) 
            {
                node xx  = {l1,r1,z};
                q.push(xx);
            }
        }
        else
        {
            if(t.l<=r1+1) 
            {
                r1 = t.r;
                if(z>1) 
                {
                    node xx  = {t.l,r1,z};
                    q.push(xx);
                }
            }
            else
            {
                ans++;
                l1 = t.l,r1 = t.r,cnt = t.w;
                if(z>1) 
                {
                    node xx  = {l1,r1,z};
                    q.push(xx);
                }
            }
        }
    }
    
    cout<<ans<<"\n";
    
    return 0;
}

找性质

#include 

using namespace std;

typedef long long LL;
const int N = 2e5+10;
LL f[N][10];
LL w[N];
LL ar[10];
int n;
int main()
{   
    scanf("%d",&n);
    int mx = 0,cnt = 0;
    for(int i=1; i<=n; i++)  scanf("%lld",&w[i]);

    for(int i=1; i<=n; i++)
    {
        cnt = 0;
        while(w[i]>1)
        {
            ar[++cnt] = w[i];
            w[i] = w[i]/2+1;
            w[i] = sqrt(w[i]);
        }
        mx = max(mx,cnt);
        for(int j=1,k=cnt; j<=cnt; j++,k--) f[i][j]=ar[k];
    }
    LL res = 0;
    for(int i=1; i<=mx; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(f[j][i]!=f[j-1][i]&&f[j][i]>0) res++;
        }
    }
    printf("%lld\n",res);
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/584802.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-12
下一篇 2022-04-12

发表评论

登录后才能评论

评论列表（0条）

保存