第七届蓝桥杯(软件类)C++决赛A组题解

第七届蓝桥杯(软件类)C++决赛A组题解文章目录题目链接A组真题题目结构第一题随意组合第二题拼棋盘第三题打靶第四题路径之谜第五题碱基第六题圆圈舞(待补)题目链接A组真题题目结构题目类型第一题随意组合结果填空第二题拼棋盘结果填空第三题打靶代码填空第四题路径之谜程序设计第五题碱基程序设计第六题圆圈舞程序设计第一题随意组合问题重现小明被绑架到X星球的巫师W那里。其时,W正在玩弄两组数据(2358)和(1467

大家好,又见面了,我是你们的朋友全栈君。

题目链接

A组真题

题目结构

题目 类型
第一题 随意组合 结果填空
第二题 拼棋盘 结果填空
第三题 打靶 代码填空
第四题 路径之谜 程序设计
第五题 碱基 程序设计
第六题 圆圈舞 程序设计

第一题 随意组合

  • 问题重现

    小明被绑架到X星球的巫师W那里。

    其时,W正在玩弄两组数据 (2 3 5 8) 和 (1 4 6 7)

    他命令小明从一组数据中分别取数与另一组中的数配对,

    共配成4对(组中的每个数必被用到)。

    小明的配法是:{(8,7),(5,6),(3,4),(2,1)}

    巫师凝视片刻,突然说这个配法太棒了!

    因为:
    每个配对中的数字组成两位数,求平方和,无论正倒,居然相等:
    87^2 + 56^2 + 34^2 + 21^2 = 12302
    78^2 + 65^2 + 43^2 + 12^2 = 12302

    小明想了想说:“这有什么奇怪呢,我们地球人都知道,
    随便配配也可以啊!”

    {(8,6),(5,4),(3,1),(2,7)}

    86^2 + 54^2 + 31^2 + 27^2 = 12002
    68^2 + 45^2 + 13^2 + 72^2 = 12002

    巫师顿时凌乱了。。。。。

    请你计算一下,包括上边给出的两种配法,

    巫师的两组数据一共有多少种配对方案具有该特征。

    配对方案计数时,不考虑配对的出现次序。
    就是说:
    {(8,7),(5,6),(3,4),(2,1)}

    {(5,6),(8,7),(3,4),(2,1)}
    是同一种方案。

    注意:需要提交的是一个整数,不要填写任何多余内容(比如,解释说明文字等)

  • 解题思路

    由于这组两种数据已经给出了,且数据量特别小,我们完全可以暴力全排列,为了避免重复,所以我们只需要对一组数据进行全排列配对判断即可。

  • 代码

/** *@filename:随意组合 *@author: pursuit *@CSDNBlog:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-03-21 17:24 **/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;


//答案为24种。
int a[]={ 
   2,3,5,8};
int b[]={ 
   1,4,6,7};
void solve(){ 
   
  int ans=0,temp1,temp2;
  do{ 
   
    temp1=pow(a[0]*10+b[0],2)+pow(a[1]*10+b[1],2)+pow(a[2]*10+b[2],2)+pow(a[3]*10+b[3],2);
    temp2=pow(b[0]*10+a[0],2)+pow(b[1]*10+a[1],2)+pow(b[2]*10+a[2],2)+pow(b[3]*10+a[3],2);
    if(temp1==temp2){ 
   
      cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl;
      ans++;
    }
  }while(next_permutation(a,a+4));
  cout<<ans<<endl;
}
int main() { 
   
  solve();
  return 0;
}
  • 答案

    24 24 24


第二题 拼棋盘

  • 问题重现

    有 8×8 和 6×6 的棋盘两块(棋盘厚度相同,单面有棋盘,背面无图案)。参见下图:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QUpveHNU-1616515786984)(第七届蓝桥杯(软件类)C++决赛A组题解.assets/image-20210323152742472.png)]

    组成棋盘的小格子是同样大小的正方形,黑白间错排列。

    现在需要一个10×10的大棋盘,希望能通过锯开这两个棋盘,重新组合出大棋盘。

    要求:

    1。 拼好的大棋盘仍然保持黑白格间错的特性。

    2。 两个已有的棋盘都只允许锯一锯(即锯开为两块),必须沿着小格的边沿,可以折线锯开。

    3。 要尽量保证8×8棋盘的完整,也就是说,从它上边锯下的那块的面积要尽可能小。

    要求提交的数据是:4块锯好的部分的面积。按从小到大排列,用空格分开。

    (约定每个小格的面积为1)

    比如:10 10 26 54

    当然,这个不是正确答案。

    请严格按要求格式提交数据,不要填写任何多余的内容(比如,说明解释等)

  • 解题思路

    见下图即可:

