20241013 洛谷SCP模拟

20241013 洛谷SCP模拟

J1. 带余除法

急眼了，J 组 T1 做不出来。经 cyq 大神指点。

考虑将题中给出的带余除法转化：\(n=kq+r\)，移项得到 \(r=n-kq\)。

这里 \(n,k\) 都是定值，于是对于每一个 \(q\)，都有唯一的一个 \(r\) 与之对应。考虑余数的性质：

解不等式得到 \(\lfloor\frac n{k+1} \rfloor < q\le\lfloor \frac n k\rfloor\)。容易发现这个范围内的所有整数都可以取到，于是答案为 \(\lfloor \frac n k\rfloor-\lfloor\frac n{k+1} \rfloor\)。

J2. 奖牌排序

急眼了，J 组 T2 做不出来。经 cyq 大神指点。

对于每个人，有三种排序方式取最优。

那么对某种方式考虑，我们先对这一维排序，接着对每个人更新答案。考虑每个人在这种方式下的最高排名怎么算，发现其实就是这一维比他小的人的个数加一，于是可以二分求解。

J4. 配对序列

cyq 大神说这题代码很简单并且是 \(O(n)\) 的，可是我只会无脑数据结构，破防。

考虑一个朴素的 dp。设 \(f_{i,0/1}\) 表示选第 \(i\) 个位置，且这个位置是相邻数对中的第 \(1/2\) 个数，最长序列的长度。转移枚举上一个选的位置 \(j\)，那么若 \(a_j=a_i\)，则 \(f_{j,0}\) 可以转移到 \(f_{i,1}\)；否则 \(f_{j,1}\) 可以转移到 \(f_{i,0}\)。

对于第一种转移，我们记录 \(g_i\) 表示所有满足 \(a_j=i\) 的 \(j\) 中，\(f_{j,0}\) 的最大值，这样就能 \(O(1)\) 转移了。对于第二种转移，我们开一颗权值线段树，记录 \(f_{j,1}\) 的最大值，转移时只要查询区间 \([1,a_i)\) 和 \((a_i,V]\) 即可。\(O(n\log V)\)。

这题 \(n,V\) 同阶，\(V\) 开大时加个离散化就行了。所以时间复杂度是 \(O(n\log n)\) 的。

S1. 商店砍价

这题绝对比 J 组 T1T2 都简单。

注意到 \(v\) 只有 \(10^5\)，那么容易看出，第二种操作进行时，剩余数的位数一定不超过 \(5\)。于是容易想到枚举进行第二种操作时的 \(n\) 并计算贡献，注意这里枚举的数一定是原数的子序列，子序列自动机判一下即可。

cyq 大神说我绝对是非正解。又被 D 了。