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