当前位置:首页 >> 学科竞赛 >>

NOIP2011提高组解题报告day1


NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺地毯 【问题描述】 为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标 系的第一象限)铺上一些矩形地毯。一共有 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。 【输入输出样例】 carpet.in 3 1023 0233 2133 22 3 carpet.out 3 【解题报告】 从后往前扫,找到第一个覆盖这个点的就输出,否则无解。 program carpet; //uses sysutils; var n,i,a,b:longint; x2,x1,y1,y2:array[0..100001]of longint; //time:extended; procedure main; begin readln(n);

for i:=1 to n do begin readln(x1[i],y1[i],a,b); x2[i]:=x1[i]+a; y2[i]:=y1[i]+b; end; readln(a,b); for i:=n downto 1 do if (a<=x2[i])and(a>=x1[i])and(b>=y1[i])and(b<=y2[i]) then begin writeln(i); exit; end; writeln(-1); end; begin assign(input,'carpet.in'); reset(input); assign(output,'carpet.out'); rewrite(output); //time:=now; //当前时间 main; //writeln((now-time)*24*3600:0:2);//输出程序运行时间 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 523 05 13 02 14 15 【输入输出样例说明】 客栈编号 色调 最低消费 ① 0 5

hotel.out

3

② 1 3

③ 0 2

④ 1 4

⑤ 1 5

2 人要住同样色调的客栈,所有可选的住宿方案包括:住客栈①③,②④,②⑤,④⑤,但 是若选择住 4、5 号客栈的话,4、5 号客栈之间的咖啡店的最低消费是 4,而两人能承受的 最低消费是 3 元,所以不满足要求。因此只有前 3 种方案可选。 【数据范围】 对于 30%的数据,有 n≤100; 对于 50%的数据,有 n≤1,000; 对于 100%的数据,有 2≤n≤200,000,0<k≤50,0≤p≤100, 0≤最低消费≤100。 【一句话题意】 合法区间[l,r]定义: l,r 的色调相同, 且[l,r]之间存在一个最低消费不超过 p。 求合法区间总数。 【考察知识点】 二分查找/枚举 ①:O(n^3): 看完题目后不知所云,再多看几遍,一个 O(n^3)的算法有了一点雏形。 用两层循环枚举区间的左右端点 l、r,再用一层循环判断区间内是否有可行的咖啡店,累计 即可。这个算法思维难度和编程难度都非常低,但是只能过 30%的数据,可以作为对拍程 序备份。 ②:O(nk) 再仔细思考,发现题中合法区间的限制条件其实很强。首先区间端点的色调必须相同,其次 区间内必须要存在一个咖啡店最低消费不超过 P。 因此, 如果我们用一层循环枚举左端点, 并很快找到右端点的可行数, 那么题目就能解决了。 这里置答案为变量 ans ,千万注意类型要为 int64 这里首先要用到区间部分和优化。设 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(nlogn) 这个办法比②更优一些。来自 Clarkok 的做法。 用 list[i, j] 表示颜色为 i 的第 j 个客栈,也就是将客栈按照颜色紧缩存储。另用 pos[i] 表示第 i 个旅馆在 list[color[i]] 中的位置。用线段树/ST 算法(推荐)预处理出区间消费的最小值,也就 是 min{cost[i..j]} ,易得到 min[k,i] 是非增的,注意这是后面二分的关键。 然后枚举第二个人,在 list[color[i]] 中用二分找到一个 j 满足 min[j, i]<=P,那么 ans=ans+j, 因为 list[color[i],1..j] 中必然都是颜色为 color[i] ,且区间最小值也都<=P。 ④: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)<r(i) ,那么必然有 f(i)=f(r(i)) ,故 count2(i)=count2(r(i)) 。 (II)若 f(i)>=r(i) ,那么第 1~r(i)号旅馆中,所有与第 i 号旅馆色调相同的旅馆到第 i 号旅馆的 路上必然存在一个旅馆的最低消费不大于 p。故此时 count2(i)=count1(i) 。 从 1 到 n 扫描一次即可,时间复杂度 O(n)。具体实现时可以将数组压缩,空间复杂度 O(k)。 【时间复杂度】 最低 O(n) //O(nk) program hotel; //uses sysutils; const proname='hotel'; type kezhan=record color,cost:longint; end; var fin,fout:text; i,j,k,l,r,m,n,x,y,s,t:longint; a:array[-10..200100]of kezhan; sum:array[-10..200100,-10..60]of longint; colorsum,mincost:longint; cafe:array[-10..200100]of longint; v:array[-10..200100]of boolean; ans:int64;

procedure pin; var i,j,k:longint; begin readln(fin,n,colorsum,mincost); fillchar(a,sizeof(a),0); for i:=1 to n do readln(fin,a[i].color,a[i].cost); end; function find(x:longint):longint; var i,j,k,mid:longint; begin l:=1; r:=s; find:=-1; repeat mid:=(l+r) shr 1; if x<=cafe[mid] then begin r:=mid-1; find:=cafe[mid]; end else l:=mid+1; until l>r; end; procedure main; var i,j,k:longint; begin for i:=0 to colorsum-1 do sum[0,i]:=0; for i:=1 to n do 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);

