P1892 有关测试点#11的奇怪特性
查看原帖
P1892 有关测试点#11的奇怪特性
741528
WHYHW2297楼主2025/6/25 09:37

提交记录:P221354442P221354460
代码区别:
前者:

if(opt=='E') {
    relation[findroot(q+1000)]=findroot(p);
    relation[findroot(p+1000)]=findroot(q);
}
else{
    relation[findroot(p)]=findroot(q);
}

后者:

pp=findroot(p),pq=findroot(q),np=findroot(p+1000),nq=findroot(q+1000);
if(opt=='E') {
    relation[nq]=pp;
    relation[np]=pq;
}
else{
    relation[pp]=pq;
}

relation数组用于存储所在集合,findroot()函数用于寻找该集合的“根”并进行路径压缩。
下载测试点后发现在#11上,后者代码的relation数组在57号位上会存储57而非前者的408,导致结果比正解高1。
尝试过不进行路径压缩的写法但结果未受影响。
不清楚具体为什么。个人认为两种写法的本质相同,但实际导致了不一样的结果。
希望能有大佬解答。

2025/6/25 09:37
加载中...