LuoguLOJ分析根据拟阵的相关理论可以知道:$A$ 是权值最小的基当且仅当 $\forall u\in A,v\notin A$,只要 $(A\backslash\{u\})\cup\{v\}$ 是基,则 $v_u\leq v_v$;权值最大的基的情况同理。这样子就把原题中最小值、最大值的限制转化成了若干组偏序关系。现在的问题即为 $p=2$ 时的保序回归问题。根据论文中的理论,考虑整体...
LuoguGym分析考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭,可以列出线性规划用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==============...
比赛地址Chocolate Bar横着竖着是一样的,这里只考虑横着。那么要么是横切三刀,要么是先横切一刀再竖切一刀。前面只要看 $H$ 是不是 $3$ 的倍数,不是的话差最小是 $W$。后面可以直接枚举横切在哪,竖切一定切在 $\frac{W}{2}$ 的位置。代码3N Numbers显然存在一个分界线 $i\in[n,2n]$,满足在 $[1,i]$ 中选了最大的 $n$ 个、在 $[i+...
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案,可以发现只有以下三种情况:团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外,于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$,则一定存在一段和为 $w-2$,...
LuoguLOJ分析考虑二分答案,则我们需要判定是否存在混合图欧拉回路。首先混合图不连通的话一定不存在。然后给无向边任意定向,算出每个点的度数,如果有点度数为奇数则不存在。那么对于一条无向边,假设我们定向 $u\to v$,则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。因此可以考虑网络流。对于 $in_ out_i$ 的点,从源点...
Luogu分析不难看出一个最大权闭合子图的模型,然而直接求最大流显然过不了,于是可以考虑模拟最大流。首先把这个坐标系变换一下。如果警卫 $a$ 能看到手办 $b$,则应有于是可以把 $(h\times x+w\times y,h\times x-w\times y)$ 作为每个点的坐标,这样子警卫 $a$ 能看到手办 $b$ 当且仅当 $x_b\leq x_a,y_a\leq y_b$。考虑...
CodeforcesLuogu分析有几个比较显然的结论(证明不会):一定存在一组最优解,使得所有卡都被摆上去过。感性理解:因为 $b_i\geq 0$ 所以你就算摆上去再拿下来也不会更差。一定存在一组最优解,满足首先摆上 $k-1$ 张卡,再将 $n-k$ 张卡摆上去后立即拿下来,再将剩下的那张卡摆上去。感性理解:此时 $b_i$ 的贡献是最大的,且 $a_i$ 的贡献没有影响。那么相当于要...
LOJCF 原题分析感觉很像最小权闭合子图。为了方便把所有费用取负。考虑这样的连边方式源点向每种药连容量为 $+\infty+p_i$ 的边。每种药向所需的药材连容量为 $+\infty$ 的边。每种药材向汇点连容量为 $+\infty$ 的边。拿最小割减去所有 $+\infty+p_i$ 的和即为答案(因为取了负)。下面是正确性理解:首先可以发现,第二种的边是不会割的,如果割了换成第三种边...
LOJ分析考虑二分图。对于每一行、列被 # 隔开的每一段拿出来当做一个点,然后对于每个点从其所属的行连通块向列连通块连边。但是每个连通块内可以放多个棋子。假设一个连通块内放了 $x$ 个棋子,那么会产生 $\frac{x(x-1)}{2}$ 的费用,我们要最小化费用。考虑费用递增。由于 $\frac{(x+1)x}{2}-\frac{x(x-1)}{2}=x$,所以我们只需要连若干条容量为 ...
LuoguLOJ分析数组开小 -> 100->40 -> 身败名裂先考虑没有费用的情况,显然是最大权闭合子图模型(选了 $[i,j]$ 就必须选它的所有子区间)。因此对于每个 $[i,j]$,如果 $d_{i,j}$ 为正则从源点向它连容量为 $d_{i,j}$ 的边,否则从它向汇点连容量为 $-d_{i,j}$ 的边,然后对于每个 $[i,j]$ 向它的子区间连容量为 $...