乐趣区

关于c++:2020年7月B组C蓝桥杯真题试水

哇!刚刚忽然发现我的那篇扩大欧几里得达到了 500+ 的浏览量,开森森~ 看起来致力就是有回报的嘛!用心写的文章和不用心写的文章置信宽广程序员萌都一眼看得出来撒~
高兴!你们的关注和点赞是我最大的能源嗷!┗|`O′|┛

好了,闲话不多说~ 正片开始!

A. 跑步训练

这个题集体不倡议写程序,间接手算就好了,然而要留神的是,每一轮 -600 而后 +300,就相当于 -300,然而!肯定要记得这 -300 的工夫是 120s,而不是 60s,手算党千万要小心!查看查看再查看,这个分丢得相当不值得。
后果:3880

B. 纪念日


日期题目年年有,一点都不稀奇~ 关键在于疾速 A,据说 C ++ 算日期很麻烦,谁要咱也不是 Java 选手呢,害,鱼和熊掌⑧可兼得嘛,祭上大杀器——计算器!
后果:52038720

C. 合并检测


这个题,数学功底相当强 懒得写程序的我,间接手算!

后果:10

D.REPEAT 程序


先说好啊,这玩意不是依照样例算的,实战的时候人家是给了数据的,是一个 txt 文件,那玩意长的,保障你放弃硬写出这些个循环的想法。
我从新梳理了一遍带佬的思路,而后附上了具体正文

`#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char str[N];
int a[N], b[N];// a 用来寄存以后行层的缩进格数,b 用来寄存以后层的循环次数

int main(int argc, char const *argv[])
{
    int pos = 0, p = 0, w = 1, ans = 0;//pos 存第几层循环,p 存每行后面的空格数,w 是总的循环数,ans 存后果
    a[0] = -1, b[0] = 1;
    freopen("prog.txt","r",stdin);// 就是将规范输出流重定向到这个 txt 文件中,// 从文件中获取输出
    gets(str);// 首行的“A=0”不须要
    while(gets(str)){int len = strlen(str);
        p = 0;// 每次 p 都要归零啊
        while(str[p] == ' ') p++;
        while(p <= a[pos]) w /= b[pos--];// 阐明退出了最近的那一层
        if(str[len - 1] == ':'){// 是 REPEAT 语句
            int k = str[len - 2] - '0';// 以后循环反复的次数
            w *= k;
            pos ++;// 来到新的一层
            a[pos] = p, b[pos] = k;
        }else {// 不是循环语句
            int k = str[len - 1] - '0';// 要加上的数
            ans += w * k;
        }
    }
    cout<<ans<<endl;
    return 0;
}` 

*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15
*   16
*   17
*   18
*   19
*   20
*   21
*   22
*   23
*   24
*   25
*   26
*   27
*   28
*   29
*   30
*   31

后果:241830

E. 矩阵


这题很容易让人想起咱们之前做过的那一道 DP+ 打表的题目,有人说 DP 实质就是打表,我感觉能够这么说,起码以目前我不太浅近的实力,能够这么了解。
首先咱们本人列出小数据表格,而后依据列出的表格找法则并且写代码。

这样的填表莫名让我想起了小学课本上的那个找国王要米的人,在棋盘上堆米直到堆成山。。
其实本人在草稿纸上画一画很容易发现法则——也就是咱们要的递推式。
代码就很好写了~~

`#include <bits/stdc++.h>
using namespace std;

const int N = 2025;
int dp[N][N];

int main(int argc, char const *argv[])
{dp[1][1] = 1;// 1 必然在首格
    for (int i = 2; i <= 2020; ++i)
    {for (int j = 1; j <= i; ++j)// 在第一行放 j 个
        {dp[i][j] += dp[i - 1][j - 1];
            if(2 * j >= i) dp[i][j] += dp[i - 1][j];// 如果第一行的数目 >= 第二行,那么就还能够加上上方那个
            dp[i][j] %= 2020;// 可能数很大
        }
    }
    printf("%dn", dp[2020][1010]);// 留神是第 1010 列
    return 0;
}` 

*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15
*   16
*   17
*   18
*   19
*   20
*   21

F. 整除序列


苦等了这么久终于来了一道签到题!/(ㄒ o ㄒ)/~~
蓝桥是不是变???? 了呜呜呜

`#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n;

int main(int argc, char const *argv[])
{scanf("%ld", &n);
    while(n >= 1){printf("%ld", n);
        if(n != 1) printf(" ");
        else printf("n");
        n = (int) n >> 1;
    }
    return 0;
}` 

*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15
*   16
*   17

G. 解码


签到×2!果然不会让咱们太难看哈~
我呵呵呵我又不审题!我把字母 l 看成了 1,哭晕。。我难看了,对八七!我检查!我当前肯定好好审题!

`// #include <bits/stdc++.h>
// using namespace std;
// const int MAXN = 110;
// char str[MAXN];

