企业官网建设流程全解析

B - 数字序列

题意：给定长度为nnn的序列，每个位置只能填数字0,1,2,30,1,2,30,1,2,3。序列需满足：

1. 任意相邻两个数字不能是下列模式：00,11,22,33,02,20,23,32,13,31。
2. 有mmm个约束，每个约束给出若干位置，要求这些位置上的数字互不相同。

判断是否存在合法序列。T≤10T \le 10T≤10，n≤105n \le 10^5n≤105，m≤5000m \le 5000m≤5000，每个约束大小≤100\le 100≤100。

其实答案是类似0303030，1212121这样的东西不断拼接起来的。

首先，0和1的位置的奇偶性是不相等的，1和3以及0和2的位置的奇偶性是相等的。

对于L>4L>4L>4肯定无解，或者读入的LLL个数，奇数位或偶数位的数量大于222也是无解。

假如若干条条件结合起来。

首先，可以发现有解的话必然存在不止一个。对于任意一个解，将1和0，3和2互换一下必然也是一种解。这其实可以启发出，强制钦定奇数位填1和3，偶数为填剩余的，这样在有解的情况下一定也是可以找到答案的。

由于现在的L≤4L \le 4L≤4，所以分完奇偶后，而且奇偶互相独立。相当于告诉我们一个条件，对于位置iii和jjj，它们不相等。对于奇偶相关的关系，很显然，2两边都只能是1，3两边都只能是0。又因为每个位置只有两种选择，这很容易想到2-sat，直接做就行了。

C - 最小生成树

题意：给定一个nnn点mmm边的连通无向图，每条边有权值。指定一条边LabLabLab。每次操作：选择一条边，然后将图中除了这条边之外的所有边的权值减少111。求最少操作次数，使得边LabLabLab一定出现在图的最小生成树中。n≤500n \le 500n≤500，m≤800m \le 800m≤800，边权<106<10^6<106。

容易发现，那条边成为最小生成树上的必需边等价于找不到一条所有路径均小于validval_{id}valid​使得xidx_{id}xid​与yidy_{id}yid​联通的边。

这样就可以直接使用最小割求解，将边权小于validval_{id}valid​的两个端点连接起来，边权为valid−vali+1val_{id}-val_i+1valid​−vali​+1，最小割就是使得整个图xidx_{id}xid​与yidy_{id}yid​不联通。