ZigZagK的博客
[Manacher+离线+线段树]2015计蒜之道初赛第三场【商品推荐走马灯】题解
题目概述给出一个序列,一个回文区间的权值是区间权值和,问 $[L,R]$ 中所有回文区间的权值和。解题报告刚开始想用回文自动机 $O(n\sqrt n)$ 暴搞,然后我自带大常数TLE了……只需...
[生成函数+FFT]计蒜客NAIPC2016E【K-Inversions】题解
题目概述有一个AB字符串,问间距为 $k$ 的BA对有多少,其中 $k\in[1,n-1]$ 。解题报告emm……应该算是生成函数吧?令A的位置的权值为下标,B的位置的权值为下标的相反数,那么只...
[Trie]2018计蒜之道初赛第二场【阿里巴巴的手机代理商】题解
题目概述有 $n$ 个询问:$Insert\ s\ x$ :增加 $x$ 个 $s$ 。$Delete\ s$ :删除所有 $s$ 。$Query\ s$ :查询以 $s$ 为后缀的字符串数量。...
[树形DP+two-pointer]2016计蒜之道初赛第六场【微软的员工福利】题解
题目概述有 $n$ 个ZZK给JZ打工,他们的上下级关系是一棵树。现在JZ要给蒟蒻ZZK输送一定的神犇之力,每个ZZK可以得到 $r_i$ 点神犇之力或者 $p_i$ 点神犇之力。但是在ZZK得...
[最大密度子图]2017计蒜之道初赛第三场【腾讯狼人杀】题解
题目概述有 $n$ 个神犇JZ,某两个JZ配合有神犇值,共有 $m$ 组这样的JZ。现在要选出若干个JZ(假设选了 $k$ 个),贡献为存在于这些JZ中的所有配合的神犇值之和除以 $k(2n-k...