。。。经过 2周 的 Coding 。。。R3 昨天落幕。。
。。由于我最后一个版本的算法（。。贪心 后接 搜索。。。
。表现非常不佳。。。
于是最后退回到了倒数第二个版本。。。
（主函数二分套二分。。。
（框架是 构造 接 随机抛点。。 接 构造 再接构造。。。
（后面两个构造是在已得到的结果上进行调整优化。。。
（前面第一个构造是主函数。。。但是因为测试中部分数据得不到良好效果。。因此又接了一个 6s 的随机过程。。。。
最后一天只能算是勉强守住了 21th 。。。然后 wata 很神勇的交了一发超过了 Chokudai 。。。。然后认识的几个人里面。。。
xiaodao 21th
discover 33th
rejudge 48th
abcdxyzk 97th
预计 System Testing 后 Rank 不会发生太大变化。。。
说起来今年算是第一次正式做 Marathon 。。虽然去年就开始留意。。
。感觉这个类型的比赛其实也许很适合我 0w0。。。总之还是经验不足吧。。。。
。。。这样各大主流赛事的衣服就收集齐了。。。以后要争取 onsite 的名额了。。
Brief description:
给定一个 C 个蛋糕，G 个人。I 种口味的材料。。
每个人对每种口味的材料有一个偏好矩阵。。（1-10）。。。
这 I 种材料中前面一半是 Base 。。（面包。。
后面一半称为装饰物。。Decoration 。。。
每个蛋糕由若干种材料组成。。对于每种 Base 生成一个平均的高度均匀涂抹在蛋糕的每一片上（存在着 +-5 的噪音。。
。。然后对于装饰物。。选出一种作为 Rim （花边。。。
。。生成一个宽度均匀的涂抹在外围。。（存在着 +-5 的噪音。。。
。。。。然后其余的装饰物生成 Rose 。。。（具体生成的规则比较复杂。。反正是对称分布的。。。
总之基本依据现实中的蛋糕。。。
现在要你给每个人分一片蛋糕（换而言之。。只能是来自一个蛋糕的一个联通块
。。使得得分最少的那个人最大。。。
Analysis:
。。。对于这次的问题主要的收获是。。。在状态空解集巨大的时候。。。如何舍弃一些次要的问题。
。（比如再这题中。。。如果真的按题目中说的从联通块的角度入手可能只在 C=1 的情况下可行。。。
。。我现在觉得正确的做法。。应该是这样比较科学。。
。。。先大致枚举每个蛋糕可以服务多少人。。在枚举分哪些人。。
。。再枚举具体怎么分。。。。
External link:
。。。
http://community.topcoder.com/tco12/marathon-round-3-preliminary-results/
