题解 P2354 【[NOI2014]随机数生成器】

2019-04-18 09:20:17


发一篇详细一点的题解。


首先要生成这个棋盘。算一下发现按照题意模拟就行了。

这里注意一下是 $x_i\mod i+1$ 而不是 $x_i\mod (i+1)$ ,也就是说其实是 $(x_i\mod i)+1$ 是不是只有我这种菜鸡看错了

然后既然是重排后的字典序最小,那么考虑贪心。

从小到大枚举每个数,如果能选到就选。

考虑如何判断一个数能否选到。显然对于每一行,它会有一个范围 $[l_i,r_i]$ ,表示路径最左从上一行的 $l_i$ 位置下来,最右从 $r_i$ 位置出去。显然如果当前数的 $y$ 不在 $[l_x,r_x]$ 内就不能选到。

那么只要动态维护 $l$ 和 $r$ 就可以判断了。每次选了一个数后直接扫一遍更新即可。

如果不懂可以画图理解。具体实现及细节见代码

另外这题比较卡空间、卡常,请注意优化。