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

NOIP 2013 解题报告


全国信息学奥林匹克联赛(NOIP2013)复赛

提高组 —解题报告

NOIP 2013 解题报告
BY DOVECL

Doveccl
第 0 页共 26 页

NOIP 2013 senior

Solution By Doveccl

/>提高组 day1
题目概况
中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限 传统 128M 转圈游戏 circle circle circle.in circle.out 1秒 10 10 有 火柴排队 match match match.in match.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 传统 128M 传统 128M 货车运输 truck truck truck.in truck.out 1秒 20 5 有

第 1 页共 26 页

NOIP 2013 senior

Solution By Doveccl

1.转圈游戏
(circle.cpp/c/pas) 【问题描述】 n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位 置编号,从 0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位 置,……,依此类推。 游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小 伙伴走到第 m+1 号位置,……,依此类推,第 n ? m 号位置上的小伙伴走到第 0 号位置, 第 n-m+1 号位置上的小伙伴走到第 1 号位置,……,第 n-1 号位置上的小伙伴顺时针走到第 m-1 号位置。 现在,一共进行了 10k 轮,请问 x 号小伙伴最后走到了第几号位置。 【输入】 输入文件名为 circle.in。 输入共 1 行,包含 4 个整数 n、m、k、x,每两个整数之间用一个空格隔开。 【输出】 输出文件名为 circle.out。 输出共 1 行,包含 1 个整数,表示 10k 轮后 x 号小伙伴所在的位置编号。 【输入输出样例】 circle.in 10 3 4 5 circle.out 5

【数据说明】 对于 30%的数据,0 < < 7; 对于 80%的数据,0 < < 107; 对于 100%的数据,1 < < 1,000,000 ,0 < < ,1 ≤ x ≤ n,0 < < 109。

第 2 页共 26 页

NOIP 2013 senior

Solution By Doveccl

【分析】 对于本题,不难推出,所求解即为 (m 10 k+x) mod n 然而对于 k≤109 ,显然暴力求解是不行的,有很大的超时风险 大概有两种做法: 1、求出循环节,然后用 k mod 循环节长度即可(长度必然不会超过 n) 2、使用快速幂算法,以下程序将使用快速幂求解

【代码】
#include <cstdio> typedef long long LL; int m,n,k,x; LL qmul(int p,int k) { LL temp=p,s=1; while(k!=0) { if(k%2==1) s=(s*(temp%n))%n; temp=(temp*temp)%n; k=k/2; } return s; } int main() { freopen("circle.in","r",stdin); freopen("circle.out","w",stdout); scanf("%d%d%d%d",&n,&m,&k,&x); printf("%I64d",(m*qmul(10,k)+x)%n); return 0; }

第 3 页共 26 页

NOIP 2013 senior

Solution By Doveccl

2.火柴排队
(match.cpp/c/pas) 【问题描述】 涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴 各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为: 其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。 每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离 最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个 最小交换次数对 99,999,997 取模的结果。 【输入】 输入文件为 match.in。 共三行,第一行包含一个整数 n,表示每盒中火柴的数目。 第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。第三 行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。 【输出】 输出文件为 match.out。 输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。 【输入输出样例 1】 match.in 4 2 3 1 4 3 2 1 4 【输入输出样例说明】 最小距离是 0,最少需要交换 1 次,比如:交换第 1 列的前 2 根火柴或者交换第 2 列 的前 2 根火柴。 【输入输出样例 2】 match.in match.out match.out 1 ,

第 4 页共 26 页

NOIP 2013 senior

Solution By Doveccl

4 1 3 4 2 1 7 2 4 【输入输出样例说明】

2

最小距离是 10,最少需要交换 2 次,比如:交换第 1 列的中间 2 根火柴的位置,再交 换第 2 列中后 2 根火柴的位置。 【数据范围】 对于 10%的数据, 1 ≤ n ≤ 10 ; 对于 30%的数据,1 ≤ n ≤ 100 ; 对于 60%的数据,1 ≤ n ≤ 1,000 ; 对于 100%的数据,1 ≤ n ≤ 100,000 ,0 ≤火柴高度≤ 231 ? 1。

【分析】 首先要思考,当出现什么情况时,才会有距离最小? 经分析后,不难发现,这其实就是一个贪心的思想: 设两列火柴分别为 a、b,不难发现,当 a 中第 i 大的数与 b 中第 i 大的数相对应时,距 离有最大值,这里不给出严格的证明过程,仅简单陈述:

距离的公式

? ( Ai ? Bi ) ? ? ( Ai
2 i ?1 i ?1
n i ?1

n

n

2

? Bi ) ? 2? AiBi
2 i ?1

