第十一届蓝桥杯省赛第一场C++A/B组真题

目录

整数序列

解码

走方格

整数拼接

网络分析

整数序列

 代码：

#include<iostream>
#include<vector>
using namespace std;
int main(){
	long long n; 
	cin>>n;
	vector<int> C;
	while(n>0){
		cout<<n<<' ';
		n/=2;
	}
	return 0;
}

解码

代码：

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    string s, res;
    cin >> s;

    for (int i = 0; i < s.size(); i ++ )
    {
        if (i + 1 < s.size() && s[i + 1] <= '9')   //下一个字母在范围内并且下一个字母是数字，ASCLL<=9一定是数字
        {
            int k = s[i + 1] - '0';  //求一下数字
            while (k -- ) res += s[i];  //字母重复k次
            i ++ ; //i++是把数字跳过
        }
        else
        {
            res += s[i];  //后面没有字母表示这个字母只出现一次
        }
    }

    cout << res << endl;
    return 0;
}

走方格

代码：dp

#include <iostream>
#include <cstring>
using namespace std;

const int N = 40;

int n, m;
int f[N][N];

int main()
{
    cin >> n >> m;
    f[1][1] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (i == 1 && j == 1) continue;  //起点
            if (i % 2 || j % 2)
                f[i][j] = f[i - 1][j] + f[i][j - 1];  //向下走和向右走
        }

    cout << f[n][m] << endl;

    return 0;
}

整数拼接

 代码：

固定A[i],计算有多少个A[j]，使得A[j]*(10^m)+A[i]是k的倍数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;

int n, m;
int a[N], s[11][N];  //s[][]ha'xi'biao

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < n; i ++ )
    {
        LL t = a[i] % m;
        for (int j = 0; j < 11; j ++ )
        {
            s[j][t] ++ ;
            t = t * 10 % m;
        }
    }

    LL res = 0;
    for (int i = 0; i < n; i ++ )
    {
        LL t = a[i] % m;
        int len = to_string(a[i]).size();  //看一下数组的大小，把数组变成字符串
        res += s[len][(m - t) % m];

        LL r = t;
        while (len -- ) r = r * 10 % m;
        if (r == (m - t) % m) res -- ;
    }

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

    return 0;
}

网络分析

 代码： 

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
int p[N], d[N];

int find(int x)
{
    if (p[x] == x || p[p[x]] == p[x]) return p[x];
    int r = find(p[x]);
    d[x] += d[p[x]];
    p[x] = r;
    return r;
}

int main()
{
    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 = find(a), b = find(b);  //a,b变成父节点
            if (a != b)
            {
                d[a] -= d[b];  //a指向b
                p[a] = b;
            }
        }
        else
        {
            a = find(a);
            d[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)]);
    puts("");

    return 0;
}

来源 acwing