[数据结构与算法]第十一届蓝桥杯省赛第一场真题C++A/B组真题

真题

纸上得来终觉浅，绝知此事要躬行。

1.整除序列

题目描述

有一个序列，序列的第一个数是 n，后面的每个数是前一个数整除 2，请输出这个序列中值为正数的项。

输入格式
输入一行包含一个整数 n。

输出格式
输出一行，包含多个整数，相邻的整数之间用一个空格分隔，表示答案。

数据范围
1≤n≤1018
输入样例：

20

输出样例：

20 10 5 2 1

解题思路

注意数据范围

代码实现

#include<cstdio>
typedef long long ll;
int main()
{
    ll n;
    scanf("%lld",&n);
    while(n>=1){
        printf("%lld ",n);
        n/=2;
    }
}

2.解码

题目描述

小明有一串很长的英文字母，可能包含大写和小写。

在这串字母中，有很多连续的是重复的。

小明想了一个办法将这串字母表达得更短：将连续的几个相同字母写成字母 + 出现次数的形式。

例如，连续的 5 个 a，即 aaaaa，小明可以简写成 a5（也可能简写成 a4a、aa3a 等）。

对于这个例子：HHHellllloo，小明可以简写成 H3el5o2。

为了方便表达，小明不会将连续的超过 9 个相同的字符写成简写的形式。

现在给出简写后的字符串，请帮助小明还原成原来的串。

输入格式
输入一行包含一个字符串。

输出格式
输出一个字符串，表示还原后的串。

数据范围
输入字符串由大小写英文字母和数字组成，长度不超过 100。
请注意原来的串长度可能超过 100。

输入样例：

H3el5o2

输出样例：

HHHellllloo

解题思路

简写的形式为字母 + 出现次数，所以对于每一个字母，我们判断它的后面是否是数字，如果是，数字是几就连续输出几个字母，如果后面不是数字，直接将该字母输出即可，注意，因为每次要考虑后面一个数据，所以要保证(i+1)<str.length()。但是，如果将循坏改成i<str.length()-1，则当最后一个字符是字母的时候，我们无法输出。

代码实现

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
string str;
int main() 
{
    cin>>str;
    for(int i=0;i<str.length();i++){
        if((i+1)<str.length()&&str[i+1]>='0'&&str[i+1]<='9'){
            while(str[i+1]>'0'){
                cout<<str[i];
                str[i+1]--;
            } 
            i++;
        }else{
            cout<<str[i];
        }
    }
    cout<<endl;
    return 0;
}

3.走方格

题目描述

在平面上有一些二维的点阵。

这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。

现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。

只能向右或者向下走。

注意，如果行号和列数都是偶数，不能走入这一格中。

问有多少种方案。

输入格式
输入一行包含两个整数 n,m。

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

数据范围
1≤n,m≤30

输入样例1：

3 4

输出样例1：

2

输入样例2：

6 6

输出样例2：

0

解题思路

此题我用动态规划解决的，
集合：f[i][j]表示从(1,1)走到(n,m)的方案数
属性：count
状态转移方程f[i][j]=f[i-1][j]+f[i][j-1]
因为如果想走到(i,j)，则要么从它的上面(i-1)走过来，要么从它的左面(j-1)走过来的，但因为这题要求行和列都为偶数的不能走，所以要将上判断

代码实现

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=35;
int f[N][N];

int main()
{
    int n,m;
    cin>>n>>m;
    
    f[1][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((i-1)&1||j&1) f[i][j]+=f[i-1][j]; //只有当行数和列数不同为奇数才能走
            if(i&1||(j-1)&1) f[i][j]+=f[i][j-1];
        }
    }
    if(n%2==0&&m%2==0) cout<<0<<endl;//如果终点就是行和列都是偶数，那么一定走不到，方案数为0
    else cout<<f[n][m]<<endl;
    return 0;
}

4.整数拼接

题目描述

给定一个长度为 n 的数组 A1,A2,???,An。

你可以从中选出两个数 Ai 和 Aj(i 不等于 j)，然后将 Ai 和 Aj 一前一后拼成一个新的整数。

例如 12 和 345 可以拼成 12345 或 34512。

注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便是 Ai=Aj 时。

请你计算有多少种拼法满足拼出的整数是 K 的倍数。

输入格式
第一行包含 2 个整数 n 和 K。

第二行包含 n 个整数 A1,A2,???,An。

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

数据范围
1≤n≤105,
1≤K≤105,
1≤Ai≤109
输入样例：

4 2
1 2 3 4

输出样例：

6

解题思路

暴力解法就是枚举所有的组合，拼接之后判断是否能被k整除即可:

>for(int i=0;i<n;i++){
        int l2=pow(10,len(a[i]));
        for(int j=i+1;j<n;j++){
            int l1=pow(10,len(a[j]));
            if((a[i]*l1+a[j])%k==0) cnt++;
            if((a[j]*l2+a[i])%k==0) cnt++;
        }
    }

