攢了一個月的時間沒寫程序，換來一次集訓，時間還是很緊，回去后看我的手寫的總結吧。
晚自習遲到了15min，又晃掉了15min，第一題完全看出了算法，寫了1h，結果由于手生，紅了一大片（由于測試點太多看不出是多少分），第二題是輸出方案的最小環，以前沒寫過輸出方案，糾結了好久，花了78min，由于輸出順序與標準答案不同，結果10分。最后一題剩下10min，果斷搜索20分。。。。。。。。
好悲劇。
試題
省選班訓練試題一
花園（ gar ）
百特先生擁有百特鎮上最漂亮的花園。他在自己的花園里面種了n朵玫瑰花。夏天來了，所有的花都開的非常的漂亮。 百特先生開始意識到自己沒有能力看管自己花園里的所有的花，所以他決定雇傭兩個園丁來幫助他。他想在花園中選擇兩塊矩形的區域分別交給兩個園丁看管。而且這兩個矩形區域必須不能相交或者重疊，并且每一個區域要恰好包含k朵玫瑰花。
百特先生想要給這兩塊矩形區域的周圍安上柵欄，但是他現在手頭比較緊，所以他希望自己花的錢盡量的少。你的任務就是幫助百特先生選擇兩塊矩形的區域,使得它們在滿足條件的情況下周長和最小。
百特先生的花園有l米長，w米寬。花園被分成了l*w個大小相同(1*1)的方格。我們以平行于花園的兩邊建立起一個坐標系。所有的方格的坐標(x,y)滿足1<=x<=l,1<=y<=w.每個方格內可能會有任意數目的玫瑰。
所選的矩形區域的兩邊必須跟花園的兩邊平行，并且矩形區域的四個角的坐標必須是整數。對于1<=l1<=l2<=l 并且 1<=w1<=w2<=w,一個矩形區域的四個角為(l1,w1), (l1,w2), (l2,w1)和(l2,w2):
* 這個矩形內所包含的點的坐標(x,y)滿足 l1<=x<=l2 并且 w1<=y<=w2.
* 這個矩形的周長是 2•(l2-l1+1)+2•(w2-w1+1).
所選的兩塊矩形不能重疊或者相交。也就是它們不能有公共的方格。即使它們有公共的邊，計算周長的時候也要分別計算。
[輸 入]：
輸入文件有若干行，第一行有兩個整數l和w(1<=l,w<=250),用一個空格隔開，表示花園的長和寬。第二行包括兩個整數n和k(2<=n<=5000，1<=k<=n/2),用一個空格隔開，表示玫瑰花的總數和每個矩形中的玫瑰花數。下面n行是n朵玫瑰花的位置，第i+2行包括兩個整數li, wi (1<=li<=l, 1<=wi<=w),允許兩朵或更多玫瑰花長在同一位置。
[輸 出]：
輸出文件只有一行，一個整數，兩個矩形周長的最小值。在沒有合適的一對矩形存在時，輸出一個單詞NO。
[輸入輸出樣例]
gar.in ：
6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1
gar.out：
22
[數據規模]：對50%的數據，l,w<=40
參觀旅行(trip)
在Zanzibar島的Adelton鎮，有一旅行社。它決定提供給游客的有：除參觀許多的名勝外，還可參觀該城鎮。為了從這些名勝地賺取盡可能多的利潤，該旅行社做出了一個精明的決策：有必要找到一條開始并結束于同一地方的最短的旅行路線。你的任務就是編寫一個程序來找出這樣一條路線。
在鎮上，有N個交匯點，編號從1到N。有M條雙向的馬路，編號從1到M。兩個交匯點之間可能有多條馬路連接，但沒有一條馬路將某交匯點與其自身相連。每條參觀路線是一個馬路編號的序列：y_1,…y_k, k>2。馬路y_i(1<=I<=k-1)連接交匯點x_k和x_1。所有的編號x_1,…x_k必須不同。參觀路線的長度就是參觀路線上所經過馬路的長度之和，即L(y_1)+L(y_2)+…L(y_k),此處的L(y_i)表示馬路y_i(1<=i<=k)的長度。你的程序需要找到這樣一條路線，使其長度最小，或者若不存在這樣一條路線，便申明不存在。
輸入：在輸入文件TRIP.IN的首行包括兩個整數：交匯點的數目N(N<=100)和馬路的條數（M<=10000）,接下來的M行，每行描述一條馬路，它包括3個正整數：第一個交匯點的編號，第二個交匯點的編號和這條馬路的長度（一個小于500的正整數）。
輸出：
在輸出文件TRIP.OUT中僅有一行。若不存在這樣一條路線，顯示‘No solution’ )。若存在，便按順序顯示這條最短路線所經過的交匯點的編號。（即我們的參觀路線中所定義的編號x_1到x_k）,分別由空格隔開。如果有多條最短長度的路線，你可任選其中一條。
例子1；
TRIP.IN:
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
TRIP.OUT:(one of the correct answers)
1 3 5 2
例子2：
TRIP.IN:
4 3
1 2 10
1 3 20
1 4 30
TRIP.OUT:(the only correct answer)
No solution.
裝箱（binpack）
某工廠在一條裝配線的末尾有一個裝箱的機器人，恰有兩個箱子打開著。機器人將物品一件接一件地裝進任意一個打開的箱子內。箱子是完全相同的，一個箱子能在給定的重量范圍內容納多件物品。更確切地，機器人能完成以下四種命令：
1. 將當前的物品裝進箱子1。
2. 將當前的物品裝進箱子2。
3. 將箱子1關上并打開一個新的空箱來代替這個關上的箱子。
4. 將箱子2關上并打開一個新的空箱來代替這個關上的箱子。
一條裝箱的命令只有在下述條件下被執行：當前物品的重量加上箱中已有物品的重量之和不超過限度范圍。給出你一個物品重量的序列和對所有箱子適用的一個重量范圍，編寫一個程序計算出能將所有物品裝進箱子，所需的箱子最少數目。
輸入數據：
輸入文件由整形數據構成。輸入文件的第一行包含重量限度L（1≦L≦100），這個范圍對所有的箱子適用；第二行包含物品的數目N（1≦N≦5000）；以下的N行每行是一件物品的重量，每件重量在1至100之間。
輸出數據：
在第一行顯示能裝下所有物品所需箱子的最小數目。
輸入輸出示例：
BINPACK.IN：
8
6
4
2
5
3
5
4
BINPACK.OUT：
3
第一題AC代碼
#include<cstdio>
#include<cstring>
int const maxint=0x7FFFFFFF;
int p[251][251];//l,w ___ x,y
int sum[251][251];
int xsum[251][251];
int ysum[251][251];
int xu[251],xd[251],yu[251],yd[251];
int n,w,k,l;
int a,b;
int head,tail,now,t;
int ans=maxint;
int inline min(int a,int b)
{return a<b?a:b;}
void inline show(int x[251][251]){ for(int j=w;j>=1;j--){for(int i=1;i<=l;i++)printf("%d ",x[i][j]);printf("\n");}}
int inline srect(int x1,int y1,int x2,int y2){return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];}
int inline crect(int x1,int y1,int x2,int y2){return 2*(x2-x1+1)+2*(y2-y1+1);}
int main(){
freopen("gar.in","r",stdin);
freopen("gar.out","w",stdout);
memset(p,0,sizeof(p));
memset(sum,0,sizeof(sum));
memset(xsum,0,sizeof(xsum));
memset(ysum,0,sizeof(ysum));
scanf("%d %d",&l,&w);
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d %d",&a,&b);
p[a][b]++;
}
//
for(int i=1;i<=l;i++)
xu[i]=xd[i]=maxint;
for(int i=1;i<=w;i++)
yu[i]=yd[i]=maxint;
/**//*//sum
for(int i=1;i<=l;i++){
for(int j=1;j<=w;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+p[i][j];
}
//xsum
for(int i=1;i<=l;i++){
xsum[i][1]=p[i][1];
for(int j=2;j<=w;j++)
xsum[i][j]=xsum[i][j-1]+p[i][j];
} */
//ysum
for(int j=1;j<=w;j++){
ysum[1][j]=p[1][j];
for(int i=2;i<=l;i++)
ysum[i][j]=ysum[i-1][j]+p[i][j];
}
//
for(int i=1;i<=l;i++)
for(int j=i;j<=l;j++)
{
now=0;
for(int head=1,tail=0;head<=w;head++){
for(;now<k&&tail<=w;){
tail++;
now+=ysum[j][tail]-ysum[i-1][tail];
}
if(now==k){
t=crect(i,head,j,tail);
xu[i-1]=min(xu[i-1],t);
xd[j]=min(xd[j],t);
yd[tail]=min(yd[tail],t);
yu[head-1]=min(yu[head-1],t);
}
now-=ysum[j][head]-ysum[i-1][head];
}
/**//*now=ysum[j][1]-ysum[i-1][1];
head=tail=1;
for(;head<=tail&&tail<=w;){
if(now==k){
t=crect(i,head,j,tail);
xu[i-1]=min(xu[i-1],t);
xd[j]=min(xd[j],t);
yd[tail]=min(yd[tail],t);
yu[head-1]=min(yu[head-1],t);
}
if(now<=k){
tail++;
now+=ysum[j][tail]-ysum[i-1][tail];
}
else{
now-=ysum[j][head]-ysum[i-1][head];
head++;
}
}*/
}
//寫的時候思考了很多對于類似的不同問題的預處理方法 ，都/**/了，不過少了下面一段就WA了。
for(int i=2;i<=w-1;i++)
yd[i]=min(yd[i],yd[i-1]);
for(int i=2;i<=l-1;i++)
xd[i]=min(xd[i],xd[i-1]);
for(int i=w-2;i>=1;i--)
yu[i]=min(yu[i],yu[i+1]);
for(int i=l-2;i>=1;i--)
xu[i]=min(xu[i],xu[i+1]);
//
for(int i=1;i<=w-1;i++)
ans=min(ans,yu[i]+yd[i]);
for(int i=1;i<=l-1;i++)
ans=min(ans,xu[i]+xd[i]);
if(ans!=maxint)
printf("%d",maxint);
else
printf("NO");
//
fclose(stdin);
fclose(stdout);
return 0;
}
//1h