蓝桥杯 2025 备赛（省赛C++ A 组）

蓝桥杯备赛
Start: 2025.03.10
End: Doing
Plan: PM 22:30-24:00
There are totally 10 questions in each provincial competition.

Mon Tue Wed Thur Fri Sat Sun
1/2 3/4 5/6 7 8 9 10

Check:

COMP 1 2 3 4 5 6 7 8 9 10
2023 03.10 03.10 03.11 03.11 03.12
2022
2021
2020

蓝桥杯 2025 备赛（省赛C++ A 组）

2023年

1. 平方差

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<vector>

using namespace std;

// 比较
bool cmp(vector<int> &A, vector<int> &B) {
    if(A.size() != B.size()) return A.size() > B.size();

    for(int i = A.size() - 1; i >= 0; i--) {
      if(A[i] != B[i]) return A[i] > B[i];
    }

    return true;
}


// 减法 A - B
vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;

    // 减操作
    for(int i = 0, t = 0; i < A.size(); i++) {
      t = A[i] - t;
      if(i < B.size())  t -= B[i];

      C.push_back((t + 10) % 10);

      if(t < 0)  t = 1;
      else  t = 0;
    }

    // 去除前导 0
    while(C.size() > 1 && C.back() == 0)  C.pop_back();
    return C;
}

// 乘法
vector<int> mul(vector<int> &A, vector<int> &B) {
    vector<int> C(A.size() + B.size(), 0); // 直接最大化长度，全0

    // 第 i+j 位的所有可能来源数字
    for(int i = 0; i < A.size(); i++) 
      for(int j = 0; j < B.size(); j++) 
        C[i + j] += A[i] * B[j];

    // 正确处理所有位置应该的数字大小（只保留一位，多余的进位）
    for(int i = 0, t = 0; i < C.size(); i++) {
      t += C[i];
      C[i] = t % 10;
      t /= 10;
    }

    // 去除前导 0
    while(C.size() > 1 && C.back() == 0)  C.pop_back();

    return C;
}

int main(void) {
    // 预处理
    vector<int> A, B, C;
    string aa, bb, a, b;
    cin >> aa >> bb; 
    if(aa[0] == '-')  for(int i = 1; i < aa.size(); i++)  a += aa[i];
    else a = aa;
    if(bb[0] == '-')  for(int i = 1; i < bb.size(); i++)  b += bb[i];
    else b = bb;
    // 倒着存储
    for(int i = a.size() - 1; i >= 0; i--)  A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--)  B.push_back(b[i] - '0');

    // 计算各自平方
    A = mul(A, A);
    B = mul(B, B);

    // 再减法（注意负数）
    if(cmp(A, B))
      C = sub(A, B);
    else {
      cout << '-';
      C = sub(B, A);
    }
    for(int i = C.size() - 1; i >= 0; i--)  cout << C[i];
    cout << endl;
    
    return 0;
}

时间复杂度：O(mn)O(mn).
空间复杂度：O(m+n)O(m+n).

2. 幸运数

填空题

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
#include <iostream>
using namespace std;

int main()
{
  // 请在此输入您的代码
  /*
  int ans = 0;
  for(int i=5e7; i<1e8; i++){
    string s = to_string(i);
    int n = s.size();
    if(n%2 != 0)  continue;

    int a = 0, b = 0;
    for(int i=0; i<n; i+=2){
      a += s[i] - '0';
      b += s[i+1] - '0';
    }
    if(a == b)  ans++;
  }

  cout << ans << endl;
  */
  // 先运行看 0-1e5 : 624
  // 1e5 - 1e7: 50412
  // 1e7 - 5e7: 1971040
  // 5e7 - 1e8: 2408015
  cout << 624 + 50412 + 1971040 + 2408015 << endl;
  // 答案：4430091 正确

  return 0;
}

时间复杂度：O(1e8)O(1e8).
空间复杂度：O(1)O(1).

3. 有奖问答

