题目描述

•有一个01序列,长度<=1000000000,现在有n条信息,每条信息的形式是－a
b even/odd。表示第a位到第b位元素之间的元素总和是偶数/奇数。
•你的任务是对于这些给定的信息，输出第一个不正确的信息所在位置-1。信息的数目不超过5000。
•如果信息全部正确，即可以找到一个满足要求的01序列，那么输出n。

输入

•输入文件
•第一行一个整数m表示01序列的长度，第二行一个整数n表示信息的数目。
•接下来是n条信息

输出

输出第一条错误信息的位置-1.

如果没有错误信息，则输出n

样例输入

10

5

1 2 even

3 4 odd

5 6 even

1 6 even

7 10 odd

样例输出

3

这道题可以用并查集的思路做

将第三行数据的1 2看做半开半闭区间( 0 , 2 ]中的所有整数元素，他们的和是偶数，可将0当做2的父亲，他们之间的距离为0（偶数mod2的余数）

以此类推，如果为奇数，则他们之间的距离为1

那么，输入x和y，找到他们各自的父亲g和h，如果g不等于h，则无需验证，将g作为h的父亲，其距离计算公式为：

s[ h ]=( s[ x ] + m - s[ y ] )%2

其中m为x到y的和的奇偶性（看不懂就慢慢想）

如果，g等于h，则进行验证，看看abs( s[ x ] - s[ y ] )%2是否满足此语句的奇偶性

整体思路到位

接下来，由于输入的x和y最大为十亿，无法开出这么大的数组，则必须将其理想化

由于只有5000条语句，所以元素最多只有10000个，则用数组将输入的x和y装进去，要验证的时候直接数组里面找，将其在数组中的编号代替其本身进行运算

还不明白？看代码吧：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<algorithm>
  5. using namespace std;
  6. int abs(int x){return x>=0?x:-x;}
  7. int a[10001];
  8. int f[10001],s[10001];
  9. int m,n,k;
  10. int find(int x)//找父亲与离父亲的距离，顺便找沿路所有元素与离父亲的距离（看不懂？自己慢慢想）
  11. {
  12. if(f[x]==0)return x;
  13. int xx=find(f[x]);
  14. s[x]+=s[f[x]];
  15. s[x]%=2;
  16. return f[x]=xx;
  17. }
  18. int main()
  19. {
  20. int i,j;
  21. scanf("%d%d",&m,&n);
  22. for(i=1;i<=n;i++)
  23. {
  24. char c[11];
  25. int x,y,r1,r2;
  26. scanf("%d%d%s",&x,&y,c);
  27. if(x>m||y>m){printf("%d",i-1);return 0;}
  28. if(x>y)swap(x,y);
  29. x--;//半开半闭区间，小的元素减减
  30. bool p=0,q=0;
  31. for(j=1;j<=k;j++)//找数组中是否有x和y
  32. <span style="white-space:pre">  </span>{
  33. if(a[j]==x&&!p)x=j,p=1;
  34. if(a[j]==y&&!q)y=j,q=1;
  35. }
  36. if(!p)a[++k]=x,x=k;//没有就将其加进去
  37. if(!q)
  38. {
  39. if(x!=y)a[++k]=y,y=k;//这里要注意
  40. else y=x;
  41. }
  42. r1=find(x),r2=find(y);
  43. if(r1!=r2)
  44. {
  45. if(r1>r2)swap(r1,r2);
  46. f[r2]=r1;
  47. if(c[0]=='o')s[r2]=abs(s[x]+1-s[y])%2;
  48. else s[r2]=abs(s[x]-s[y])%2;
  49. }
  50. else//验证
  51. {
  52. if(c[0]=='o'&&abs(s[x]-s[y])%2!=1){printf("%d",i-1);return 0;}
  53. if(c[0]=='e'&&abs(s[x]-s[y])%2){printf("%d",i-1);return 0;}
  54. }
  55. }
  56. printf("%d",n);
  57. }

最新文章

  1. XP之后Windows的一些变化
  2. [FMX] Android APP 启动黑屏优化补丁
  3. 《C#编程》课件 - C#基础
  4. .Net中几种常见的页面跳转传值方法
  5. 数字转换为壹仟贰佰叁拾肆的Java方法
  6. UVA5870 乱搞 Smooth Visualization
  7. R语言缺失值信息处理
  8. Mahout之Canopy Clustering深入理解
  9. [C# 基础知识系列]专题四：事件揭秘
  10. 绘图quartz之阴影
  11. uva 755 - 487--3279
  12. 【转】android TV CTS 4.0.3_r1测试
  13. Glide的加载图片的帮助类,用来把图片圆角或者改成圆形图片
  14. elasticsearch-5.0.0初见
  15. Galaxy (hdu 5073 数学)
  16. Unity 的几种打包姿势（android）
  17. 剑指Offer——笔试题+知识点总结
  18. （八）喜马拉雅Demo引出的细节（代理模式和图片缩放）
  19. 【SpringCloud】Zuul在何种情况下使用Hystrix
  20. vm Linux centos 链接外网

热门文章

  1. 【u034】追查坏奶牛
  2. 推荐：mysql锁　innodb下的记录锁，间隙锁，next-key锁
  3. Node.js入门-知识整理
  4. C#获取美团评价信息
  5. CentOS7.6部署k8s环境
  6. PyCharm永久破解方法
  7. 「洛谷P2397」 yyy loves Maths VI (mode) 解题报告
  8. kubelet--help-v1.15.4
  9. PHP 对接第三方 LINE 登录，网上找到相关的不多 但是网上哪些乱七八糟的啰啰嗦嗦 要么就是怎么做的， 什么步骤 总会给你省略， 如果有幸你看到我的 可以放心的复制即用， 当然 你也可以用postman去尝试 不过我觉得既然做开发 就没必要那个了！ 如果用postman再最后一步的时候 请用本文最下方式
  10. netcore 自动生成Dockerfile的坑