CSP-S 游记

· · 生活·游记

10.27~10.31

仍旧本校考试爽抽一周，但是被限制参加体艺节了，难过。

绝区零提前大保底，这算rp++还是rp--？

GD 终于入秋了，但是没有完全入秋。

11.1

因为二楼机房空调很冷，考虑穿上秋衣秋裤，但是五楼机房没开空调，怎么回事呢.jpg

同桌考生没来，放飞自我

查询键盘状态，发现不稳，打字时会发出巨大响声，在此为周围的同学说一声对不起（

解压密码Ren5Jie4Di4Ling5%，并没有什么意味。

16min 秒掉 T1，15min 秒掉 T2。

5min 发现 T3 只能换一次，15min 发现 T3 |S_{i,1}|=|S_{i,2}|，与上方内容形成鲜明对比。

然后瞬间想到去掉匹配前后缀的部分必须相同，于是枚举 S 的长度的集合，使用哈希即可 O(L\sqrt{L})，考场上给分析成 O(n\sqrt{L}) 了，于是开始漫长的卡常。

首先，map<pair<ll,ll>,int>是很慢的，考虑将 S_{i,0,0},S_{i,1,0},S_{i,0,1},S_{i,1,1}\dots 交错排列一起哈希，优化为map<ll,int>，但是此时已经等价于一个多模匹配问题，可以直接 ACAM+树上前缀和 O(L _1\Sigma+L_2) 解决。

但是我试图将 O(n) 个map优化为一个map，鉴定为脑抽了。

经过分段测试发现此时的时间瓶颈在于ll的乘法，此时我使用的是强转int128，想了一会想出了这个东西：


ll mul(ll x,ll y){
    ll s=0;
    for(;x;x>>=16,y=y*65536%mod)s=(s+(x&65535)*y)%mod;
    return s;
}

但是代价是mod由 10^{16} 级变为 10^{14} 级（我写的随机质数），碰撞率由 e^{-10000} 飙升至 e^{-100}，当然无伤大碍。

此时过了 16:00，开 T4。

第一眼忘了放弃人数也要算忍耐度，写了个假 DP，然后想到快 17:00 想出了绝对正确的状态：dp[i][j][k]表示前 i 个人中失败或放弃了 j 个，忍耐度 >j 的还有 k 个人的方案数，但是脑抽了写到一半误以为 j\to j+1 的过程中 j+1 的数量对应的贡献和之前是有关系的，于是炸了。

18:00 紧急转 20pts，写了 20min 终于战胜。

upd：出分了，100+100+100+0，T4开了8e7long long直接mle。

这是真失败了。