[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...
