A - Beauty of Trees

题意:

链接:https://www.nowcoder.com/acm/contest/119/A
来源:牛客网

Beauty of Trees
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld

题目描述

It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
One day the tree manager wants to play a game with you. There are N trees lining up in a straight road. The beauty of a set of trees is defined as the bitwise XOR sum of the heights of these trees. The game will last for M rounds, and each time he will tell you an interval [Li,Ri] and its beauty. However, he mixed some fake messages with the correct ones. Your task is to find the messages that cannot logically correspond to its former correct messages. Otherwise you’ll think the message is correct.

输入描述:

The first line contains two integer N and M(1≤N,M≤10

5

), the number of trees and the rounds of game.
Then M lines followed, in each line are three integer L, R and k(1≤L≤R≤N,0≤k≤10

9

), indicating that the beauty of [L

i

,R

i

] is k.

输出描述:

If the i-th message is wrong, then print i in a single line.
If there is no mistake, print -1.

输入例子:
3 4
1 3 6
1 2 5
3 3 10000
3 3 3
输出例子:
3

-->

示例1

输入

3 4
1 3 6
1 2 5
3 3 10000
3 3 3

输出

3

说明

You can infer from the first two messages that the height of the third tree is 3.

题意: 
        有nn个数,每次给你一个信息l,r,kl,r,k,代表al xor al+1... xor ar=kal xor al+1... xor ar=k,问你哪些信息是错误的,如果xx信息和yy信息只可以xx对yy错或者xx错yy对,那么认为先给出的信息是对的。

思路: 
并查集路径压缩。 记aa数组的前缀异或和是sumsum,那么信息l,r,kl,r,k实际上就是sumr xor suml−1=ksumr xor suml−1=k,如果已知sumr xor sumx=k1,suml−1 xor sumx=k2sumr xor sumx=k1,suml−1 xor sumx=k2,那么只要判断k1 xor k2k1 xor k2是否等于kk即可,否则设sumr xor sumx=k1,suml−1 xor sumy=k2sumr xor sumx=k1,suml−1 xor sumy=k2,那么有sumx xor sumy=k1 xor k2 xor k,sumx xor sumy=k1 xor k2 xor k,可以合并x,y,x,y,并设sum[x] xor sum[y]=k1 xor k2 xor ksum[x] xor sum[y]=k1 xor k2 xor k, 然后直接用路径压缩就好了。

#include<bits/stdc++.h>
using namespace std; const int N = 1e5 + ;
const int INF = 1e9; int f[N], a[N]; int father(int x)
{
if (x != f[x])
{
int tmp = father(f[x]);
a[x] ^= a[f[x]];
f[x] = tmp;
}
return f[x];
} int main()
{
int n, m; scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++)
{
f[i] = i;
a[i] = ;
}
bool flag = ;
for (int i = ; i <= m; i++)
{
int l, r, k; scanf("%d%d%d", &l, &r, &k);
--l;
int fl = father(l), fr = father(r);
if (fl == fr)
{
if ((a[l] ^ a[r]) != k)
{
printf("%d\n", i);
flag = ;
}
}
else
{
f[fr] = fl;
a[fr] = k ^ a[l] ^ a[r];
}
}
if (flag) printf("-1");
return ;
}

最新文章

  1. 初识jsonp
  2. 移动APP的自动化测试
  3. angularjs中的页面访问权限设置
  4. [JavaEE]理解ThreadLocal
  5. 【Android Demo】悬浮窗体实现
  6. Android实例-闪光灯的控制(XE8+小米2)
  7. Sql Server 与CLR集成
  8. 【读书笔记】【CLR via C#】【第一章】The CLR’s Execution Model
  9. Nodejs in Visual Studio Code 08.IIS
  10. Oracle database启动过程分析
  11. poj1920 Towers of Hanoi
  12. http?https?相对协议?
  13. Android jni 编程2(对基本类型一维整型数组的操作)
  14. 【learning】[待完善]关于辛普森公式的一点想法
  15. 爬虫 -----爬取百度时事热点和url
  16. lucene的suggest(搜索提示功能的实现)
  17. Linux中sudo的用法
  18. mysql分组后将未分组的列合并成行GROUP BY,GROUP_CONCAT
  19. netstat参数
  20. javascript分页显示

热门文章

  1. codeforces Codeforces Round #318 div2 A. Bear and Elections 【优先队列】
  2. freemarker入门实例与源码研究准备工作
  3. jupyter &amp;&amp; ipython notebook简介
  4. 如何在java中导入jar包
  5. QT 创建对话框 Dialog 实例
  6. vue v-if with v-for
  7. codevs1907 方格取数 3
  8. MySql基础学习-Sql约束
  9. review41
  10. Respond.js的作用