首页 > 试题广场 >

组一组

[编程题]组一组

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

输入第一行两个正整数 n,m，意义如上
接下来 m 行，每行四个整数 op,l,r,x，表示一组限制
op = 1 表示是限制 1，op = 2 表示是限制 2

输出仅一行，n 个整数 a_i 表示数列 A。要求 0 <= a_i < 10⁹

示例1

输入

1 9 2 6

1<=n,m<=10^5, 1<=l<=r<=n, 0<=x<2^20

算法知识视频讲解

唯沁

发表于 2021-09-01 21:23:26

差分约束系统的解法如下：1、根据条件把题意通过变量组表达出来得到不等式组，注意要发掘出隐含的不等式，比如说前后两个变量之间隐含的不等式关系。2、进行建图：首先根据题目的要求进行不等式组的标准化。(1)、如果要求取最小值，那么求出最长路，那么将不等式全部化成xi – xj >= k的形式展开全文

最短路

上传者：牛客301599号

难度：

0条回答 0收藏 26浏览

查看代码

组一组

扫一扫，把题目装进口袋