但是，由于ai非常大，即使用lon long拼接也会超范围，所有要想想别的办法，我们要求的，是(a[i]*10^len(a[j])+a[j])%k=0的组合的个数，但是由于a[i]*10^len(a[j])+a[j]太大，可以将等式化成这样的形式：
a[i]*10^len(a[j])%k+a[j]%k=0即a[i]*10^len(a[j])%k=-a[j]%k，当a[j]确定之后，len(a[j])也确定了，只需要找到满足条件的a[i]有多少个即可
这里可能会绕，为什么要乘上10的len(a[j])次幂，因为要将a[j]拼接在a[i]的后面，那么这个len(a[j])也就是指数
因为k的取值范围最大是10^5，可以用哈希表，所以可以用数组cnt[i][j]预处理存下来每一个a[i]*10^n%k（其中n可以取0~10，因为ai的取值最大是10的九次方）的余数为j的有多少个
然后我们再枚举a[j]，直接查表就可以知道，因为当有了a[j]，就有了长度len(a[j])，-a[j]%k的余数也能知道，对应可以整除k的a[i]的个数就是cnt[len(a[j])][(k-a[j]%k)%k]。
因为这样求出来的数满足i<j的拼接aiaj，所以要在从后往前求一便，但其实没有必要，我们将数组翻转，然后继续从前往后求就行了。
总：我们预处理的哈希表其实就是cnt[i][j]其实就是，对于长度为ln(ai)的数aj，-aj%k的余数为j的个数，所以预处理所有可能之后，对于要枚举的任何一个数，我们得到它的长度 和-模上k的余数查表即可