// int main(int argc, char const *argv[])
// {//     scanf("%s",str);
//     int len = strlen(str);
//     for (int i = 0; i < len;)
//     {
//         char ch;
//         int num = 0, digit = 0;
//         if((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z')){//             ch = str[i];
//         }
//         while(str[++i] >= '0' && str[i] <= '9'){//             digit += str[i] - '0';
//             num += digit;
//             digit *= 10;
//         }
//         for (int j = 0; j < num; ++j) putchar(ch);
//     }
//     printf("n");
//     return 0;
// }
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 110;
char s[MAXN];
int main() {scanf("%s", s);
    for (int i = 0; s[i]; i++) {if (s[i] >= 'a' && s[i] <= 'z') {putchar(s[i]);
        } else if (s[i] >= 'A' && s[i] <= 'Z') {putchar(s[i]);
        } else {int k = s[i] - '0' - 1;
            while (k--) putchar(s[i - 1]);
        }
    }
    puts("");
    return 0;
}` 

*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15
*   16
*   17
*   18
*   19
*   20
*   21
*   22
*   23
*   24
*   25
*   26
*   27
*   28
*   29
*   30
*   31
*   32
*   33
*   34
*   35
*   36
*   37
*   38
*   39
*   40
*   41
*   42
*   43
*   44
*   45
*   46

H. 走方格


尽管兴奋,切记还是不能粗心~

`#include <bits/stdc++.h>
using namespace std;

const int N = 35;
int dp[N][N];

int main(int argc, char const *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {for (int j = 1; j <= m; ++j)
        {if(i == 1 && j == 1){ // 只须要一个 1
                dp[i][j] = 1;
                continue;
            }
            if(i & 1 || j & 1) // 只有有一个不是 2 的倍数
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    printf("%dn", dp[n][m]);
    return 0;
}` 

*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15
*   16
*   17
*   18
*   19
*   20
*   21
*   22
*   23
*   24
*   25

I. 整数拼接


这题,的确没思路,要是暴力必定炸,于是瞪着带佬没有正文的代码看了一个小时,终于。。懂了,当初给敬爱的读者敌人们奉上正文~

`#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
int cnt[10][N];
int a[N];
int ans;

int get_length(int x){ // 失去一个整数的长度(利用传形参不变理论值)int length = 0;
    while(x){
        x /= 10;
        length++;
    }
    return length;
}

int main(int argc, char const *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    int ans = 0;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
    {int len = get_length(a[i]);
        int left = (m - a[i] % m) % m; // 这个 left 和 a[i]%m 是对于 m 互余的
        ans += cnt[len][left];// 看看后面有没有符合的拼接对象
        int p = 10;// 十位起步
        for (int j = 1; j <= 9; ++j)
        {cnt[j][1ll * p * a[i] % m] ++;// 这个数的另一半是 j 位,这个数就是 (j+1) 位,不然无奈拼接
            p *= 10;
        }
    }
    memset(cnt, 0, sizeof(cnt));// 记得清空
    for (int i = n; i >= 1; --i)// 反着跑一遍
    {int len = get_length(a[i]);
        int left = (m - a[i] % m) % m;
        ans += cnt[len][left];// 看看前面有没有符合的拼接对象
        int p = 10;// 十位起步
        for (int j = 1; j <= 9; ++j)
        {cnt[j][1ll * p * a[i] % m] ++;// 这个数的另一半是 j 位,这个数就是 (j+1) 位,不然无奈拼接
            p *= 10;
        }
    }
    printf("%dn", ans);
    return 0;
}` 

*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15
*   16
*   17
*   18
*   19
*   20
*   21
*   22
*   23
*   24
*   25
*   26
*   27
*   28
*   29
*   30
*   31
*   32
*   33
*   34
*   35
*   36
*   37
*   38
*   39
*   40
*   41
*   42
*   43
*   44
*   45
*   46
*   47
*   48
*   49
*   50
*   51
*   52

为什么 (m-x%m) 和 x%m 是符合的呢?
咱们来钻研一个案例就分明了——
45 为什么能够整除 3?
因为 40%3=1(这一部分余三多一),而 3 -5%3 也 =1(这一部分余三少一),刚刚好,一拍即合!加起来就能够整除 3。这也就是 ans += cntlen 的理由。

J. 网络分析

最初一题拖了三天了 QWQ,效率太低了(废物哇的一声哭进去)


这题,不是裸的并查集,留神标黄局部。
每次新的结点退出之后,之前汇合中的点加上的值是不能算在新人头上的,洗澡的时候想到了,每次新人退出的时候,就问问本人的父亲当初手上有多少值,而后本人的结点就要减去前人积攒(也就是退出的时候父亲的值)的值,最初在输入的时候查看是否是根结点,如果不是就要加上父亲的值,等于新人退出之后的值之和。
原本想的是每个点都标记前人的值,起初借鉴了带佬的思路,每次在 merge 的时候减去根结点的值,而后再在最初加回来,就是退出之后的值,还是感觉这样比较简单。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e4 + 10;
int father[N];
ll ans[N];

void init(int x){for (int i = 1; i <= x; ++i)
        father[i] = i;
}

int find(int x){
    int a = x;
    while(x != father[x]) x = father[x];// x 到达根节点
    while(a != father[a]){// 门路压缩
        father[a] = x;
        a = father[a];
    }
    return x;
}

void merge(int x, int y){x = find(x), y = find(y);
    if(x != y) {father[x] = y; // x 的粑粑是 y
        ans[x] -= ans[y]; // 之前的他人的就要减掉,只算退出之后的【要害一步】}
}

int main(int argc, char const *argv[])
{
    int n, m, flag;
    scanf("%d%d", &n, &m);
    init(n);
    while(m--){scanf("%d", &flag);
        if(flag == 1){int a, b; scanf("%d%d",&a, &b);
            merge(a, b);
        }else {int p, t; scanf("%d%d",&p, &t);
            int fa = find(p);
            ans[fa] += t;
        }
    }
    for (int i = 1; i <= n; ++i)
    {ll res = ans[i];
        int fa = find(i);
        if(i != fa) res += ans[fa];
        printf("%lld%c", res, "n"[i == n]);// 最初输入换行的办法,学习!}
    return 0;
}
退出移动版