牛客小白月赛33题解
A - 字符统计
按照题意模拟计数即可,只考察一些字符串的操作
B - 连分数
这个分数的拆分是有套路的,按照题目的样子,一路递归下去就可以
C - 挪酒瓶
置换的状况可以表示成: ,每个物品都会换到一个指定的位置。
有恰好 个东西换到他现在的位置,置换的关系会形成一个圈。也就是说,假设
要换到位置
,位置
要换到
,
,最后换回
。这个东西在数学上称为置换群。
对于一个有 个元素的置换群
,从最后一个
往前开始换,则费用为
虽然每个元素都至少会被换一次,所以后面的 是固定的。
最优的策略则是选择较小的 开始换。
如果改变交换的顺序则会产生更复杂的式子,但最优的情况下只会交换 次,所以可以放在一起比较。
而上述的式子可以轻易证明是最优的。
可是让我们看下面这个例子
5 1 3 4 5 2 1 99 99 99 99
答案为 。可是如果只用上述的策略则会算出
。这个例子的置换群为
。可以发现,如果只考虑该置换群内最小的
,并不会最好。
新想法:把目前最轻的酒瓶拿进来替换,最后再换回去。令置换群 内最轻重量为
,令全部的酒里面最轻重量为
。这个策略的花费为
最后对于每一个置换群,考虑两个 如下,都选择最优即可:
D - 购物
字符串处理。
表示原本第
种商品有几份。
表示第
种商品有多少人拥有,那么可以知道第
种商品有
人买。
答案就是有几个
满足
E - 喝可乐
因为
,兑换空瓶数量会逐渐减少
枚举所有可能购买的方法即可
注意剩余的两种空瓶的数量
常见错误:
- 如果
,买
的整数倍不就好了
- 试考虑
的状况
F - 天旋地转
- 旋转坐标轴
人物反方向旋转。
- 繁琐的四方向移动模拟。
很大
- 如果是移动,往朝该方向走
步,等同于坐标加减
- 如果是旋转,转
次,绕一圈等于没绕,所以转
次即可
- 反方向转
- 视为往正方向转
- 也就是往正方向转
很大
- 坐标范围是
,
嘿嘿
G - 挑数字
- 考虑部分和
- 一组答案可以对应到一组相同的部分和
- 答案就是找众数
H - 货物运输
直觉:找很多条路径+小小张的图
?
哈哈
网络流吧
复杂度好像很对
实际:样例过不了
,跟花费流正确的条件反过来
观察:你不会想要分多条路走
任两条路
,把
换成
或者把
换成
,至少有一个
不会上升。
直观证明1:同一条路只会越用越便宜,
多加一条
直观证明2:若
换成
上升,
加
加
,
换成
会降
。
所以一条边要么就不用,要么就用
次,每条边的
设为走
次时的花费。
耶
变成一般的最短路
I - 三角尼姆
水题不表
J - 线段的交
直接求面积,然后判断正负即可