信息學(xué)集訓(xùn)隊作業(yè)northeastern europe2005,far-eastern subregion

1、Northeastern Europe 2005, Far-Eastern Subregion題目編號題目名稱題目大意算法概要心得體會3430 HYPERLINK /JudgeOnline/problem?id=3430 Pizza schedule給定一年內(nèi)某些天的Pizza訂單，要求一個最匹配的周期訂單。給定時間范圍內(nèi)未被涉及的日子里沒有訂單。周期訂單是以14星期為周期的通用訂單。周期訂單的第一個星期對應(yīng)給定日期范圍的第一個星期。最匹配的定義是不匹配的天數(shù)最少。如果不在給定日期范圍內(nèi)的日期訂單不考慮。模擬，枚舉周期訂單的周期數(shù)，找出每個對應(yīng)天的眾數(shù)。注意題目中提及的各種條件例如不在給定日期

2、范圍內(nèi)的日期訂單不考慮而不是訂單為0，周期訂單的第一個星期對應(yīng)給定日期范圍的第一個星期而不是一年的第一個星期對應(yīng)周期訂單的第一個星期。很艱難地看懂題目，很輕松地實現(xiàn)程序，很小心地調(diào)試到AC。3431 HYPERLINK /JudgeOnline/problem?id=3431 Texture Tile給一個n*n的像素矩陣，要求找一個最大的正方形，滿足正方形的第一行與最后一行相同，第一列與最后一列相同。N=370枚舉答案，然后從左到右，從上到下枚舉正方形的左上角，枚舉的過程中可以常數(shù)時間計算當(dāng)前格子與最后一行的相應(yīng)格子向右可以匹配多少格，當(dāng)前格子與最后一列的相應(yīng)格子向下可以匹配多少格。然后判斷

3、是否滿足枚舉的答案即可。復(fù)雜度O(n3)很危險的復(fù)雜度，常數(shù)處理不當(dāng)極其容易tle。3432 HYPERLINK /JudgeOnline/problem?id=3432 Count Squares給定平面上n個點的坐標(biāo)，求能有多少組的四個點是一個正方形的四個頂點。N=2000枚舉。首先將所有點用hash存儲。枚舉一條邊的兩個點，并計算，若他們都在一個正方形頂點上，那么剩余兩個點的坐標(biāo)（2組），用hash判斷剩余兩個點是否存在。注意這種方法下，每個正方形會被選中4次。比較平常的題目，一些計算幾何的技巧可以讓程序顯得短小而優(yōu)美。3433 HYPERLINK /JudgeOnline/proble

4、m?id=3433 Road Accident3434 HYPERLINK /JudgeOnline/problem?id=3434 Terrarium某個生態(tài)系統(tǒng)用一個n*n的矩陣描述。里面放置著若干條蛇（用字母az描述）。每回和所有的蛇按照字典順序開始移動。每條蛇會探查當(dāng)前所朝向方向是否有障礙物（原先的障礙物或者某條蛇身體的一部分），若沒有則向前移動一步，若有則先向右，再向左重復(fù)探查。如果三個方向都無法移動則這個回合停留。模擬計算出T回合后這個生態(tài)系統(tǒng)的情況。2 N 1000,1 T 106.模擬。因為要模擬的回合數(shù)很多，而蛇身子最壞可能很長，所以用鏈表保存蛇身子的坐標(biāo)，這樣每次移動的模擬

5、可以在常數(shù)時間內(nèi)完成。然后直接按照題設(shè)模擬即可。一個小優(yōu)化是如果某個回合所有蛇沒有移動，那么之后所有的回合所有的蛇依然不會移動，所以可以直接跳出。比較麻煩的題目，同樣考驗常數(shù)。3435 HYPERLINK /JudgeOnline/problem?id=3435 Sudoku Checker給定一個N2*N2的數(shù)獨的未完成情況，判斷當(dāng)前狀態(tài)是否已經(jīng)產(chǎn)生了矛盾。直接按題設(shè)條件判斷即可。題目很容易讓人誤解成檢查當(dāng)前未完成數(shù)獨是否最終有解而陷入復(fù)雜的思考，實際上確實一道比較簡單的模擬題?？炊}目是AC此題的充分條件。3436 HYPERLINK /JudgeOnline/problem?id=3436 ACM Computer Factory一臺電腦包括P個部分，現(xiàn)在有n個生產(chǎn)設(shè)備。每個設(shè)備能將某種狀態(tài)的電腦（每個部分用0（該部分必須不存在）1（該部分必須存在）2（該部分存在與否無所謂）表示）加工成某個結(jié)束狀態(tài)（每個部分用0（該部分不存在）1（該部分存在）每個設(shè)備有個加工上限Qi。問最多能加工出多少臺完整的電腦（所有部分存在）1 P 10 1 N 501 Qi 10000網(wǎng)絡(luò)流。最大流模型，構(gòu)圖如下：每個設(shè)備的起止?fàn)顟B(tài)分別作為一個結(jié)點。起始狀態(tài)向目標(biāo)狀態(tài)連邊，容量為加工上限。設(shè)置源點，向每個起止?fàn)顟B(tài)可以匹配空白電腦的狀態(tài)連邊，容量為正無窮。設(shè)置匯點，每個終止?fàn)顟B(tài)為完整電腦的向匯點連邊