题目分析

本题要求将集合 $S = {1, 2, \dots, N}$ 划分为两个不相交的子集 $S_0$ 和 $S_1$，满足给定的约束条件，并最小化 $|L_0 - L_1|$（两个子集大小的差值）。

关键观察

1. 约束条件分析：

对于每个数列 $A$，要求相邻元素必须属于不同的子集：

这意味着：相邻元素在划分中必须交替出现。这本质上是一个二分图染色问题：

如果 $A_i$ 属于 $S_0$，则 $A_{i+1}$ 必须属于 $S_1$

如果 $A_i$ 属于 $S_1$，则 $A_{i+1}$ 必须属于 $S_0$

2. 图模型构建：

将每个数字 $x$ 看作图中的一个顶点。对于每个数列中的相邻元素 $A_i$ 和 $A_{i+1}$，在它们之间连一条边。这样：

约束条件转化为：每条边的两个端点必须染上不同颜色（$S_0$ 或 $S_1$）

问题转化为：判断图是否为二分图，并最小化两种颜色顶点数量的差值

3. 冲突检测：

如果图中存在奇环，则无法进行二分图染色，输出 impossible。

算法思路

1. 二分图染色检查

使用 DFS 或 BFS 对图进行二分图染色：

初始时所有顶点未染色

从任意未访问顶点开始，将其染为颜色 0

遍历其邻接点，要求染为相反颜色（颜色 1）

如果发现相邻顶点颜色相同，说明存在奇环，无解

2. 连通分量分析

图可能由多个连通分量组成。对于每个连通分量：

如果染色成功，得到两种颜色的顶点数分别为 $cnt_0$ 和 $cnt_1$

该连通分量的颜色分配是固定的（除了可以整体交换颜色 0 和 1）

该分量对最终差值的贡献为 $|cnt_0 - cnt_1|$

3. 差值最小化问题

设所有连通分量的差值绝对值为 $d_1, d_2, \dots, d_k$。我们需要决定哪些连通分量交换颜色（将 $cnt_0$ 和 $cnt_1$ 互换），从而最小化最终的总差值。

这转化为一个子集和问题：

每个连通分量可以选择贡献 $+d_i$ 或 $-d_i$（对应是否交换颜色）

目标是让所有贡献的和的绝对值最小

等价于：从差值集合中选出一个子集，使得子集和尽可能接近总和的一半

4. 动态规划优化

由于 $N$ 可达 $10^6$，直接背包 DP 不可行。代码中使用了巧妙优化：

对差值进行计数压缩

使用 bitset 加速 DP（bitset 优化背包）

时间复杂度分析

建图：$O(\sum K_i) = O(10^6)$

DFS 染色：$O(N + \sum K_i)$

bitset DP：$O(N \cdot \frac{sum}{wordsize})$，其中 $wordsize = 64$，实际很快

正确性证明

1. 二分图染色的正确性：

约束条件要求相邻元素属于不同子集，这等价于二分图染色问题。如果染色失败（发现相邻顶点同色），说明存在奇环，不可能满足约束。

2. 差值最小化的正确性：

每个连通分量的两种颜色分配方案本质只有两种（交换或不交换），对应贡献 $+d_i$ 或 $-d_i$。要使总差值最小，就是选择合适的符号组合，这等价于子集和问题。

3. bitset DP 的正确性：

bitset 的每一位表示一个和是否可达。左移操作相当于添加一个物品（差值）。由于我们只关心最接近总和一半的和，所以只需计算到 $sum/2$。

特殊情况处理

1. 自环或连续相同元素：

如果数列中出现 $A_i = A_{i+1}$，则要求同一个元素同时属于 $S_0$ 和 $S_1$，这是不可能的。在染色过程中会检测到这种情况。

2. 多个连通分量：

每个连通分量独立，可以分别处理。最终结果通过 DP 组合。

3. 大量重复差值：

通过差值合并优化，将多个相同差值合并，减少 DP 计算量。

总结

本题通过图论建模和动态规划的组合，巧妙地解决了约束满足和优化问题：

图论建模：将约束条件转化为二分图染色问题

连通分量分析：独立处理每个连通分量，计算颜色数量差

优化问题转化：将颜色交换选择转化为子集和问题

高效求解：使用 bitset 加速 DP，处理大规模数据

算法的时间复杂度和空间复杂度都在可接受范围内，能够处理 $N \le 10^6$ 的大规模数据。

AC代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k[1050000], pre[1050000], x[1050000];
int vis[1050000], col[1050000], cnt[2];
int dp[1050000], sum;
vector<int> edge[1050000];
queue<int> qu;
bitset<1005000> f;
void dfs(int x) {
    vis[x] = 1;
    cnt[col[x]]++;

    for (auto y : edge[x]) {
        if (vis[y])
            continue;

        col[y] = col[x] ^ 1;
        dfs(y);
    }
}
int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) {
        scanf("%d", &k[i]);
        pre[i] = pre[i - 1] + k[i];

        for (int j = pre[i - 1] + 1; j <= pre[i]; j++) {
            scanf("%d", &x[j]);

            if (j != pre[i - 1] + 1) {
                edge[x[j - 1]].push_back(x[j]);
                edge[x[j]].push_back(x[j - 1]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) {
            dfs(i);

            if (cnt[0] > cnt[1])
                dp[cnt[0] - cnt[1]]++;

            if (cnt[1] > cnt[0])
                dp[cnt[1] - cnt[0]]++;

            cnt[0] = cnt[1] = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (auto j : edge[i]) {
            if (col[i] == col[j]) {
                printf("impossible\n");
                return 0;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dp[i] >= 3) {
            dp[i * 2] += (dp[i] - 1) / 2;
            dp[i] -= (dp[i] - 1) / 2 * 2;
        }
    }

    for (int i = 1; i <= n; i++)
        sum += dp[i] * i;

    f[0] = 1;

    for (int i = 1; i <= sum / 2; i++) {
        for (int j = 0; j < dp[i]; j++) {
            f |= (f << (i * 2));
        }
    }

    for (int i = sum; i >= 0; i--) {
        if (f[i]) {
            printf("%d\n", sum - i);
            return 0;
        }
    }

    printf("%d\n", sum);
    return 0;
}