「HDU6094」Rikka with K-Match
题目链接题目大意$n \times m$ 的网格图 要求你求一个大小为 $k$ 的最小权匹配。$n \leq 40000,m \leq 4,k \leq \frac{nm}{2}$多组数据 数据组数 $T \leq 1000$，保证只有三组数据 $n > 100$。题解首先这个题是可以二分图染色跑费用流的。所以设 $w_i$ 表示 $i$ 条边的答案。很容易有 $w_i-w_{i-1}...
题目链接题目大意$n \times m$ 的网格图 要求你求一个大小为 $k$ 的最小权匹配。$n \leq 40000,m \leq 4,k \leq \frac{nm}{2}$多组数据 数据组数 $T \leq 1000$，保证只有三组数据 $n > 100$。题解首先这个题是可以二分图染色跑费用流的。所以设 $w_i$ 表示 $i$ 条边的答案。很容易有 $w_i-w_{i-1}...
题目链接题目大意$n \times m$ 的网格图 这个网格图中不能往上走 要求支持如下操作：修改网格图上的一条边询问从第一行某个点到最后一行某个点的最短路径$n \leq 5000,m \leq 200,q \leq 2\times 10^5$ 修改次数 $d \leq 500$。题解看到这个行+单点修改可以考虑维护一个线段树：令 $A_{i,j}$ 表示当前块内上面第 $i$ 个点到下...
题目链接题目大意坐标轴上有 $n$ 个点 每个点有一个收益 $v_i$ 。你从 $s$ 点开始 在接下来的 $m$ 天里每一天你可以选择移动到相邻的城市或获得这个城市的收益。一个城市的收益只能被获得一次。求最大可能的收益。$n \leq 10^5$题解发现这个路径只可能是先往左，在折回来往右（或者倒过来）。我们只需要考虑第一种情况（后面那种情况可以通过 reverse 再做一遍得到）如果我们...
题目链接题目大意有两个长度为 $n$ 的序列序列 $a$ 和 $b$，要求你计算出一个长度为 $n$ 的序列满足我们令 $sm_d = \sum_{d|j} [b_j \geq b']$。发现 $sm$ 只会根据 $b'$ 的变化而变化 于是我们想到了整体二分。整体二分的时候运用类似于莫队的移动指针的技巧 预处理因数分解和 $\mu$ 就可以快速判定了。时间复杂度 $O(nlog^3n)$...
题目大意维护一个序列 支持以下操作：序列末尾插入一个向量$(x,y)$序列末尾删除一个向量询问区间 $[l,r]$ 中和向量 $(u,v)$ 叉积的最大值（设 $(x,y) \in [l,r]$,要求 $(u,v)\times(x,y)$ 最大）$n \leq 5\times 10^5$题解看到叉积 先想到斜率优化。给出 $(u,v)$，要求最大化 $uy-vx$。设 $b=uy-vx$ 变...