ZigZagK的博客
ZJOI2019 Round1 退役记
Day [-n,-2]天天考试,天天爆炸+被学弟吊打。Day -1在家休息(颓废)了一天,下午去找放学了的同学打了下乒乓球。内心虚的一批,和同学聊了下未来规划发现人家是立志考少年班的人……我这种...
[广义SAM]BZOJ3926(Zjoi2015)【诸神眷顾的幻想乡】题解
题目概述有一棵 $n$ 个节点的树,每个节点有一个字符。定义一条路径 $(x,y)$ 形成的字符串为从 $x$ 走到 $y$ 路径上所有字符按顺序接起来形成的字符串。求所有本质不同的字符串。叶子...
[思维+区间DP]BZOJ4574(Zjoi2016)【线段树】题解
题目概述有一个序列 $\{a_n\}$ ,定义一次操作 $[L,R]$ 表示将 $[L,R]$ 中的数改成 $[L,R]$ 中的最大数。现在要进行 $q$ 轮,每轮随机一个区间 $[L,R]$ ...
[离线+扫描线+LCT]BZOJ4573(Zjoi2016)【大森林】题解
题目概述有 $n$ 棵树和 $m$ 个操作,操作有:1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $x$ 树中 $A$ 到 $B$ 的...
[容斥+三元环]BZOJ5407【girls】题解
题目概述JZ需要从 $n$ 个妹子中挑出 $3$ 个出去浪,但是三个妹子之间不能有冲突,一种方案 $(i,j,k),i<j<k$ 的贡献为:$Ai+Bj+Ck$ ,求所有合法方案的总...
[思维+第二类斯特林数]BZOJ5413【color】题解
题目概述用 $K$ 种颜色对 $n\times m$ 的网格进行染色,需要保证无论怎么样纵切将棋盘分为左右两个部分, 两个部分的颜色种类数都必须相等,求方案数。解题报告在NOIP前,这道题被法老...
[第一类斯特林数+广义容斥]BZOJ5406【Gift】题解
题目概述定义两个 $n$ 的排列 $A,B$ 的相似度为通过交换两个元素使得两个排列相同的最小次数。现在给出两个 $n$ 的排列,有些位置还没有确定,求相似度为 $i,i\in[0,n-1)$ ...
[思维+组合+NTT]LOJ6261【一个人的高三楼】题解
题目概述给出一个数组,求这个数组的 $k$ 次前缀和(前缀和的前缀和的前缀和……)。解题报告就是这题套个NTT,水博客真开心。可能略有卡常……示例程序#include<cstdio>...
[bitset+树链剖分+线段树+霍尔定理]BZOJ5404【party】题解
题目概述有 $n$ 个点的有根树,每个节点只能往上走,且每个节点有一个特产。现在有 $q$ 个询问,每次询问 $c$ 个点,求这些点走到他们的公共祖先,在满足:1.每个人带的特产数量相等。2.没...
[后缀平衡树]BZOJ5084【hashit】题解
题目概述给出一个操作串:如果是小写字母,表示在当前字符串后面添加这个小写字母。如果是 $−$ ,表示删除当前字符串最后的小写字母(保证合法)。求每次操作后当前字符串不同子串的个数。解题报告暴力后...