n

欲求距离最小值,即是求

? AiBi 的最大值,这样推理过程就和去年的“国王游戏”

证明过程基本一样了,即 若a ? b, c ? d , 则有ac ? bd ? ad ? bc (a, b, c, d ? N*) 所以贪心得证。 然后就是分别排序两个数组,得到对应的关系。 例如 A:5 2 3 4 1 B:4 1 3 2 5 则可保持 A 不动,单独移动 B 中元素(不影响最优解) 在 A 中 5 对应 B 下标 5 ,2—4 ,3—3 ,4—1 ,1—2 。 现在需要解决的是,如何使(5、4、3、1、2)操作最少次数成为有序状态。
第 5 页共 26 页

NOIP 2013 senior

Solution By Doveccl

这就需要用到逆序对,最少操作次数即是逆序对数。 什么是逆序对呢? 在一个数组 A 中,如果 i>j 且 Ai>Aj ,则称(Ai,Aj)是一个逆序对 比如数组 A={4,1,3,2},有(4,1) , (4,3) , (4,2) , (3,2) 4 个逆序对。 求逆序对可以用定义法,双重循环搜索,O(n2) :
for(int i=1;i<n;i++) for(int j=i+1;i<=n;j++) if(a[i]>a[j]) ans++;

效率在 n 较大时显得十分低下。 目前有两个通行的逆序对求法,复杂度 O(n log2n) 1、利用 BIT,线段树 或其他各种 BST 2、使用归并排序 在这里,介绍归并排序的求法: 在合并两个有序数组时(A 和 B) ,若有 Ai>Bj ,则 Ai+1>Bj …… Aend>Bj 由此我们只需要在 merge 中加几句话即可解决问题。 【代码】
#include <cstring> #include <cstdio> #include <algorithm> #define MaxN 100010 #define mod 99999997 using namespace std; typedef long long LL; int a[MaxN],b[MaxN],temp[MaxN],aa[MaxN],bb[MaxN]; inline void qs(int *x,int *y,int l,int r) { int i=l,j=r,m=x[(l+r)>>1]; while(i<=j) { while(x[i]<m)i++; while(x[j]>m)j--; if(i<=j) { swap(x[i],x[j]); swap(y[i++],y[j--]); } } if(i<r) qs(x,y,i,r); if(j>l) qs(x,y,l,j); } inline LL merge(int *a,int l,int m,int r,int *b) { int i=l,k=l,j=m+1; LL sum=0; memcpy(b+l,a+l,sizeof(int)*(r-l+1)); while(i<=m&&j<=r) {
第 6 页共 26 页

NOIP 2013 senior

Solution By Doveccl

if(b[i]<=b[j]) a[k++]=b[i++]; else { a[k++]=b[j++]; sum+=(m-i+1); sum%=mod; } } while(i<=m) a[k++]=b[i++]; while(j<=r) a[k++]=b[j++]; return sum; } inline LL merge_sort(int *a,int l,int r,int *b) { LL sum=0; if(l<r) { int m=(l+r)>>1; sum+=merge_sort(a,l,m,b); sum+=merge_sort(a,m+1,r,b); sum+=merge(a,l,m,r,b); sum%=mod; } return sum; } int main() { freopen("match.in","r",stdin); freopen("match.out","w",stdout); int n,i; LL sum; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]), aa[i]=i; for(i=1;i<=n;i++) scanf("%d",&b[i]), bb[i]=i; qs(a,aa,1,n); qs(b,bb,1,n); for(i=1;i<=n;i++) b[aa[i]]=bb[i]; sum=merge_sort(b,1,n,temp); printf("%I64d",sum); return 0; }

第 7 页共 26 页

NOIP 2013 senior

Solution By Doveccl

3.货车运输
(truck.cpp/c/pas) 【问题描述】 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有 重量限制,简称限重。现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限 重的情况下,最多能运多重的货物。 【输入】 输入文件名为 truck.in。 输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道 路。 接下来 m 行每行 3 个整数 x、y、z,每两个整数之间用一个空格隔开,表示从 x 号城 市到 y 号城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。 接下来一行有一个整数 q,表示有 q 辆货车需要运货。 接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市 运输货物到 y 城市,注意:x 不等于 y。 【输出】 输出文件名为 truck.out。 输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货 车不能到达目的地,输出-1。 【输入输出样例】 truck.in 4 3 1 2 4 2 3 3 3 3 1 1 1 1 1 3 4 3 truck.out 3 -1 3

【数据说明】
第 8 页共 26 页

NOIP 2013 senior

Solution By Doveccl

