不正经

这个屌丝很懒，什么也没留下！

热门标签

2020 第十一届蓝桥杯大赛软件类省赛第二场 C/C++ 大学 B 组完整题面和题解_第十届蓝桥杯大赛软件类省赛b类第二场题解(c/c++)

作者：不正经 | 2024-04-15 21:25:01

踩

第十届蓝桥杯大赛软件类省赛b类第二场题解(c/c++)

A:门牌制作

题面：

在这里插入图片描述

思路：

暴力遍历，1-2020的数字，然后判断每一位，计数。

代码：

/*
 * @Date: 2020-10-17 21:49:55
 * @LastEditTime: 2020-10-17 21:58:58
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
int main() {
  int ans = 0;
  for (int i = 1; i <= 2020; i++) {
    int j = i;
    while (j) {
      if (j % 10 == 2){
        ans++;
      }
      j /= 10;
    }
  }
  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

答案：

624

B:既约分数

在这里插入图片描述

思路：

遍历1-2020之间的任意点对，判断gcd是否为1，计数。

代码：

/*
 * @Date: 2020-10-17 22:02:12
 * @LastEditTime: 2020-10-17 22:02:24
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
  int ans = 0;
  for (int i = 1; i <= 2020; i++) {
    for (int j = 1; j <= 2020; j++) {
      if (__gcd(i, j) == 1){
        ans++;
      }
    }
  }
  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

答案:

2481215

C:蛇形填数

题面：

在这里插入图片描述

思路：

模拟整个过程，判断一下奇偶位置的特殊情况。

代码：

/*
 * @Date: 2020-10-17 22:05:26
 * @LastEditTime: 2020-10-17 22:06:55
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
int mmp[50][50], id;
int main() {
  for (int i = 1; i <= 40; i++) {
    if (i & 1) {
      int idx = i, idy = 1;
      for (int j = 0; j < i; j++){
        mmp[idx - j][idy + j] = ++id;
      }
    } else {
      int idx = 1, idy = i;
      for (int j = 0; j < i; j++){
        mmp[idx + j][idy - j] = ++id;
      }
    }
  }
  cout << mmp[20][20] << 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

答案：

761

D:跑步锻炼

题面：

在这里插入图片描述

思路：

直接模拟日期加法，递增到2020年10月1日为止，计数（注意第一天也是2哦），注意判断闰年，处理好年月日。

代码：

/*
 * @Date: 2020-10-17 22:09:57
 * @LastEditTime: 2020-10-17 22:11:55
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */

