[思维+最大费用最大流]ACL Contest 1C【Moving Pieces】题解
题目概述ACL Contest 1C解题报告这题还是挺可做的，首先考虑棋子之间拦路的问题，在一颗棋子穿过了另一颗棋子时，我们可以认为两颗棋子互换位置，显然移动次数不变。既然没有棋子之间互相拦路，...
[扩展欧几里得]ACL Contest 1B【Sum is Multiple】题解
题目概述求最小 $k$ 使得 $k(k+1)\over 2$ 是 $n$ 的倍数。解题报告AC的题太难了，我全都不会做😭。移下项：$k(k+1)\equiv0\pmod{2n}$ 。显然 $...
[二分+后缀数组]HDU2328【Corporate Identity】题解
题目概述HDU2328解题报告首先将所有串中间隔开接起来（注意中间隔开的字符不能相同）。二分枚举答案 $len$ ，然后根据 $Height$ 数组分块，每个块中检查是否 $n$ 个字符串都出现...
[后缀数组]HDU3518【Boring counting】题解
题目概述HDU3518解题报告枚举子串的长度 $len$ ，然后将后缀数组按照 $Height\ge len$ 分块，每个块中检查最左和最右的子串是否交叉就行了。示例程序#include<...
两种常见的树上差分
树上差分忘完了……康复一下。记 $x$ 节点的父亲为 $fa(x)$ 。记 $x,y$ 节点的LCA为 $lca$ 。记权值数组为 $w_x$ ，差分数组为 $D_x$ 。记DFS序中 $IN_...
[拉格朗日插值]Codeforces622F【The Sum of the k-th Powers】题解
题目概述求 $f(n,k)=\sum_{i=1}^{n}i^k$ 。解题报告我们知道 $f(n,k)$ 的公式可以由组合数推导，并且由推导方式可知 $f(n,k)$ 是一个 $k+1$ 次多项式...
[DP+单调栈+线段树动态开点]Codeforces1407D【Discrete Centrifugal Jumps】题解
题目概述有 $n$ 个建筑物，高度 $h_i$ 。要从 $1$ 跳到 $n$ ，求最少跳跃步数。$i\to j$ 的跳跃要求：$i+1=j$$\max(h_{i + 1}, \ldots, h_...
[思维]Codeforces1407C【Chocolate Bunny】题解
题目概述交互题。有一个 $1\sim n$ 的排列 $\{p_n\}$ ，每次可以询问 $(x,y)$ ，得知 $p_x\bmod p_y$ 。在 $2n$ 次询问内问出这个排列。解题报告考虑两...
拉格朗日插值
求多项式我们知道 $n$ 个点可以确定 $n-1$ 次多项式（比如三点求抛物线）。假设 $f(x)=\sum_{i=0}^{n-1}a_ix^i$ ，如果我们要求 $f(k)$ ，可以先解出 $...
