首页 > 代码库 > HDU 3038 How Many Answers Are Wrong
HDU 3038 How Many Answers Are Wrong
http://acm.hdu.edu.cn/showproblem.php?pid=3038
题意:
给定数字个数N(A1,...,AN)和M句话,"l r s"代表下标[l,r]的数字之和为s
求出现冲突的句子数量
解法:
带权并查集
以区间右端为父节点,将l-1与r点合并
查询时进行路径压缩 sum[x] += sum[fa[x]]
合并时更新根节点的 sum[x] = sum[r] - sum[l] + s
则sum[x]表示[x+1, fa[x]]数字之和 (fa[x]<x时,sum[x]等于负的[A(fa[x]+1), Ax]数字之和)
同时判断同根节点的sum[l] - sum[r]是否等于给出的s
代码: 62MS 2236K
#include <cstdio>using namespace std;#define N 200001int fa[N], sum[N], ans;void init(int n) { ans = 0; for (int i = 0; i <= n; i++) { fa[i] = i; sum[i] = 0; }}int findfa(int n) { if (n == fa[n]) { return n; } int t = findfa(fa[n]); sum[n] += sum[fa[n]]; return fa[n] = t;}bool unite(int l, int r, int s) { int x = findfa(l), y = findfa(r); if (x == y) { return (sum[l] - sum[r] != s); } fa[x] = y; sum[x] = sum[r] - sum[l] + s; return 0;}int main() { int n, q, l, r, s; while (~scanf("%d%d", &n, &q)) { init(n); for (int i = 0; i < q; i++) { scanf("%d%d%d", &l, &r, &s); ans += unite(l - 1, r, s); } printf("%d\n", ans); } return 0;}
HDU 3038 How Many Answers Are Wrong
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。