試題、程序及解題報(bào)告省選noi day

1、NOI2004 Day2講題大會(huì)降雨量rainfall數(shù)據(jù)范圍很小，算法也不難想到考察的重點(diǎn)不是算法，而是選手的編程基本功坐標(biāo)系tx事件點(diǎn)t0t1t2tr-1trtx計(jì)算每一段的陰影面積t1t2tx其它算法以一個(gè)很小的值d作為時(shí)間步長(zhǎng)得到的時(shí)刻，即T0=0，Tr=T，Ti+1-Ti=d（i=1,2,r）預(yù)計(jì)得分 20分 小H的小屋hut基礎(chǔ)題動(dòng)態(tài)規(guī)劃畢業(yè)生graduate不易把握、開(kāi)放、靈活寫(xiě)程序、手算或是二者結(jié)合checker程序被設(shè)計(jì)成具有豐富信息，靈活運(yùn)用checker可以提高解題效率。估算邊界編程對(duì)各個(gè)數(shù)據(jù)進(jìn)行必要的統(tǒng)計(jì)工作玩具面積的分布閉包面積分布所有玩具的總面積人眼對(duì)各個(gè)數(shù)據(jù)進(jìn)行必

2、要的統(tǒng)計(jì)工作是否為規(guī)則圖形輪廓是否光滑實(shí)心還是空心由此可以初步估算出一個(gè)比較理想的邊界核心算法按照面積從大到小，把各個(gè)基塊進(jìn)行排序。按照從左到右從上到下的順序，嘗試各個(gè)位置能否放入，在每個(gè)位置上試驗(yàn)四種旋轉(zhuǎn)方案。調(diào)整邊界如果所有基塊都被成功放在設(shè)定的邊界里，則找到了一組解。如果找不到解，需要把邊界稍微擴(kuò)大點(diǎn)。graduate1graduate2graduate3graduate4第一塊的縱橫跨度達(dá)到了7*36，這是解的下界。猜想其他玩具都可以插到縫隙里：第二塊的跨度很大，所以應(yīng)先把它嵌入。第四塊也只有一種放置方法。第五塊貼近第四塊幾乎不會(huì)造成什么浪費(fèi)，暫時(shí)把它也固定下來(lái)。graduate5第一

3、塊的縱橫跨度達(dá)到了18*121，這是解的下界。猜想其他玩具都可以插到縫隙里：第4塊非?！膀暄亚邸?，它只有一種放置方法。第5、6塊吻合得相當(dāng)好，而且合并以后恰好能放在第7塊里。第2塊可以裝在第10塊里。數(shù)據(jù)生成器隨機(jī)選擇k個(gè)格子，作為每個(gè)基塊的生長(zhǎng)格每次根據(jù)grow_factor隨機(jī)選擇一個(gè)基塊，作為擴(kuò)展對(duì)象。把與該基塊相鄰的且不屬于任何基塊的格子叫做可擴(kuò)展格，為每個(gè)可擴(kuò)展格加權(quán)，從權(quán)最大的幾個(gè)中隨機(jī)選擇一個(gè)，把它加入該基塊中。graduate6規(guī)模為80*20基塊數(shù)目等于4grow_factor均為1占滿所有區(qū)域graduate7規(guī)模為100*100基塊數(shù)目50grow_factor均為1占滿所有區(qū)域。 graduate8規(guī)模為100*100基塊數(shù)目5000grow_factor均為1占滿所有區(qū)域。 graduate9規(guī)模為100*100基塊數(shù)目5000