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

CCF NOIP2013 解题报告&心得


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

提高组 day1

CCF NOIP2013 解题报告&心得
虽然已经过去很久了, 但是终于有机会有时间写一下解题 报告 ——By 黄锦松 FJ-0318 泉州五中
NOIP 2013 成绩单
姓名 准考证号 总分 circle match truck

block flower 100 10 0 10 100 puzzle 5 黄锦松 FJ-0318 225

我拿到了 225 分,坑爹地传错了一题, ( 还是最简单的 Day2 的 block,我的 100 分啊!!,在我大福建只有三等奖, !) 即使全国省一等奖基准线只有 200, 今年的分数线变高了, 我欣喜中国未来的计算机产业的良好发展势头。 我只是其 中微不足道的一员,我觉得我是一个奇怪的人,别人都是 数学+信息,我是化学+信息。我觉得我大学应该是会去读 化学了,信息产业的舞台就留给大家去表演了。

第1 页共4 页

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

提高组 day1

切入正题******

CCF

全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 (请选手务必仔细阅读本页内容)

一.题目概况 中文题目名称 英文题目与子目录 名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限

转圈游戏 火柴排队 货车运输 circ matc tru le h ck circ matc tru le h ck circle.in match.in truck.in circle.out match.out truck.out 1 1 1 秒 秒 秒 10 10 20 10 10 5 有 有 有 全文比较(过滤行末空格及文末回车) 传 传 传 统 统 统 128M 128M 128M

二.提交源程序文件名 对于 C++语言 circle.cpp 对于 C 语言 circle.c 对于 pascal 语言 circle.pas

match.cpp match.c match.pas

truck.cpp truck.c truck.pas

三.编译命令(不包含任何优化开关) 对于 C++语言 g++ -o g++ -o match circle match.cpp -lm 对于 C 语言 circle.cp gcc-o circle gcc-o match pcircle.c -lm match.c – 对于 pascal 语 fpc -lm fpc lm match.pas 言 circle.pas

g++ -o truck truck.cpp gcc-o truck -lm truck.c fpc -lm truck.pas

注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、 C/C++中函数 main()的返回值类型必须是 int, 程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+,
第2 页共4 页

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

提高组 day1

2.71GHz,内存 2G,上述时限以此配置为准。 4、只提供 Linux 格式附加样例文件。 5、特别提醒:评测在 NOI Linux 下进行。

第3 页共4 页

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

提高组 day2

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 < k < 7; 对于 80%的数据,0 < k < 107; 对于 100%的数据,1 < n< 1,000,000,0 <m <n ,0 ≤ x ≤ n,0 < k< 109。 对于转圈游戏(快速幂) 根据题目,答案明显是(x+10^km) mod n,化简一下,就成了(x + m (10^k mod n) mod n) mod n,所以,只需要求出 10^k mod n 即可,可以使用快速幂来求解,复杂度 O(log k)。 本人代码(100 分) var n,m,k,x,g,t,r,i:longint; a:array[0..1000000]of longint; begin assign(input,'circle.in'); reset(input); assign(output,'circle.out'); rewrite(output);
第1 页共5 页

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

提高组 day2

readln(n,m,k,x); g:=k; t:=0; while g<>0 do begin inc(t); a[t]:=g mod 2; g:=g div 2; end; r:=1; for i:=t downto 1 do begin k:=(r*r) mod n; if a[i]<>0 then r:=((10*k)mod n)mod n else r:=k; end; for i:=1 to r do x:=(x+m)mod n; writeln(x); close(input); close(output); end.

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

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

提高组 day2

【输入输出样例 1】 match.in 4 2 3 1 4 3 2 1 4

match.out 1

【输入输出样例说明】 最小距离是 0,最少需要交换 1 次,比如:交换第1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。 【输入输出样例 2】 match.in 4 1 3 4 2 1 7 2 4 【输入输出样例说明】 最小距离是 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。 对于火柴排队(贪心+逆序对) 对距离公式化简得: ∑(ai-bi)^2=∑(ai^2-2aibi+bi^2)=∑ai^2+∑bi^2-2∑aibi 要求∑(ai-bi)^2 最 小,就只需要∑aibi 最大即可。这里有个贪心,当 a1<a2<…<an,b1<b2<..<bn 时, ∑aibi 最大。证明如下: 若存在 a>b,c>d,且 ac+bd<ad+bc,则 a(c-d)<b(c-d),则 a<b,与 a>b 矛盾,所以若 a>b,c>d,则 ac+bd>ad+bc 将此式子进行推广: 当 a1<a2<a3<...<an ,b1<b2<...<bn 的情况下∑aibi 最大,即∑(ai-bi)^2 最小。 然后,将两个序列分别排序,确定每对数的对应关系,明显,同时移动两个序列中 的数等效于只移动一个序列中的数,那么,我们就保持一个序列不动,然后根据另 外那个序列中的数对应的数的位置,重新定义一个数组,求逆序对个数,就是答案。 PS. 在求逆序对的时候我用了堆牌,然后忘记怎么计数了,坑了好久还是没弄出来, 最后用了变形冒泡,结果连变形冒泡都打错。。 。 本人代码(10 分) const fuck=99999997;
第3 页共5 页