在这里插入图片描述

  • 答案

    8   8   28   56 8\space8 \space 28 \space56 8 8 28 56


第三题 打靶

  • 问题重现

小明参加X星球的打靶比赛。

比赛使用电子感应计分系统。其中有一局,小明得了96分。

这局小明共打了6发子弹,没有脱靶。

但望远镜看过去,只有3个弹孔。

显然,有些子弹准确地穿过了前边的弹孔。

不同环数得分是这样设置的:

1 , 2 , 3 , 5 , 10 , 20 , 25 , 50 1,2,3,5,10,20,25,50 1,2,3,5,10,20,25,50

那么小明的6发子弹得分都是多少呢?有哪些可能情况呢?

下面的程序解决了这个问题。

仔细阅读分析代码,填写划线部分缺失的内容。

#include <stdio.h>

#define N 8
void f(int ta[], int da[], int k, int ho, int bu, int sc){
   //我们发现ta[i]即为环数i得分,da[i]表示打中环数i的子弹数,k表示当前的子弹环数。ho表示弹孔数。bu表示子弹数,sc表示得分。
   int i,j;
   if(ho<0 || bu<0 || sc<0) return;

   if(k==N){
       if(ho>0 || bu>0 || sc>0) return;
       for(i=0; i<N; i++){
       for(j=0; j<da[i]; j++)
           printf("%d ", ta[i]);
       }
       printf("\n");
       return;
   }
   for(i=0; i<=bu; i++){
       da[k] = i;//枚举打中k环的子弹数。
       //f(ta, da, k+1, _____________ , bu-i, sc-ta[k]*i);  //填空位置
   }
   da[k] = 0;
}
int main()
{
   int ta[] = {1,2,3,5,10,20,25,50};//得分表。
   int da[N];
   f(ta, da, 0, 3, 6, 96);
   return 0;
}
  • 解题思路

    对于这种代码填空的问题我们首先要知道我们的目的:是为了得到所有可能的情况,那么我们再看这 f f f函数的参数列表分别对应什么,不难得知 t a [ i ] ta[i] ta[i]为环数得分,因为这是最后输出的数组,那么对应的 k = = N k==N k==N以及 k k k的初值,说明 k k k表示当前所枚举的子弹环数。还有其他的参数也可根据初值以及所处位置推出。清楚了这些,我们再看函数内部,其中正式在枚举打中的子弹数,然后继续往下一环遍历枚举。那么在这改变下,得分要变,子弹剩余数要变,同时还有的就是弹孔数,由于这个值只有 1 1 1 0 0 0的消费范围,故我们只要判断我们有没有枚举打中即可。故此空易解。

  • 答案

    i==0?ho:ho-1


第四题 路径之谜

  • 问题重现

    小明冒充X星球的骑士,进入了一个奇怪的城堡。

    城堡里边什么都没有,只有方形石头铺成的地面。

    假设城堡地面是 n x n 个方格。【如图1.png】所示。

    按习俗,骑士要从西北角走到东南角。

    可以横向或纵向移动,但不能斜着走,也不能跳跃。

    每走到一个新方格,就要向正北方和正西方各射一箭。

    (城堡的西墙和北墙内各有 n 个靶子)

    同一个方格只允许经过一次。但不必走完所有的方格。

    如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?

    有时是可以的,比如图1.png中的例子。

    本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)

    输入:

    第一行一个整数N(0<N<20),表示地面有 N x N 个方格

    第二行N个整数,空格分开,表示北边的箭靶上的数字(自西向东)

    第三行N个整数,空格分开,表示西边的箭靶上的数字(自北向南)

    输出:

    一行若干个整数,表示骑士路径。

    为了方便表示,我们约定每个小格子用一个数字代表,

    从西北角开始编号: 0,1,2,3…

    比如,图1.png中的方块编号为:

    0 1 2 3
    4 5 6 7
    8 9 10 11
    12 13 14 15

    示例:
    用户输入:
    4
    2 4 3 4
    4 3 3 3

    程序应该输出:
    0 4 5 1 2 3 7 11 10 9 13 14 15

    资源约定:
    峰值内存消耗 < 256M
    CPU消耗 < 1000ms

    请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

  • 解题思路

    对于这种类型的题,我们需要使用 d f s dfs dfs来求解,由于此题比较特殊,我们慢慢分析。我们已知每次走到一个点都会向所在行与所在列射一箭,也就是说,我们最后找出来的路径必须符合箭数相等,所以我们就可以根据给定的行箭数和列箭数来进行模拟判断走到最后一点后所有箭数是不是都清 0 0 0了。 那么我们就可以据此模拟来跑 d f s dfs dfs,为了避免重复,我们需要一个 v i s vis vis数组来标记各点状态,由于此题点是顺序编号的,所以我们可以不用建立图,完全可以根据坐标来确定编号。值得注意的是,我们每次走完一条路后都要还原状态,这是为了避免所有情况都遍历到,同时,我们也需要一个 f l a g flag flag标记变量来确定路径是否已找到,避免已经确定的路径被覆盖。

  • 代码

