题解
凸包斜率优化动态规划（斜率优化 DP）几何基础基础分治
题意
在线进行 $n$ 个操作：
把向量 $(x,y)$ 插入到平面内；
给一个向量 $(x,y)$ ，问平面内第 $l$ 个到第 $r$ 个向量之间中的一个向量与该向量的点积最大值。
$n\leq 3\times10^5$ 。
口胡
挺酷炫的。考虑到查询操作的 $x,y$ 相当于给了个直线斜率。那么解肯定在 $[l,r]$ 的凸包上，那么线段树每个点维护一个凸包（ …
Jayun 发布于 2023-10-31 11:55:53
00
WQS 二分决策单调性优化动态规划（决策单调性优化 DP）
题解
这里用了 WQS 二分，二分队列做法。
const int N = 5e5 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c …
Jayun 发布于 2023-10-30 22:01:54
00
重链剖分（HLD）深度优先搜索（DFS）
题意
一棵 $n$ 个节点的树，第 $i$ 个点值为 $a_i$ 。 $q$ 次操作，每次操作要么单点修改；要么给出 $k$ 个数，查询这 $k$ 个点中任意两点的简单路径上的所有点的点值总和。
$n,q\leq10^5,\sum k\leq10^6$
口胡
询问先按 dfs 序排序，然后从第 1 个点往后合并（统计到 lca 的答案）。树剖维护。
然后看答案验证发现错了。 …
Jayun 发布于 2023-10-30 19:59:19
00
决策单调性优化动态规划（决策单调性优化 DP）
口胡
设 $f_{i,j}$ 表示 $i$ 是第 $j$ 个邮局，有
$$f_{i,j}=\min_{k<i,g\text{二分得到}}\left\{f_{k,j-1}+\sum_{h=k+1}^{g-1}(a_h-a_k)+\sum_{h=g}^{i-1}(a_i-a_h)\right\}
$$
后面那一串满足四边形不等式。
Jayun 发布于 2023-10-30 19:16:33
00
计数枚举
题意
$n$ 个数，每个数 $a_i$ ，选 $k$ 个数，一个选取方案的值是异或和。求所有选取方案值的和。
$n\leq10^5,a_i<2^{31}$ 。
题解
加法和异或本质相同。
考虑每一位的贡献，简单组合计数。
代码
const int N = 3e5 + 5, mod = 998244353;
inline ll Read() {
ll x = 0, f = 1; …
Jayun 发布于 2023-10-30 19:02:53
00
计数组合意义树形动态规划（树形 DP）
题面
有一颗 $n$ 个点的树，第 $i$ 个点有点权 $a_i$ 。
现在要断掉一些边，记一个连通块的权值为连通块中所有点的点权和，一个断边方案的权值为所有连通块的权值的乘积的平方。
求所有不同的断边方案的权值和对 $10^9+7$ 取模后的结果。
$n\leq5\times10^5$
题解
直接组合意义：每个连通块 $\sum a_i$ 个球，对每个连通块选两个球（放回） …
Jayun 发布于 2023-10-30 18:48:18
00
贪心
题目大意
给一个 $2n$ 结点的二分图，左边的点 $i$ 连向 $i+n$ 并且有值 $LE,LF,E,F$ 分别表示经过此边需要多少 $e,f$ 、经过此边后会使 $e\leftarrow e+E,f\leftarrow f+F$ ，右边的点连向任意左边点无值无条件。现在可以从任意点出发，一笔画遍历图，问起始时可以带最小的 $e,f$ 是多少。
$n\leq10^5$ …
Jayun 发布于 2023-10-30 18:23:46
00
鸽笼原理计数
题目大意
给定 $n$ 个数，求出这 $n$ 个数的一个非空子集，使得这个子集中的数的和能被 $n$ 整除，无解输出 -1。 $n\leq 10^5$ 。
口胡
一眼鸽笼，算上 0 位前缀和有 $n+1$ 个，而最多 $n$ 个余数，此处鸽笼。
Jayun 发布于 2023-10-30 15:56:31
00