填空题
但是这里还是需要使用动态规划来做！

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
#include <iostream>
#include <vector>
using namespace std;
int main()
{
  
  // dp[i][j] 表示答了前i题，得分是j*10  (0<j<10) 的情况有多少种
  vector<vector<int>> dp(31, vector<int>(11, 0));

  // 初始化
  dp[0][0] = 1;
  
  // 递推
  for(int i=1; i<=30; i++){
    // 当前得分为零：前一题任何情况，当前题答错(注意，100 分自动结束，不能加 100 分)
    for(int j=0; j<=9; j++)  dp[i][0] += dp[i-1][j];
    // 当前得分为 10：前一题时是 0 分，当前题答对
    // 当前得分为 20：前一题时是 10 分，当前题答对
    // ...      100
    for(int j=1; j<=10; j++)  dp[i][j] = dp[i-1][j-1];
  }
  
  // 答案：所有得分为 70 的情况，加起来
  int ans = 0;
  for(int i=0; i<=30; i++)  ans += dp[i][7];
  cout << ans << endl;
  
  // cout << 8335366 << endl;

  return 0; 
}

时间复杂度：O(31∗11)O(31*11).
空间复杂度：O(31∗11)O(31*11).

4. 更小的数

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
#include <iostream>
#include <string>
using namespace std;
int main()
{
  string num;
  cin >> num;
  // 直接暴力
  int ans = 0;
  int n = num.size();
  for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
      // 反转 [i...j] 部分，判断反转后是否更小
      int t = 0;
      while(i+t < j-t){
        if(num[i+t] > num[j-t]){
          ans++;
          break;
        }
        else if(num[i+t] < num[j-t])
          break;
        t++;
      }
    }
  }

  cout << ans << endl;

  return 0;
}

时间复杂度：O(n3)O(n^3).
空间复杂度：O(1)O(1).

5. 颜色平衡树

AC 70%，超时 30%
我自己的做法。

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
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 判断一个哈希表是否所有值相同
bool check(const unordered_map<int, int>& map){
  if(map.empty())  return true;
  int num = map.begin()->second;
  for(auto& [k, v]: map)  if(num != v)  return false;
  return true;
}

int main()
{
  // 输入
  int n;  cin >> n;
  vector<int> C(n+1, 0);
  vector<int> F(n+1, 0);
  for(int i=1; i<=n; i++){
    cin >> C[i] >> F[i];
  }
  int ans = 0;

  // 处理
  // 每个节点记录时，一直向上记录到根
  unordered_map<int, int> Table[n+1];
  for(int i=1; i<=n; i++){
    // 处理节点 i 的颜色
    int color = C[i];
    // 同时给父节点所在的树算上颜色
    int t = i;
    while(t != 0){
      Table[t][color]++;
      t = F[t];
    }
  }

  // 检测每一个子树
  for(int i=1; i<=n; i++)  ans += check(Table[i]);

  // 输出
  cout << ans << endl;
  return 0;
}

时间复杂度：O(n2)O(n^2).
空间复杂度：O(n2)O(n^2).

AC 70%, 超时 30%
尝试优化check，但是仍然一样的结果。

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
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;


// 判断一个哈希表是否所有值相同
bool check(const unordered_map<int, int>& map){
  if(map.empty())  return true;
  int num = map.begin()->second;
  for(auto& [k, v]: map)  if(num != v)  return false;
  return true;
}

// 新的检测函数：颜色最多的颜色数量 x 颜色数量 == 树的所有节点数
bool newCheck(int maxColCnt, int kinds, int nodeNum){
  // cout << maxCol << " " << kinds << " " << nodeNum << endl;
  return maxColCnt * kinds == nodeNum;
}


