这个题的 hash 做法怎么卡(详细揭秘)
查看原帖
这个题的 hash 做法怎么卡(详细揭秘)
47863
Imakf楼主2022/9/29 15:27

众所不一定周知,某开小号的匿名毒瘤把 dp 状态哈希,使得复杂度不优的方法通过了此题。今天闲着无聊小编芙卡米重读了毒瘤的题解,结果发现有一句话:

特判无解的话我们用这份哈希+记搜的代码跑一下,然后打个表,发现在 nn12331\sim 233 时,10p10|pp=25p=25p=26p=26 时总是无解的。

10p10|p 无解很有道~理~,因为尾数取不到 00p=25p=25 无解也有道~理~,因为位数取不到 25,50,7525,50,75;但是 p=26p=26 又是怎么一回事呢?于是小编拿之前的 std 跑了下,发现 p=26p=26 确实是有解的。小编不太放心,于是拿了另一篇题解,发现跑出来也有解。那么毒瘤为什么会通过呢?原来是出题人之前的数据里没有 p=26p=26,于是小编马上联系了出题人加上了这样的数据。

但出题人觉得这并没有彻底 hack 掉这种做法,因为将毒瘤代码中对 p=26p=26 的特判删掉之后就可通过了。不信邪的出题人于是开始对着代码卡,注意到毒瘤在暴搜中的这句话具有关键作用:

if( idcnt > 1500000 ) return ;

其含义为,如果 idcnt 大于 1,500,000,就返回。即,如果 identity count 大于 1.51061.5\cdot10^6,就退出 dfs 函数,也即剪枝。那么我们能否构造一组数据,使得其有解,但 idcnt1.51061.5\cdot 10^6 的时候依然跑不出解呢?事实上这组数据是存在的,并且已经被出题人加入了最新数据中。但是出题人发现,把 1.51061.5\cdot 10^6 改成 41064\cdot 10^6,则毒瘤的代码又可以通过了!令人唏嘘。

更令人唏嘘的是,将毒瘤的代码与出题人代码进行对拍,约 100 组数据即可拍出错,但在洛谷上上传 200 组左右的数据实在是影响不好,故就此作罢。果然,毒瘤是不可战胜的。

2022/9/29 15:27
加载中...