这是一份口胡笔记,gza 这个菜菜人打算明年尝试一下蓝桥杯,先从 AK 2022 年的国 B 开始吧!
P8799 [蓝桥杯 2022 国 B] 齿轮
略加思索。
考虑到连比的过程对于中间的齿轮是没有要求的,所以本质是寻找是否有一对数比值为 $q$。
搞个 map,寻找每个数是否有其 $q$ 倍存在。
P8802 [蓝桥杯 2022 国 B] 出差
最短路板子题。
考虑将 $w_i \to w_i+C_{v_i}$。
记得 $n$ 号点不需要隔离。
P8804 [蓝桥杯 2022 国 B] 故障
假定这个故障是在那一个错误中产生的,那么剩下的就都没有产生,可以计算i故障发生并且导致出现当前现象的概率,进而算出发生当前现象的总概率,排序做一下就好了。
P8805 [蓝桥杯 2022 国 B] 机房
点权转边权,那么就是树上距离了,求 lca 的过程我推荐倍增,好写。
P8806 [蓝桥杯 2022 国 B] 搬砖
经典贪心,推一下 exchange argument,发现要按照 $w+v$ 排序,然后直接对于序列进行 01 背包即可。
P8800 [蓝桥杯 2022 国 B] 卡牌
二分套数,可行性明显具有单调性,check 只要扫一遍就行了。
P8789 [蓝桥杯 2022 国 B] 填空问题
379187662194355221
4 48 0
P8803 [蓝桥杯 2022 国 B] 费用报销
把票据按照时间排序,定义 $f_{i,j}$ 表示前 $i$,取了 $j$ 张票据的最大金额,转移不难。
P8801 [蓝桥杯 2022 国 B] 最大数字
先改变高位,如果可以到 9,就改到 9,但是用那种方式,搜一搜就好了!
总结
蛮水的。