题解 - 第十二届蓝桥杯大赛软件赛省赛 - C/C++ 大学 A 组

发表于 更新于 分类于 ， 合著者：AgOH 本文字数： 1.1k 阅读时长 ≈ 4 分钟

  • 打之前：蓝桥杯有手就行

    打完后: wc 我手呢

  • 暴力杯 (x)

    DP 杯 (√)

简单题目的程序已省略

题目概览

题号 标题 1 做法
A 卡片 模拟
B 直线 暴力 / 数学
C 货物摆放 枚举因子
D 路径 最短路
E 回路计数 状压 + 记忆化搜索
F 砝码称重 01 背包
G 异或数列 博弈论 + DP
H 左孩子右兄弟 树形 DP
I 括号序列 DP + 前缀和
J 分果果 二分答案 + DP

A - 卡片

答案参考

Answerview raw
1
3181

B - 直线

解题思路

扔 set 去重即可，注意精度误差，建议计算一般式而不是斜截式

或者用数学方法，下面的代码即为数学方法

设点阵为 \(m\) 行 \(n\) 列 (\(m,n>1\)), 显然答案为

\[ m+n+2\sum_{i=1}^{m-1}\sum_{j=1}^{n-1}[(i,j)=1]((m-i)(n-j)-[2i\leqslant m][2j\leqslant n](m-2i)(n-2j)) \]

因为是提答题，这式子就不化简了

答案参考

Answerview raw
1
40257

代码参考

Show code

Bview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <iostream>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int X = 20, Y = 21;
int main() {
  int ans = X + Y;
  for (int x = 1; x < X; ++x)
    for (int y = 1; y < Y; ++y)
      if (gcd(x, y) == 1)
        ans += 2 * ((X - x) * (Y - y) -
                    (X >= 2 * x && Y >= 2 * y) * (X - 2 * x) * (Y - 2 * y));
  cout << ans;
  return 0;
}

C - 货物摆放

解题思路

懒得算的话直接暴力枚举质因子乘积即可

不过这个直接算也好算，由整数的唯一分解定理并注意到只有 \(3\) 是重复出现的质因子且只有 \(3\) 个，所以答案即为 \(3^5(1+3+6)=2430\)

其中 \(1\) 表示 \(3\) 个 \(3\) 均分在三个乘积里，\(3\) 代表 \(3\) 个 \(3\) 放在同一个乘积里，\(6\) 则是其他情况

答案参考

Answerview raw
1
2430

代码参考

Show code

Cview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <iostream>
#include <set>
#include <tuple>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r) for (auto i = l; i <= r; ++i)
const int pfs[] = {2, 3, 3, 3, 17, 131, 2857, 5882353},
          len = sizeof(pfs) / sizeof(pfs[0]);
i64 factors[1 << len];
int main() {
  _for(i, 0, (1 << len) - 1) {
    factors[i] = 1;
    _for(j, 0, len - 1)
      if (i & (1 << j)) factors[i] *= pfs[j];
  }
  set<tuple<i64, i64, i64>> s;
  _for(a, 0, (1 << len) - 1)
    _for(b, 0, (1 << len) - 1)
      _for(c, 0, (1 << len) - 1)
        if (((a | b | c) == (1 << len) - 1) && !((a & b) || (b & c) || (c & a)))
          s.insert(make_tuple(factors[a], factors[b], factors[c]));
  cout << s.size();
  return 0;
}

D - 路径

答案参考

Answerview raw
1
10266837

E - 回路计数

解题思路

设图为 \(G=\lang V,E\rang\)

设 \(f(i,J)\) 表示当前到达点 \(i\) 处且已经到达 \(J\subseteq V\) 中所有点时的方案数，则

  • 初始状态: \(f(1,\{1\})=1\)

  • 转移方程:

    \[ f(i,J)=\sum_{k\in V;~(i,k)\in E;~k\notin J\setminus\{i\}}f(k,J\setminus\{i\}) \]

  • 答案:

    \[ \sum_{i\in V\setminus\{1\}}f(i,V) \]

答案参考

Answerview raw
1
881012367360

代码参考

Show code

Eview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r) for (int i = (l); i < (r); ++i)
const int K = 21;
bool g[K][K];
i64 f[K][1 << K];
int main() {
  _for(i, 0, K)
    _for(j, i + 1, K) g[i][j] = g[j][i] = (__gcd(i + 1, j + 1) == 1);
  f[0][1] = 1;
  _for(i, 0, 1 << K)
    _for(j, 0, K)
      if ((i >> j) & 1)
        _for(k, 0, K)
          if (g[j][k] && ((i >> k) & 1)) f[j][i] += f[k][i ^ (1 << j)];
  i64 ans = 0;
  _for(i, 1, K) ans += f[i][(1 << K) - 1];
  cout << ans;
}

F - 砝码称重

解题思路

看成是重量为 \(w_i\) 和 \(-w_i\) 的 \(2n\) 个物品做 01 背包即可

代码参考

Show code

Fview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstring>
#include <iostream>
using namespace std;
#define _for(i, l, r) for (int i = l; i <= r; ++i)
#define _rfor(i, r, l) for (int i = r; i >= l; --i)
const int N = 105, W = 1e5 + 5;
int w[N];
bool f[W];
int main() {
  f[0] = 1;
  int n;
  cin >> n;
  int sum = 0;
  _for(i, 1, n) {
    cin >> w[i];
    sum += w[i];
  }
  int ans = 0;
  _for(i, 1, n)
    _rfor(j, sum, w[i]) f[j] |= f[j - w[i]];
  _for(i, 1, n)
    _for(j, 1, sum - w[i]) f[j] |= f[j + w[i]];
  _for(i, 1, sum) ans += f[i];
  cout << ans;
  return 0;
}

