信息学集训队作业corn

1、蜂窝玉米的解题报告【题目大意】给定一棵树，要求对每个结点给出一对坐标(xi,yi)满足0=xi=M，0= yi=M，且都是整数。图中的边不得相连，除非它们在树中就是邻边，图中点不得重叠。得分的多少取决于M的大小（M越小分数越高）。【算法分析】这里介绍解决本题的两种思路。首先，由于这棵树必须边不得交叉，容易想到边通常应该比较短，否则长边多了容易绞在一起形成交叉。对于其他的问题，比如如何放置每一条边，很难找到一个十全十美的方法。于是，我们可以用随机化算法解决本题。算法的基本思路是，预先设定一个期望的M，每一次随机找一个起点，然后以这个结点为根遍历整棵树。在遍历的同时，我们为所走过的每一个点确定坐标

2、，我们尽量让每个结点靠近它的父亲结点，并且保持边不交叉的性质。当然，有的时候我们会发现这个性质无法保持下去了，那么本次试探宣告失败。否则，我们就找到了一个可行解，算法终止。我们发现这个算法在应对较小数据的时候得心应手，当然，手算也同样得心应手，而在对付稍大的数据时效果就要变差很多，因为整个算法难以出解。这里给出一些优化：假如一些启发函数来控制这棵树的“生长”过程。对于有一定特点（如第5组）的数据，可以进行特殊的调整（如确定起点位置，改变生长方式等）。最后，随机化的程序在前6组数据的运行效果还是不错的，都能控制在25以下， 第4组数据的效果超过了标准答案(11)，只有10。但是无论怎么优化，想用

3、本算法得到后4组数据的解都是很困难的。对于大数据，这里有第二种算法：动态规划！我们关注的，首先是要求出解，其次才是解的好坏。这里的“动态规划”并不是求最优解的动态规划，而仅仅求出一个近似解。它的基本思路是，把这棵树的每一个子树放在一个矩形里。那么，我们通过讨论某些特殊的摆放方法，就可以进行树状的动态规划。比如说我采用的方法：用f(a,b)表示以f 为根的子树放进宽度为b的矩形，长度最小是多少。这里的“最小”当然是在我们讨论的范围内的“最小”了。图中红色圆形表示当前考虑的子树的根结点，白色圆形表示当前考虑的子树的根结点的儿子，那么我们通过进行动态规划，就可以求出这种摆法下的最优解了。当然，由我们

4、的这种方法，有的时候会出现f(a,b) b的情况，这样，我们对这种情况可以通过加入一个“空列”和“翻转”整个图形来优化。这样做，看上去增加了很多空白，但是实际效果却很好。第10组测试数据加入这两个优化以前，结果是一百九十几，加入以后就立刻降到了七十几。由于这样的摆法一定不会交叉，所以它可以轻松地得到一组可行解。事实上，在大数据时，动态规划可以得到相当好的解。这也就是标准答案的后几组数据所使用的解法了。另外，这里还提一下，有一个很有意思的思路。如右图所示，我们选择一个根结点，从根结点深度遍历这棵树，每一个结点的横坐标就是该点的深度，纵坐标就是该点在该层结点中第几个被访问。也可以想象成，这棵树的树

5、枝“贴”着格子的上边缘生长。容易证明，这种构造是可行的。程序很短，而可以得的分数却不算太低。我曾经试图优化该算法，分别采用增加随机的“背叛”（即部分枝条向左生长）和对于某些需要的结点，把它的最后一个儿子向下而不是向右生长。两种算法的效果都还不错，但是并不能令人很满意。这种算法的问题在于，它的结果为max(树的最大宽度，树的深度)。但是对于大数据，树的最大宽度很容易达到一百多甚至更多。怎么办？一个也许可以的方法是，在这个算法中揉入前两种算法的一些思想，即，我们找一个根结点，然后每一次深度增加1，即相当于一次广度优先搜索，我们在这个结点周围“裹” 一圈结点，并使包含这些结点的最小正方形尽量小。然后

6、再“裹”一圈。容易证明，假如不限制边长，这种算法是一定有解的。我们再加入一定随机化的成分，然后多次运行，可以想象，效果应该不错。但是由于时间问题，我没有写这个算法的程序。如果谁有兴趣的话可以试验一下。这里给出几种算法的运行情况表（其中动态规划算法的程序写得比较简单，因此效果不是很好）算法数据12345678910手工计算249N/AN/AN/AN/AN/AN/AN/A随机化249102021N/AN/AN/AN/A简单的构造3861551313512239139199简单的构造+随机化25311166187731122164简单的构造+向下生长256055130238741120173动态规划

7、37613713129109296276附原题：【问题描述】“蜂窝玉米”是一道湖南名菜，也是岳岳和佳佳的最爱。既然名叫“蜂窝玉米”，这道菜自然由很多颗玉米粒组成，两颗玉米粒之间可以用一根可食用的线连接。他们观察发现，如果把玉米粒看作点，把线看成边的话，每盘“蜂窝玉米”恰好构成一棵树。他们还发现，饭馆用来装“蜂窝玉米”的盘子一般是正方形的，如果适当地建立平面直角坐标系，玉米粒均放在整点（横坐标和纵坐标都是整数的点）上，连接玉米粒的线都被拉直且不相交。回家后不久就要过年了，岳岳和佳佳想为朋友们表演一下自己的厨艺做一盆色香味俱全的“蜂窝玉米”。但是问题来了，要一个多大的正方形盘子才能够装下这道菜呢？

8、【输入格式】输入文件corn*.in第一行为玉米粒的颗数n，以下n-1行每行包含两个整数u和v，表示玉米粒u和v连有一条线。【输出格式】输出文件corn*.out包含n行，依次表示玉米粒1,2,3.n的坐标，用两个非负整数x, y表示。按照题意，正方形盘子的边长就等于。【样例输入】41 22 32 4【样例输出】0 10 01 01 1【评分方法】对于每个测试点，如果你的输出非法，得0分，否则至少得1分，具体计算公式如下：假设参考解的边长为Best，你的边长为Ans，则你的得分为：10，如果Ans Best，如果Ans Best，其中为取下整操作。【如何测试你的输出】你可以使用checker程序检查你的输出，格式为：checker TestNo其中TestN