BOP2015(Qualification Round & Round 1)
JOI2015 OPEN

THUSC2012

__Shi posted @ Tue, 02 Jun 2015 18:31:56 +0800 in Other Contests with tags THUSC , 310 readers

马上就要出发了,熟悉了下大前年的题。THUSC在tsinsen公共题库里似乎只有2012年的是完整的。。。

TASK A 水位

按地表高度从小到大合并块,合并的时候顺便更新块的答案。需要高精度。写得太浪被卡常。。。

TASK B 社交网络结构洞

需要求[tex]\sum_{j,k} span_i(j,k)[/tex].

如果枚举i,再枚举j出发不经过i BFS,复杂度为[tex]O(m^2)[/tex],大概有50~80分。

可以枚举j,出发BFS出到每个点的两条经过的第一条边不同的路径,就可以算出所有的[tex]span(j,k)[/tex].

最后再统计答案即可。复杂度[tex]O(nm)[/tex].

TASK C 森林旅店

KD Tree模板题。可以离线建好整棵树,再处理操作。

卡常。。。算距离的时候sqrt最后再取就可以过了。

 

May29.

blog comments powered by Disqus