G - 异或数列

解题思路

考虑从高到低考虑每个二进制位，如果某个二进制位上已经可以决出胜负，则结束；如果每一位都是平局则平局

所以问题中 \(X_i\) 的取值可简化为 \(\{0,1\}\)

接下来我们考虑 DP

令 \(f(i,j,a,b)\) 表示还剩 \(i\) 个 \(0\), \(j\) 个 \(1\), Alice 为 \(a\), Bob 为 \(b\) 时的结果，则

\[ f(i,j,a,b)=-\min\{f(i-1,j,a,b),f(i,j-1,a\oplus1,b),f(i,j-1,a,b\oplus1)\} \]

不难证明

\[ f(i,j,0,0)=\begin{cases} 1,&(i,j)\in\{(x,y):x\in\mathbb{N},y\in2[2\mid x]\mathbb{N}+1\}\\ 0,&2\mid j\\ -1,&\text{otherwise}\\ \end{cases} \]

代码参考

Show code

Gview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
#define _for(i, l, r) for (auto i = (l); i <= (r); ++i)
#define _rfor(i, r, l) for (auto i = (r); i >= (l); --i)
const int N = 2e5 + 5;
int x[N];
int main() {
  int kase;
  scanf("%d", &kase);
  while (kase--) {
    int n;
    scanf("%d", &n);
    _for(i, 1, n) scanf("%d", x + i);
    int state = 0;
    _rfor(i, 20, 0) {
      int now = 1 << i;
      int cnt = 0;
      _for(i, 1, n) cnt += !!(x[i] & now);
      if (!(cnt & 1)) continue;
      state = ((n - cnt) & 1) && (cnt != 1) ? -1 : 1;
      break;
    }
    printf("%d\n", state);
  }
}

H - 左孩子右兄弟

解题思路

简单的树上 DP, 关键是读题

代码参考

Show code

H.cppview raw
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
// From AgOH
//! AgOH TQL
//! stO AgOH Orz
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct E {
  int to, next;
} e[N];
int cnt_edge, head[N];
void addEdge(int u, int v) {
  e[++cnt_edge] = {v, head[u]};
  head[u] = cnt_edge;
}
int f[N];
void dfs(int u) {
  int sum = 0, max_f = 0;
  for (int i = head[u], v; i; i = e[i].next) {
    v = e[i].to;
    ++sum;
    dfs(v);
    max_f = max(max_f, f[v]);
  }
  f[u] = max_f + sum;
}
int main() {
  int n;
  cin >> n;
  for (int i = 2, fa; i <= n; ++i) {
    cin >> fa;
    addEdge(fa, i);
  }
  dfs(1);
  cout << f[1] << endl;
  return 0;
}

I - 括号序列

解题思路

不妨假设只需插入右括号，否则

  • 若只需插入左括号，则反转序列并将左右括号互换即可
  • 若需插入两种括号，则可分解成只插入左括号和只插入右括号两种情况，并将对应的两答案相乘即可

考虑一个简化模型

求数列 \(\{a_i\}_n\) 的个数，要求 \(\forall s\in[1,n]_\mathbb{N},\sum_{i=1}^sa_i\leqslant i\)

解：显然可以 \(O(n^2)\) DP

令 \(f(i,j)\) 表示 \(\sum_{k=1}^ia_k=j\) 的方案数

状态转移方程 \(f(i+1,j)=\sum_{k=0}^jf(i,j-k)\)

此模型显然与该题等价

代码参考

Show code

I.cppview raw
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
// From AgOH
//! AgOH TQL
//! stO AgOH Orz
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r) for (decltype(l + r) i = (l); i <= (r); ++i)
#define _set_nul(a) memset(a, 0, sizeof(a))

const int N = 5e3 + 5, MOD = 1e9 + 7;
int lb[N];
int dp[N][N], pre[N][N];
int calc(string &s) {
  int l = 0, r = 0, cnt = 0, len_lb = 0, x = 0;
  for (char c : s) {
    if (c == 40) {
      ++l;
      ++cnt;
    } else {
      lb[++len_lb] = max(++r - l, 0);
      --cnt;
    }
    if (cnt < 0) {
      ++x;
      ++cnt;
    }
  }
  _set_nul(dp);
  _set_nul(pre);
  _for(i, lb[1], x) pre[dp[1][i] = 1][i] = i - lb[1] + 1;
  _for(i, 2, len_lb)
    _for(j, lb[i], x) {
      dp[i][j] = pre[i - 1][j];
      pre[i][j] = j ? pre[i][j - 1] + dp[i][j] % MOD : dp[i][j];
    }
  return dp[len_lb][x];
}
int main() {
  string s;
  cin >> s;
  i64 ans = calc(s);
  transform(
    s.begin(), s.end(), s.begin(), [](char c) -> char { return c ^ 1; });
  reverse(s.begin(), s.end());
  cout << ans * calc(s) % MOD << endl;
  return 0;
}

J - 分果果

解题思路

二分差值，枚举最小值，之后 DP 即可

  1. 带超链接的是找到了原题或原型↩︎