差分约束系统

差分约束系统的解法如下：
1、 根据条件把题意通过变量组表达出来得到不等式组，注意要发掘出隐含的不等式，比如说前后两个变量之间隐含的不等式关系。
2、 进行建图：
首先根据题目的要求进行不等式组的标准化。
(1)、如果要求取最小值，那么求出最长路，那么将不等式全部化成xi – xj >= k的形式，这样建立j->i的边，权值为k的边，如果不等式组中有xi – xj > k，因为一般题目都是对整形变量的约束，化为xi – xj >= k+1即可，如果xi – xj = k呢，那么可以变为如下两个：xi – xj >= k, xi – xj <= k,进一步变为xj – xi >= -k，建立两条边即可。
(2)、如果求取的是最大值，那么求取最短路，将不等式全部化成xi – xj <= k的形式, 这样建立j->i的边，权值为k的边，如果像上面的两种情况，那么同样地标准化就行了。
(3)、如果要判断差分约束系统是否存在解，一般都是判断环，选择求最短路或者最长路求解都行，只是不等式标准化时候不同，判环地话，用spfa即可，n个点中如果同一个点入队超过n次，那么即存在环。
值得注意的一点是：建立的图可能不联通，我们只需要加入一个超级源点，比如说求取最长路时图不联通的话，我们只需要加入一个点S，对其他的每个点建立一条权值为0的边图就联通了，然后从S点开始进行spfa判环。最短路类似。
3、 建好图之后直接spfa或bellman-ford求解，不能用dijstra算法，因为一般存在负边，注意初始化的问题。

有一个长为 n 的数列 A，其中有 m 个限制条件，条件有两种：
1、对于区间 [l,r]，其区间元素按位或和等于 x
2、对于区间 [l,r]，其区间元素按位与和等于 x
求出一个数列 A，使得满足给定的 m 个条件，保证有解。

转化有一点点巧妙哦
解：
对于每一位分开考虑
问题简化：有一个长为n的01串，记Sum[]为前缀和，有四种限制：
1、对于[l,r]按位与和为x，且x的当前位为1，则区间[l,r]全为1
(Sum[r] - Sum[l - 1] == r - l + 1)
2、对于[l,r]按位或和为x，且x的当前位为0，则区间[l,r]全为0
(Sum[r] - Sum[l - 1] == 0)
3、对于[l,r]按位或和为x，且x的当前位为1，则区间[l,r]存在1
(Sum[r] >= Sum[l - 1] + 1)
4、对于[l,r]按位与和为x，且x的当前位为0，则区间[l,r]存在0
(Sum[r] <= Sum[l - 1] + r - l)
可以用差分约束系统 +最短路来求一组解，题目保证有解，不用判负环。