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

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


相关文章:
2011noip提高组复赛题解
Noip 2011 提高组 (Day 1) 解题报告及程序 一、铺地毯 正着扫一遍 判断每个矩形是否覆盖询问的点,覆盖则更新结果 或者倒着扫一遍,找到第一个覆盖询问点的矩形...
NOIP2015提高组day1第二题解题报告
NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组day1第二题的解题报告因为太简单所以写出来(误作者:蒟蒻zrw ...
2011noip提高组解题报告
12页 1财富值 2011noip解题报告 13页 1财富值 2011noip复赛解题报告(未完... 3页 免费 2011noip复赛解题报告day1 2页 2财富值 noip2010提高组解题报告 11页...
NOIP2011初赛提高组答案详细解析
NOIP2011 提高组 Day2 4页 免费 NOIP2011 提高组 解题报... 4页 1下载券...NOIP2011提高组解题报告... 9页 2下载券 Noip2011普及组Pascal初... 11页...
NOIP2011 提高组 day1 试题
NOIP2011 提高组 day1 试题_其它考试_资格考试/认证_教育专区。NOIP,2011,DAY...NOIP2011提高组复赛试题... 6页 1下载券 NOIP2011提高组解题报告... 9页 ...
冲刺NOIP2011长乐一中day1解题报告
冲刺NOIP2011长乐一中day2 暂无评价 4页 免费 NOIP2011提高组解题报告da... 15...(城堡的位置 的最迟出发时间为 min-1,因为这个时刻还不走就会被发现) ,如果...
NOIP2011DAY2解题报告
NOIP2011DAY2解题报告_初三英语_英语_初中教育_教育专区。NOIP2011提高组复赛DAY2解题报告 NOIP2011DAY2 解题报告 ——by 北京一零一中学 张子威(c++) 今天的题...
2011noip复赛解题报告day1
NOIP2007提高组解题报告 20页 免费 2011noip解题报告 13页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
noip2010提高组解题报告
NOIP2010普及组解题报告 7页 1下载券 2011年学业水平思想品德... 暂无评价 9...NOIP2010 解题报告(提高) 作者:张宇昊所有见解仅供参考 考试时。。。发挥 1/3...
NOIP2011普及组解题报告
NOIP2011普及组解题报告_学科竞赛_初中教育_教育专区。NOIP2011 普及组解题报告一...2009NOIP普及组复赛解题... 6页 免费 NOIP2011提高组复赛DAY1... 2页 ...
更多相关标签:
noip2016提高组day1 | noip2011day1选择客栈 | noip2012提高组day1 | noip2015提高组day1 | noip2011提高组复赛 | noip2011提高组初赛 | noip2011提高组 | noip2016 day1 |