match.out 2

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

提高组 day2

var n,i,j,ans,t:longint; a,b,c:array[0..100000]of longint; {procedure work(l,m,r:longint); var left,count,mid:longint; begin left:=l; mid:=m+1; count:=l; if ((left>=m)or(mid>r))and (count<=r) then begin b[left]:=b[mid]; inc(count); inc(left); end else begin ans:=(ans+m-left+1)mod fuck; b[mid]:=b[r]; inc(count); end; end; procedure pp(l,r:longint); var m:longint; begin m:=(l+r)div 2; while l<m do pp(l,m); while r>m do pp(m,r); work(l,m,r); end;} procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i); while x<a[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; y:=b[i]; b[i]:=b[j]; b[j]:=y; inc(i); dec(j); end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; begin
第4 页共5 页

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

提高组 day2

assign(input,'match.in'); reset(input); assign(output,'match.out'); rewrite(output); readln(n); ans:=0; for i:=1 to n do begin read(a[i]); b[i]:=i; end; sort(1,n); for i:=1 to n do c[i]:=b[i]; for i:=1 to n do begin read(a[i]); b[i]:=i; end; sort(1,n); for i:=1 to n do for j:=1 to n do if b[i]=c[j] then begin b[i]:=j; break; end; //pp(1,n); for i:=1 to n-1 do for j:=i+1 to n do begin if b[i]>b[j] then begin inc(ans); ans:=ans mod fuck; t:=b[i]; b[i]:=b[j]; b[j]:=t; end; end; writeln(ans); close(input); close(output); end.

第5 页共5 页

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

提高组 day2

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

truck.out 3 -1 3

【数据说明】 对于 30%的数据,0 < n < 1,000,0 < m < 10,000,0 < q< 1,000; 对于 60%的数据,0 < n < 1,000,0 < m < 50,000,0 < q< 1,000; 对于 100%的数据,0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,000。 对于货车运输(贪心+最大生成树+树上路径倍增) 首先,我们可以确定贪心的正确性,我们先把边按权值从大到小排序,然后依次加
第6 页共5 页

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

提高组 day2

入图中,如果该边的起末点不在同一连通块中,那么就把边加入,否则不加处理, 很明显,这样生成的图,两点之间要么没有路径,要么唯一一条路径中权值的最小 值最大。所以,我们只要先跑一次最大生成树,然后在求点对之间的树上路径最小 值就可以了。 复杂度:O(m log m + q log n) PS.当时没想到要用最大生成数,然后用弗洛伊德,复杂度 O(q*N3) ,结果 0 分, 后来听说 wrieln(‘-1’)都有五分,欲哭无泪。 坑爹的 Day1 就这么过去了,睡了一下午,晚上和老师打牌,和同校的玩天黑请闭 眼。10:00 后又练了一题,果断睡觉,半夜还被热醒(坑爹的三个人睡两张床) 。 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 (请选手务必仔细阅读本页内容) 一.题目概况 中文题目名称 英文题目与子目录 名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限

积木大赛 bloc k bloc k block.in

花 匠 flowe r flowe r flower.in

华容 道 puzzl e puzzl e puzzle.in

block.out flower.out puzzle.out 1 1 1 秒 秒 秒 10 10 20 10 10 5 有 有 有 全文比较(过滤行末空格及文末回车) 传 传 传统 统 统 128M 128M 128M

二.提交源程序文件名 对于 C++语言 block.cpp 对于 C 语言 block.c 对于 pascal 语言 block.pas

flower.cpp flower.c flower.pas

puzzle.cpp puzzle.c puzzle.pas

三.编译命令(不包含任何优化开关) 对于 C++语言 g++ -o g++ -o block flower 对于 C 语言 gcc -o gcc -o block.cpp flower.cpp block flower -lm –lm 对于 pascal 语言 fpc block.pas fpc flower.pas block.c flower.c -lm –lm
第7 页共5 页

g++ -o puzzle puzzle.cpp -lm gcc-o puzzle fpc puzzle.pas puzzle.c -lm

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

提高组 day2

注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+, 2.71GHz,内存 2G,上述时限以此配置为准。 4、只提供 Linux 格式附加样例文件。 5、特别提醒:评测在 NOI Linux 下进行。

第8 页共5 页

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

提高组 day2

1.积木大赛 (block.cpp/c/pas) 【题目描述】 春春幼儿园举办了一年一度的“积木大赛” 。今年比赛的内容是搭建一座宽 度为 n 的大厦, 大厦可以看成由 n 块宽度为 1 的积木组成,第 i 块积木的最终高 度需要是 ?i。 在搭建开始之前,没有任何积木(可以看成块高度为 0 的积木) 。接下来每 次操作, 小朋友们可以选择一段连续区间[L,R], 然后将第 L 块到第 R 块之间 (含 第 L 块和第 R 块)所有积木的高度分别增加 1。 小 M 是个聪明的小朋友, 她很快想出了建造大厦的最佳策略,使得建造所需 的操作次数最少。 但她不是一个勤于动手的孩子, 所以想请你帮忙实现这个策略, 并求出最少的操作次数。 【输入】 输入文件为 block.in 输入包含两行,第一行包含一个整数 n,表示大厦的宽度。 第二行包含 n 个整数,第 i 个整数为 ?i。 【输出】 输出文件为 block.out 仅一行,即建造所需的最少操作数。 【输入输出样例】 block.in 5 23412 【样例解释】 其中一种可行的最佳方案,依次选择 [1,5] [1,3] [2,3] [3,3] [5,5] 【数据范围】 对于 30%的数据,有 1 ≤ n ≤ 10; 对于 70%的数据,有 1 ≤ n ≤ 1000; 对于 100%的数据,有 1 ≤ n ≤ 100000,0 ≤ hi ≤ 10000。

block.out 5

坑爹啊坑爹啊坑爹啊坑爹啊坑爹啊坑爹啊坑爹啊坑爹啊 坑爹啊坑爹啊坑爹啊坑爹啊坑爹啊坑爹啊坑爹啊坑爹啊 一开始没思路,存了个贪心,做完第二题后,想到第一题也可以用单调队列,做 完后忘记换回来了,TMD。
第9 页共5 页

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

提高组 day2

本人代码(10 分) var n,min,i,ans,kk,t:longint; bo,pp:boolean; h,a:array[0..100000]of longint; begin assign(input,'block.in'); reset(input); assign(output,'block.out'); rewrite(output); readln(n); min:=maxlongint; bo:=false; fillchar(h,sizeof(h),0); for i:=1 to n do begin read(h[i]); if h[i]<min then min:=h[i]; end; for i:=1 to n do h[i]:=h[i]-min; repeat t:=0; a[t]:=0; for i:=1 to n do if h[i]=0 then begin inc(t); a[t]:=i; end; a[t+1]:=n+1; kk:=0; repeat min:=maxlongint; pp:=false; for i:=a[kk] to a[kk+1] do if (h[i]>0)and(h[i]<min) then min:=h[i]; for i:=a[kk] to a[kk+1] do if h[i]>0 then begin h[i]:=h[i]-min; pp:=true; end; if pp then inc(ans,min); inc(kk); until kk>t; bo:=true; for i:=1 to n do if h[i]<>0 then begin bo:=false; break; end; until bo; writeln(ans+1); close(input); close(output); end.

2.花匠 (flower.cpp/c/pas) 【问题描述】 花匠栋栋种了一排花, 每株花都有自己的高度。 花儿越长越大, 也越来越挤。 栋栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间 长大,同时,栋栋希望剩下的花排列得比较别致。 具体而言,栋栋的花的高度可以看成一列整数 ?1, ?2, ? , ?n。设当一
第 10 页 共 5 页

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

提高组 day2

部分花被移走后,剩下的花的高度依次为 g1, g2, ? , gm,则栋栋希望下面两 个条件中至少有一个满足: 条件 A:对于所有的 1≤i≤ m ,有 g2i > g2i-1,同时对于所有的 1≤i≤ m ,有
2 2

g2i > g2i+1; 条件 B:对于所有的 1≤i≤ m ,有 g2i < g2i-1,同时对于所有的 1≤i≤ m ,有
2 2

g2i < g2i+1。 注意上面两个条件在 m = 1 时同时满足,当 m > 1 时最多有一个能满足。 请问,栋栋最多能将多少株花留在原地。 【输入】 输入文件为 flower.in。 输入的第一行包含一个整数,表示开始时花的株数。 第二行包含个整数,依次为 ?1, ?2, … , ?n,表示每株花的高度。 【输出】 输出文件为 flower.out。 输出一行,包含一个整数,表示最多能留在原地的花的株数。 【输入输出样例】 flower.in 5 5 3 2 1 2 【输入输出样例说明】 有多种方法可以正好保留3 株花,例如,留下第 1、4、5 株,高度分别为 5、 1、2,满足条件 B。 【数据范围】 对于 20%的数据,n ≤ 10; 对于 30%的数据,n ≤ 25; 对于 70%的数据,n ≤ 1000,0 ≤ ?n≤ 1000; 对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤ ?n≤ 1,000,000,所有的 ?n 随机生 成,所有随机数服从某区间内的均匀分布。 单调队列,复杂度 O(N log N) 本人代码(100 分) var n,i,l,r,max,ans,k,ansi:longint; bo,po:boolean; a:array[0..100000]of longint; begin
第 11 页 共 5 页

flower.out 3

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

提高组 day2

assign(input,'flower.in'); reset(input); assign(output,'flower.out'); rewrite(output); readln(n); for i:=1 to n do read(a[i]); bo:=false;

ans:=0; l:=1; r:=2; while (l<=r)and(r<=n) do begin if bo then if a[r]>=a[l] then begin inc(r); inc(l); end else begin inc(ans); bo:=not bo; end; if not bo then if a[r]<=a[l] then begin inc(r); inc(l); end else begin inc(ans); bo:=not bo; end; end; po:=true; ansi:=0; l:=1; r:=2; while (l<=r)and(r<=n) do begin if po then if a[r]>=a[l] then begin inc(r); inc(l); end else begin inc(ansi); po:=not po; end; if not po then if a[r]<=a[l] then begin inc(r); inc(l); end else begin
第 12 页 共 5 页

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

提高组 day2

inc(ansi); po:=not po; end; end; max:=ans; if ansi<max then max:=ansi; writeln(max+2); close(input); close(output); end.

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。
第 13 页 共 5 页

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

提高组 day2

输出有 q 行,每行包含 1 个整数,表示每次游戏所需要的最少时间,如果 某次游戏无法完成目标则输出?1。 【输入输出样例】 puzzle.in 3 4 2 0 1 1 1 0 1 1 0 0 1 0 0 3 2 1 2 2 2 1 2 2 2 3 2 puzzle.out 2 -1

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

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

要将指定块移入目标位置, 必须先将空白块移入目标位置,空白块要移动到
第 14 页 共 5 页

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

提高组 day2

目标位置,必然是从位置(2, 2)上与当前图中目标位置上的棋子交换位置, 之后能与空白块交换位置的只有当前图中目标位置上的那个棋子, 因此目标棋子 永远无法走到它的目标位置, 游戏无法完成。 【数据范围】 对于 30%的数据,1 ≤ n, m ≤ 10,q = 1; 对于 60%的数据,1 ≤ n, m ≤ 30,q ≤ 10; 对于 100%的数据,1 ≤ n, m ≤ 30,q ≤ 500。 表示根本不知道在干嘛, 结果就 var a,b,c,i,x:longint; begin assign(input,'puzzle.in'); reset(input); assign(output,'puzzle.out'); rewrite(output); readln(a,b,c); for i:=1 to a do readln(x,x,x,x); for i:=1 to c do readln(x,x,x,x,x,x); if (a=3)and(b=4)and(c=2)then begin writeln('2'); writeln('-1'); end else for i:=1 to c do writeln('-1'); close(input); close(output); end. 果然只有 5 分。 Day2 也结束了,高兴的事就是回来的时候抱了一下洪骈大汉子,好高兴。

泉州五中只有 4 个三等奖:郑正和,刘锐意,洪佩怡,黄锦松。 一起在机房奋斗过的 13 个人,有遗憾吗? 高二的六个汉子在机房苦逼打代码,我们是屌丝,我们用机房的话筒唱歌。 这是我的一次 NOIP 复赛,也是最后一次。 调试到初始化之前 VC 上要复杂一些 做课设写报告度过每天 手工的测试数据 深搜出的无解 代码带我回当年那个十一月 调试到初始化之前 麻木地看着头文 件 傻傻运行到红色的断点 模拟也写得装模作样 刚解禁 STL 封装 动态规划又 是由谁讲给谁 那次相逢偶遇幽长的走廊 回到破旧机房前后 把老掉牙键盘敲打 那弹不起的回车 一起水的贴吧 日夜一起去把 OJ 刷 那些年堆起的程序 那些年
第 15 页 共 5 页

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

提高组 day2

创造的传奇 脑海回放着 为你创造的奇迹 曾经想把代码精简 到最后 AC 才发现 这代码字里行间 全部都是你 那些年堆起的程序 那些年创造的传奇 难忘的意 义 我们的爱感动天地 稠密图繁杂的节点 背包解密往事重现 再一次匹配 我要 永远在一起 永远在一起 调试到初始化之前 麻木地看着头文件 傻傻运行到红 色的断点 模拟也写得装模作样 刚解禁 STL 封装 动态规划又是由谁讲给谁 那 次相逢偶遇幽长的走廊 回到破旧机房前后 把老掉牙键盘敲打 那弹不起的回车 一起水的贴吧 日夜一起去把 OJ 刷 那些年堆起的程序 那些年创造的传奇 脑海 回放着 为你创造的奇迹 曾经想把代码精简 到最后 AC 才发现 这代码字里行间 全部都是你 那些年堆起的程序 那些年创造的传奇 难忘的意义 我们的爱感动 天地 稠密图繁杂的节点 背包解密往事重现 再一次匹配 我要永远在一起 永远 在一起 那些年堆起的程序 那些年创造的传奇 脑海回放着 为你创造的奇迹 曾 经想把代码精简 到最后 AC 才发现 这代码字里行间 全部都是你 那些年堆起的 程序 那些年创造的传奇 难忘的意义 我们的爱感动天地 稠密图繁杂的节点 背 包解密往事重现 再一次匹配 我要永远在一起 永远在一起

第 16 页 共 5 页


相关文章:
CCF NOIP2013 解题报告&心得
CCF NOIP2013 解题报告&心得_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 CCF NOIP2013 解题报告&心得_学科竞赛_高中教育_教育专区。全国信息...
Noip 2013 解题报告与参赛总结(PASCAL版)
Noip 2013 解题报告与参赛总结(PASCAL版)_学科竞赛_高中教育_教育专区。noip2013Noip 2013 解题报告与参赛总结(pascal 版) Noip 结束也有一段时间了,网上也能 查...
NOIP2013解题报告
NOIP2013解题报告_计算机软件及应用_IT/计算机_专业资料。NOIP2013解题报告 第一...CCF NOIP2013 解题报告&... 19页 1下载券 《乘积最大》解题报告 28页 免费...
Pascal 2013解题报告和心得文档
Pascal 2013解题报告和心得文档_调查/报告_表格/模板_实用文档。搞笑心得!!!计数...CCF NOIP2013 解题报告&... 19页 免费 喜欢此文档的还喜欢 动态...
Noip 2013 Day1 解题报告
Noip 2013 Day1 解题报告 --By GreenCloudS 第一题:转圈游戏(快速幂)根据题目,答案明显是(x+10^km) mod n,化简一下,就成了(x + m (10^k mod n) ...
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告 (普及组)宁波市镇海蛟川书院 郁庭 第一题:记数(count) 【分析】直接用最朴素的模拟来做,时间复杂度小于(...
NOIP2013复赛模拟8解题报告
NOIP2013复赛模拟8解题报告_学科竞赛_高中教育_教育专区。NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟试题 4(4P36) [题目描述]...
NOIP2013普及组第二题解题报告(汇文客原创)
NOIP2013普及组第二题解题报告(汇文客原创)_学科竞赛_初中教育_教育专区。2.表达式求值 (expr.cpp/c/pas) 【问题描述】 给定一个只包含加法和乘法的算术表达式...
NOIP2013复赛模拟8解题报告
NOIP2013复赛模拟8解题报告_韩语学习_外语学习_教育专区。NOIP2013复赛模拟8解题...CCF NOIP2013 解题报告&... 19页 免费 连云港2011NOIP第一次模... 19页 免费...
Noip_2013_提高组_Day2_解题报告
Noip_2013_提高组_Day2_解题报告_计算机软件及应用_IT/计算机_专业资料。第二题:花匠(动态规划) 1.令 S[i][1]表示以 i 为结尾, 且降序到达 a[i]的最长...
更多相关标签:
ccf noip2016 | ccf noip | noip ccf评测机速度 | ccf noip2015 | ccfnoip2016数据水 | ccf noip2016成绩 | ccfnoip | noip2016解题报告 |