2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛83
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛83 [2021/05/23 09:12] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛83 [2021/05/23 10:01] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 69: | 行 69: | ||
| ==== 题解 ==== | ==== 题解 ==== | ||
| - | 首先给定结论当 $a,b$ 互素时，$ax+by(x,y\ge 0)$ 不能表示的正数等价于所有形如 $ab-na-mb(n,m\ge 1)$ 的正数。 | + | 首先给定结论当 $a,b$ 互素时，$ax+by(x,y\ge 0)$ 不能表示的正数等价于所有形如 $ab-na-mb(n,m\ge 1)$ 的正数，具体见 [[https://wiki.buaaacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:other:%E7%BB%93%E8%AE%BA_2#%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%A4%BA|证明]]。 |
| + | |||
| + | 接下来问题转化为求所有形如 $ab-na-mb(n,m\ge 1)$ 的正数中第 $k$ 大的元素。 | ||
| + | |||
| + | 考虑维护两个队列，队列一维护所有 $ab-a-mb(m=1)$，且保证递减。 | ||
| + | |||
| + | 队列二维护所有 $ab-na-mb(n\ge 1,m\ge 2)$，且保证递减。每次选择当前两个队列的队首的较大者进行 $\text{pop}$，连续 $k$ 次即可得到第 $k$ 大。 | ||
| + | |||
| + | 队列一的维护仅需要每次 $\text{pop}$ 后 $m$ 加一即可。队列二初始时为空，每次 $\text{pop}$ 元素 $t$ 后将 $t-b$ 加入队列。 | ||
| + | |||
| + | 现证明这样得到的队列二一定满足递减性质。假设先前 $\text{pop}$ 的所有元素确实为前 $k$ 大，记为 $a_1,a_2\cdots a_k$。 | ||
| + | |||
| + | 记本次 $\text{pop}$ 的元素为 $a_{k+1}$。则队列二的当前所有元素一定是由 $a_t-b$ 得到的，由于 $a_t\gt a_{k+1}$，所以 $a_t-b\gt a_{k+1}-b$，满足单调性。 | ||
| + | |||
| + | 于是总时间复杂度 $O(k)$。另外假定 $a\gt b$，可以考虑二分答案，然后枚举 $n$，然后统计 $m$，时间复杂度 $O(\sqrt k\log (ab))$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | int main() | ||
| + | { | ||
| + | LL a=read_int(),b=read_int(),k=read_int(),pos=1; | ||
| + | queue<LL> q; | ||
| + | while(true){ | ||
| + | if(q.empty()||q.front()<a*b-pos*a-b){ | ||
| + | k--; | ||
| + | if(k==0){ | ||
| + | enter(a*b-pos*a-b); | ||
| + | break; | ||
| + | } | ||
| + | q.push(a*b-pos*a-2*b); | ||
| + | pos++; | ||
| + | } | ||
| + | else{ | ||
| + | k--; | ||
| + | if(k==0){ | ||
| + | enter(q.front()); | ||
| + | break; | ||
| + | } | ||
| + | q.push(q.front()-b); | ||
| + | q.pop(); | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/牛客练习赛83.1621732350.txt.gz · 最后更改: 2021/05/23 09:12 由 jxm2001