for i:=1 to n do if a[i].cost<=mincost then begin inc(s); cafe[s]:=i; v[i]:=true; end; ans:=0; for i:=1 to n-1 do //mei ju di yi ge ren begin if v[i] then begin ans:=ans+(sum[n,a[i].color]-sum[i,a[i].color]); end else begin j:=find(i); if j=-1 then exit; ans:=ans+(sum[n,a[i].color]-sum[j-1,a[i].color]); end; end; end; procedure pout; var i,j,k:longint; begin writeln(fout,ans); end; begin assign(fin,proname+'.in'); assign(fout,proname+'.out'); reset(fin); rewrite(fout); //time:=now; pin; main; pout; //writeln(fout,(now-time)*24*3600*1000:0:0); close(fin); close(fout); end.

mayan 游戏 【问题描述】 Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 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 3 10 210 2340 310 mayan.out 211 311 301

2 4 3 40 【输入输出样例说明】 按箭头方向的顺序分别为图 6 到图 11 样例输入的游戏局面如上面第一个图片所示,依次移动的三步是: (2,1)处的方格向右移 动, (3,1)处的方格向右移动, (3,0)处的方格向右移动,最后可以将棋盘上所有方块消 除。 【数据范围】 对于 30%的数据,初始棋盘上的方块都在棋盘的最下面一行; 对于 100%的数据,0 < n≤5。 【一句话题意】 给定一个存在重力的矩阵, 每次只能向左或右交换方块, 连续 3 个或以上的方块群会被消除。 求操作次数为 N 时的操作步骤。 【考察知识点】 DFS 【思路】 第一页描述这题每个测试点时间限制是 3S 马上确定这是搜索题目, 抛弃所有动规贪心等等。 然后锁定 DFS,因为题中已经限定搜索深度,BFS 是自找 MLE。 再确定状态存储方式, 我是将输入逆时针转 90° 后用数组保存, 因此坐标之类的要特别注意。 然后,然后就没什么特别的了,搜素顺序题目已经给了。 设过程 down(i) ,表示将第 i 列的所有方块下沉。设函数 clear,分行列清空后返回是否可以 清空,这里用到连续区间指针 l、r 优化,类似前向星分组时的操作。于是: while clear do for i:=1 to 5 do down(i); 注意在此之前如果有方块一交换就往下掉,那么就 down 交换的那两列。 表示码了 200 多行代码用了半小时,调试几乎用了 1 小时,那叫一个蛋疼。 。 。 。 根据我的 CCF 测评分数可以看出,爆搜只能过 50 分,若常数小一点可以过 80 分。回家后 我稍微修改了一下代码,用上了 WJMZBMR 的前两个剪枝,最后一个点在家里的电脑上跑 了 2s ,其他点轻松通过了。 下面附加几个剪枝 左右交换是等价的,根据题中的顺序,只需向右交换即可 某个颜色方块的数量<=2,则很显然不能被消除 掉落不能改变方块的列,因此某列 l1 上某颜色方块数量∈[1,2],则必须通过交换来从其他 列 l2 得到方块。取一个 l1,且 l2 最远,设这个距离为 Di,那么必须要把多有颜色的 Di 消 到 0 。 而 一 次 操 作 最 多 减 少 两 个 颜 色 的 Di , 因 此 最 少 操 作 次 数 为 : max{max{Di}(1<=i<=10),(sum(Di)(1<=i<=10)+1)/2} 设个变量掐时,大概快超时的时候直接输出-1 【时间复杂度】 O(k(4*7)^5) program mayan; //uses sysutils; const proname='mayan';

type game=record data:array[0..8,0..6]of longint; end; var fin,fout:text; i,j,k,l,r,m,n,x,y,s,t,ans:longint; first:game; b:array[0..10]of game; caozuo:array[0..10,0..3]of longint; tt:array[0..8,0..6]of longint; cut:array[0..11]of longint; procedure pin; var i,j,k:longint; begin readln(fin,n); fillchar(first,sizeof(first),0); for j:=1 to 5 do begin i:=8; repeat read(fin,k); if k=0 then break; dec(i); first.data[i,j]:=k; until false; readln(fin); end; end; procedure swap(x,x1,y1,x2,y2:longint); var t:longint; begin t:=b[x].data[x1,y1]; b[x].data[x1,y1]:=b[x].data[x2,y2]; b[x].data[x2,y2]:=t; end; function ok(x:longint):boolean; var i,j,k:longint;

begin ok:=true; for i:=1 to 5 do if b[x].data[7,i]<>0 then exit(false); end; procedure down(x,lie:longint); var i,j,k:longint; begin for i:=6 downto 1 do if (b[x].data[i,lie]<>0)and(b[x].data[i+1,lie]=0) then begin for k:=7 downto 1 do if b[x].data[k,lie]=0 then break; swap(x,i,lie,k,lie); end; end; function clear(x:longint):boolean; var i,j,k:longint; l,r:longint; step:longint; begin fillchar(tt,sizeof(tt),0); l:=0; r:=0; step:=x; clear:=false; for i:=1 to 7 do begin for j:=1 to 5 do if b[x].data[i,j]<>b[x].data[i,j-1] then begin r:=j-1; if (l<>0)and(r-l+1>=3)and(b[x].data[i,l]<>0) then begin for k:=l to r do tt[i,k]:=1; clear:=true; end;