对于 30%的数据,0 < < 1,000,0 < < 10,000 ,0 < < 1,000; 对于 60%的数据,0 < < 1,000,0 < < 50,000 ,0 < < 1,000; 对于 100%的数据,0 < < 10,000 ,0 < < 50,000,0 < < 30,000,0 ≤ z ≤ 100,000 。

【分析】 还真的误以为这道题要写树链剖分,其实并没有这么麻烦,因为这毕竟只是 NOIP 的题 目。 在考场上时基本上都能想到最大生成树,即把边权从大到小排序,顺次取出每一条边, 然后建图(注意不能成为环图) 。 此时城市的交通网就变成了一棵树,可以证明,这棵树中任意两个节点只可能有一条通 路,并且这条通路上边权的最小值即为答案。 现在麻烦的地方就在于如何实现快速的查询,我们先假定所有边都在一棵树中,那么就 变成了查询两个点的最近公共祖先(LCA) ,暴力 LCA 就不用说什么了,预计得分 60 分,并且如果给定的原图不是连通图,那么生成树就不只一棵。 那么大部分人写的都是树上倍增法在线求 LCA,并且答案是由与 LCA 通路中的边权最小 值得出。 当然,我用的不是裸的 LCA 解决问题,一般的 LCA 建图方式是把与边相连的两个节点 定义为父子关系,所以同时也带来了查询上的不便,其实我们可以巧妙地将 LCA 问题变 成一个 RMQ 问题,并且最终由 LCA 实现。 具体方式: 用并查集维护最大生成树,将边作为两个相邻节点的父节点,整张图建立下来是二叉 树。例如样例:

E 2 ( 权值为 3)

E1 ( 权值为 4)

V4

V1

V2

V3

其实答案就已经很明显了。 具体讲解,详见 RMQ&LCA 问题(湖南省长郡中学 郭华阳) :
第 9 页共 26 页

NOIP 2013 senior

Solution By Doveccl

http://wenku.baidu.com/view/98cf2e6baf1ffc4ffe47acf2.html 那么这道题就和水管局长就基本是一样的了,在这里我采用离线的 tarjan_LCA 方式实现 求解,只需记录每个解所对应的问题编号顺次输出即可。 【代码】
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #define clean(x,y) memset(x,y,sizeof(x)) #define MaxN 20010 #define MaxM 50010 #define MaxQ 30010 using namespace std; int n,m,q; struct edge { int x,y,w; inline void read() { scanf("%d%d%d",&x,&y,&w); } }e[2*MaxM]; bool cmp(edge x,edge y) { return x.w>y.w; } int f[2*MaxN]; inline void InitUFS(int n) { for(int i=1;i<=n;i++) f[i]=i; } int find(int x) { if(f[x]!=x) f[x]=find(f[x]); return f[x]; } inline void link(int a,int b) { f[find(a)]=find(b); } int QuesNum[MaxN]; struct ques { int v,id; ques(int op,int _id):v(op),id(_id){}; }; vector<ques> Q[MaxN]; int ans[MaxQ]; int a[2*MaxN],l[2*MaxN],r[2*MaxN]; int indegree[2*MaxN]; bool v[2*MaxN]; void dfs(int x) { if(!x) return; int y,id;
第 10 页共 26 页

NOIP 2013 senior

Solution By Doveccl

f[x]=x; for(int i=0;i<QuesNum[x];i++) { y=Q[x][i].v; id=Q[x][i].id; if(v[y]) ans[id]=a[find(y)]; } v[x]=1; dfs(l[x]); f[l[x]]=x; dfs(r[x]); f[r[x]]=x; } inline void init() { int x,y; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) e[i].read(); scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%d%d",&x,&y); QuesNum[x]++; Q[x].push_back(ques(y,i)); QuesNum[y]++; Q[y].push_back(ques(x,i)); } } inline void work() { int x,y,num=n; InitUFS(2*n); sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++) { x=e[i].x; y=e[i].y; if(find(x)!=find(y)) a[++num]=e[i].w, l[num]=f[x], r[num]=f[y], indegree[f[x]]++, indegree[f[y]]++, link(f[x],num), link(f[y],num); } clean(ans,-1); InitUFS(num); for(int i=n+1;i<=num;i++) if(!indegree[i]) clean(v,0), dfs(i); for(int i=1;i<=q;i++) printf("%d\n",ans[i]); } int main() { freopen("truck.in","r",stdin);
第 11 页共 26 页

NOIP 2013 senior

Solution By Doveccl

freopen("truck.out","w",stdout); init(); work(); return 0; }

第 12 页共 26 页

NOIP 2013 senior

Solution By Doveccl

