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