l:=j; end; if (5-l+1>=3)and(b[x].data[i,5]<>0) then begin for k:=l to 5 do tt[i,k]:=1; clear:=true; end; end; l:=0; r:=0; for i:=1 to 5 do begin for j:=1 to 7 do if b[x].data[j,i]<>b[x].data[j-1,i] then begin r:=j-1; if (l<>0)and(r-l+1>=3)and(b[x].data[l,i]<>0) then begin for k:=l to r do tt[k,i]:=1; clear:=true; end; l:=j; end; if (7-l+1>=3)and(b[x].data[l,i]<>0)and(b[x].data[7,i]<>0) then begin for k:=l to 7 do tt[k,i]:=1; clear:=true; end; end; for i:=1 to 7 do for j:=1 to 5 do if tt[i,j]=1 then b[x].data[i,j]:=0; end; procedure dfs(step:longint); var i,j,k:longint; begin if step=n+1 then begin

if ok(n+1) then begin for i:=1 to n do writeln(fout,caozuo[i,1],' ',caozuo[i,2],' ',caozuo[i,3],' '); close(fin); close(fout); halt; end; exit; end; //剪枝 2 fillchar(cut,sizeof(cut),0); for i:=1 to 5 do for j:=1 to 7 do inc(cut[b[step].data[j,i]]); for i:=1 to 10 do if (cut[i]=1)or(cut[i]=2) then exit; b[step+1]:=b[step]; for i:=1 to 4 do for j:=7 downto 1 do //剪枝 1 这里有一个问题,即第一层为 01101 且操作数为 1 时,必须要向右移 //因此这个剪枝需要稍加修改,这段程序不能 AC! ! ! if (b[step+1].data[j,i]<>b[step+1].data[j,i+1]) then begin swap(step+1,j,i,j, i+1); down(step+1,i+1); down(step+1,i); while clear(step+1) do for k:=1 to 5 do down(step+1,k); caozuo[step,1]:=i-1; caozuo[step,2]:=7-j; caozuo[step,3]:=1; dfs(step+1); b[step+1]:=b[step]; end; end; procedure main; var i,j,k:longint; begin fillchar(b,sizeof(b),0);

fillchar(caozuo,sizeof(caozuo),0); b[1]:=first; dfs(1); end; procedure pout; var i,j,k:longint; begin writeln(fout,-1); end; begin assign(fin,proname+'.in'); assign(fout,proname+'.out'); reset(fin); rewrite(fout); //time:=now; pin; main; pout; //writeln(fout,(now-time)*24*3600*1000:0:0); close(fin); close(fout); end.

分享

分享到新浪 Q


相关文章:
NOIP2011提高组解题报告day1
NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告day1NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺地...
NOIP2011提高组解题报告day2
NOIP2011提高组解题报告day2_理学_高等教育_教育专区。noip历届复赛试题及解析 ...【数据范围】 对于 10%的数据,k=0; 对于 20%的数据,k=1; 对于 40%的...
NOIP2015提高组day1第二题解题报告
NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组day1第二题的解题报告因为太简单所以写出来(误作者:蒟蒻zrw ...
NOIP 2011 提高组 day1 题解
NOIP 2011 提高组 day1 题解_其它考试_资格考试/认证_教育专区。NOIP2011 题解 铺地毯: 顺序处理每一个长方形, 并判断当前的点是否在长方形内, 并记录尽可能...
2011noip提高组解题报告
12页 1财富值 2011noip解题报告 13页 1财富值 2011noip复赛解题报告(未完... 3页 免费 2011noip复赛解题报告day1 2页 2财富值 noip2010提高组解题报告 11页...
NOIP2011提高组复赛试题Day1
第 3 页共 6 页 全国信息学奥林匹克联赛(NOIP2011)复赛 提高组 day1 输出...NOIP2011提高组复赛试题... NOIP2011DAY2解题报告1/2 相关文档推荐 ...
2011noip复赛解题报告day1
NOIP2007提高组解题报告 20页 免费 2011noip解题报告 13页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
2011noip提高组复赛题解
Noip 2011 提高组 (Day 1) 解题报告及程序 一、铺地毯 正着扫一遍 判断每个矩形是否覆盖询问的点,覆盖则更新结果 或者倒着扫一遍,找到第一个覆盖询问点的矩形...
NOIP2011 提高组 day1 试题
NOIP2011 提高组 day1 试题_其它考试_资格考试/认证_教育专区。NOIP,2011,DAY...NOIP2011提高组复赛试题... 6页 1下载券 NOIP2011提高组解题报告... 9页 ...
更多相关标签:
noip2011提高组day1 | noip2016提高组day1 | noip2015提高组day1 | noip2014提高组day1 | noip2012提高组day1 | noip2011day1 | noip2013提高组day1 | noip2014提高解题报告 |