代码实现

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100010;
int a[N];
int n,m;
LL res;
int cnt[11][N];//cnt[i][j] 表示a[j]*10^i % k=j的个数
int len(int x){
    int res=0;
    while(x){
        x/=10;
        res++;
    }
    return res;
}
void cal(){
    for(int i=0;i<n;i++){//枚举a[i]
        res+=cnt[len(a[i])][(m-a[i]%m)%m];//累加满足a[j]*10^len(a[i])%m==-a[i]%m的a[i]的个数,也就是在哈希表里找到长度是a[i]，且与-a[i]%m的余数相同的数的个数
        for(int j=0,power=1;j<11;j++){//因为ai最大是10^9
            cnt[j][power * 1LL * a[i] % m]++;//预处理所有的a[i],也就是求出哈希表
            power=power*10%m;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    
    cal();
    memset(cnt,0,sizeof(cnt));
    reverse(a,a+n);
    cal();
    cout<<res<<endl;
    return 0;
}

5.网络分析

题目描述

小明正在做一个网络实验。

他设置了 n 台电脑，称为节点，用于收发和存储数据。

初始时，所有节点都是独立的，不存在任何连接。

小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。

两个节点如果存在网线连接，称为相邻。

小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。

所有发送和接收的节点都会将信息存储下来。

一条信息只存储一次。

给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

输入格式
输入的第一行包含两个整数 n,m，分别表示节点数量和操作数量。

节点从 1 至 n 编号。

接下来 m 行，每行三个整数，表示一个操作。

如果操作为 1 a b，表示将节点 a 和节点 b 通过网线连接起来。当 a = b 时，表示连接了一个自环，对网络没有实质影响。
如果操作为 2 p t，表示在节点 p 上发送一条大小为 t 的信息。
输出格式
输出一行，包含 n 个整数，相邻整数之间用一个空格分割，依次表示进行完上述操作后节点 1 至节点 n 上存储信息的大小。

数据范围
1≤n≤10000,
1≤m≤105,
1≤t≤100
输入样例1：

4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1

输出样例1：

13 13 5 3

解题思路

考查算法：并查集
题目中有两个操作：
1.给两个点之间加一条边
2.给某个连通块的每一个点权值加上t
第一个操作就是并查集维护连通性的基本操作，第二个操作，如果每次遍历某个集合给一个连通块的每个元素权值都加上t，时间复杂度是O(nm)的，时间超限。
只能优化加权值这一步操作，对于每个连通块，每个元素权值都加上t太复杂了，我们考虑只给每个连通块的根结点的权值加上t，而这个连通块的其他的点的权值就等于该结点到根结点路径的权值和。
合并两个点的时候，并查集基本操作是将找到两个点a，b的根节点，将a的根节点的根节点赋值为b的根结点，即p[find(a)]=find(b)，就是将a的根结点接到b的根结点下面，但是，如果直接合并，那么a的根结点的权值就改变了，因为根据我们的定义，a的根节点的权值等于a的根节点的权值加上b的根节点的权值。因为合并并不能将之前的权值传过去，所以不能直接加，好的办法就是，将a的根结点的权值减去b的根结点的权值再合并，这样的话，a的根节点以及子孙的权值在计算的时候，权值不变。
比如：


路径压缩的时候，x结点的位置有三种情况:
1.x结点就是根结点 那么它的权值就是他本身的权值，不用路径压缩，权值d[x]=d[x]
2.若x结点的根节点p[x]，p[x]的根结点就是p[x]，也就是x是第二层，也不用路径压缩了,权值d[x]+=d[p[x]]
3.其他的情况归为一类，都需要路径压缩，若x结点的根节点p[x]，p[x]的祖宗结点是r，p[x]到r可能要经历好几个点，但一步步路径压缩之后，r是p[x]的根结点了，那么p[x]的权值为d[p[x]]=d[p[x]]+d[r]，x的权值就是d[x]=d[x]+d[p[x]]+d[r]，代入之后，d[x]+=d[p[x]]

代码实现

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=10010;
int p[N],d[N];
int find(int x){//查找加合并
    if(x==p[x]||p[p[x]]==p[x]) return p[x];//如果一个结点本身是父结点或者它上面只有一个结点，不用合并，直接返回
    int r=find(p[x]);//否则找到x的父节点的祖宗结点
    d[x]+=d[p[x]];//x结点的权值就是x的权值加上父节点的权值（此时只有两层）
    p[x]=r;//修改p[x]的结点为祖宗结点
    return r;//返回x的根结点（此时p[x]就是root，也就是第一层的了）
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--){
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(t==1){//合并a和b
            if(find(a)!=find(b)){//在一个集合的话就不用合并了 一定要先算权值再合并，不然找到的a和b的根结点是合并之后的根结点
                d[find(a)]-=d[find(b)];//合并之前，让a的根结点的权值减去b根结点的权值 这样a的根结点权值或者a的子孙的权值加上b的根结点的权值之后还是原来的权值
                 p[find(a)]=find(b);//将a的根结点合并到b的根结点上
            }
        }else{
            d[find(a)]+=b;//将a的根结点权值加b
        }
    }
    for(int i=1;i<=n;i++){//遍历所有的点
        if(i==find(i)) printf("%d ",d[i]);//如果这个点是根结点，它的权值就是最后的答案
        else printf("%d ",d[i]+d[find(i)]);//否则，一个结点的权值就是它本身加上它的父结点的权值，因为我们合并完只有两层
    }
    return 0;
}

6.超级胶水

题目描述

小明有 n 颗石子，按顺序摆成一排。

他准备用胶水将这些石子粘在一起。

每颗石子有自己的重量，如果将两颗石子粘在一起，将合并成一颗新的石子，重量是这两颗石子的重量之和。

为了保证石子粘贴牢固，粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比，本题不考虑物理单位，认为所需要的胶水在数值上等于两颗石子重量的乘积。

每次合并，小明只能合并位置相邻的两颗石子，并将合并出的新石子放在原来的位置。

现在，小明想用最少的胶水将所有石子粘在一起，请帮助小明计算最少需要多少胶水。

输入格式
输入的第一行包含一个整数 n，表示初始时的石子数量。

第二行包含 n 个整数 w1,w2,…,wn，依次表示每颗石子的重量。

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

数据范围
1≤n≤105,
1≤wi≤1000
输入样例1：

3
3 4 5

输出样例1：

47

输入样例2：

8
1 5 2 6 3 7 4 8

输出样例2：

546

解题思路

加入有三堆石子x1，x2，x3，我们有两种选择
1.先合并x1,x2,再合并x1+x2,x3,需要的胶水数量是x1*x2+(x1+x2)*x3=x1*x2+x1*x3+x2*x3=x1*(x2+x3)+x2*x3
2.先合并x2,x3,再合并x1,x2+x3，需要的胶水数量是x2*x3+x1*(x2+x3)
两者需要的胶水数量是一样的，对于所有的石子都一样，合并的先后顺序并不会影响最后的结果，所有我们可以直接从前往后计算即可
对于两堆石子 重量分别为a b
合并的答案是 a*b
对于三堆石子 重量分别为a b c
合并的答案是a*b+(a+b)*c
对于四堆石子 重量分别为a b c d
合并的答案是 a*b+(a+b)*c+(a+b+c)*d
所以很容易计算，每次将第i堆石子和第i-1堆石子相乘，第i堆的石子加上第i-1堆石子的重量，再往后遍历下一堆石子，还是与前面一堆相乘，重量再加上前面一堆石子的重量。。。

代码实现

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N=100010;
LL a[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    LL res=0;
    for(int i=2;i<=n;i++){
        res+=a[i-1]*a[i];//所需胶水数量是当前石子和前面一堆石子相乘
        a[i]+=a[i-1];//当前石子的重量变成自己的重量加上前面一堆石子的重量
    }
    printf("%lld\n",res);
    return 0;
}

这次的分享就到这里了，欢迎留言讨论，大家加油呀！！！
想到一句话：有些鸟儿注定是不会被关在笼子里的，它们的羽翼都闪耀着自由的光辉