洛谷6621 [省选联考 2020 A 卷]魔法商店
Luogu LOJ 分析 根据拟阵的相关理论可以知道：$A$ 是权值最小的基当且仅当 $\forall u\in A,v\notin A$，只要 $(A\backslash\{u\})\cup\{v\}$ 是基，则 $v_u\leq v_v$；权值最大的基的情况同理。这样子就把原题中最小值、最大值的限制转化成了若干组偏序关系。 现在的问题即为 $p=2$ 时的保序回归问题。根据论文中的理论，...
Luogu LOJ 分析 根据拟阵的相关理论可以知道：$A$ 是权值最小的基当且仅当 $\forall u\in A,v\notin A$，只要 $(A\backslash\{u\})\cup\{v\}$ 是基，则 $v_u\leq v_v$；权值最大的基的情况同理。这样子就把原题中最小值、最大值的限制转化成了若干组偏序关系。 现在的问题即为 $p=2$ 时的保序回归问题。根据论文中的理论，...
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...