提高组 day2
题目概况
中文题目名称 英文题目与子目录 名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限 积木大赛 block block block.in block.out 1秒 10 10 有 传统 128M 花匠 flower flower flower.in flower.out 1秒 10 10 有 传统 128M 华容道 puzzle puzzle puzzle.in puzzle.out 1秒 20 5 有 传统 128M

全文比较(过滤行末空格及文末回车)

第 13 页共 26 页

NOIP 2013 senior

Solution By Doveccl

1.积木大赛
(block.cpp/c/pas)

【题目描述】 春春幼儿园举办了一年一度的“积木大赛” 。今年比赛的内容是搭建一座宽度为 的大厦,大厦可以看成由 块宽度为 的积木组成,第 块积木的最终高度需要是 ? 。 在搭建开始之前,没有任何积木(可以看成 块高度为 0 的积木) 。接下来每次操作, 小朋友们可以选择一段连续区间[ , ],然后将第 块到第 块之间(含第 L 块和第 R 块)所有积木的高度分别增加 。 小 是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次 数最少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少 的操作次数。

【输入】 输入文件为 block.in 输入包含两行,第一行包含一个整数 ,表示大厦的宽度。 第二行包含 个整数,第 个整数为 ? 。 【输出】 输出文件为 block.out 仅一行,即建造所需的最少操作数。

【输入输出样例】 block.in 5 23412 block.out 5

【样例解释】 其中一种可行的最佳方案,依次选择 [1,5] [1,3] [2,3] [3,3] [5,5] 【数据范围】 对于 30% 的数据,有 1 ≤ ≤ 10;
第 14 页共 26 页

NOIP 2013 senior

Solution By Doveccl

对于 70% 的数据,有 1 ≤ ≤ 1000; 对于 100% 的数据,有 1 ≤ ≤ 100000,0 ≤ ? ≤ 10000。

【分析】 这一道题开始时容易想到用分治来做,每次在给定的区间里寻找最小值,然后对答案执 行操作 ans+=min ,接下来递归分治,当时竞赛时即是这么写的,从数据范围来看,只 能拿到 70%的分数,而可能由于 NOIP 测试数据是随机生成的,所以复杂度会退化,仍 能 AC,如果 NOIP 卡暴力的话,可以将数据设计成形似 /\ 的“金字塔形” ,这样暴力就 很难过了。 分治代码就不贴了。 其实较优的算法是线性算法,复杂度为 O(n) 在一个序列中,起伏是最常见不过的事,例如 \/\/\____/\/\/\/\____/\/\/\/\/\/\/\/\___/\/\/\/\/\/\(一般情况) ,对于子序列 /\ (左升右 降型) ,不难看出需要搭建最少 Hmax-Hmin 次,证明就不需要了吧!单调递增递减都有这 样的规律,所以最后的工作即是统计每一个这样的区间所需的步数(当然需要判重,毕 竟有形如 _^^^^^^_ 的区间) 具体讲一下简洁的思路,读入每个点时判断它是否比前一个点高,如果是,则需要将答 案数增加上他们的高度差(因为还要向上搭建) ,否则不用管它。 这样做的好处是自动将两个公共区间的最低点去重步骤给省掉了,非常简便。 【代码】
#include <cstdio> int x=0,y,ans=0; int main() { freopen("block.in","r",stdin); freopen("block.out","w",stdout); scanf("%d",&y); while(~scanf("%d",&y)) { if(y>x) ans+=y-x; x=y; } printf("%d",ans); return 0; }

第 15 页共 26 页

NOIP 2013 senior

Solution By Doveccl

2.花匠
(flower.cpp/c/pas) 【问题描述】 花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋 栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大, 同时,栋栋希望剩下的花排列得比较别致。 具体而言,栋栋的花的高度可以看成一列整数 ?1, ?2, … , ? 。设当一部分花被移走 后,剩下的花的高度依次为 1, 2, … , ,则栋栋希望下面两个条件中至少有一个满 足:条件 A:对于所有的 , 2 > 2 ?1 ,且 2 > 2 +1 ;条件 B:对于所有的 , 2 < 2 ?1 ,且 2 < 2 +1 。 注意上面两个条件在 = 1 时同时满足,当 > 1 时最多有一个能满足。 请问,栋栋最多能将多少株花留在原地。

【输入】 输入文件为 flower.in。 输入的第一行包含一个整数 ,表示开始时花的株数。 第二行包含 个整数,依次为 ?1, ?2,… , ? ,表示每株花的高度。

【输出】 输出文件为 flower.out。 输出一行,包含一个整数 ,表示最多能留在原地的花的株数。

