详解讲题大会day22.pptxVIP

NOI2004Day2讲题大会

降雨量——rainfall数据范围很小，算法也不难想到考察的重点不是算法，而是选手的编程基本功

坐标系tx

事件点t0t1t2tr-1trtx

计算每一段的阴影面积t1t2tx

其它算法以一个很小的值d作为时间步长得到的时刻，即T0=0，Tr=T，Ti+1-Ti=d（i=1,2,…,r）预计得分20分

小H的小屋——hut基础题动态规划

毕业生——graduate不易把握、开放、灵活写程序、手算或是二者结合checker程序被设计成具有丰富信息，灵活运用checker可以提高解题效率。

估算边界编程对各个数据进行必要的统计工作玩具面积的分布闭包面积分布所有玩具的总面积人眼对各个数据进行必要的统计工作是否为规则图形轮廓是否光滑实心还是空心由此可以初步估算出一个比较理想的边界

核心算法按照面积从大到小，把各个基块进行排序。按照从左到右从上到下的顺序，尝试各个位置能否放入，在每个位置上试验四种旋转方案。

调整边界如果所有基块都被成功放在设定的边界里，则找到了一组解。如果找不到解，需要把边界稍微扩大点。

graduate1

graduate2

graduate3

graduate4第一块的纵横跨度达到了7*36，这是解的下界。猜想其他玩具都可以插到缝隙里：第二块的跨度很大，所以应先把它嵌入。第四块也只有一种放置方法。第五块贴近第四块几乎不会造成什么浪费，暂时把它也固定下来。

graduate5第一块的纵横跨度达到了18*121，这是解的下界。猜想其他玩具都可以插到缝隙里：第4块非常“蜿蜒曲折”，它只有一种放置方法。第5、6块吻合得相当好，而且合并以后恰好能放在第7块里。第2块可以装在第10块里。

数据生成器随机选择k个格子，作为每个基块的生长格每次根据grow_factor随机选择一个基块，作为扩展对象。把与该基块相邻的且不属于任何基块的格子叫做可扩展格，为每个可扩展格加权，从权最大的几个中随机选择一个，把它加入该基块中。

graduate6规模为80*20基块数目等于4grow_factor均为1占满所有区域

graduate7规模为100*100基块数目50grow_factor均为1占满所有区域。

graduate8规模为100*100基块数目5000grow_factor均为1占满所有区域。

graduate9规模为100*100基块数目5000growfactor除了中间一个为1外其余为0占满所有区域。

graduate101200*1200