攒了一个月的时间没写程序，换来一次集训，时间还是很紧，回去后看我的手写的总结吧。
晚自习迟到了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