【输入输出样例】 flower.in 5 5 3 2 1 2 【输入输出样例说明】 有多种方法可以正好保留 3 株花,例如,留下第 1、4、5 株,高度分别为 5、1、 2,满足条件 B。 flower.out 3

【数据范围】 对于 20% 的数据, ≤ 10; 对于 30% 的数据, ≤ 25;
第 16 页共 26 页

NOIP 2013 senior

Solution By Doveccl

对于 70% 的数据, ≤ 1000,0 ≤ ? ≤ 1000; 对于 100% 的数据,1 ≤ ≤ 100,000,0 ≤ ? ≤ 1,000,000,所有的 ? 随机生成,所 有随机数服从某区间内的均匀分布。

【分析 1】 抽象一下此题的模型,稍微动一下脑筋,就不难推出,题目的意思是让我们求“最长波 动子序列” ,实际上就可以用线性动规求解。 首先说明一下, “最长波动子序列”是形如“/\/\/\/\/\/\”或“\/\/\/\/\/\”或 “/\/\/\/\/\/\/”或“\/\/\/\/\/\/\/”的序列(注意,只在转折点上有节点) 首先说一下朴素的动规思想:
if(h[i]>h[j]) f[i]=max(f[i],g[j]+1); else if(h[i]<h[j]) g[i]=max(g[i],f[j]+1);

f 是当前点作为最高点时最优解,g 是当前点作为最低点时的最优解。 该算法 O(n2),对于题目所给的数据范围,只能拿 70%的分。 于是我们必然会想到如何降低复杂度: 考虑到我们每次取最值时候取得都是一个区间里的数,所以可以使用线段树或者是 BIT 抑或是 BST 来优化,这样复杂度就是 O(n log2n),可以过全部数据。 【代码 1】(By GreenCloudS) (DP with BIT)
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define MAXN 100010 #define lowbit(x)(((~(x))+1)&x) #define MAXH 1000010 #define For(i,x) for (int i=x;i;i-=lowbit(i)) #define rep(i,x) for (int i=x;i<=maxh;i+=lowbit(i)) int t0[MAXH],t1[MAXH]; int h[MAXN],n,maxh=0; int f[MAXN][2],ans=0; void Add0(int x,int y) { rep(i,x) t0[i]=max(t0[i],y); } void Add1(int x,int y) { rep(i,x) t1[i]=max(t1[i],y); } int Max0(int x) { int rec=0; For(i,x) rec=max(rec,t0[i]); return rec; } int Max1(int x) {
第 17 页共 26 页

NOIP 2013 senior

Solution By Doveccl

int rec=0; For(i,x) rec=max(rec,t1[i]); return rec; } int main() { scanf("%d",&n); for (int i=0;i++<n;) { scanf("%d",&h[i]); maxh=max(maxh,++h[i]); f[i][0]=f[i][1]=1; } maxh++; memset(t0,0,sizeof(t0)),memset(t1,0,sizeof(t1)); for (int i=0;i++<n;) { f[i][0]=max(Max0(h[i]-1)+1,f[i][0]); f[i][1]=max(Max1(maxh-h[i]-1)+1,f[i][1]); Add0(h[i],f[i][1]),Add1(maxh-h[i],f[i][0]); ans=max(ans,max(f[i][0],f[i][1])); } printf("%d\n",ans); return 0; }

【分析 2】 其实再进一步分析,发现问题可以简化成为求转折点数的问题,又是一个 O(n) 【代码 2】
#include <cstdio> int n,i,x=0,y,ans=1,flag=0; int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); scanf("%d%d",&n,&x); for(i=1;i<n;i++) { scanf("%d",&y); if(y>x&&flag!=1) ans++, flag=1; if(y<x&&flag!=-1) ans++, flag=-1; x=y; } printf("%d",ans); return 0; }

第 18 页共 26 页

NOIP 2013 senior

Solution By Doveccl

3.华容道
(puzzle.cpp/c/pas) 【问题描述】 小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。 于是,他想到用编程来完成华容道:给定一种局面,华容道是否根本就无法完成,如 果能完成,最少需要多少时间。 小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的:
1. 在一个 n*m 棋盘上有 n*m 个格子,其中有且只有一个格子是空白的,其余

n*m-1 个格子上每个格子上有一个棋子,每个棋子的大小都是 1*1 的;
2. 有些棋子是固定的,有些棋子则是可以移动的; 3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格

