2021-04-17 22:00 临沂大学 C#工程师

关注

牛客小白月赛33题解

A - 字符统计

按照题意模拟计数即可，只考察一些字符串的操作

B - 连分数

这个分数的拆分是有套路的，按照题目的样子，一路递归下去就可以

C - 挪酒瓶

置换的状况可以表示成： $i \rightarrow a_i \rightarrow a_{a_i} \rightarrow ...$ ，每个物品都会换到一个指定的位置。

有恰好 $1$ 个东西换到他现在的位置，置换的关系会形成一个圈。也就是说，假设 $a$ 要换到位置 $b$ ，位置 $b$ 要换到 $c$ ， $...$ ，最后换回 $a$ 。这个东西在数学上称为置换群。

对于一个有 $n$ 个元素的置换群 $p$ ，从最后一个 $a$ 往前开始换，则费用为 $(w_a + w_b) + (w_a+w_c)+...=(n-2)w_a+\sum_{i \varepsilon p} w_i$

虽然每个元素都至少会被换一次，所以后面的 $\sum w_i$ 是固定的。

最优的策略则是选择较小的 $w_a$ 开始换。

如果改变交换的顺序则会产生更复杂的式子，但最优的情况下只会交换 $n-1$ 次，所以可以放在一起比较。

而上述的式子可以轻易证明是最优的。

可是让我们看下面这个例子

5
1 3 4 5 2
1 99 99 99 99

答案为 $500$ 。可是如果只用上述的策略则会算出 $594$ 。这个例子的置换群为 $(1)(2 \quad 3 \quad 4 \quad 5)$ 。可以发现，如果只考虑该置换群内最小的 $w$ ，并不会最好。

新想法：把目前最轻的酒瓶拿进来替换，最后再换回去。令置换群 $p$ 内最轻重量为 $m_p = min_{i \varepsilon p} w_i$ ，令全部的酒里面最轻重量为 $m_{all}$ 。这个策略的花费为 $2(m_{all}+m_p)+(n-2)m_{all}+\sum_{i \varepsilon p} w_i$

最后对于每一个置换群，考虑两个 $Case$ 如下，都选择最优即可：

$\quad \quad (n-2)m_p+\sum_{i \varepsilon p} w_i$
$\quad \quad 2(m_{all} + m_p) + (n-2)m_{all} + \sum_{i \varepsilon p} w_i$

D - 购物

字符串处理。

$a_i$ 表示原本第 ${i}$ 种商品有几份。
$c_i$ 表示第 ${i}$ 种商品有多少人拥有，那么可以知道第 ${i}$ 种商品有 ${N-c_i}$ 人买。
答案就是有几个 ${i}$ 满足 $a_i-(N-c_i)>0$

E - 喝可乐

因为 ${A,B > 1}$ ，兑换空瓶数量会逐渐减少 $!$
枚举所有可能购买的方法即可 $!$
注意剩余的两种空瓶的数量 $!$

常见错误：

如果 $A < B$ ，买 $A$ 的整数倍不就好了 $?$
试考虑 $N=7,A=2,B=3$ 的状况

F - 天旋地转

旋转坐标轴 $\Rightarrow$ 人物反方向旋转。
繁琐的四方向移动模拟。
$No \quad - \quad Time \quad Limit \quad Exceede$
$k$ 很大
如果是移动，往朝该方向走 ${k}$ 步，等同于坐标加减 ${k}$
如果是旋转，转 ${4}$ 次，绕一圈等于没绕，所以转 ${k}$ ${mod}$ ${4}$ 次即可
$No \quad - \quad Wrong \quad Answer$
反方向转 $k$
视为往正方向转 $-k,(ex.-1)$
也就是往正方向转 $4+k \quad mod \quad 4,(ex.3)$
$No \quad - \quad Wrong \quad Answer$
$k$ 很大
坐标范围是 $N \times k$
$Overflow \quad!!$ ， $long \quad long$ 嘿嘿
$Accept$

G - 挑数字

考虑部分和
一组答案可以对应到一组相同的部分和
答案就是找众数 $!$

H - 货物运输

直觉：找很多条路径+小小张的图 $N \le 100$ ？
哈哈 $!$ 网络流吧 $!$ 复杂度好像很对 $!$
实际：样例过不了 $OAO.$
$\forall C^{''} \le C$ ，跟花费流正确的条件反过来 $QQ$
观察：你不会想要分多条路走 $OAO！$
任两条路 ${A,B}$ ，把 ${A}$ 换成 ${B}$ 或者把 ${B}$ 换成 ${A}$ ，至少有一个 ${cost}$ 不会上升。
直观证明1:同一条路只会越用越便宜， $cost(A) \ge cost($ 多加一条 $A）$
直观证明2:若 $A$ 换成 $B$ $cost$ 上升， $cost(B) \ge cost($ 加 $B)>cost(A)\ge cost($ 加 $A)$ ， $B$ 换成 $A$ 会降 $cost$ 。
所以一条边要么就不用，要么就用 $F$ 次，每条边的 $cost$ 设为走 $F$ 次时的花费。
耶 $!$ 变成一般的最短路 $!$