COCI 2010-7题解

哎。。我真是太菜了。。
30,50:忽略啦。。
70:这道题直接按距离从小到大处理每一对L和X的关系,关键是因为题目中有一个信息所没有两个L跟一个X一样近,所以实际上X和L的数量不会非常多的,这样子是不会TLE的囧。。我在写的时候是照曼哈顿距离写的。。居然会有49分。。天哪囧。。。
100:根据最小生成树的计算可以把一个环上的最大边忽略掉,可以发现除了分别按X,Y,Z排序的相邻点之间的边之外的边,都可以忽略掉囧。。所以之后之间用Kruskal就OK了。。
120:注意到两点之间的距离就是X,Y轴差的最大值。。注意到|A+B|+|A-B|=Max(A,B)*2,所以将每个点的坐标由(x,y)->(x+y,x-y)。。那么题目中定义的距离就变成曼哈顿距离了。。曼哈顿距离就好算了(*^__^*) 嘻嘻……。。。这样的变换好像在IOI中出现过。。哎。。。悲剧。。
130:晕。。这不就是SGU的原题么。。当时我SB了囧。。首先由1度点之间判不行。。否则不断找欧拉回路。。对这个回路用间隔染色来染色。。特判一下整个图为奇环的情况就OK了。。

6 thoughts on “COCI 2010-7题解

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>