POJ 1364 King

继续套路地把每个位置 a_i 拿出来当做“值”。

然后再套路地把前缀和搞出来 s_i = \sum_{j=1}^i{a_j}

然后题面的约束条件就成了:

s_r - s_{l-1} > ki

s_r - s_{l-1} < ki

差分约束用的是 \leqslant\geqslant 。 

那么就全转化成 A - B \leqslant C 算了。

那么就

s_{l-1} - s_r \leqslant -1-k

s_{r} - s_{l-1} \leqslant k-1

判负环。

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据