NOIP2011提高组解题报告day1.docx

《NOIP2011提高组解题报告day1.docx》由会员分享，可在线阅读，更多相关《NOIP2011提高组解题报告day1.docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、NOIP2011提高组解题报告day1NOIP2020提高组解题报告day1(2020-12-1309:29:54)标签：杂谈铺地毯【问题描绘】为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域可看做是平面直角坐标系的第一象限铺上一些矩形地毯。一共有n张地毯，编号从1到n。如今将这些地毯根据编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。【输入】输入文件名为carpet.in。输入共n+2行。第一行，一个整数n，表示总共有n张地毯。接下来的

2、n行中，第i+1行表示编号i的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标a，b以及地毯在x轴和y轴方向的长度。第n+2行包含两个正整数x和y，表示所求的地面的点的坐标x，y。【输出】输出文件名为carpet.out。输出共1行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。【输入输出样例】carpet.in3102302332133223carpet.out3【解题报告】从后往前扫，找到第一个覆盖这个点的就输出，否则无解。programcarpet;/usessysutils;varn,i,a,b:longint;x

3、2,x1,y1,y2:array0.100001oflongint;/time:extended;proceduremain;beginreadln(n);当前位置：文档视界NOIP2020提高组解题报告day1NOIP2020提高组解题报告day1是若选择住4、5号客栈的话，4、5号客栈之间的咖啡店的最低消费是4，而两人能承受的最低消费是3元，所以不知足要求。因而只要前3种方案可选。【数据范围】对于30%的数据，有n100；对于50%的数据，有n1,000；对于100%的数据，有2n200,000，0j)sumi,j=sumi-1,j+1(colori=j)这里要用O(NK)的复杂度，是算法

4、的瓶颈所在，不过对于题中的数据范围已经足够了。并且详细实现能够先用数组赋值sumi=sumi-1，然后再为sumi,colori+1，应该会快很多。我们还需要解决的问题就是，已知了L，怎样快速找到R的可行范围？再次注意区间内必需要存在一个咖啡店最低消费不超过P。因而，假如L就是一个最低消费不超过P的咖啡店，那么R能够取到L+1,n中所有色调为colorL的客栈，即ans=ans+sumn,colorL-sumL,colorL；假如L是一个最低消费超过P的咖啡店，那么我们要找到一个TL+1,n，且咖啡店T的最低消费不超过P，那么R就能够取到T,n中所有色调为colorL的客栈，即ans=ans+

5、sumn,colorL-sumT-1,colorL。问题是我们怎样找到这个T，其实很简单，二分查找即可。再次预设一个数组，保存所有最低消费不超过P的咖啡店序号，二分查找L即可。注意这里L一定不存在这个数组中，因而找到的应该是最靠近L且大于L的序号，细节处理很重要。找不到返回-1，不用累加ans就是了。：O(nlogn)这个办法比更优一些。来自Clarkok的做法。用listi,j表示颜色为i的第j个客栈，也就是将客栈根据颜色紧缩存储。另用posi表示第i个旅馆在listcolori中的位置。用线段树/ST算法(推荐)预处理出区间消费的最小值，也就是mincosti.j，易得到mink,i是非增

6、的，注意这是后面二分的关键。然后枚举第二个人，在listcolori中用二分找到一个j知足minj，i=r(i)，那么第1r(i)号旅馆中，所有与第i号旅馆色调一样的旅馆到第i号旅馆的路上必然存在一个旅馆的最低消费不大于p。故此时count2(i)=count1(i)。从1到n扫描一次即可，时间复杂度O(n)。详细实现时能够将数组压缩，空间复杂度O(k)。【时间复杂度】最低O(n)/O(nk)programhotel;/usessysutils;constproname=hotel;typekezhan=recordcolor,cost:longint;end;varfin,fout:text

7、;i,j,k,l,r,m,n,x,y,s,t:longint;a:array-10.200100ofkezhan;sum:array-10.200100,-10.60oflongint;colorsum,mincost:longint;cafe:array-10.200100oflongint;v:array-10.200100ofboolean;ans:int64;procedurepin;vari,j,k:longint;beginreadln(fin,n,colorsum,mincost);fillchar(a,sizeof(a),0);fori:=1tondoreadln(fin,ai

8、.color,ai.cost);end;functionfind(x:longint):longint;vari,j,k,mid:longint;beginl:=1;r:=s;find:=-1;repeatmid:=(l+r)shr1;ifxr;end;proceduremain;vari,j,k:longint;beginfori:=0tocolorsum-1dosum0,i:=0;fori:=1tondobeginsumi:=sumi-1;sumi,ai.color:=sumi-1,ai.color+1;end;s:=0;fillchar(cafe,sizeof(cafe),0);fill

