注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

祝灾区人民早日度过难关

努力工作

 
 
 

日志

 
 

做到吐血的Friendship  

2007-04-08 23:56:49|  分类: 真我风采 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    ACM预赛1006题,从晚上9点到凌晨4点,除去中间休息的时间,估计花去了我4个小时的时间。不写不行,我要被它搞崩溃了!
    题目如下:
Friendship
Time limit: 3 Seconds   Memory limit: 32768K  
Total Submit: 82   Accepted Submit: 21  
A friend is like a flower,
a rose to be exact,
Or maybe like a brand new gate
that never comes unlatched.

A friend is like an owl,
both beautiful and wise.
Or perhaps a friend is like a ghost,
whose spirit never dies.

A friend is like a heart that goes
strong until the end.
Where would we be in this world
if we didn't have a friend?

                       - By Emma Guest

Now you've grown up, it's time to make friends. The friends you make in university are the friends you make for life. You will be proud if you have many friends.

Input

There are multiple test cases for this problem.

Each test case starts with a line containing two integers N, M (1 <= N <= 100'000, 1 <= M <= 200'000), representing that there are totally N persons (indexed from 1 to N) and M operations, then M lines with the form "M a b" (without quotation) or "Q a" (without quotation) follow. The operation "M a b" means that person a and b make friends with each other, though they may be already friends, while "Q a" means a query operation.

Friendship is transitivity, which means if a and b, b and c are friends then a and c are also friends. In the initial, you have no friends unless yourself, when you are freshman, you know nobody, right? So in such case you have only one friend.

Output

For each test case, output "Case #:" first where "#" is the number of the case which starts from 1, then for each query operation "Q a", output a single line with the number of person a's friends.

Separate two consecutive test cases with a blank line, but Do NOT output an extra blank line after the last one.

Sample Input

3 5
M 1 2
Q 1
Q 3
M 2 3
Q 2
5 10
M 3 2
Q 4
M 1 2
Q 4
M 3 2
Q 1
M 3 1
Q 5
M 4 2
Q 4

Sample Output

Case 1:
2
1
3

Case 2:
1
1
3
1
4

Notes

This problem has huge input and output data, please use 'scanf()' and 'printf()' instead of 'cin' and 'cout' to avoid time limit exceed.

    其实题目并不难,甚至没有用到DP!我的第一反应是用stl的set容器做。其实set的效率并不高,因为查找要用logN(在我看来已经很快了),合并集合又是logN.由于之前曾经做过类似的题目并且AC了,我毫不犹豫地用set。结果先是WA,然后是运行超时。当时smamonkey就提出应该有更好的算法,但是我一直为过去的成功所迷惑,认为稍作优化就行。我减少不必要的memset,用引用传递代替值拷贝,可是,毫无用处。很快,比赛时间就过了。
    赛后,6题中做出5题的小胖说要用并差集,令我茅塞顿开。我从《数据结构与算法》中抄了并差集的相关代码。结果,输入一直不对,调了半天没调出来。最后把小胖请来,发现是用scanf("%c",&c)时,c声明成了int。
    终于,sample过了,提交,segment fault.这令我很诧异。找了半天的数组下标越界,没找到bug。后来得flaresky的提醒,由于递归导致堆栈溢出,从而导致段错误。
于是我打算重写Find()函数。灾难从此开始。
    一开始,我这样写:
SetType Find(ElementType X,DisjSet S)
{
    for(;;)
    {
        SetType parent = S[X];
        if(parent <= 0)
        {
            return X;
            break;
        }        
        S[X] = S[parent];
        X=parent;
    }
}
这里面有一个逻辑错误:首先,指向父结节时,当parent为根节点时,子结节就不应该动。
所以应该这样写:
SetType Find(ElementType X,DisjSet S)
{
    for(;;)
    {
        SetType parent = S[X];
        if(parent <= 0)
        {
            return X;
            break;
        }    
        if(S[parent]>0)    
            S[X] = S[parent];
    }
}
其次,并差集的路径压缩是让子节点直接指向根节点。而不是父节点。
所以要用两个循环,第一个循环找出根节点。第二个循环更新子节点。
SetType Find(ElementType X,DisjSet S)
{
    SetType root,p = X;
    for(;;)
    {
        SetType parent = S[p];
        SetType root;
        if(parent <= 0)
        {
            root = p;
            break;
        }    
        //if(S[parent]>0)    
        //    S[X] = S[parent];
        X=parent;
    }
    p=X;
    for(;;)
    {
        SetType parent = S[p];
        if(parent <= 0)
        {
            break;
        }
        S[p] = root;
        p = parent;
    }
}
期间又犯了几个低级错误,其实这些错误都可以从源代码的逻辑上看出来。结果用测试数据测了半天才测出来。
终于,sample再次通过,提交,WA
这令我很无语。继续进行捉虫之旅。
打印了一堆信息,最后发现,
SetUnion()这个函数有问题。
我原来是抄书的,结果书里面的参数含义和我的用法不一样。
void SetUnion(DisjSet S,SetType Root1,SetType Root2)书上的用法里,第二个和第三个参数是并差集的根节点。
void SetUnion(DisjSet S,SetType child,SetType main)我的用法,第二个和第三个参数成为普通结节。
继续改。
OK,提交,仍然WA
我很郁闷。
自己又编了一个测试数据,果然有问题,原来SetUnion没改全。
提交,终于AC,0.86秒。好险。

经验总结:
1.C的输入输入没有类型检查,类型一定要小心。C里scanf会把'\n'之类的也读进来,和cin cout不太一样。要加强输入输出的练习。
2.代码写好后要多看几遍,很多错误是逻辑错误,不需要通过运行就能找出来。
3.代码的风格很重要,最好能做到自注释,即,清晰的变量名,清晰的函数结构,不需要注释也能看懂,这有助于发现程序的逻辑错误。

  评论这张
 
阅读(141)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018