10.6 牛客

扯

唯一感觉能做的一场

感觉能做的原因是有分

100 + 0 + 50 + 5 = 155

T2 因不会写暴力而卑微爆零

发现只有奇偶有关又都是 (01) 串直接维护前缀和作差即为答案

一个结论: 网格图中对于两个点设 (a) 为其横坐标的距离 (b) 为其纵坐标的距离那么这里面可以选择的点的个数有 (g = gcd(a, b) - 1) 个

原题相当于在这条线上再找 (n - 2) 个球放到 (g) 个盒子里面相邻两个球的盒子编号至少为 (k) 这个东西的方案数为 ({g - (n - 1) imes (k - 1) choose n - 2})

所以可以直接枚举网格中的两个点计算答案

复杂度 (O(TW^2H^2))

对相同的 (a, b) 方案数相同考虑枚举 (a, b) 算出答案后再乘上 ((W - a + 1) imes (H - b + 1))

复杂度 (O(TWH))

一个节点 (u) 可以将子树中两个序列拼成一个序列处理完 (u) 的父亲时 (u) 已经不用管了可以用堆维护出 (u) 和 (u) 的子树中的点能组成的序列转移将所有子树的堆合并取出最大的两个合并成一个合并直接暴力启发式

复杂度 (O(nlog^2n))

放弃治疗