子上。 游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的,但是 棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不 同。第 i 次玩的时候,空白的格子在第 EXi 行第 EYi 列,指定的可移动棋子的初始位置 为第 SXi 行第 SYi 列,目标位置为第 TXi 行第 TYi 列。 假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。 请 你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。 【输入】 输入文件为 puzzle.in。 第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n、m 和 q; 接下来的 n 行描述一个 n*m 的棋盘,每行有 m 个整数,每两个整数之间用一个空 格隔开,每个整数描述棋盘上一个格子的状态,0 表示该格子上的棋子是固定的,1 表示该格子上的棋子可以移动或者该格子是空白的。 接下来的 q 行,每行包含 6 个整数依次是 EXi 、EYi 、SXi 、SYi 、TXi 、TYi,每两 个整数之间用一个空格隔开,表示每次游戏空白格子的位置,指定棋子的初始位置和 目标位置。

【输出】 输出文件名为 puzzle.out。 输出有 q 行,每行包含 1 个整数,表示每次游戏所需要的最少时间,如果某次游戏无 法完成目标则输出?1。

第 19 页共 26 页

NOIP 2013 senior

Solution By Doveccl

【输入输出样例】 puzzle.in 3 0 0 0 3 1 4 1 1 1 2 2 2 1 1 0 1 2 1 0 0 2 2 2 2 3 2 puzzle.out 2 -1

【输入输出样例说明】 棋盘上划叉的格子是固定的,红色格子是目标位置,圆圈表示棋子,其中绿色圆 圈表示目标棋子。
1. 第一次游戏,空白格子的初始位置是 (3, 2)(图中空白所示) ,游戏的目标是将 初始位置在(1, 2)上的棋子(图中绿色圆圈所代表的棋子)移动到目标位置(2, 2)(图中 红色的格子)上。

移动过程如下:

O OO
2.

OOO

第二次游戏,空白格子的初始位置是(1, 2) (图中空白所示) ,游戏的目标是 将初始位置在(2, 2)上的棋子(图中绿色圆圈所示)移动到目标位置 (3, 2)上。 初始状态

O O

O O O
要将指定块移入目标位置,必须先将空白块移入目标位置,空白块要移动到目标 位置,必然是从位置(2,2)上与当前图中目标位置上的棋子交换位置,之后能与空
第 20 页共 26 页

NOIP 2013 senior

Solution By Doveccl

白块交换位置的只有当前图中目标位置上的那个棋子,因此目标棋子永远无法走到它 的目标位置,游戏无法完成。

【数据范围】 对于 30% 的数据,1 ≤ n, m ≤ 10,q = 1;对 于 60% 的数据,1 ≤ n, m ≤ 30,q ≤ 10;对 于 100% 的数据,1 ≤ n, m ≤ 30,q ≤ 500

【分析】 考场上遇到这种题,就只能呵呵了,下面开始搬运 GreenCloudS 题解: 这道题的数据范围是 n≤30,所以,我们可以看到,裸的 O(n4 ) 的 BFS 对于求解 q 较小 的情况是无压力的,但是在 q 大的情况下,毫无疑问会 TLE,明显,在 q 较大的情况 下,我们需要将每次 BFS 中重复搜索的冗余信息除去,所以我们可以先分析题目性质: (这里称要移动的棋子为目标棋子) 首先,如果要移动目标棋子,那么我们首先必须要将空格移到该棋子的上下左右四个方 向上相邻位置之一,然后才可以移动该棋子。 然后,我们分析该棋子移动时候的性质: 棋子每次可以移动,仅当空格位于其相邻位置的时候,每次移动完棋子,空格总会在棋 子相邻的位置,那么我们发现,对于棋子在某一位置,然后空格又在其四个方向上某一 相邻位置时,棋子要想某一方向移动一个时的花费的步数是一定的,那么,就可以先进 行一次预处理,预处理出对于目标棋子在上述条件下每次移动所需的步数。 然后,预处理完成之后,我们会发现每次查询都会变成一个求最短路的问题,用 Dijstra 或 SPFA 的话,可以在时限范围内解决。 实现: 定义一个数组 Step[x][y][k][h] ,表示目标棋子在位置(x,y)且空格在目标棋子的 k 方 向上的相邻格子时,目标棋子往 h 方向移动 1 格所需的步数,然后用状态[x][y][k]作为 节点建图,用各个状态的关系连边,每次询问时重新定义一个源点跟终点,跑最短路就 可以得出答案。( 预处理时跑 n2 次 O(n2)的 BFS 就可以了) 复杂度(Dijstra) :O(n4+n2 log2n) 复杂度(SPFA) :O(n4+n2) 其实 wjk 大神在考场上的 BFS 就已经有 70 分了,并且他用的是纯 BFS,稍稍加了一些 剪枝。 下面给出两份代码,一份是 wjk 考场原作 (TLE) 另一份是基于某题解的代码修改版 (AC)
第 21 页共 26 页