int main()
{
  // 输入
  int n;  cin >> n;
  vector<int> C(n+1, 0);
  vector<int> F(n+1, 0);
  for(int i=1; i<=n; i++)  cin >> C[i] >> F[i];
  

  // 每个节点记录时，一直向上记录到根
  int ans = 0;
  vector<int> cnt(n+1, 0);            // cnt[i] 表示节点i为根的树上有多少节点
  unordered_map<int, int> Table[n+1]; // Table[i][j] 表示节点i为根的树上的颜色j的数量
  vector<int> maxColor(n+1, 0);       // maxColor[i] 表示节点i为根的树上的最多的那种颜色

  for(int i=1; i<=n; i++){
    // 向上给父节点所在的树算上颜色
    int color = C[i];
    int t = i;
    while(t != 0){
      cnt[t]++;
      Table[t][color]++;

      if(maxColor[t] == 0)  maxColor[t] = color;
      else if(Table[t][color] > Table[t][maxColor[t]])  maxColor[t] = color;

      t = F[t];
    }
  }

  // 检测每一个子树
  for(int i=1; i<=n; i++){
    ans += newCheck(Table[i][maxColor[i]], Table[i].size(), cnt[i]);
  }

  // 输出
  cout << ans << endl;
  return 0;
}

时间复杂度：O(n2)O(n^2).
空间复杂度：O(n2)O(n^2).

官方解答：dfs序 + 莫队

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
75
76
#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 10;
int n, m, num, t, sum, c[N], siz[N], in[N], out[N], id[N], pos[N], cnt[N], tot[N], ans;
vector<int> g[N];
struct node {
    int l, r;
} q[N];
bool cmp(node a, node b) {
    if (pos[a.l] == pos[b.l]) {
        if (pos[a.l] & 1) {
            return a.r < b.r;
        } else {
            return a.r > b.r;
        }
    }
    return a.l < b.l;
}
void dfs(int x) {
    siz[x] = 1;
    in[x] = ++num;
    id[num] = x;
    for (int y : g[x]) {
        dfs(y);
        siz[x] += siz[y];
    }
    out[x] = num;
    q[++t] = {in[x], out[x]};
}
void add(int x) {
    if (cnt[c[x]]) {
        if (--tot[cnt[c[x]]] == 0) {
            sum--;
        }
    }
    cnt[c[x]]++;
    if (++tot[cnt[c[x]]] == 1) {
        sum++;
    }
}
void del(int x) {
    if (--tot[cnt[c[x]]] == 0) {
        sum--;
    }
    cnt[c[x]]--;
    if (cnt[c[x]]) {
        if (++tot[cnt[c[x]]] == 1) {
            sum++;
        }
    }
}

int main() {
    cin >> n;
    m = sqrt(n);
    for (int i = 1; i <= n; i++) {
        pos[i] = (i - 1) / m + 1;
        int fa;
        cin >> c[i] >> fa;
        g[fa].push_back(i);
    }
    dfs(1);
    sort(q + 1, q + 1 + n, cmp);
    for (int l = 1, r = 0, i = 1; i <= n; i++) {
        while (l > q[i].l) add(id[--l]);
        while (r < q[i].r) add(id[++r]);
        while (l < q[i].l) del(id[l++]);
        while (r > q[i].r) del(id[r--]);
        if (sum == 1) {
            ans++;
        }
    }
    cout << ans;
    return 0;
}

时间复杂度：O(nn)O(n\sqrt{n}).
空间复杂度：O(n)O(n).

6. 

1

时间复杂度：O()O().
空间复杂度：O()O().

1

时间复杂度：O()O().
空间复杂度：O()O().

7. 

1

时间复杂度：O()O().
空间复杂度：O()O().

1

时间复杂度：O()O().
空间复杂度：O()O().

评论
avatar
isSeymour
志之所趋，无远弗届，穷山距海，不能限也。
文章
67
标签
34
分类
8
Follow Me
最新文章
CS224W - Colab 2
CS224W - Colab 2
GCN 图卷积神经网络
GCN 图卷积神经网络
PageRank:《哈利·波特》人物节点重要度
PageRank:《哈利·波特》人物节点重要度
分类
标签
前后端分离C/C++汇编语言Assembly计算机视觉GNN计网实验原神颜色素材密码学数据库系统原理数字逻辑实验数据结构后端GCNNode2VecMLPageRankDeepWalk身份认证LaTeXLinuxDL现代密码学监督学习理论MarkdwonPHPPythonPyTorch正则表达式SQLCTFWEB技术sqlmapPandas
归档
网站资讯
文章数目 :
67
已运行时间 :
本站总字数 :
352.3k
本站访客数 :
本站总访问量 :
最后更新时间 :