#include <bits/stdc++.h>
using namespace std;
int M[13] = {0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main() {
  int y = 2000, m = 1, d = 1, w = 6, ans = 2;
  while (y != 2020 || m != 10 || d != 1) {
    if (y % 400 == 0 || (y % 4 == 0 && y % 100)) {
      M[2] = 29;
    } else {
      M[2] = 28;
    }
    d++;
    w = (w + 1) % 7;
    if (d > M[m]) {
      d = 1;
      m++;
      if (m > 12) {
        m = 1;
        y++;
      }
    }
    if (d == 1 || w == 1) {
      ans++;
    }
    ans++;
  }
  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
32
33
34
35
36
37

答案：

8879

E:七段码

题面：

在这里插入图片描述

思路：

暴力枚举 $2^7=128$ 次方的所有七段码，然后DFS判断联通块。（不愧是~~暴力杯~~ ）

代码：

建图代码:

/*
 * @Date: 2020-10-17 21:20:30
 * @LastEditTime: 2020-10-17 22:15:57
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
int main() {
  int ans = 0;
  freopen("in.txt", "w", stdout);
  for (int a = 0; a <= 1; a++) {
    for (int b = 0; b <= 1; b++) {
      for (int c = 0; c <= 1; c++) {
        for (int d = 0; d <= 1; d++) {
          for (int e = 0; e <= 1; e++) {
            for (int f = 0; f <= 1; f++) {
              for (int g = 0; g <= 1; g++) {
                int mmp[6][4] = {0};
                if (a) {
                  for (int i = 1; i <= 3; i++) {
                    mmp[1][i] = 1;
                  }
                }
                if (b) {
                  for (int i = 1; i <= 3; i++) {
                    mmp[i][3] = 1;
                  }
                }
                if (c) {
                  for (int i = 3; i <= 5; i++) {
                    mmp[i][3] = 1;
                  }
                }
                if (d) {
                  for (int i = 1; i <= 3; i++) {
                    mmp[5][i] = 1;
                  }
                }
                if (e) {
                  for (int i = 3; i <= 5; i++) {
                    mmp[i][1] = 1;
                  }
                }
                if (f) {
                  for (int i = 1; i <= 3; i++) {
                    mmp[i][1] = 1;
                  }
                }
                if (g) {
                  for (int i = 1; i <= 3; i++) {
                    mmp[3][i] = 1;
                  }
                }
                printf("5 3\n");
                for (int i = 1; i <= 5; i++) {
                  for (int j = 1; j <= 3; j++) {
                    printf("%d", mmp[i][j]);
                  }
                  puts("");
                }
                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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

DFS求联通块代码

/*
 * @Date: 2020-10-17 21:20:03
 * @LastEditTime: 2020-10-17 21:27:00
 * @Author's blog: nuoyanli
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
char a[N][N];
int n, m, vis[N][N];

void dfs(int r, int c, int f) {
  if (r < 0 || r >= m || c < 0 || c >= n) {
    return;
  }
  if (vis[r][c] > 0 || a[r][c] != '1') {
    return;
  }
  vis[r][c] = f;
  for (int i = -1; i <= 1; i++){
    for (int j = -1; j <= 1; j++){
      if (i != 0 || j != 0){
        dfs(r + i, c + j, f);
      }
    }
  }
}

int main() {
  int sum = 0;
  freopen("in.txt", "r", stdin);
  while (~scanf("%d%d", &m, &n)) {
    for (int i = 0; i < m; i++){
      scanf("%s", a[i]);
    }
    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for (int i = 0; i < m; i++){
      for (int j = 0; j < n; j++){
        if (vis[i][j] == 0 && a[i][j] == '1'){
          dfs(i, j, ++cnt);
        }
      }
    }
    if (cnt == 1){
      sum += 1;
    }
  }
  printf("%d\n", sum);
  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
53

F:成绩统计

题面：

在这里插入图片描述

思路：

直接计算，然后注意四舍五入。

代码：

/*
 * @Date: 2020-10-17 22:18:36
 * @LastEditTime: 2020-10-17 22:21:48
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, jg = 0, yx = 0;
  scanf("%d", &n);
  while (n--) {
    int x;
    scanf("%d", &x);
    if (x >= 60) {
      jg++;
    }
    if (x >= 85) {
      yx++;
    }
  }
  double Jg = jg * 1.0 / n * 1.0;
  double Yx = yx * 1.0 / n * 1.0;
  int ans_jg = int(Jg * 1000 + 5) / 10;
  int ans_yx = int(Yx * 1000 + 5) / 10;
  printf("%d%%\n%d%%\n", ans_jg, ans_yx);
  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

G:回文日期

题面：

在这里插入图片描述

思路：

直接按照题意模拟，暴力判断。

代码：

/*
 * @Date: 2020-10-18 13:13:44
 * @LastEditTime: 2020-11-24 14:41:52
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
int temp[10], m[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool hw(int x) {
  int tot = 0;
  while (x) {
    temp[tot++] = x % 10;
    x /= 10;
  }
  for (int i = 0; i < tot; i++) {
    if (temp[i] != temp[tot - i - 1]) {
      return 0;
    }
  }
  return 1;
}
bool check(int x) {
  int year = x / 10000;
  int month = temp[3] * 10 + temp[2];
  int day = temp[1] * 10 + temp[0];
  if ((year % 100 != 0 && year % 4 == 0) || year % 400 == 0) {
    m[2] = 29;
  } else {
    m[2] = 28;
  }
  if (month > 12 || month <= 0) {
    return 0;
  } else {
    if (day > m[month]) {
      return 0;
    }
  }
  return 1;
}
int main() {
  int n;
  scanf("%d", &n);
  int ans1, ans2;
  bool f = 0;
  for (int i = n + 1; i <= 1e8; i++) {
    if (hw(i)) {      //判断回文
      if (check(i)) { //判断合法
        ans1 = i;
        if (temp[0] == temp[2] && temp[2] == temp[5] && temp[5] == temp[7] &&
            temp[1] == temp[3] && temp[3] == temp[4] && temp[4] == temp[6]) {
          ans2 = i;
          f = 1;
        }
        break;
      }
    }
  }
  if (!f) {
    for (int i = ans1 + 1; i <= 1e8; i++) {
      if (hw(i)) {
        if (check(i)) {
          if (temp[0] == temp[2] && temp[2] == temp[5] && temp[5] == temp[7] &&
              temp[1] == temp[3] && temp[3] == temp[4] && temp[4] == temp[6]) {
            ans2 = i;
            break;
          }
        }
      }
    }
  }
  printf("%d\n%d\n", ans1, ans2);
  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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

H:子串分值和

题面：

在这里插入图片描述

思路：

算单字母的贡献，然后记录一下上一个位置。

代码：

/*
 * @Date: 2020-10-18 13:13:49
 * @LastEditTime: 2020-10-18 15:26:45
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
char s[N];
ll vis[40];
int main() {
  scanf("%s", s + 1);
  int n = strlen(s + 1);
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += (i - vis[s[i] - 'a']) * (n - i + 1);
    vis[s[i] - 'a'] = i;
  }
  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

I：平面划分

在这里插入图片描述

思路：

这题比赛的时候没做（我考的Java b），赛后听到工作室的他们说感觉很难，最近补题发现，其实不是很难，就是没加入一条直线都要把情况考虑全，每加入一条边，和其余已经存在的边进行比较，如果平行则无需继续向下做，否则，求交点，判重点，可能存在多条边相交于同一个点，这就需要去重了，最后需要加 1，因为最后会形成一个闭合的区间，新生成的，之后累加，即每加入一条边所划分的区域都需加入答案中。
当然需要知道前置知识，直线分平面公式：直线分平面公式是指n条直线最多能把平面分成1+1+2+3+……+n个部分。

代码：

/*
 * @Date: 2020-10-18 13:13:54
 * @LastEditTime: 2020-11-24 15:00:14
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, inf = 1e9 + 10;
int n, ans, a[N], b[N];
#define Point pair<double, double>
#define x first
#define y second
const Point INF = Point{inf, inf};
bool check(Point e1, Point e2) {
  return (abs(e1.x - e2.x) <= 1e-2 && abs(e1.y - e2.y) <= 1e-2);
}

Point jd(int m, int n) { //求交点
  double x1 = a[m], x2 = a[n], y1 = b[m], y2 = b[n];
  //平行则无交点
  if (x1 == x2) {
    return INF;
  }
  Point cp = Point{};
  cp.x = (y2 - y1) / (x1 - x2);
  cp.y = (x1 * y2 - x2 * y1) / (x1 - x2);
  return cp;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a[i], &b[i]);
  }
  ans = 2; //初始一条直线可以划分为两个平面
  for (int i = 2; i <= n; ++i) {
    vector<Point> v;
    bool f = 0;
    for (int j = 1; j < i; ++j) {
      // i 为新加入的点，与之前的点做划分,判断直线 i, j是否存在交点
      Point now = jd(i, j);
      if (check(now, INF)) {//直线 i, j不存在交点 continue
        continue;
      }
      //直线i, j存在交点 去重
      int len = v.size();
      for (int k = 0; k < len; ++k) {
        if (check(now, v[k])) {
          f = 1;
        }
      }
      if (!f) {
        v.push_back(now);
      }
    }
    ans += v.size() + 1;
  }
  printf("%d\n", 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
53
54
55
56
57
58
59
60
61

J：字串排序

题面：

在这里插入图片描述

思路：

代码：

~~串场了下面两个题目是第一场的最后两题2333333~~

I：整数拼接(第一场)

题面：

在这里插入图片描述

思路：

首先暴力跑一下， $O(n^2)$ 骗 $30$ 分：
代码如下：

/*
 * @Date: 2020-10-18 13:13:54
 * @LastEditTime: 2020-11-18 18:10:48
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k;
vector<ll> num;
bool check(ll a, ll b) {
  if (a % k == 0 && b % k == 0) {//本身算的话也要加 但是只能加一次
    return 1;
  }
  ll temp = b;
  while (temp) {
    temp /= 10;
    a *= 10;
  }
  return (a + b) % k == 0;
}
int main() {
  scanf("%lld%lld", &n, &k);
  while (n--) {
    ll x;
    scanf("%lld", &x);
    num.push_back(x);
  }
  n = num.size();
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j && check(num[i], num[j])) {
        ans++;
      }
    }
  }
  printf("%lld\n", 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

那么怎么优化呢？
我们能不能优化掉一个循环呢？
显然最外层肯定是去不掉的，因为至少要枚举到每个数，那么考虑如何优化掉内层循环，也就是考虑如何快速求出与 $a [i]$ 拼接起来为 $k$ 的倍数的数字的个数。
不难发现， $a [i]$ 和 $a [j]$ 拼起来等价于： $a[i]*10^{a[j]的长度}+a[j]$ ，学过数学的都知道， $a[j]的长度=⌊log_{10}a[j]⌋+1$ ，那么与 $a [i]$ 拼接起来为 $k$ 的倍数的数字也就是： $a[i]*10^{⌊log_{10}a[j]⌋+1}+a[j]$ 是 k 的倍数，展开就是： $a[i]*10^{⌊log_{10}a[j]⌋+1}\%k+a[j]\%k$ 是 k 的倍数。由于 $k\leq1e5$ 那么这些余数是可以用数组存下的，我们用 $s u m [i] [j]$ 表示：乘 $10^i$ 后模 $k$ 的结果为 $j$ 的数的个数。
然后对于所有的 $a [i]$ ， $ans+=sum[⌊log_{10}a[i]⌋+1][(k-a[i]\%k)\%k]$ 即可。
要注意的是这样求出来的是所有 $i < j$ 也就是 $a [i]$ 放在 $a [j]$ 前面的情况，对于 $a [i]$ 放在 $a [j]$ 后面的情况，我们只需要把数组 $a$ 反转，然后再求一遍答案累加就好了！

代码：

/*
 * @Date: 2020-10-18 13:13:54
 * @LastEditTime: 2020-11-18 18:50:43
 * @Author's blog: blog.nuoyanli.com
 * @Description: Plum blossom from the bchter cold!
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, k, ans, sum[11][N];
vector<ll> a;
ll log_10(ll x) {
  ll len = 0;
  while (x) {
    x /= 10;
    len++;
  }
  return len;
}
void solve() {
  for (ll i = 0; i < n; i++) {
    ans += sum[log_10(a[i])][(k - a[i] % k) % k];
    for (ll j = 0, temp = 1; j < 11; j++) {
      sum[j][temp * a[i] % k]++;
      temp = temp * 10 % k;
    }
  }
}

int main() {
  scanf("%lld%lld", &n, &k);
  for (ll i = 0; i < n; i++) {
    ll x;
    scanf("%lld", &x);
    a.push_back(x);
  }
  solve();
  memset(sum, 0, sizeof(sum));
  reverse(a.begin(), a.end());
  solve();
  printf("%lld\n", 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

J:网络分析(第一场)

题面：

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/430166

2020 第十一届蓝桥杯大赛软件类省赛第二场 C/C++ 大学 B 组 完整题面和题解_第十届蓝桥杯大赛软件类省赛b类第二场题解(c/c++)

文章目录

A:门牌制作

题面：

思路：

代码：

答案：

B:既约分数

思路：

代码：

答案:

C:蛇形填数

题面：

思路：

代码：

答案：

D:跑步锻炼

题面：

思路：

代码：

答案：

E:七段码

题面：

思路：

代码：

建图代码:

DFS求联通块代码

F:成绩统计

题面：

思路：

代码：

G:回文日期

题面：

思路：

代码：

H:子串分值和

题面：

思路：

代码：

I：平面划分

思路：

代码：

J：字串排序

题面：

思路：

代码：

I：整数拼接(第一场)

题面：

思路：

代码：

J:网络分析(第一场)

题面：

2020 第十一届蓝桥杯大赛软件类省赛第二场 C/C++ 大学 B 组完整题面和题解_第十届蓝桥杯大赛软件类省赛b类第二场题解(c/c++)