2-SAT 2-SAT 属于 k-SAT 问题的一种。不幸的是，对于 \(k > 2\)，都是 NPC 问题。 给定 \(n\) 个变量，每个变量 \(A_i \in \{0,1\}\)。接着给定 \(m\) 个条件，每个条件形如 \[ A_i=0/1 \text{ or } A_j=0/1 \] 求 \(n\) 个变量的合法赋值，满足全部 \(m\) 个条件。 求解 将条件

最小树型图 最小树形图，也可以理解为有向图的最小生成树。 更学术地说，在一张有向带权图 \(G\) 中，找出一棵以 \(root\) 为根，权值和最小的有向生成树，满足： \(root\) 入度为 0，其余节入度为 1 任意两点 \((u,v)\) 间，有且仅有 1 条简单路径 朱刘算法 理论 朱刘算法是一个能在 \(O(nm)\) 的时间内验证有向带权图是否有最小

分析 预处理出每个铁匠能够打造的剑能够打败的怪物集合 \(s(x)\) 与每条道路上的怪物集合 \(u(x)\)。还是正常连边。 设 \(f(i,S)\) 为从起点到节点 \(i\)，能够打败的怪物集合为 \(S\) 时，花费的最小时间。状态是一张图，用 Dijkstra 算法转移。 边界自然是 \(f(1,s(1)=0)\)。考虑 \(x\) 的子节点 \(y\)，\(i\) 为 \

把能够到达的宫室连边。 具体地，对于一个横天门，将它与同一行中的普通点连单向边，横天门连双向边。对于一个纵寰门，将它与同一列中的普通点连单向边，纵寰门连双向边。对于一个任意门，向周围的 8 个点连单向边（前提是不越界）。 由于只要到达一个强连通分量里，周围的点都能到达，所以求出所有强连通分量，缩点。点权为改强连通分量中点的个数。然后 DP 最长路就行了。 这题主要是实现麻烦。 #inc

本文重写于 2023.8.27 把每个外星人的存活时间看成是区间，那么本题又可以转化成那种经典模型。 区间的贡献在交点上。 设 \(f(i,j)\) 为消灭被 \([i,j]\) 完全包含的所有区间的最小代价。 我们肯定是找到 \(d\) 最大的那个区间一发干掉。 枚举干掉它的时间，以这个为轴，划分子问题 。 #include<

分析 老样子，先判断无解情况。 我们假设 \(h_n\) 无限高于或者低于 \(h_1\)，那么中间的那些都必须尽力去逼近 \(h_n\)，一定是递增或递减的。但由于相邻的两堆石头高度差不能超过 \(d\)，所以递增或递减的最大长度为 \((n-1) \cdot d\)。如果 \(|h_n-h_1| > (n-1) \cdot d\)，那么肯定是无解。反过来想，如果不大于，那么一

分析 将多游修理点按照位置递增排序。由于经过一个点便会立即修复它，所以每次被修复的点一定是一个连续的区间。由于修完一个区间后处于左右端点有后效性，要加进状态里。这样状态就出来了。 不难发现，最终答案能转化为 每个点立即修复的花费+增长的花费。我们只计算后者就好了。 设 \(f(i,j,p)\) 为修完区间 \([i,j]\)，处于 \(p\) 时增长的最小花费。\(p=0\) 时在 \(i

先判断无解的情况。 由于每一段都要非 0 的偶数朵花，那么当 \(n\) 为奇数时显然无解。 用 \(m\) 个点固定，就是分成了 \(m-1\) 段。每个半段不能超过 \(d\) 朵，那么总数最多为 \(2 d \cdot (m-1)\)，最少为 \(2 \cdot m\)。所以当 \(n\) 大于最大值，小于最小值时，无解。   题目要求最小的半段重量的最大值，可以二分答案。我们定义

这题我只想称之为神 最优解中，开凿的道路一定联通，且一定是一棵树。这是因为如果最终不连通，那么显然不符合题意；如果最后不是一棵树，那么删去若干一条边后，不仅仍然可能连通，而且会减少代价。 暴搜显然不合适，那就考虑状压 DP。 DP 需要一定的顺序。和树形 DP 一样设子树信息为状态？不行，一开始并不是一棵树，直接 pass 掉。节点编号？也不行，根本转移不动。考虑到最后求出的实际上是一棵

直接设状态为花费的钱数是不行的，硬币的使用顺序与购买顺序都会影响答案，复杂度爆炸。 设 \(f(S)\) 为使用的硬币为 \(S\) 时，最多能买的物品个数。 对于 \(S_0 \subseteq S\)，显然能够转移，但方程并不是一个简单的多项式。 不难发现，枚举 \(S\) 的子集是不行的，不能直接转移，且复杂度过高。那就考虑枚举硬币。 对于一个集合 \(S\)，枚举枚举其中每一个