ZigZagK的博客
[NTT]AtCoder Grand Contest 005F【Many Easy Problems】题解
题目概述AGC005F解题报告考虑每个点对 $k$ 的贡献:$$ \sum_{i=1}^{n}[{n\choose k}-\sum_{(i,j)\in E}{size_j\choose k}]=...
[离散+DFS+计数]AtCoder Regular Contest 104E【Random LIS】题解
题目概述AtCoder Regular Contest 104E解题报告这题还是挺可做的。我们发现 $n$ 小的一批,因此考虑离散。我们没必要对于每个 $i$ 都枚举 $1\to A_i$ ,对...
[容斥+计数]HHKB Programming Contest 2020 D【Squares】题解
题目概述HHKB Programming Contest 2020 D解题报告其实不难,就是烦的一批,考试的时候写复杂了然后调不出来。首先补集转化,我们求相交的数量,然后总数量减去相交的数量。为...
[思维+区间DP]AtCoder Regular Contest 104F【Visibility Sequence】题解
题目概述AtCoder Regular Contest 104F解题报告我又来翻译题解了😭。我们在最前面加上一个 $+\infty$ ,然后把 $P$ 中的 $-1$ 改成 $0$ ,那么不难发...
[计数+背包]AtCoder Regular Contest 104D【Multiset Mean】题解
题目概述AtCoder Regular Contest 104D解题报告对于每个 $x$ ,我们认为第 $i$ 个物品大小为 $x-i$ ,共有 $K$ 个,现在的问题就转化为有多少种方案,使得...
[容斥+生成函数+分治NTT]ACL Beginner Contest F【Heights and Pairs】题解
题目概述ACL Beginner Contest F解题报告直接求不太可做,我们考虑容斥,用总方案数减去至少一组相同的方案数加上至少两组相同的方案数……$2n$ 个元素两两组合的方案数为 $f_...
[DP]AtCoder Regular Contest 104C【Fair Elevator】题解
题目概述AtCoder Regular Contest 104C解题报告我英语太渣题目读错了😭,以为只要存在某两个人满足 $C_i=C_j$ 就行了,实际上应该是只要出现两个人在电梯上,就必须有...
[思维+树状数组]ACL Contest 1E【Shuffle Window】题解
题目概述ACL Contest 1E解题报告神仙转化题我根本做不来……我又来翻译题解了。按顺序random_shuffle可以转化为以下形式:有一个数组 $A$ ,刚开始有排列 $p$ 中 $[...
[线段树]ACL Beginner Contest E【Replace Digits】题解
题目概述ACL Beginner Contest E解题报告不知道各位数学课上有没有求过这个数列的通项公式……
[思维+倍增]ACL Contest 1D【Keep Distances】题解
题目概述ACL Contest 1D解题报告根本不会做,我来翻译原题解了QAQ。如果要求的是 $[L,R]$ 中最长的good set,我们直接 从 $L$ 开始向后贪心 或者 从 $R$ 开始...