版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: 题解 - 第十二届蓝桥杯大赛软件赛省赛 - C/C++大学A组 author: "Tifa & AgOH(code H & I)" coauthor:
打之前: 蓝桥杯有手就行
打完后: wc 我手呢
暴力杯 (x)
DP 杯(√)
简单题目的程序已省略
| 题号 | 标题1 | 做法 |
|---|---|---|
| A | 卡片 | 模拟 |
| B | 直线 | 暴力 / 数学 |
| C | 货物摆放 | 枚举因子 |
| D | 路径 | 最短路 |
| E | 回路计数 | 状压 + 记忆化搜索 |
| F | 砝码称重 | 01 背包 |
| G | 异或数列 | 博弈论 + DP |
| H | 左孩子右兄弟 | 树形 DP |
| I | 括号序列 | DP + 前缀和 |
| J | 分果果 | 二分答案 + DP |
{% pdf /archives/lq2021-p1/problems.pdf 600px %}
{% icodeweb blog lq2021-p1/A.php %}
扔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 blog lq2021-p1/B.php %}
懒得算的话直接暴力枚举质因子乘积即可
不过这个直接算也好算, 由整数的唯一分解定理并注意到只有 $3$ 是重复出现的质因子且只有 $3$ 个, 所以答案即为 $3^5(1+3+6)=2430$
其中 $1$ 表示 $3$ 个 $3$ 均分在三个乘积里, $3$ 代表 $3$ 个 $3$ 放在同一个乘积里, $6$ 则是其他情况
{% icodeweb blog lq2021-p1/C.php %}
{% icodeweb blog lq2021-p1/D.php %}
设图为 $G=\lang V,E\rang$
设 $f(i,J)$ 表示当前到达点 $i$ 处且已经到达 $J\subseteq V$ 中所有点时的方案数, 则
转移方程:
$$ 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 blog lq2021-p1/E.php %}
看成是重量为 $w_i$ 和 $-w_i$ 的 $2n$ 个物品做 01 背包即可
考虑从高到低考虑每个二进制位, 如果某个二进制位上已经可以决出胜负, 则结束; 如果每一位都是平局则平局
所以问题中 $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} $$
简单的树上 DP, 关键是读题
不妨假设只需插入右括号, 否则
考虑一个简化模型
{% 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 %}
此模型显然与该题等价
二分差值, 枚举最小值, 之后 DP 即可
带超链接的是找到了原题或原型↩