PKUSC游记 - Blog E

PKUSC游记 - Blog E

坐火车到余姚，晚上到余姚宾馆，颓了一会，复习了下教练说往年都考了的ntt和线段树合并，又打了一遍网络流和sa(然而都没用上)，就睡觉了。

到考场试机发现是windows系统，好在提供gvim安装包，不过由于我平时都用的是neovim，对gvim的配置不太熟，只好又现查了查，改了下之前背的vimrc。

第一题，发现每个矩阵只和它前一个矩阵每行每列的和有关，于是就推了下这个东西的递推方法，矩阵快速幂搞定因为交错题又wa又re的调了一个小时。

第二题，先写了个暴力，发现整体修改的部分分相当是把询问的l，r移一下，于是写了个st表，把询问离线之后从后往前，在单调栈上二分，得了46分。

第三题，又是斗地主德州扑克，写了会放弃了。

100+46+0=146，同学差不多也是 这个分（有个同学爆切t3,得了38，但t2写的7分做法，总分加起来少了一分)

第一题，大力推式子，写了一个小时。

第二题，先写了个复杂度和值域有关的暴力dp。后来仔细想想觉得这个过程是可以贪心的：

• 对于每道菜价格mod c的余数部分金额，是可以随便用代金券的。
• 此最后一道菜肯定会尽量用代金券，因为再不用之后就没机会了，而如果最后一道菜完全用代金券支付，代金券还有剩余，那么第二道菜就会尽量用代金券，以此类推（差不多是这个意思，具体有点细节）。

得出一个结论：一个最优解必分为三段，前面一段对于余数部分尽量用代金券，中间是单独的一道菜，后面部分完全用代金券支付。

于是可以预处理出在第一个策略下，每个前缀中能净赚到的代金券数，以及前缀中花的钱，每次枚举前面一段的长度，计算出中间那道菜最少花多少钱（这个有二分性，可以直接除），加上前缀中花的钱取min，这样算复杂度O(n2)。

对c=1的情况，可以用树状数组维护前缀中赚的代金券和花的钱（就是价格的前缀和），发现后面的枚举其实也可以用二分替代，可以O(Qlogn)解决。

听说这样离正解只差用线段树维护那个前缀中赚的代金券和花的钱了，但是我就是死活想不出怎么维护c不等于1的情况，于是51分滚粗。

第三题，没有subtask，输出1得5分，考完听说输出0还可以再得5分。

考场上没啥思路，尝试积了个分，结果算出负的概率来。还尝试随机撒点，估算出概率的double值，然后找一个比较接近的分数输出，但是都以失败告终。

100+51+5=156，一些同学没写第二题的贪心分，自我感觉还可以。

面试问了一些奇怪的问题，后面就颁奖了。

总分302，初三的不少大佬没来，分数线不太高，于是就1=了

---

作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接

阅读量 56

---

• Previous
  USACO 2021 US Open 铂金组 T1 题解

---