仓库源文，站点原文

title: 题解 - 第十二届蓝桥杯大赛软件赛省赛 - C/C++大学A组 author: "Tifa & AgOH(code H & I)" coauthor:

AgOH categories:
算法竞赛
题解 tags:
算法竞赛
题解
蓝桥杯
模拟
暴力
搜索
图论
最短路
Iverson括号
DP
背包DP
01背包DP
状态压缩
记忆化搜索
树形DP
博弈论
数论
前缀和
最大公约数
最小公倍数
素数/质数 date: 2021-04-19 19:21:54

打之前: 蓝桥杯有手就行

打完后: wc 我手呢
暴力杯 (x)

DP 杯(√)

简单题目的程序已省略

题目概览

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

{% pdf /archives/lq2021-p1/problems.pdf 600px %}

A - 卡片

答案参考

{% icodeweb cpa_nohead title:Answer lang:php misc/lanqiao2021-p1-ca/A/0.php %}

B - 直线

解题思路

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

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

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

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

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

答案参考

{% icodeweb cpa_nohead title:Answer lang:php misc/lanqiao2021-p1-ca/B/1.php %}

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:B misc/lanqiao2021-p1-ca/B/0.cpp %} </details>

C - 货物摆放

解题思路

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

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

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

答案参考

{% icodeweb cpa_nohead title:Answer lang:php misc/lanqiao2021-p1-ca/C/1.php %}

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:C misc/lanqiao2021-p1-ca/C/0.cpp %} </details>

D - 路径

答案参考

{% icodeweb cpa_nohead title:Answer lang:php misc/lanqiao2021-p1-ca/D/0.php %}

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) $$

答案参考

{% icodeweb cpa_nohead title:Answer lang:php misc/lanqiao2021-p1-ca/E/1.php %}

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:E misc/lanqiao2021-p1-ca/E/0.cpp %} </details>

F - 砝码称重

解题思路

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

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:F misc/lanqiao2021-p1-ca/F/0.cpp %} </details>

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} $$

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:G misc/lanqiao2021-p1-ca/G/0.cpp %} </details>

H - 左孩子右兄弟

解题思路

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

代码参考

<details open> <summary>Show code</summary> {% icodeweb blog lang:cpp lq2021-p1/H.cpp %} </details>

I - 括号序列

解题思路

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

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

考虑一个简化模型

{% note primary no-icon %}

求数列 ${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)$

{% endnote %}

此模型显然与该题等价

代码参考

<details open> <summary>Show code</summary> {% icodeweb blog lang:cpp lq2021-p1/I.cpp %} </details>

J - 分果果

解题思路

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

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