题解.docx
《题解.docx》由会员分享，可在线阅读，更多相关《题解.docx（36页珍藏版）》请在冰点文库上搜索。
题解
第十七届全国青少年信息学奥林匹克联赛复赛试题
（NOIP2011提高组）
Day1
铺地毯
【问题描述】
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。
一共有n张地毯，编号从1到n。
现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。
注意：
在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
【输入】
输入文件名为carpet.in。
输入共n+2行。
第一行，一个整数n，表示总共有n张地毯。
接下来的n行中，第i+1行表示编号i的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y轴方向的长度。
第n+2行包含两个正整数x和y，表示所求的地面的点的坐标（x，y）。
【输出】
输出文件名为carpet.out。
输出共1行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
【输入输出样例1】
carpet.in
carpet.out
3
1023
0233
2133
22
3
【输入输出样例说明】
如下图，1号地毯用实线表示，2号地毯用虚线表示，3号用双实线表示，覆盖点（2，2）的最上面一张地毯是3号地毯。
【输入输出样例2】
carpet.in
carpet.out
3
1023
0233
2133
45
-1
【输入输出样例说明】
如上图，1号地毯用实线表示，2号地毯用虚线表示，3号用双实线表示，点（4，5）没有被地毯覆盖，所以输出-1。
【数据范围】
对于30%的数据，有n≤2；
对于50%的数据，0≤a,b,g,k≤100；
对于100%的数据，有0≤n≤10,000，0≤a,b,g,k≤100,000。
【一句话题意】
给定n个按顺序覆盖的矩形，求某个点最上方的矩形编号。
【考察知识点】
枚举
【思路】置答案ans=-1，按顺序枚举所有矩形，如果点在矩形内则更新ans。
注意题中给出的不是对角坐标，实际上是（a,b）与（a+g,b+k）。
还有一种办法可以从n到1枚举矩形，一旦在矩形内就直接输出，可能会快一点。
不过对于这题的范围什么都是浮云。
【时间复杂度】O（n）
代码/标程
programcarpet;
//usessysutils;
type
juxing=record
x1,y1,x2,y2:
longint;
end;
var
i,j,k,l,r,m,n,x,y,s,t,ans:
longint;
a:
array[0..11000]ofjuxing;
t1,t2,t3,t4:
longint;
// time:
double;
procedureinit;
var
i,j,k:
longint;
begin
readln（n）;
fillchar（a,sizeof（a）,0）;
fori:
=1tondo
begin
readln（t1,t2,t3,t4）;
a[i].x1:
=t1;
a[i].y1:
=t2;
a[i].x2:
=t1+t3;
a[i].y2:
=t2+t4;
end;
readln（x,y）;
end;
functionok（i:
longint）:
boolean;
begin
if（a[i].x1<=x）and（x<=a[i].x2）then
if（a[i].y1<=y）and（y<=a[i].y2）then
exit（true）;
exit（false）;
end;
proceduremain;
var
i,j,k:
longint;
begin
ans:
=-1;
fori:
=1tondo
ifok（i）then
ans:
=i;
end;
procedureprint;
var
i,j,k:
longint;
begin
writeln（ans）;
end;
begin
assign（input,'carpet.in'）;
assign（output,'carpet.out'）;
reset（input）;
rewrite（output）;
// time:
=now;
Init;
main;
print;
// writeln（（now-time）*24*3600*1000:
0:
0）;
close（input）;
close（output）;
end.
选择客栈
【问题描述】
丽江河边有n家很有特色的客栈，客栈按照其位置顺序从1到n编号。
每家客栈都按照某一种色调进行装饰（总共k种，用整数0~k-1表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。
晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。
【输入】
输入文件hotel.in，共n+1行。
第一行三个整数n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；接下来的n行，第i+1行两个整数，之间用一个空格隔开，分别表示i号客栈的装饰色调和i号客栈的咖啡店的最低消费。
【输出】
输出文件名为hotel.out。
输出只有一行，一个整数，表示可选的住宿方案的总数。
【输入输出样例1】
hotel.in
hotel.out
523
05
13
02
14
15
3
【输入输出样例说明】
客栈编号
①
②
③
④
⑤
色调
0
1
0
1
1
最低消费
5
3
2
4
5
2人要住同样色调的客栈，所有可选的住宿方案包括：
住客栈①③，②④，②⑤，④⑤，但是若选择住4、5号客栈的话，4、5号客栈之间的咖啡店的最低消费是4，而两人能承受的最低消费是3元，所以不满足要求。
因此只有前3种方案可选。
【数据范围】
对于30%的数据，有n≤100；
对于50%的数据，有n≤1,000；
对于100%的数据，有2≤n≤200,000，0【一句话题意】
合法区间[l,r]定义：
l,r的色调相同，且[l,r]之间存在一个最低消费不超过p。
求合法区间总数。
【考察知识点】
二分查找/枚举
【思路】
①：
O（n^3）：
看完题目后不知所云，再多看几遍，一个O（n^3）的算法有了一点雏形。
用两层循环枚举区间的左右端点l、r，再用一层循环判断区间内是否有可行的咖啡店，累计即可。
这个算法思维难度和编程难度都非常低，但是只能过30%的数据，可以作为对拍程序备份。
②：
O（nk）
再仔细思考，发现题中合法区间的限制条件其实很强。
首先区间端点的色调必须相同，其次区间内必须要存在一个咖啡店最低消费不超过P。
因此，如果我们用一层循环枚举左端点，并很快找到右端点的可行数，那么题目就能解决了。
这里置答案为变量ans，千万注意类型要为int64，如果为ans:
longint，超级大杯具！
！
！
这里首先要用到区间部分和优化。
设sum[i,j]为前i个客栈中，色调为j的客栈总数，那么：
sum[i,j]=sum[i-1,j] （color[i]<>j）
sum[i,j]=sum[i-1,j]+1 （color[i]=j）
这里要用O（NK）的复杂度，是算法的瓶颈所在，不过对于题中的数据范围已经足够了。
并且具体实现可以先用数组赋值sum[i]=sum[i-1]，然后再为sum[i,color[i]]+1，应该会快很多。
我们还需要解决的问题就是，已知了L，如何快速找到R的可行范围？
再次注意区间内必须要存在一个咖啡店最低消费不超过P。
因此，如果L就是一个最低消费不超过P的咖啡店，那么R可以取到[L+1,n]中所有色调为color[L]的客栈，即ans=ans+sum[n,color[L]]-sum[L,color[L]]；如果L是一个最低消费超过P的咖啡店，那么我们要找到一个T∈[L+1,n]，且咖啡店T的最低消费不超过P，那么R就可以取到[T,n]中所有色调为color[L]的客栈，即ans=ans+sum[n,color[L]]-sum[T-1,color[L]] 。
问题是我们如何找到这个T，其实很简单，二分查找即可。
再次预设一个数组，保存所有最低消费不超过P的咖啡店序号，二分查找L即可。
注意这里L一定不存在这个数组中，因此找到的应该是最靠近L且大于L的序号，细节处理很重要。
找不到返回-1，不用累加ans就是了。
③：
O（n）
这应该是最优算法了，无论从空间、时间、编程复杂度方面来说。
记f（i）为第1~i的客栈中，编号最大的最低消费小于p的旅馆编号；r（i）为1~i-1号旅馆中，编号最大的与第i号旅馆色调相同的旅馆编号，count1（i）为第1~i-1号旅馆中与第i号旅馆色调相同旅馆数目，count2（i）为第1~i-1号旅馆中与第i号旅馆色调相同，且到第i号旅馆的路上存在最低消费不大于p的旅馆的旅馆数目。
（I）若f（i）（II）若f（i）>=r（i），那么第1~r（i）号旅馆中，所有与第i号旅馆色调相同的旅馆到第i号旅馆的路上必然存在一个旅馆的最低消费不大于p。
故此时count2（i）=count1（i）。
从1到n扫描一次即可，时间复杂度O（n）。
具体实现时可以将数组压缩，空间复杂度O（k）。
【时间复杂度】最低O（n）
代码/标程
programhotel;
type
kezhan=record
color,cost:
longint;
end;
var
i,j,k,l,r,m,n,x,y,s,t:
longint;
a:
array[-10..200100]ofkezhan;
sum:
array[-10..200100,-10..60]oflongint;
colorsum,mincost:
longint;
cafe:
array[-10..200100]oflongint;
v:
array[-10..200100]ofboolean;
ans:
int64;
procedureinit;
var
i,j,k:
longint;
begin
readln（n,colorsum,mincost）;
fillchar（a,sizeof（a）,0）;
fori:
=1tondo
readln（a[i].color,a[i].cost）;
end;
functionfind（x:
longint）:
longint;
var
i,j,k,mid:
longint;
begin
l:
=1;
r:
=s;
find:
=-1;
repeat
mid:
=（l+r）shr1;
ifx<=cafe[mid]then
begin
r:
=mid-1;
find:
=cafe[mid];
end
else
l:
=mid+1;
untill>r;
end;
proceduremain;
var
i,j,k:
longint;
begin
fori:
=0tocolorsum-1do sum[0,i]:
=0;
fori:
=1tondo
begin
sum[i]:
=sum[i-1];
sum[i,a[i].color]:
=sum[i-1,a[i].color]+1;
end;
s:
=0;
fillchar（cafe,sizeof（cafe）,0）;
fillchar（v,sizeof（v）,false）;
fori:
=1tondo
ifa[i].cost<=mincostthen
begin
inc（s）;
cafe[s]:
=i;
v[i]:
=true;
end;
ans:
=0;
fori:
=1ton-1do//meijudiyigeren
begin
ifv[i]then
begin
ans:
=ans+（sum[n,a[i].color]-sum[i,a[i].color]）;
end
else
begin
j:
=find（i）;
ifj=-1thenexit;
ans:
=ans+（sum[n,a[i].color]-sum[j-1,a[i].color]）;
end;
end;
end;
procedureprint;
var
i,j,k:
longint;
begin
writeln（ans）;
end;
begin
assign（input,'hotel.in'）;
assign（output,'hotel.ans'）;
reset（input）;
rewrite（output）;
init;
main;
print;
close（input）;
close（output）;
end.
mayan 游戏
【问题描述】
Mayanpuzzle是最近流行起来的一个游戏。
游戏界面是一个7行5列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。
游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：
1、每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：
当拖动这一方块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图6到图7）；如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图1和图2）；
2、任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除（参见图1到图3）。
注意：
a）如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图4，三个颜色为1的方块和三个颜色为2的方块会同时被消除，最后剩下一个颜色为2的方块）。
b）当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除（例如下面图5所示的情形，5个方块会同时被消除）。
3、方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。
注意：
掉落的过程中将不会有方块的消除。
上面图1到图3给出了在棋盘上移动一块方块之后棋盘的变化。
棋盘的左下角方块的坐标为（0,0），将位于（3,3）的方块向左移动之后，游戏界面从图1变成图2所示的状态，此时在一竖列上有连续三块颜色为4的方块，满足消除条件，消除连续3块颜色为4的方块后，上方的颜色为3的方块掉落，形成图3所示的局面。
【输入】
输入文件mayan.in，共6行。
第一行为一个正整数n，表示要求游戏通关的步数。
接下来的5行，描述7*5的游戏界面。
每行若干个整数，每两个整数之间用一个空格隔开，每行以一个0结束，自下向上表示每竖列方块的颜色编号（颜色不多于10种，从1开始顺序编号，相同数字表示相同颜色）。
输入数据保证初始棋盘中没有可以消除的方块。
【输出】
输出文件名为mayan.out。
如果有解决方案，输出n行，每行包含3个整数x，y，g，表示一次移动，每两个整数之间用一个空格隔开，其中（x，y）表示要移动的方块的坐标，g表示移动的方向，1表示向右移动，-1表示向左移动。
注意：
多组解时，按照x为第一关健字，y为第二关健字，1优先于-1，给出一组字典序最小的解。
游戏界面左下角的坐标为（0，0）。
如果没有解决方案，输出一行，包含一个整数-1。
【输入输出样例1】
mayan.in
mayan.out
3
10
210
2340
310
24340
211
311
301
【输入输出样例说明】
按箭头方向的顺序分别为图6到图11
样例输入的游戏局面如上面第一个图片所示，依次移动的三步是：
（2，1）处的方格向右移动，（3，1）处的方格向右移动，（3，0）处的方格向右移动，最后可以将棋盘上所有方块消除。
【数据范围】
对于30%的数据，初始棋盘上的方块都在棋盘的最下面一行；
对于100%的数据，0【一句话题意】
给定一个存在重力的矩阵，每次只能向左或右交换方块，连续3个或以上的方块群会被消除。
求操作次数为N时的操作步骤。
【考察知识点】
DFS
【思路】
第三题竟然是iPhone上MayanPuzzle游戏的完全复制。
对于这种完全裸搜索，固定搜索顺序，掐死搜索深度，基本无任何剪枝。
注意注意，第一页描述这题每个测试点时间限制是3S。
首先马上确定这是搜索题目，抛弃所有动规贪心等等。
然后锁定DFS，因为题中已经限定搜索深度。
设过程down（i），表示将第i列的所有方块下沉。
设函数clear，分行列清空后返回是否可以清空，这里用到连续区间指针l、r优化，类似前向星分组时的操作。
于是：
whilecleardo
fori:
=1to5do
down（i）;
注意在此之前如果有方块一交换就往下掉，那么就down交换的那两列。
根据我的CCF测评分数可以看出，爆搜只能过50分，若常数小一点可以过80分。
稍微修改了一下代码，用上两个剪枝，就可以通过了。
下面附加几个剪枝：
· 若两种相同颜色的方块进行交换，显然没有意义。
· 某个颜色方块的数量<=2，则很显然不能被消除
· 设个变量掐时，大概快超时的时候直接输出-1
【时间复杂度】
O（k（4*7）^5）
mayan 游戏
programmayan;
type
arr=array[-2..6,-2..8]ofinteger;
sdata=record
x,y,g:
integer;
end;
vard:
arr;
step:
array[1..5]ofsdata;
n,f:
integer;
procedureinit;//初始化
vari,j:
integer;
begin
fillchar（d,sizeof（d）,0）;
readln（n）;
fori:
=0to4do
begin
j:
=-1;
repeatinc（j）;read（d[i,j]）;untild[i,j]=0;//在此位置，可以修改代码把颜色小于等于2的情况剪掉
end;
f:
=-1;
end;
procedureprint;//输出结果
vari:
integer;
begin
iff=1thenfori:
=1tondowriteln（step[i].x,'',step[i].y,'',step[i].g） elsewriteln（-1）;
end;
functionok（a:
arr）:
boolean;
vari,j:
integer;t:
boolean;
begin
t:
=true;
fori:
=0to4do
forj:
=0to6doifa[i,j]>0then begint:
=false;break;end;
exit（t）;
end;
procedurecheck（vara:
arr）;//消除 下落
vars:
arr;i,j,k,t:
integer;
begin
repeat
t:
=0;fillchar（s,sizeof（s）,0）;
fori:
=0to4do
forj:
=0to6doifa[i,j]>0then
begin
if（a[i,j+2]=a[i,j+1]）and（a[i,j+1]=a[i,j]）then
begint:
=1;fork:
=0to2dos[i,j+k]:
=1;end;
if（a[i+2,j]=a[i+1,j]）and（a[i+1,j]=a[i,j]）then
begint:
=1;fork:
=0to2dos[i+k,j]:
=1;end;
end;
ift=1then
begin
fori:
=0to4do
forj:
=0to6do
ifs[i,j]=1thena[i,j]:
=0;
fori:
=0to4do
forj:
=5downto0do
升级会员 