20260526

B - 数字序列题意给定长度为nnn的序列每个位置只能填数字0,1,2,30,1,2,30,1,2,3。序列需满足任意相邻两个数字不能是下列模式00,11,22,33,02,20,23,32,13,31。有mmm个约束每个约束给出若干位置要求这些位置上的数字互不相同。判断是否存在合法序列。T≤10T \le 10T≤10n≤105n \le 10^5n≤105m≤5000m \le 5000m≤5000每个约束大小≤100\le 100≤100。其实答案是类似03030301212121这样的东西不断拼接起来的。首先0和1的位置的奇偶性是不相等的1和3以及0和2的位置的奇偶性是相等的。对于L4L4L4肯定无解或者读入的LLL个数奇数位或偶数位的数量大于222也是无解。假如若干条条件结合起来。首先可以发现有解的话必然存在不止一个。对于任意一个解将1和03和2互换一下必然也是一种解。这其实可以启发出强制钦定奇数位填1和3偶数为填剩余的这样在有解的情况下一定也是可以找到答案的。由于现在的L≤4L \le 4L≤4所以分完奇偶后而且奇偶互相独立。相当于告诉我们一个条件对于位置iii和jjj它们不相等。对于奇偶相关的关系很显然2两边都只能是13两边都只能是0。又因为每个位置只有两种选择这很容易想到2-sat直接做就行了。C - 最小生成树题意给定一个nnn点mmm边的连通无向图每条边有权值。指定一条边LabLabLab。每次操作选择一条边然后将图中除了这条边之外的所有边的权值减少111。求最少操作次数使得边LabLabLab一定出现在图的最小生成树中。n≤500n \le 500n≤500m≤800m \le 800m≤800边权10610^6106。容易发现那条边成为最小生成树上的必需边等价于找不到一条所有路径均小于validval_{id}valid​使得xidx_{id}xid​与yidy_{id}yid​联通的边。这样就可以直接使用最小割求解将边权小于validval_{id}valid​的两个端点连接起来边权为valid−vali1val_{id}-val_i1valid​−vali​1最小割就是使得整个图xidx_{id}xid​与yidy_{id}yid​不联通。