NOIP 2013 senior

Solution By Doveccl

【代码 1】
program puzzle; const maxn=31; maxq=810000; type node=record x1,y1,x2,y2,s:longint; end; var v:array[0..maxn,0..maxn,0..maxn,0..maxn] of boolean; a:array[0..maxn,0..maxn] of boolean; q:array[0..maxq] of node; dx:array[1..4] of longint=(0,1,0,-1); dy:array[1..4] of longint=(1,0,-1,0); i,j,k,n,m,p,x1,y1,x2,y2,x3,y3,head,tail:longint; procedure work; var i,j,k,x,y,s,xx,yy,xxx,yyy,cnt,newx,newy:longint; now:node; begin if (x2=x3)and(y2=y3) then begin writeln(0); exit; end; cnt:=0; for i:=1 to 4 do begin x:=x3+dx[i]; y:=y3+dy[i]; if a[x,y] then inc(cnt); end; if cnt<=1 then begin writeln(-1); exit; end; cnt:=0; xx:=0; yy:=0; for i:=1 to 4 do begin x:=x2+dx[i]; y:=y2+dy[i]; if a[x,y] then begin inc(cnt); xx:=x; yy:=y; end; end; if (cnt<=1)and((x3<>xx)or(y3<>yy)) then begin writeln(-1); exit; end; fillchar(v,sizeof(v),0); head:=0; tail:=1; q[1].x1:=x1; q[1].y1:=y1; q[1].x2:=x2; q[1].y2:=y2; q[1].s:=0; v[x1,y1,x2,y2]:=true;
第 22 页共 26 页

NOIP 2013 senior

Solution By Doveccl

while head<tail do begin inc(head); now:=q[head]; s:=now.s; x:=now.x1; y:=now.y1; xx:=now.x2; yy:=now.y2; for i:=1 to 4 do begin xxx:=xx; yyy:=yy; newx:=x+dx[i]; newy:=y+dy[i]; if not a[newx,newy] then continue; if (newx=xxx)and(newy=yyy) then begin xxx:=x; yyy:=y; end; if (xxx=x3)and(yyy=y3) then begin writeln(s+1); exit; end; if not v[newx,newy,xxx,yyy] then begin inc(tail); q[tail].x1:=newx; q[tail].y1:=newy; q[tail].x2:=xxx; q[tail].y2:=yyy; q[tail].s:=s+1; v[newx,newy,xxx,yyy]:=true; end; end; end; writeln(-1); end; begin assign(input,'puzzle.in'); reset(input); assign(output,'puzzle.out'); rewrite(output); fillchar(a,sizeof(a),false); readln(n,m,p); for i:=1 to n do begin for j:=1 to m do begin read(k); if k=1 then a[i,j]:=true; end; readln; end; for i:=1 to p do begin readln(x1,y1,x2,y2,x3,y3); work; end; close(input); close(output);
第 23 页共 26 页

NOIP 2013 senior

Solution By Doveccl

end.

【代码 2】
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #define MaxN 35 using namespace std; const int INF=~0U>>2, dx[]={0,0,-1,1}, dy[]={-1,1,0,0}; int mat[MaxN][MaxN],dis[MaxN][MaxN][4]; int step[MaxN][MaxN][4][4]; int d[MaxN][MaxN]; int n,m,q,test,ex,ey,sx,sy,tx,ty; struct node { int x,y; }; struct node2 { int x,y,k; }; bool inside(int x, int y) { return (x>=1&&x<=n&&y>=1&&y<=m); } int spfa() { queue<node2> q; while(!q.empty()) q.pop(); for(int k=0;k<4;k++) if(dis[sx][sy][k]!=INF) q.push((node2){sx,sy,k}); while(!q.empty()) { int x=q.front().x; int y=q.front().y; int k=q.front().k; q.pop(); for(int i=0;i<4;i++) { int _x=x+dx[i]; int _y=y+dy[i]; if(inside(_x,_y)) if(mat[_x][_y]) if(step[x][y][k][i]!=INF) if(dis[_x][_y][i^1]>dis[x][y][k]+step[x][y][k][i]+1) { dis[_x][_y][i^1]=dis[x][y][k]+step[x][y][k][i]+1; q.push((node2){_x,_y,i ^ 1 }); } } } int ans=INF;
第 24 页共 26 页

NOIP 2013 senior

Solution By Doveccl

