当前位置: 首页 > news >正文

AtCoder Regular Contest 207 (Div.1) 游记

省流

赛时一个半小时没出题,赛后再来三个小时终于搞出 A。

10.5

内含剧透,请vp后再来。

不是题解!!!!!!!

赛前

本来发现要补的东西还剩很多,结果当天上午就补完了前一天的 \(ABC\),下午又搞了两道区域赛题,想着晚上打 \(ARC\)\(CF\)。结果到赛前发现 \(CF\) 竟然是凌晨 \(00:35\) 开始,被震惊了一下,最后就决定只打 \(ARC\) 了。

赛时

先看第一题,也只看了第一题。题目给了 \(n\) \((n\leq100)\) 个商品,每个商品都有一个很大价格,然后有一个总钱数 \(x\),要求每秒买一个物品,每过一秒所有商品的价格减一,到零为止,求购买完所有商品不同顺序有多少种。
看到这个范围很容易想到 \(n^4\)\(DP\),进而考虑怎么把很大的范围变成 \(n\) 的范围。发现其实可以看作总花费是 \(\sum_{a_i}^n\),然后减去一些减掉的价格。第 \(i\) 个位置买第 \(j\) 个商品减免的花费其实就是 \(min(a_j, i - 1)\),这样就把所有数据范围都缩到 \(n\) 这个级别,容易想到 \(DP\) 的三维分别是当前位置 \(i\),与购买了哪些相关的 \(j\) 和减免的价值 \(k\)\(k\) 的范围总之小于 \(n^2\),具体就是求和前 \(n-1\) 个数。最后取减免的花费大于等于原总花费和拥有的钱数之差的情况数。
显然这里面最需要设计的就是那个 \(j\),毕竟你不可能来一个状压存 \(2^{100}\)。我一开始是选择存了当前到第 \(i\) 位的总情况数,\(j\) 是当前位中以第 \(j\) 个商品结尾的情况数,结果发现这样存其实只是把同一个商品不能连续拿而不是我们想要的只能拿一次。
此时发现取商品的顺序应该是可以动刀的,毕竟这个量的大小顺序应该会非常好用,但不知道排序后该怎么设计,在赛中 \(100min\) 左右逃跑了,遂寄。

赛后

因为打挂了没熬夜打 \(CF\),第二天起来发现 \(qwsxza\) 竟然上黄了,而我现在差距还很大,而昨天满打满算也就学了 \(7h\) 左右,就这样我还在以打挂了心情不好为借口逃避,非常失败了。
继续看 A 题,重新理清思路之后可以发现一个重要的性质,就是
减免的花费其实就是 \(min(a_j, i - 1)\)
再加上排序这个想法,状态的设计就不言自明了(其实还是很难想)。我们只取考虑较小的那个放到较大的花费,如对位置考虑时就把所有该位置放较大数的情况都加上位置的花费,而放较小数则无视。同理对一个商品考虑时只加上该商品放较大位置时的花费,放较小位置则因为已经在考虑这个较小位置的时候加过了就不需要再管了。
那么排序之后我们就可以按照上面的思路搞一下。对于一个位置,我们把商品,也就是题目中的灯分成三类,小灯,中灯和老灯,分别表示这个商品的价格小于,等于和大于这个位置的编号减一。我们的状态就统计当前 \(i\) 位置中已经塞入了 \(j\) 个小灯时减免花费为 \(k\) 的情况有多少个。
首先我们转移 \(i\)。一个新的位置进来时,可以往这个位置里放小灯或者中老灯,如果放小灯那么减免花费已经在后面算小灯(等一下还要转移灯)时统计过了,就 \(i+1\)\(j+1\) 直接转相应的 \(k\) 就行。如果加入的是中老灯,那么 \(j\) 不变,\(k\) 则要增加 \(i - 1\),因为不管放置哪个中老灯的效果都一样,所以可以放置的种类就是现在剩余的中老灯数量。
在转移过 \(i\) 之后,我们要把和 \(i - 1\) 相等的中灯全部转移了。中灯同样有两种放法,一种是放到小于等于的位置上,一种是放到大于的位置上。和位置的转移一样,如果放到比较小的位置,那么直接 \(j+1\) 就可以了,因为这个放置的花费 \(k\) 在前面转移中老灯时已经计算过了。如果放到大于的位置上,那么当前 \(i\) 个位置的小灯数 \(j\) 就不变,而增加的 \(k\) 同样都是 \(i-1\),且后面大于的位置都可以放,也就是种类是 \(n - i\)
需要注意的是转移某个灯的时候,一定要静态的转移再赋值,否则放置的数量会左脚踩右脚上天,以及开的数组不要太大了,在本地虽然不会影响编译但内存的分配方面可能出诡异的问题,平常能写还是节省空间开个滚动数组更好。
现在还是太摆了,我要继续努力,不然就这个水平真去打比赛就要变成大笨猪了。
(事后看来虽然还是实际上让商品按价格排序了,但其实直接遍历一遍也没问题,但是重要的还是利用这个顺序,至于找这个顺序的方式其实无所谓)

2025年10月6日

http://www.hskmm.com/?act=detail&tid=25417

相关文章:

  • 深入解析:AI破局:饿了么如何搅动即时零售江湖
  • 从零开始学Flink:数据输出的终极指南
  • 数据编织平台实现AI代理自助数据访问
  • [题解]P12008 【MX-X10-T4】[LSOT-4] Fragment of Memories
  • 线性表的顺序存储和链式存储
  • AWS WebRTC:获取ICE服务地址(part 3):STUN服务和TURN服务的作用 - 实践
  • Python中的对象池与驻留机制:小整数、字符串与大整数
  • 基于ADMM无穷范数检测算法的MIMO通信系统信号检测MATLAB仿真,对比ML,MMSE,ZF以及LAMA
  • 点乘与叉乘的由来:从四元数到公理自洽的启示
  • 【算法深练】分组循环:“分”出条理,化繁为简 - 教程
  • java学习日记10.5
  • 【JNI】JNI基础语法
  • 【EF Core】通过 DbContext 选项扩展框架
  • 从Chrome渲染器代码执行到内核:MSG_OOB漏洞分析与利用
  • assistant-ui
  • 20251006 之所思 - 人生如梦
  • C# Avalonia 16- Animation- RotateButton
  • 2025 十一集训
  • 汇编实验3
  • 20251005 模拟测 总结
  • 基于Python+Vue开发的体育用品商城管理系统源码+运行步骤
  • 完整教程:Microsoft Word使用技巧分享(本科毕业论文版)
  • (转)The Ten Commandments of Digital Cotrol(Part1)
  • ctf逆向常见算法----base64
  • 02020409 EF Core基础09-一对一、多对多、EF Core基于关系的复杂查询
  • 02020503 EF Core高级03-分页查询、IQuerable底层的实现形式、DataReader、DataTable、EF Core中的异步方法
  • 02020502 EF Core高级02-IQuerable会延迟执行、分部和动态构建IQuerable、IQuerable的复用
  • 在 PyCharm 中,环境:bert_env , 执行 import wandb 报错。但是,在CMD窗口,环境:bert_env , 执行 import wandb 正常。
  • Linux_T(Sticky Bit)粘滞位详解 - 详解
  • P2831 [NOIP 2016 提高组] 愤怒的小鸟 题解