社区讨论

更改板子而不能保证正确的思路

P4051[JSOI2007] 字符加密参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lobxdiwd
此快照首次捕获于
2023/10/30 04:30
2 年前
此快照最后确认于
2023/11/04 09:46
2 年前
查看原帖
目前我并没有用这个思路A掉这道题
既然是一个环,我们不妨考虑更改模板(对不起,板子不该改)。对于一个 sai+len>nsa_i+len>n,板子中我们将 rkrk 的值赋值为负无穷,本题中不妨模拟这个环,当 sai+len>nsa_i+len>nsaisa_i在本次排序中的权值为 rksai+lennrk_{sa_i+len-n},这就相当于将第二关键字改为了环上的某一个点。如果这样做会丢失一个优化,因为第二关键字必须排序。但是 NN 减少了一倍。
目前在题解里没有看到这种方法谁会写这种东西啊,正确性存疑。所以发出蒟蒻の问。

回复

2 条回复,欢迎继续交流。

正在加载回复...