/** *@filename:路径之谜 *@author: pursuit *@CSDNBlog:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-03-22 20:27 **/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 25;
const int mod = 1e9+7;

int n;
bool vis[maxn][maxn];
int go[][2]={ 
   { 
   -1,0},{ 
   1,0},{ 
   0,-1},{ 
   0,1}};
int col[maxn],row[maxn];
bool flag;//判断是否已经找到路径。
vector<int> path;//记录路径。
bool check(){ 
   
    for(int i = 1;i <= n;i++){ 
   
        if(row[i]||col[i]){ 
   
            return false;
        }
    }
    return true;
}
void dfs(int x,int y){ 
   
    if(x==n&&y==n){ 
   
        if(check()){ 
   
            flag=true;
            return;
        }
    }
    for(int i=0;i<4;i++){ 
   
        int tx=x+go[i][0];
        int ty=y+go[i][1];
        if(tx<1||tx>n||ty<1||ty>n||vis[tx][ty]||!row[tx]||!col[ty])continue;
        vis[tx][ty]=true;
        row[tx]--;
        col[ty]--;
        path.push_back((tx-1)*n+(ty-1));
        dfs(tx,ty);
        if(flag)return;
        row[tx]++;
        col[ty]++;
        path.pop_back();
        vis[tx][ty]=0;
    }
}
void solve(){ 
   
    flag=false;
    dfs(1,1);
    int len=path.size();
    for(int i=0;i<len;i++){ 
   
        cout<<path[i];
        i==len-1?cout<<endl:cout<<" ";
    }
}
int main() { 
   
    while(cin>>n){ 
   
        memset(vis,false,sizeof(vis));
        for(int i = 1;i <= n;i++){ 
   
            cin>>col[i];
        }
        for(int i = 1;i <= n;i++){ 
   
            cin>>row[i];
        }
        path.clear();
        vis[1][1]=true;
        row[1]--,col[1]--;
        path.push_back(0);
        solve();
    }
    return 0;
}

第五题 碱基

  • 问题重现

    生物学家正在对n个物种进行研究。

    其中第i个物种的DNA序列为s[i],其中的第j个碱基为s[i][j],

    碱基一定是A、T、G、C之一。

    生物学家想找到这些生物中一部分生物的一些共性,

    他们现在关注那些至少在m个生物中出现的长度为k的连续碱基序列。

    准确的说,科学家关心的序列用2m元组(i1,p1,i2,p2…im,pm)表示,

    满足:

    1<=i1<i2<…<im<=n;

    且对于所有q(0<=q<k), s[i1][p1+q]=s[i2][p2+q]=…=s[im][pm+q]。

    现在给定所有生物的DNA序列,请告诉科学家有多少的2m元组是需要关注的。

    如果两个2m元组有任何一个位置不同,则认为是不同的元组。

    【输入格式】
    输入的第一行包含三个整数n、m、k,两个整数之间用一个空格分隔,

    意义如题目所述。

    接下来n行,每行一个字符串表示一种生物的DNA序列。

    DNA序列从1至n编号,每个序列中的碱基从1开始依次编号,

    不同的生物的DNA序列长度可能不同。

    【输出格式】
    输出一个整数,表示关注的元组个数。

    答案可能很大,你需要输出答案除以1000000007的余数。

    【样例输入】
    3 2 2
    ATC
    TCG
    ACG

    【样例输出】
    2

    再例如:
    【样例输入】
    4 3 3
    AAA
    AAAA
    AAA
    AAA

    【样例输出】
    7

    【数据规模与约定】
    对于20%的数据,k<=5,所有字符串总长L满足L <=100s
    对于30%的数据,L<=10000
    对于60%的数据,L<=30000
    对于100%的数据,n<=5,m<=5,1<=k<=L<=100000
    保证所有DNA序列不为空且只会包含’A’ ’G’ ’C’ ’T’四种字母

    资源约定:
    峰值内存消耗 < 256M
    CPU消耗 < 1000ms

    请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

    所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

    注意: main函数需要返回0
    注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
    注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。

    提交时,注意选择所期望的编译器类型。

  • 解题思路

    这道题比较新颖有趣。我们既然是要找长度为 k k k的子字符串进行配对,那么我们完全可以先将这所有的子字符串给找出来,统计它们的出现次数以及不同的子字符串。为了方便,我们采用哈希表来存储每个字符串对应子字符串的个数,用 s e t set set来统计不同的字符串。存储好之后就可以判断匹配了,每次用 s e t set set里的字符串去跑一遍 d f s dfs dfs来枚举我们可能配对成功的字符串,统计元组个数即可。

  • 代码

