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

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

    打完后: 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

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

J - 分果果

解题思路

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


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