for(int i=0;i<4;i++) if(dis[tx][ty][i]<ans) ans=dis[tx][ty][i]; return (ans==INF)? -1:ans; } int bfs(int sx,int sy,int tx,int ty) { if(!mat[sx][sy]) return INF; if(!mat[tx][ty]) return INF; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) d[i][j]=INF; d[sx][sy]=0; queue<node> q; while(!q.empty()) q.pop(); q.push((node){sx,sy}); while(!q.empty()) { if(d[tx][ty]!=INF) return d[tx][ty]; int x=q.front().x; int y=q.front().y; q.pop(); for(int i=0;i<4;i++) { int _x=x+dx[i]; int _y=y+dy[i]; if(inside(_x,_y)) if(mat[_x][_y]&&d[_x][_y]==INF) { d[_x][_y]=d[x][y]+1; q.push((node){_x,_y}); } } } return INF; } void init() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int v=mat[i][j]; mat[i][j]=0; for (int k=0;k<4;k++) for (int l=0;l<4;l++) step[i][j][k][l]=bfs ( i+dx[k],j+dy[k], i+dx[l],j+dy[l] ); mat[i][j]=v; } } int getAns() { scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty); if(sx==tx&&sy==ty)
第 25 页共 26 页

NOIP 2013 senior

Solution By Doveccl

return 0; if(sx==ex&&sy==ey) return -1; if(!inside(ex,ey)||!inside(sx,sy)||!inside(tx,ty)) return -1; if(!mat[ex][ey]||!mat[sx][sy]||!mat[tx][ty]) return -1; for(int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=0;k<4;k++) dis[i][j][k]=INF; mat[sx][sy]=0; for(int k=0;k<4;k++) dis[sx][sy][k]=bfs(ex,ey,sx+dx[k],sy+dy[k]); mat[sx][sy]=1; return spfa(); } int main() { freopen("puzzle.in","r",stdin); freopen("puzzle.out","w",stdout); scanf("%d%d%d",&n,&m,&test); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mat[i][j]); init(); while(test--) printf("%d\n",getAns()); return 0; }

感谢: GreenCloudS 的题解:http://wenku.baidu.com/view/86b0a347a98271fe910ef9ef.html KQZXCMH 的题解:http://blog.csdn.net/kqzxcmh/article/details/17127627

上述 CPP code 下载地址(含测试数据) :http://pan.baidu.com/s/1o6yiw5O

第 26 页共 26 页


相关文章:
CCF NOIP2013 解题报告&心得
CCF NOIP2013 解题报告&心得_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 CCF NOIP2013 解题报告&心得_学科竞赛_高中教育_教育专区。全国信息...
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告 (普及组)宁波市镇海蛟川书院 郁庭 第一题:记数(count) 【分析】直接用最朴素的模拟来做,时间复杂度小于(...
NOIP2013复赛模拟8解题报告
NOIP2013复赛模拟8解题报告_学科竞赛_高中教育_教育专区。NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟试题 4(4P36) [题目描述]...
Noip_2013_提高组_Day2_解题报告
Noip_2013_提高组_Day2_解题报告_计算机软件及应用_IT/计算机_专业资料。第二题:花匠(动态规划) 1.令 S[i][1]表示以 i 为结尾, 且降序到达 a[i]的最长...
Noip 2013 提高组 Day2 解题报告
Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告 Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛...
NOIP2013复赛模拟8解题报告
NOIP2013复赛模拟8解题报告_韩语学习_外语学习_教育专区。NOIP2013复赛模拟8解题报告 NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟...
Pascal 2013解题报告和心得文档
Pascal 2013解题报告和心得文档_调查/报告_表格/模板_实用文档。搞笑心得!!!计数...如果读者尝试过NOIp2005 提高组《等价表 达式》, 那么这道题目其实非常轻松。 ...
NOIP2013普及组第二题解题报告(汇文客原创)
NOIP2013普及组第二题解题报告(汇文客原创)_学科竞赛_初中教育_教育专区。2.表达式求值 (expr.cpp/c/pas) 【问题描述】 给定一个只包含加法和乘法的算术表达式...
NOIP2014普及组解题报告
NOIP2014 普及组复赛解题报告本人是潍坊一中的 wyw,69 级,今年高一, 现在马上...当时我正是由于 重视(2013 年第一题爆零的教训),用了整整 15 分钟才做好,...
NOIP经典之祖玛解题报告
Zuma 解题报告 ZUMA(祖玛问题) ZUMA(祖玛问题)解题报告【SOURCE】2010NOIP ...Noip 2013 Day1 解题报告... 8页 免费 NOIP基本程序题集解题报... 21页 ...
更多相关标签:
noip2016解题报告 | noip2015解题报告 | noip2015day2解题报告 | noip2016复赛解题报告 | noip2014解题报告 | noip2015复赛解题报告 | noip2013提高组复赛 | noip2013普及组复赛 |