做网站哪家公司专业,商务网站建设心得体会,建设一个购物网站,网站推广的主要方式上链接#xff1a;P1955 [NOI2015] 程序自动分析 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1955
上题干#xff1a; 首先给你一个整数t#xff0c;代表t次操作。 每一次操作包含以下内容#xff1a; 1.给你一个整数n#xff0c;让…上链接P1955 [NOI2015] 程序自动分析 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1955
上题干 首先给你一个整数t代表t次操作。 每一次操作包含以下内容 1.给你一个整数n让你执行n次条件 接下来n行每行给你3个整数ijk 例如 1 2 1 或 1 2 0 (前面两个数代表下标第三个整数k代表条件如果它是1 ,则代表 x1 x2如果它是0代表x1x2 然后我们每一次操作需要输出yes 或 no 来表示这n个条件是否全部成立。 假如给出这样的数据 n4 1 2 1 2 3 1 1 4 1 3 4 0 第一个条件到第四个条件分别是 x1x2x2x3x1x4 x3x4 由于前面三个条件我们可以得知 x1x2x3x4 所以与x3x4矛盾输出no 数据 n1e6, i,j1e9 很显然这道题的条件和数据范围告诉我们需要用到并查集离散化 or hash表
第一并差集的特点就是能将不同的集合连接到一起然后便于我们查询某两个元素是否为同一集合。
第二这道题的数据范围太大了i能达到ie9所以我们直接用并查集的话毫无疑问数组装不下。所以我们可以用离散化来大大缩小数据范围除此之外呢我们还可以用hash表来处理这样的大数据使得每一个大数据都有一个特别的标记与之对应。
这两种方法都满足我们的需求这里主要用离散化来实现代码。
还记得离散化的具体步骤吗
记录散点排序去重二分查找
并查集的具体步骤呢
初始化集合建立查询函数合并函数。
所以我们的思路是这样的
1先将每一次的散点都存入一个数组b中
2对这个数组b进行排序
3对这个数组进行去重可以选择重新建立一个数组c来存放去重后的数据也可以直接用unique函数。
4二分查找每一对散点的相对位置。
5初始化并查集
6如果第三个数字k1我们就利用并查集来合并两个集合。
7如果第三个数字k0我们就查询两个数是否为同一集合如果是同一集合那么我们有
上代码 const int MAXN 1e6 10;
struct st {int x, y, z;
};
st a[MAXN];//三组输入数据存放之处
int b[2 * MAXN];// 存入散点
int c[2 * MAXN];//排序数组
int fa[2 * MAXN];//并查集
int btop, ctop;int find1(int x)
{if (x fa[x])return fa[x];return fa[x] find1(fa[x]);
}
void join1(int c1, int c2)
{int f1 find1(c1), f2 find1(c2);if (f1 ! f2)fa[f1] f2;
}
int main()
{int t;cin t;while (t--){btop 0;ctop 0;int n;cin n;for (int i 1; i n; i){cin a[i].x a[i].y a[i].z;b[btop] a[i].x;b[btop] a[i].y;}sort(b 1, b 1 btop);for (int i 1; i btop; i)if (i 1 or b[i] ! b[i - 1])c[ctop] b[i];for (int i 1; i n; i){a[i].x lower_bound(c 1, c 1 ctop, a[i].x) - c;a[i].y lower_bound(c 1, c 1 ctop, a[i].y) - c;}for (int i 1; i ctop; i){fa[i] i;}for (int i 1; i n; i){if(a[i].z)join1(a[i].x, a[i].y);}bool fk 1;for (int i 1; i n; i){if (a[i].z0){if (find1(a[i].x) find1(a[i].y))fk 0;}}if (fk 0)cout NO endl;else cout YES endl;}
}
