主题：第40次编程比赛结果
neverPE [专家分：1620] 发布于 2006-09-03 22:12:00
第1题 主要是集合查询和合并。合并的效率很重要，如果能想到并查集，那么做起来就不难，代码量也不大。本来第1题想出图论的，又怕控制不好难度，不过并查集跟树挂钩，也勉强算是图论吧。给出一段代码供参考：
int root(int v,int* set)
{
if (set[v] == v) return v;
return set[v]=root(set[v],set);
}
int ReligionsStd(int n,int m,int* record)
{
int i,count=n;
int* set=new int[n+1];
for (i=0;i<=n;i++) //初始化
set[i]=i;
for (i=0;i<m*2;i+=2)
if (root(record[i],set)!=root(record[i+1],set))//如果属于不同集合
{
set[set[record[i]]]=set[record[i+1]];//合并
count--;
}
delete[] set;
return count;
}
第1轮：
fstream fout ("filename");
n=50000;
m = [color=FF0000]t[/color] -1;
fout<<"1 2"<<endl;
for (i=3;i <= [color=FF0000]t[/color];i+=2)
fout<<i<<' '<<i+1<<endl<<i<<' '<<i-1<<endl;
测试数据由上面的代码生成，[color=FF0000]t[/color]=20,200,2000,20000,50000，这是针对性的数据，如果集合合并效率不高，用这组数据是很痛苦的。本来只是是想测试速度，但很多人的程序都出错了。正确结果依次是49981,49801,48001,30001,1。
1 jackin0627: >10s
2 天边蓝：错误
3 iAkiak： 47ms
5 liyanguestc： 错误
6 joekings：0ms
7 liangbch：错误
8 Cyre：错误
10 yelv：错误
11 joekings： 0ms
12 zheni： 7922ms
13 xiaopangzi：错误
14 wlsss： >10s
15 BigCarrot： <15ms
16 rickone： <15ms
17 孤独的猫：>10s
18 boxertony：Runtime Error
19 NingYusui：错误
20 xyhx：错误
21 eastcowboy：0ms
22 babyzn：错误
23 jfs771:错误
24 hwjian：错误
25 火海时代：错误
26 wshong：>10s
第2轮：
joekings和eastcowboy的程序快的出奇，但很遗憾算法不对。用一组简单的数据可以测出错误。
n=3 m=2
record={1 3 2 3}
第3轮：
12 zheni： >10s
3 iAkiak： 100ms
15 BigCarrot： 37ms
16 rickone： 68ms
多组数据测试，以上3位算法没有本质的差别，但BigCarrot实现的最快。iAkiak用模板在速度上可能有些吃亏。
第2题：第2题是简单博弈论题，实现起来很方便，大家做的正确率也很高。
2 boxertony:0ms
3 joekings:0ms
6 liyanguestc：0ms
7 BigCarrot：0ms
8 孤独的猫：0ms
9 wlsss：0ms
14 forjane：0ms
17 xyhx：0ms
5 ITER:错误
10 hainanlion：错误
11 hwjian： 错误（30位，longlong不够）
12 magicalking:错误 long更不够
13 liangbch：超时
综合以上2题的结果，第40次编程比赛的冠军是[color=FF0000]BigCarrot[/color]，恭喜他。
如果对测试结果有任何异议，请尽快跟帖，我会认真复查。
回复列表 （共44个回复）
21 楼
rickone [专家分：15390] 发布于 2006-09-03 22:38:00
嗯，2 boxertony，一开始我就是想的用图遍历，求有多少个生成树的算法，用DFS吧，50000次递归的上限也太大了，不敢做，用BFS还要开个队列的空间出来，试了一下花在空间上的时间比较多。
我对程序优化方面真的不太懂，哪些操作是比较耗时的，需要注意的？
22 楼
BigCarrot [专家分：10] 发布于 2006-09-03 23:04:00
[quote]To 14楼：你认为不会有3倍差距，是你自己的感觉，还是经过测试？
不要认为是函数调用带来的问题，我重复9楼说过的话，你看看我给的参考程序，频繁的函数调用，而且是递归，但并不比你的程序慢。[/quote]
只是感觉,没有测试,呵呵
我来总结一些这三种相似的实现吧
a)iAkiak & rickone, 每次查找一个节点的头节点时只调整那个被查节点的父指针
b)neverPE, 每次查找一个节点的头节点时调整查询过程中经过的所有节点的父指针
c)bigcarrot,每次查找一个节点的头节点的过程中经过的所有节点只向前走一步
看样子是这个差别导致了结果的差距
我当时在考虑这题时, 最大的难点在于我无法定量的分析方法a和方法b的时间复杂度,所以只能估计了. 我估计的结论是方法a的复杂度略大于O(m), 方法b的复杂度略大于O(m)且略小于方法a,但是略小于究竟是小多少? 时间复杂度上的提升是否能抵消额外的操作? 我都没有把握.
最终我得判断是时间复杂度的提高不是非常高,且不一定能抵消额外的操作. 但是我又不想放弃可能提高的机会. 所以就有了方法c, 相比a,额外操作非常少,只是多了两个赋值,又能带来更多的减少树的深度的机会.
看起来我得估计是错的, 现在我最想看到的是有人能给出方法a和方法b的准确的时间复杂度
23 楼
boxertony [专家分：23030] 发布于 2006-09-03 23:04:00
唉，我就是没有考虑到n＝50000，结果用DFS导致栈溢出。刚才改成BFS，用队列实现，结果倒是对了，但速度上只有neverPE给出的答案的约1/20。主要是用图实现辅助操作太多造成的。
24 楼
neverPE [专家分：1620] 发布于 2006-09-03 23:14:00
对并查集进行查询操作，时间复杂度是一个函数，这个函数是 Ackeman函数的反函数，由于Ackeman函数增长的速度之惊人，以至于可以把这个反函数看作是常数了O(1)。在一定范围内（10^100内），它可以看成不大于5的常数。
以上是结论，我不知道证明。
25 楼
rickone [专家分：15390] 发布于 2006-09-03 23:57:00
总结得好！
我当时想的是，一次查找只可能增加一层树的深度，然后调整一个比较深的查找的结点，以为控制能力还可以，又不知道再多花些时间‘整理’树的深度值不值，得出的经验是以后要是有这样的情况，自己多搞些数据测试一下，不要想当然拿主意。
26 楼
iAkiak [专家分：8460] 发布于 2006-09-04 07:41:00
@BigCarrot, 22
我每次调节都保证最大深度不超过1的。
27 楼
liangbch [专家分：1270] 发布于 2006-09-04 08:50:00
哈哈,第一题竟然完全错了,这个我始料不及.集合操作我从未接触过,看来我在算法方面有很多缺环,仍需继续努力.
28 楼
joekings [专家分：550] 发布于 2006-09-04 09:17:00
算法错了
29 楼
NingYusui [专家分：60] 发布于 2006-09-04 20:32:00
我将测试代码嵌入主程序中（vc2005)，有如下错误：
生成日志 重新生成 已启动: 项目: zongjiao，配置: Debug|Win32
命令行 正在创建临时文件“d:\02033111\vc\zongjiao\zongjiao\Debug\RSP00003D12601032.rsp”，其内容为
[
/Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Gm /EHsc /RTC1 /MDd /Yu"stdafx.h" /Fp"Debug\zongjiao.pch" /Fo"Debug\\" /Fd"Debug\vc80.pdb" /W3 /c /Wp64 /ZI /TP .\Religions.cpp
.\zongjiao.cpp
]
正在创建命令行“cl.exe @d:\02033111\vc\zongjiao\zongjiao\Debug\RSP00003D12601032.rsp /nologo /errorReport:prompt”
正在创建临时文件“d:\02033111\vc\zongjiao\zongjiao\Debug\RSP00003E12601032.rsp”，其内容为
[
/Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Gm /EHsc /RTC1 /MDd /Yc"stdafx.h" /Fp"Debug\zongjiao.pch" /Fo"Debug\\" /Fd"Debug\vc80.pdb" /W3 /c /Wp64 /ZI /TP .\stdafx.cpp
]
正在创建命令行“cl.exe @d:\02033111\vc\zongjiao\zongjiao\Debug\RSP00003E12601032.rsp /nologo /errorReport:prompt”
输出窗口 正在编译...
stdafx.cpp
正在编译...
zongjiao.cpp
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(18) : error C2079: “fout”使用未定义的 class“std::basic_fstream<_Elem,_Traits>”
with
[
_Elem=char,
_Traits=std::char_traits
]
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(18) : error C2440: “初始化”: 无法从“const char [9]”转换为“int”
没有使该转换得以执行的上下文
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(21) : error C2297: “<<”: 非法，右操作数包含“const char [4]”类型
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(21) : error C2563: 在形参表中不匹配
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(21) : error C2568: “<<”: 无法解析函数重载
e:\microsoft visual studio 8\vc\include\ostream(971): 可能是“std::basic_ostream<_Elem,_Traits> &std::endl(std::basic_ostream<_Elem,_Traits> &)”
with
[
_Elem=wchar_t,
_Traits=std::char_traits
]
e:\microsoft visual studio 8\vc\include\ostream(963): 或“std::basic_ostream<_Elem,_Traits> &std::endl(std::basic_ostream<_Elem,_Traits> &)”
with
[
_Elem=char,
_Traits=std::char_traits
]
e:\microsoft visual studio 8\vc\include\ostream(937): 或“std::basic_ostream<_Elem,_Traits> &std::endl(std::basic_ostream<_Elem,_Traits> &)”
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(24) : warning C4293: “<<”: Shift 计数为负或过大，其行为未定义
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(24) : warning C4554: “<<”: 检查运算符优先级可能存在的错误；使用圆括号阐明优先级
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(24) : error C2563: 在形参表中不匹配
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(24) : error C2568: “<<”: 无法解析函数重载
e:\microsoft visual studio 8\vc\include\ostream(971): 可能是“std::basic_ostream<_Elem,_Traits> &std::endl(std::basic_ostream<_Elem,_Traits> &)”
with
[
_Elem=wchar_t,
_Traits=std::char_traits
]
e:\microsoft visual studio 8\vc\include\ostream(963): 或“std::basic_ostream<_Elem,_Traits> &std::endl(std::basic_ostream<_Elem,_Traits> &)”
with
[
_Elem=char,
_Traits=std::char_traits
]
e:\microsoft visual studio 8\vc\include\ostream(937): 或“std::basic_ostream<_Elem,_Traits> &std::endl(std::basic_ostream<_Elem,_Traits> &)”
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(25) : warning C4293: “<<”: Shift 计数为负或过大，其行为未定义
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(25) : warning C4554: “<<”: 检查运算符优先级可能存在的错误；使用圆括号阐明优先级
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(25) : error C2563: 在形参表中不匹配
d:\02033111\vc\zongjiao\zongjiao\zongjiao.cpp(25) : error C2568: “<<”: 无法解析函数重载
e:\microsoft visual studio 8\vc\include\ostream(971): 可能是“std::basic_ostream<_Elem,_Traits> &std::endl(std::basic_ostream<_Elem,_Traits> &)”
with
[
_Elem=wchar_t,
_Traits=std::char_traits
]
e:\microsoft visual studio 8\vc\include\ostream(963): 或“std::basic_ostream<_Elem,_Traits> &std::endl(std::basic_ostream<_Elem,_Traits> &)”
with
[
_Elem=char,
_Traits=std::char_traits
]
e:\microsoft visual studio 8\vc\include\ostream(937): 或“std::basic_ostream<_Elem,_Traits> &std::endl(std::basic_ostream<_Elem,_Traits> &)”
Religions.cpp
正在生成代码...
结果 生成日志保存在“file://d:\02033111\vc\zongjiao\zongjiao\Debug\BuildLog.htm”
zongjiao - 9 个错误，4 个警告
请诸位告诉我怎么回事 ？
30 楼
NingYusui [专家分：60] 发布于 2006-09-04 21:31:00
楼主，我错了，真的错了，我后悔啊！！！！！！！
我来回复
您所在位置：