noip2016玛雅游戏结题报告

1 / 29 noip2016 玛雅游戏结题报告 NOIP2016 提高组解题报告 day1 标签： 杂谈 铺地毯 【问题描述】 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到 n。现在将这些地毯按照 编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。 地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形 地毯边界和四个顶 点上的点也算被地毯覆盖。 【输入】 输入文件名为 。 输入共 n+2 行。 第一行，一个整数 n，表示总共有 n 张地毯。 接下来的 n 行中，第 i+1 行表示编号 i 的地毯的信息，包含四个正整数 a， b， g， k，每 两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标以及地毯在x 轴和 y 轴方向的长度。 2 / 29 第 n+2 行包含两个正整数 x 和 y，表示所求的地面的点的坐标。 【输出】 输出文件名为 。 输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 -1。 【输入输出样例】 3 1 0 2 3 0 2 3 3 2 1 3 3 2 2 3 3 【解题报告】 从后往前扫，找到第一个覆盖这个点的就输出，否则无解。 program carpet; /uses sysutils; var 3 / 29 n,i,a,b:longint; x2,x1,y1,y2:array0.100001of longint; /time:extended; procedure main; begin readln; for i:=1 to n do begin readln; x2i:=x1i+a; y2i:=y1i+b; end; readln; for i:=n downto 1 do if andandand then begin writeln; exit; end; writeln; end; begin assign; 4 / 29 reset; assign; rewrite; /time:=now; /当前时间 main; /writeln*24*3600:0:2);/输出程序运行时间 close; close; end. 选择客栈 【问题描述】 丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰，且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。 两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调 相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间，且咖啡店的最低消费不超过 p。 他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。 5 / 29 【输入】 输入文件 ，共 n+1 行。 第一行三个整数 n， k， p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；接下来的 n 行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调和 i 号客 栈的咖啡店的最低消费。 【输出】 输出文件名为 。 输出只有一行，一个整数，表示可选的住宿方案的总数。 【输入输出样例 1】 是若选择住 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。求合法区间总数。 6 / 29 【考察知识点】 二分查找 /枚举 ： O： 看完题目后不知所云，再多看几遍，一个 O 的算法有了一点雏形。 用两层循环枚举区间的左右端点 l、 r，再用一层循环判断区间内是否有可行的咖啡店，累计即可。这个算法思维难度和编程难度都非常低，但是只能过 30%的数据，可以作为对拍程序备份。 ： O 再仔细思考，发现题中合法区间的限制条件其实很强。首先区间端点的色调必须相同，其次区间内必须要存在一个咖啡店最低消费不超过 P。 因此，如果我们用一层循环枚举左端点，并很快找到右端点的可行数，那么题目就能解决了。这里置答案为变量 ans，千万注意类型要为 int64 这里首先要用到区间部分和优化。设 sum i,j为前i 个 客 栈 中 ， 色 调 为 j 的 客 栈 总 数 ， 那 么 ： sumi,j=sumi-1,j sumi,j=sumi-1,j+1 这里要用 O 的复杂度，是算 法的瓶颈所在，不过对于题中的数据范围已经足够了。并且具体实现可以先用数组7 / 29 赋值 sumi=sumi-1，然后再为 sumi,colori+1，应该会快很多。 我们还需要解决的问题就是，已知了 L，如何快速找到 R的可行范围？ 再次注意区间内必须要存在一个咖啡店最低消费不超过 P。 因此，如果 L 就是一个最低消费不超过 P的咖啡店，那么 R 可以取到 L+1,n中所有色调为 colorL的客栈，即ans=ans+sumn,colorL-sumL,colorL； 如果 L 是一个最低消费超过 P 的咖啡店，那么我们要找到一个 T L+1,n，且咖啡店 T 的最低消费不超过 P，那么 R就可以取到 T,n中所有色调为 colorL的客栈，即 ans=ans+sumn,colorL-sumT-1,colorL 。 问题是我们如何找到这个 T，其实很简单，二分查找即可。再次预设一个数组，保存所有最低消费不超过 P的咖啡店序号，二分查找 L即可。注意这里 L 一定不存在这个数组中，因此找到的应该是最靠近 L 且大于 L 的序号，细节处理很重要。找不到返回 -1， 不用累加 ans 就是了。 ： O 这个办法比更优一些。来自 Clarkok的做法。 用 listi,j表示颜色为 i 的第 j个客栈，也就是将客栈按照颜色紧缩存储。另用 posi表示第 i 个旅馆在listcolori中的位置。用线段树 /ST 算法预处理出区间8 / 29 消费的最小值，也就是 mincosti.j，易得到 mink,i是非增的，注意这是后面二分的关键。 然后枚举第二个人，在 listcolori中用二分找到一个 j 满足 minj， i ： O 这应该是最优算法了，无论从空间、时间、编程复杂度方面来说。 这个算法转自上善若水 记 f为第 1i的客栈中，编号最大的最低消费小于p 的旅馆编号； r 为 1i-1 号旅馆中，编号最大的与第 i 号旅馆色调相同的旅馆编号， count1 为第 1i-1号旅馆中与第i 号旅馆色调相同旅馆数目， count2 为第 1i-1号旅馆中与第 i 号旅馆色调相同，且到第 i号旅馆的路上存在最低消费不大于 p 的旅馆的旅馆数目。 若 f 若 f=r，那么第 1r号旅馆中，所有与第 i号旅馆色调相 同的旅馆到第 i号旅馆的路上必然存在一个旅馆的最低消费不大于 p。故此时 count2=count1。 从 1 到 n扫描一次即可，时间复杂度 O。具体实现时可以将数组压缩，空间复杂度 O。 【时间复杂度】 最低 O /O program hotel; 9 / 29 /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.200100of kezhan; sum:array-10.200100,-10.60of longint; colorsum,mincost:longint; cafe:array-10.200100of longint; v:array-10.200100of boolean; ans:int64; procedure pin; var i,j,k:longint; begin readln; fillchar,0); 10 / 29 for i:=1 to n do readln; end; function find:longint; var i,j,k,mid:longint; begin l:=1; r:=s; find:=-1; repeat mid:= shr 1; if x begin r:=mid-1; find:=cafemid; end else l:=mid+1; until lr; end; procedure main; var 11 / 29 i,j,k:longint; begin for i:=0 to colorsum-1 do sum0,i:=0; for i:=1 to n do begin sumi:=sumi-1; sumi,ai.color:=sumi-1,ai.color+1;end; s:=0; fillchar,0); fillchar,false); 题目描述 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。 假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入 的单词数不超过 M?； 1，软件会将新单词存入一个未12 / 29 使用的内存单元；若内存中已存入 M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。 假设一篇英语文章的长度为 N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。 【数据范围】 对于 10%的数据有 M=1， N 5。 对于 100%的数据有 0 输入格式 in，输入文件共 2 行。每行中两个数之间用一个空格隔开。 第一行为 两个正整数 M 和 N，代表内存容量和文章的长度。 第二行为 N 个非负整数，按照文章的顺序，每个数代表一个英文 单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。 输出格式 共 1 行，包含一个整数，为软件需要查词典的次数。 【输入输出样例 1】 3 7 1 2 1 5 4 4 1 【输入输出样例 2】 2 10 13 / 29 8 824 11 78 11 78 11 78 8 264 【输入 输出样例 1】 5 【输入输出样例 2】 6 初拿这道题感觉很简单，不就是模拟嘛，亏我还先做的第二道题。这道题完全可以用队列 来模拟；不过这道题一定要注意，队列出队的问题，当满队的时候，如何处理？这里我是边 读边处理完全可以的；我们可以设数组 c来控制队列，数组 b 来当作字典； t 来记录查找次 数； x 是单词数，与 m一起控制队列，即当 xm 时，表示已满单词数，当前单词需要另外储存；好了，模拟算法出来了：实现如下： program p1067; var m,n,x,t,a,i:longint; b:array1.1000 of boolean; c:array1.1000 of longint; begin readln; t:=0; x:=0; for i:=1 to n do 14 / 29 begin read; if ba then continue; inc; cx:=a; ba:=true; inc; if xm then bcx-m:=false; end; writeln; end. 题目 :NOIP2016乌龟棋 问题编号 :599 题目描述 小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行 N 个格子，每个格子上一个分数。棋盘第 1 格是唯一的起点，第 N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 输入格式 输入文件的每行中两个数之间用一个空格隔开。 第 1 行 2 个正整数 N 和 M，分别表示棋盘格子数和爬行卡片数。 第 2 行 N 个非负整数， a1, a2, , aN，其中 ai 表示棋盘第 i 个格子上的分数。 15 / 29 第 3 行 M 个整数， b1,b2, , bM，表示 M 张爬行卡片上的数字。 输入数据保证到达终点时刚好用光 M 张爬行卡片，即 N?； 1= b_i 输出格式 输出只有 1 行， 1 个整数，表示小明最多能得到的分数。 【输入输出样例 1】 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1 【输入输出样例 2】 13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 1 1 1 1 1 2 4 1 【输入输出样例 1】 73 【输入输出样例 2】 455 当拿到这套题的时候，我首选做的这道题，完全可以把卡片费用，格子上分数作为物品； OK，动规出来了。可是动规方程该怎么办，费了好多的周折，甚至想到了把这16 / 29 两种物品从 新定义；甚至把格子个数作为费用，卡片作为物品，这样处理来求一个最大值想了好长 时间啊，但那样根本没办法进行动 规，因为卡片是有限的，还有一点要注意就是用了之后就 没了啊，想到这里，初思路了，注意题上就给四种卡片，我们可以设一个四维数组来一 个四维动规嘛，好吧！方程出来了： fi,j,k,l:=max,max)+ai+j*2+k*3+l*4+1; 它表示的是第一种卡片用 i 张，第二张卡片用 j张，第三张卡片用 k张，第四张卡片用 l 张 所取得的最大分数；接着是边界，这里要注意的是棋盘的第一个格子是起点，也就是当 f0,0,0,0时是等于第一个格子的分数的，来简单演示一下吧 1 3 1 2 1 1 31 21 也就是说， fI,j,k,l时也是格子数减一，那么ai+j*2+k*3+l*4+1就解释的通了；既是全部用 完也比格子数少一，况且我们还要拿第一个格子里的分数嘛； OK，出来 了，下面是 AC 程序； program p1068; var f:array-1.40,-1.40,-1.40,-1.40 of longint; b:array1.4 of longint; 17 / 29 a:array1.400 of longint; n,m,i,j,k,l:longint; function max:longint; begin if xy then max:=x else max:=y; end; begin readln; for i:=1 to n do read; readln; for j:=1 to m do begin read; inc; end; for i:=0 to b1 do for j:=0 to b2 do for k:=0 to b3 do for l:=0 to b4 do fi,j,k,l:=max,max)+ai+j*2+k*3+l*4+1; writeln; end. 题目 :NOIP2016关押罪犯 问题编号 :600 题目描述 S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1N。他们之间的关系自然也极不和谐。很18 / 29 多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。 每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表 ，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。 在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？ 【输入输出样例说明】 罪犯 之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 3512。其他任何分法都不会比这个分法更优。 【数据范围】 对于 30%的数据有 N 15。 19 / 29 对于 70%的数据有 N 2000， M 50000。 对于 100%的数据有 N 20000， M 100000。 输入格式 输入文件的每行中两个数之间用一个空格隔开。 第一行为两个正整数 N 和 M，分别表示罪犯的数目以及存在仇恨的罪犯对数。 接下来的 M 行 每行为三个正整数 aj， bj， cj，表示aj 号和 bj 号罪犯之间存在仇恨，其怨 气值为 cj。数据保证 1 输出格式 共 1 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。 样例输入 4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 样例输出 3512 恨死这道题了，哎，刚学的并查集，这里就是一个20 / 29 简单的应用吧；以前学长也介绍过这道 题；呵呵，单凭我的脑子几乎没有思路的，就像一次测验时把四道题都处理成动规，教训啊 这道题就算是对并查集的一个简单的应用吧，这里用到的是判断元素是否属于同一集合 这里附上简代码： 铺地毯 【问题描述】 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到 n。现在将这些地毯按照 编号从小到大的顺序平行于坐标轴先后铺设，后铺的地 毯覆盖在前面已经铺好的地毯之上。 地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形 地毯边界和四个顶点上的点也算被地毯覆盖。 【输入】 输入文件名为 。 输入共 n+2 行。 第一行，一个整数 n，表示总共有 n 张地毯。 接下来的 n 行中，第 i+1 行表示编号 i 的地毯的信息，包含四个正整数 a， b， g， k，每 两个整数之间用一个空格隔开，分别表示铺设地毯21 / 29 的左下角的坐标以及地毯在 x 轴和 y 轴方向的长度。 第 n+2 行包含两个正整数 x 和 y，表示所求的地面的点的坐标。 【输出】 输出文件名为 。 输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 -1。 【输入输出样例】 3 1 0 2 3 0 2 3 3 2 1 3 3 2 2 3 3 【解题报告】 从 后往前扫，找到第一个覆盖这个点的就输出，否则无解。 program carpet; 22 / 29 uses sysutils; var n,i,a,b:longint; x2,x1,y1,y2:array0.100001of longint; time:extended; procedure main; begin readln; for i:=1 to n do begin readln; x2i:=x1i+a; y2i:=y1i+b; end; readln; for i:=n downto 1 do if andandand then begin writeln; exit; end; writeln; end; 23 / 29 begin assign; reset; assign; rewrite; time:=now; /当前时间 main; writeln*24*3600:0:2);/输出程序运行时间 close; close; end. 选择客栈 【问题描述】 丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰，且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。 两位游客一起去丽江旅游，他们喜欢 相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间，且咖啡店的最低消费不超过 p。 24 / 29 他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。 【输入】 输入文件 ，共 n+1 行。 第一行三个整数 n， k， p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；接下来的 n 行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡 店的最低消费。 【输出】 输出文件名为 。 输出只有一行，一个整数，表示可选的住宿方案的总数。 【输入输出样例 1】 【输入输出样例说明】 2 人要住同样色调的客栈，所有可选的住宿方案包括：住客栈，但是若选择住 4、 5 号客栈的话， 4、 5 号客栈之间的咖啡店的最低消费是 4，而两人能承受的最低消费是 3 元，所以不满足要求。因此只有前3 种方案可选。 【数据范围】 25 / 29 对于 30%的数据，有 n 100； 对于 50%的数据，有 n 1,000； 对于 100%的数据，有 2 n 200,000， 0 【一句话题意】 合法区间 l,r定义： l,r的色调相同，且 l,r之间存在一个最低消费不超过 p。求合法区间总数。 【考察知识点】 二分查找 /枚举 ： O： 看完题目后不知所云，再多看几遍，一个 O 的算法有了一点雏形。 用两层循环枚举区间的左 右端点 l、 r，再用一层循环判断区间内是否有可行的咖啡店，累计即可。这个算法思维难度和编程难度都非常低，但是只能过 30%的数据，可以作为对拍程序备份。 ： O 再仔细思考，发现题中合法区间的限制条件其实很强。首先区间端点的色调必须相同，其次区间内必须要存在一个咖啡店最低消费不超过 P。 因此，如果我们用一层循环枚举左端点，并很快找到右端点的可行数，那么题目就能解决了。这里置答案为变量 ans，千万注意类型要为 int64 26 / 29 这里首先要用到区间部分和优化。设 sum i,j为前i 个客栈中，色调为 j的客栈总数，那么： sumi,j=sumi-1,j sumi,j=sumi-1,j+1 这里要用 O 的复杂度，是算法的瓶颈所在，不过对于题中的数据范围已经足够了。并且具体实现可以先用数组赋值 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+sumn,colorL-sumT-1,colorL 。 问题是我们如何找到这个 T，其实很简单，二分查找即 可。再次