9、char(v,sizeof(v),false);当前位置：文档视界NOIP2020提高组解题报告day1NOIP2020提高组解题报告day1mayan游戏【问题描绘】Mayanpuzzle是近期流行起来的一个游戏。游戏界面是一个7行5列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：1、每步移动能够且仅能够沿横向即向左或向右拖动某一方块一格：当拖动这一方块时，假如拖动后到达的位置下面称目的位置也有方块，那么这两个方块将交换位置参见输入输出样例讲明中的图6到图7；假如目的位置上没有方块，

10、那么被拖动的方块将从原来的竖列中抽出，并从目的位置上掉落直到不悬空，参见下面图1和图2；2、任一时刻，假如在一横行或者竖列上有连续三个或者三个以上一样颜色的方块，则它们将立即被消除参见图1到图3。注意：a)假如同时有多组方块知足消除条件，几组方块会同时被消除例如下面图4，三个颜色为1的方块和三个颜色为2的方块会同时被消除，最后剩下一个颜色为2的方块。b)当出现行和列都知足消除条件且行列分享某个方块时，行和列上知足消除条件的所有方块会被同时消除例如下面图5所示的情形，5个方块会同时被消除。3、方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的经过中将不会有方块的消

11、除。上面图1到图3给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为0,0，将位于3,3的方块向左移动之后，游戏界面从图1变成图2所示的状态，此时在一竖列上有连续三块颜色为4的方块，知足消除条件，消除连续3块颜色为4的方块后，上方的颜色为3的方块掉落，构成图3所示的局面。【输入】输入文件mayan.in，共6行。第一行为一个正整数n，表示要求游戏通关的步数。接下来的5行，描绘7*5的游戏界面。每行若干个整数，每两个整数之间用一个空格隔开，每行以一个0结束，自下向上表示每竖列方块的颜色编号颜色不多于10种，从1开场顺序编号，一样数字表示一样颜色。输入数据保证初始棋盘中没有能够消除

12、的方块。【输出】输出文件名为mayan.out。假如有解决方案，输出n行，每行包含3个整数x，y，g，表示一次移动，每两个整数之间用一个空格隔开，其中x，y表示要移动的方块的坐标，g表示移动的方向，1表示向右移动，-1表示向左移动。注意：多组解时，根据x为第一关健字，y为第二关健字，1优先于-1，给出一组字典序最小的解。游戏界面左下角的坐标为0，0。假如没有解决方案，输出一行，包含一个整数-1。当前位置：文档视界NOIP2020提高组解题报告day1NOIP2020提高组解题报告day1game=recorddata:array0.8,0.6oflongint;end;varfin,fout:

13、text;i,j,k,l,r,m,n,x,y,s,t,ans:longint;first:game;b:array0.10ofgame;caozuo:array0.10,0.3oflongint;tt:array0.8,0.6oflongint;cut:array0.11oflongint;procedurepin;vari,j,k:longint;beginreadln(fin,n);fillchar(first,sizeof(first),0);forj:=1to5dobegini:=8;repeatread(fin,k);ifk=0thenbreak;dec(i);first.datai

14、,j:=k;untilfalse;readln(fin);end;end;procedureswap(x,x1,y1,x2,y2:longint);vart:longint;begint:=bx.datax1,y1;bx.datax1,y1:=bx.datax2,y2;bx.datax2,y2:=t;end;functionok(x:longint):boolean;vari,j,k:longint;ok:=true;fori:=1to5doifbx.data7,i0thenexit(false);end;proceduredown(x,lie:longint);vari,j,k:longin

15、t;beginfori:=6downto1doif(bx.datai,lie0)and(bx.datai+1,lie=0)thenbeginfork:=7downto1doifbx.datak,lie=0thenbreak;swap(x,i,lie,k,lie);end;end;functionclear(x:longint):boolean;vari,j,k:longint;l,r:longint;step:longint;beginfillchar(tt,sizeof(tt),0);l:=0;r:=0;step:=x;clear:=false;fori:=1to7dobeginforj:=

16、1to5doifbx.datai,jbx.datai,j-1thenbeginr:=j-1;if(l0)and(r-l+1=3)and(bx.datai,l0)thenbeginfork:=ltordotti,k:=1;clear:=true;end;l:=j;end;if(5-l+1=3)and(bx.datai,50)thenbeginfork:=lto5dotti,k:=1;clear:=true;end;end;l:=0;r:=0;fori:=1to5dobeginforj:=1to7doifbx.dataj,ibx.dataj-1,ithenbeginr:=j-1;if(l0)and(r-l+1=3)and(bx.datal,i0)thenbeginfork:=ltordottk,i:=1;clear:=true;end;l:=j;end;if(7-l+1=3)and(bx.datal,i0)and(bx.data7,i0)thenbeginfork:=lto7dottk,i:=1;clear:=true;end;end;fori:=1to7doforj:=1to5doiftti,j=1thenbx.datai,j:=0;end;proceduredfs(step:longint);vari,j,k:longint;beginifstep=n+1thenbegin