dango

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

[hdu3234] Exclusive-OR

(从自己的CSDN博客转来的)

一、题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=3234

存在n个正数。题目逐渐给出信息或询问。

如果中途出现冲突,输出有冲突,其余语句全部忽略。

详见原题。

二、准备知识

对于a,b,c有:a xor b == c 和 a xor c == b 和 b xor c == a 等价

三、题目分析

    首先可以想到这是比较经典的并查集模型,不过并不是赤裸裸的,有一些细节需要考虑。

    利用带路径压缩的并查集模型,同时记录节点到其父节点的xor值。

    father[i]记录父节点,offxor[i]记录节点到父节点的xor值, value[i]记录数值大小

    一些细节,很多细节可以通过画图看出,一图胜千言:

    1、在处理I p v或者I p q v时,set_value的时候处理根节点的value。因为之后很多东西都要用到根的value值,或是判断根节点的value是否存在。

    2、处理Q,即处理询问时。记录p1 p2 ... pk的根和每个根出现的次数。如果出现的次数是奇数次,那么就需要用到根的value了。这样也可以判断是不是I don't know.

四、源代码

 

hdu3234


五、心得

1、memset(value, 255, sizeof (int) * N); 可以利用255将数组初始化为-1,以后不用写for初始化为-1了

2、"#include <sstream>" + "gets(in_str);" + "int t = sscanf(in_str, "%d%d%d", &p, &q, &v);"

    可以很好处理这道题之类I类型不知道后面要读几个数字的问题。先把字符串读进来,然后用sscanf从字符串中读取数字,利用其返回值就知道读到几个数字了。sscanf还有其他很多功能,抛砖引玉,以后再有需要就多了一个可以寻找的方向了。

3、又PE了一次,以后一定要看清楚每组数据之间是否要输出空行,不管Sample Output里头有没有。

posted on 2010-08-26 20:46 Dango 阅读(529) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理