/** *@filename:碱基 *@author: pursuit *@CSDNBlog:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-03-22 21:36 **/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const ll mod = 1e9+7;

int n,m,k;
string s[6];
int s_index[6];//存储配对好的字符串索引。
bool vis[6];//vis[i]表示第i个字符串是否被选取。
ll ans=0;//统计方案数。
map<string,ll> res[6];
set<string> cal;
void dfs(string str,int step){ 
   
    if(step>m){ 
   
        //说明当前已经填充了m个字符串。
        for(int i=1;i<m;i++){ 
   
            if(s_index[i]>s_index[i+1]){ 
   
                //为了避免出现重复情况,我们设置字符串序号升序。
                return;
            }
        }
        ll sum=1;
        for(int i=1;i<=m;i++){ 
   
            if(!res[s_index[i]][str])return;
            sum*=res[s_index[i]][str];
        }
        ans+=sum,ans%=mod;
        return;
    }
    for(int i=1;i<=n;i++){ 
   
        if(!vis[i]){ 
   
            vis[i]=true;
            s_index[step]=i;
            dfs(str,step+1);
            vis[i]=false;
        }
    }
}
void solve(){ 
   
    //接下来开始进行判断配对。
    for(auto &x:cal){ 
   
        dfs(x,1);
    }
    cout<<ans%mod<<endl;
}
int main() { 
   
    while(cin>>n>>m>>k){ 
   
        for(int i=1;i<=5;i++){ 
   
            res[i].clear();
        }
        cal.clear();
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=n;i++){ 
   
            cin>>s[i];
        }
        string temp;
        for(int i=1;i<=n;i++){ 
   
            for(int j=0;j<=s[i].length()-k;j++){ 
   
                temp=s[i].substr(j,k);
                cal.insert(temp);
                res[i][temp]++;
            }
        }
        solve();
    }
    return 0;
}

