竞赛讨论区 > 牛客小白月赛33题解
头像
DongResponse
发布于 2021-04-17 22:00
+ 关注

牛客小白月赛33题解

A - 字符统计

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

B - 连分数

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

C - 挪酒瓶

置换的状况可以表示成: ,每个物品都会换到一个指定的位置。

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

对于一个有 个元素的置换群,从最后一个 往前开始换,则费用为

虽然每个元素都至少会被换一次,所以后面的 是固定的。

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

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

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

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

5
1 3 4 5 2
1 99 99 99 99

答案为 。可是如果只用上述的策略则会算出 。这个例子的置换群为 。可以发现,如果只考虑该置换群内最小的 ,并不会最好。

新想法:把目前最轻的酒瓶拿进来替换,最后再换回去。令置换群 内最轻重量为 ,令全部的酒里面最轻重量为 。这个策略的花费为

最后对于每一个置换群,考虑两个 如下,都选择最优即可:

D - 购物

字符串处理。

  • 表示原本第种商品有几份。

  • 表示第种商品有多少人拥有,那么可以知道第种商品有人买。

  • 答案就是有几个满足

E - 喝可乐

  • 因为 ,兑换空瓶数量会逐渐减少

  • 枚举所有可能购买的方法即可

  • 注意剩余的两种空瓶的数量

常见错误:

  • 如果 ,买 的整数倍不就好了
  • 试考虑 的状况

F - 天旋地转

  • 旋转坐标轴 人物反方向旋转。
  • 繁琐的四方向移动模拟。
  • 很大
  • 如果是移动,往朝该方向走 步,等同于坐标加减
  • 如果是旋转,转次,绕一圈等于没绕,所以转 次即可
  • 反方向转
  • 视为往正方向转
  • 也就是往正方向转
  • 很大
  • 坐标范围是
  • 嘿嘿

G - 挑数字

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

H - 货物运输

  • 直觉:找很多条路径+小小张的图

  • 哈哈 网络流吧 复杂度好像很对

  • 实际:样例过不了

  • ,跟花费流正确的条件反过来

  • 观察:你不会想要分多条路走

  • 任两条路,把换成或者把换成,至少有一个不会上升。

  • 直观证明1:同一条路只会越用越便宜,多加一条

  • 直观证明2:若换成 上升,换成会降

  • 所以一条边要么就不用,要么就用次,每条边的设为走次时的花费。

  • 变成一般的最短路

I - 三角尼姆

水题不表

J - 线段的交

直接求面积,然后判断正负即可

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