哈哈哈哈各种乱搞大法。
某次校内模拟赛 T3,题意大致如下:
题目描述
给定 个节点的树,求树上有多少个三元组 (两两不同)满足其中任意两个点的树上距离不超过给定常数 .
数据范围 .
时间限制 2s
现场感觉可能是个不太套路的点分治,敲了几十行发现不太对劲咋一坨细节想不清楚,再一看表发现就剩一个小时多一点,估计以我的代码能力是写完也调不出来愉快爆零那种。正当我打算打出 GG 退出游戏的时候,突然灵光一闪虎躯一震,朴素的暴力也不过是 ,评测姬是 64 位,再考虑到吸氧,还跑不满,那么如果....[斜眼笑]
我立即写了一个 dfs 略加剪枝的预处理,用bitset
乱搞存距离是否不超过 ,然后暴力有序枚举前两个点在bitset
里查,总复杂度 ,忐忑不安的提交了(就是个很无聊的暴力)。
结果震撼我妈这暴力跑得飞快 20 个测试点只有一个点跑了 1s 以上成功 AC,绝了。
最后正解出来的确是个点分治,但是比较麻烦里面还要强制离线又要动态维护什么的还要考虑计重反正是我绝对写不出来的,哈哈哈哈幸亏老子当时没有死刚正解(原谅我比较弱)。
要说最震撼的,还是某次模拟赛,std 有问题数据全部出锅。
然而,就在这种情况下,依然有某位神犇猜测到数据出锅而成功 AC 了...
全场目瞪狗呆,或许,这就是神犇之所以是神犇吧[颤抖]。