第六题 圆圈舞(待补)

  • 问题重现

    春天温暖的阳光照耀着大地,正是草原上的小动物们最快乐的时候。小动物们在草原上开了一个舞会,欢度这美好的时光。

    舞会上最重要的一个环节就是跳圆舞曲,n只小动物手拉手围成一大圈,随着音乐跳起来。在跳的过程中,小动物们可能会变换队形。它们的变换方式是动物A松开自己右手,动物B松开自己的左手,动物A和B手拉到一起,而它们对应的松开的手(如果有的话)也拉到一起。

    例如,假设有10只小动物,按顺序围成一圈,动物1的右手拉着动物2的左手,动物2的右手拉着动物3的左手,依次类推,最后动物10的右手拉着动物1的左手。如果通过动物2和8变换队形,则动物2的右手拉着动物8的左手,而对应的动物3的左手拉着动物7的右手,这样形成了1-2-8-9-10和3-4-5-6-7两个圈。如果此时通过动物2和6变换队形,则将形成1-2-6-7-3-4-5-8-9-10一个大圈。注意,如果此时通过动物1和2变换队形,那么队形不会改变,因为动物1的右手和动物2的左手松开后又拉到一起了。

    在跳舞的过程中,每个动物i都有一个欢乐值Hi和一个感动值Fi。
    如果两个动物在一个圈中,欢乐值会彼此影响,产生欢乐能量。如果两个动物i, j(i≠j)在同一个大小为t的圈中,而动物i在动物j右手的第p个位置(动物j右手的第1个位置就是动物j右手所拉着的动物,而第2个位置就是右手第1个位置的动物右手拉着的动物,依次类推),则产生的欢乐能量为(t-p)HjFi。在跳舞的过程中,动物们的欢乐值和感动值有可能发生变化。

    圆舞曲开始的时候,所有的动物按编号顺序围成一个圈,动物n右手的第i个位置正好是动物i。现在已知小动物们变换队形的过程和欢乐值、感动值变化的过程,求每次变换后所有动物所产生的欢迎能量之和。

    【输入格式】
    输入的第一行包含一个整数n,表示动物的数量。
    接下来n行,每行两个用空格分隔的整数Hi, Fi,按编号顺序给出每只动物的欢乐值和感动值。
    接下来一行包含一个整数m,表示队形、欢乐值、感动值的变化次数。
    接下来m行,每行三个用空格分隔的整数k, p, q,当k=1时,表示小动物们通过动物p和动物q变换了队形,当k=2时,表示动物p的欢乐值变为q,当k=3时,表示动物p的感动值变为了q。

    【输出格式】
    输出m行,每行一个整数,表示每次变化后所有动物产生的能量之和。
    答案可能很大,你需要计算答案除以1000000007的余数。

    【样例输入】
    10
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    9
    1 2 8
    1 2 6
    2 8 10
    3 5 10
    1 1 2
    1 2 1
    2 5 5
    1 4 8
    1 4 5

    【样例输出】
    100
    450
    855
    1341
    1341
    811
    923
    338
    923

    【数据规模与约定】
    对于20%的数据,2<=n,m<=100。
    对于30%的数据,2<=n,m<=1000。
    另有20%的数据,只有k=1的操作且Hi,Fi均为1。
    另有20%的数据,只有k=1或2的操作且Fi均为1。
    对于100%的数据,2<=n,m<=100000,0<=Hi,Fi<=109,1<=k<=3,k=1时1<=p,q<=n且p≠q,k=2或3时1<=p<=n且0<=q<=109。

    资源约定:
    峰值内存消耗 < 256M
    CPU消耗 < 2500ms

    请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

    所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

    注意: main函数需要返回0
    注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
    注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。
    =1的操作且Hi,Fi均为1。
    另有20%的数据,只有k=1或2的操作且Fi均为1。
    对于100%的数据,2<=n,m<=100000,0<=Hi,Fi<=109,1<=k<=3,k=1时1<=p,q<=n且p≠q,k=2或3时1<=p<=n且0<=q<=109。

    资源约定:
    峰值内存消耗 < 256M
    CPU消耗 < 2500ms

    请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

    所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

    注意: main函数需要返回0
    注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
    注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。

    提交时,注意选择所期望的编译器类型。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/163851.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • springboot集成Thymeleaf(二)「建议收藏」

    springboot集成Thymeleaf(二)「建议收藏」一、基本语法使用1、传递对象:@Controllerpublic class MyController1 { @Autowired private HeroService heroService; @RequestMapping(“/hello”) public String hello(Model model) { …

  • BP 神经网络算法原理[通俗易懂]

    BP 神经网络算法原理[通俗易懂]本篇文章主要根据《神经网络与机器学习》和《人工神经网络原理》两本书,对BP神经网络的数学推导过程做了一个总结,为自己进入深度学习打下一个基础。

  • Python 字母大小写的转换

    Python 字母大小写的转换1name="AdaLovelace"2print(name.upper())3print(name.lower())

  • setCapture 和 releaseCapture

    setCapture 和 releaseCapturesetCapture函数的作用就是将后续的mouse事件都发送给这个对象,releaseCapture就是将鼠标事件还回去,由document、window、object之类的自行来处理。这样就保证了在拖动的过程中,不会由于经过了其它的元素而受到干扰另外,还有一个很重要的事情是,在Win32上,mousemove的事件不是一个连续的,也就是说,并不是我们每次移动1px的鼠标指针,就会发生一个mousemove,windows会周期性检查mouse的位置变化来产生mousemove的事件。所以,如

  • fstream 中文路径_gradle files have changed

    fstream 中文路径_gradle files have changed在C++的标准库中,std::fstream是个挺好用的文件读写流,操作文件很方便,因为是C++标准库,所以没有其它的环境依赖。在使用fstream过程中,有个打开中文路径文件会失败的问题,自己的代码中一直没处理好,这几天终于有点闲心,把这里改透。涉及很多知识点,也是个遗留已久的问题,特此做个记录。在最后用了个一劳永逸的解决此问题方法:将fstream、FILE再包装下。中文路径使用fstream调试程序过程中,发现打开含中文路径的文件时,会打开失败。查了一些资料,说在VS2008、vs200..

  • python解析json文件并提取_python读取文件并判断

    python解析json文件并提取_python读取文件并判断使用python读取json和大数据量的json.gz文件

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号