荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飛仙), 信区: ACMICPC
标 题: Contest #2题解
发信站: 荔园晨风BBS站 (Thu Mar 23 22:47:35 2006), 站内
Problem A: Pancakes
先把每种pancake的材料都算清楚，然后比较看有多少种不同材料的panckae。
要注意一下，题目存在没有材料的pancake。。
因为材料只有1-30种，所以可以用一个32bit整数来储存一个pancake有的材料。
例如某种材料的编号用a表示，如果pancake b里面包含材料a，那只需
b |= (1<<a);
就是把b的第a位置1，表示包含材料a；
Problem B: <Promise>
题目是说看一部比较恶心的电影《无极》的座位问题。。。
很简单，只是算出连续的.号然后减去人数就是那一片连接区域的解决办法，
对所有的连续区域做同样的处理就行了。
要注意下，input里的人数是没有包括Mr.K的。
Problem C: cityMap
这题简单到不知道怎样说。。。。略过。。。
Problem D: Counting Black
模拟题，小心点处理就是了。。。
Problem E: Roads
完全标准的一个最小生成树，不会的问你数据结构的老师。。。
Problem F: Reliable Nets
这题的边数比较少，最多才20个，所以可以穷举所有边的状态，就是用与不用。。
接下来就是一个判双连通图的东西了。。
双连通图就像题中所说的去掉任何一边后还是连通的。
判定的方法也不难，只要判一个顶点跟其他任何一个顶点都存在两条或以上的
路径相连就可以了。
--
我不敢去计较，
上天欠我的十辈子都算不清，
而我欠身边的人的要算千世万世。
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.14.236]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店