当前位置：文档之家 › NOIP2002-2005解题报告

NOIP2002-2005解题报告

  • 格式：doc
  • 大小：285.50 KB
  • 文档页数：29

NOIP讲义一、NOIP2002题一：均分纸牌（NOIPG1）【问题描述】有N堆纸牌，编号分别为1, 2, ..., N-1。

每堆上有若干张，但纸牌总数必为N的倍数，可以在任一堆上取若干张，s然后移动。

移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的对上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上的纸牌数都是一样多。

输入：文件名： G1.In第一行，为一个整数N(1<=N<=100)第二行，为N个整数A1， A2，…AN（N堆纸牌初始数， 1<=Ai<=10000，中间用空格分开）输出: 文件名：G2.Out只有一行，所有堆均达到相等时的最少移动次数。

输入输出样例G1.In49 8 17 6G2.Out3【问题分析】本题实际上给我们N个数A1，A2，A3，……，A N（A1＋A2＋A3＋……＋A N是N的倍数），要求我们利用一个简单的移动规则，即对于一个A I和A I＋1（1≤I≤N－1），可以从A I中移X至A I＋1（即A I=A I－X且A I＋1=A I＋1＋X）（－A I＋1≤X≤A I），使最后A1=A2=A3=……=A N；首先，通过A1，A2，A3，……，A N我们很容易想到先求出A1~A N的平均值___A，然后从左至右，若A I≠___A，则使A I＋1=A I＋1＋A I－___A ，A I=___A。

例如试题给我们的例点A1=9 A2=8 A3=17 A4=6，我们先计算出___A=10，然后通过以下3步即可得出A1=A2=A3=A4①因A1≠___A，使A2=A2＋A1－___A=7，A1=___A=10（10 7 17 6）②因A2≠___A，使A3=A3＋A2－___A=14，A2=___A=10（10 10 14 6）③因A3≠___A，使A4=A4＋A3－___A=10 A3=___A=10（10 10 10 10，A1=A2=A3=A4）。

但是，这种贪心方法有时会出现与实际不合的情况，例如N=3，A1=1，A2=2，A3=27此时，我们的步骤为，计算___A=（1＋2＋27）/3=10，①因A1≠___A，使A2=A2＋A1－___A=1＋2－10=－7，A1=___A=10，②因A2≠___A，使A3=A3＋A2－___A=10，A4=___A=10，但是，我们发现：①中，第二堆牌中有负数张，这是不可能的。

是不是这种贪心方法有错误呢？我们再来考虑，对于上面的情况，我们可以①从A3拿17至A2，（1，19，10）②从A2拿9至A1（10，10，10），通过观察，我们发现，用贪心法和后一种正确的方法所移动的牌是一样的，即都从A3移17至A2，从A2移9至A1。

是不是对于所有的数据都会符合呢？答案是肯定的，事实上，从A1考虑，若A1>___A，则不管怎样，它必须将A1－___A给A2，若A1<___A，则不管怎样，它必须从A2得到AX=___A－A1，若A2≥AX，则可直接从A2中取AX给A1，否则，相当于对A2~A N进行调整，使A2=___A＋AX，A3=A4=……=A N=___A，这样就相当于一个递归的过程，事实上，A I和A I＋1最后都最多进行一次传递，所以，我们最初的贪心是正确的。

题二字串变换（NOIPG2）【问题描述】已知有两个字串A$，B$及一组字串变换的规则(至多六个规则) ：A1$——>B1$A2$——>B2$规则的含义为：在A$中的子串A1$可以变换为B1$，A2$可以变换为B2$……。

对于给定的A$，B$以及变换规则，求出从A$变换到B$所需的最少步数。

输入：文件名： G2.In第1行，为两个字串A$ B$(用空格分开)第2行以后的每行为两个字串A1$ B1$(用空格分开)，表示一种变换规则所有字符串长度的上限为20。

输出：文件名：G2.Out只有1行，若在10步以内有解，输出最少步数，否则输出”No ANSWER!”。

输入输出样例：G2.Inabcd xyzabc xuud yy yzG2.Out3【问题分析】本题给了我们两个字符串A$、B$和最多六条变换规则，要求我们用这组变换规则，将A$变为B$。

因为本题不具有最优子结构性质，且状态较难描述，所以动态规划、贪心等算法都无法使用，只好考虑搜索。

用深搜还是广搜呢？若用广搜，因最多有6条变换规则，每个字串长度为20，故每个字串最多有6*20=120种变换方法，如果变10次，则最多有12010>1020，这显然无法存储，因此我们只好考虑深搜。

用这样毫无剪枝的搜索效率是不高的，可以加入两条剪枝，来提高效率。

剪枝一：当前得到的串的长度加上规则中增长最长的与所剩步数的积（即最多还能增长的长度）还小于目标串长则可减掉。

当前得到的串长度减去规则中减长最长的与所剩步数的积（即最多能减长的长度）还大于目标串长则可减掉。

剪枝二：可以给扩展串定一个开始位置，开始位置定为上次扩展的时候与之匹配的位置，从这个位置开始找能变换的，开始位置前面的不作变换。

如当前串为abcdabcefg，有规则abc efg，则当前如果把第一个abc变换成efg，则将扩展出来的节点开始位置定为第1位，如果当前是把第2个abc变换成efg，则把扩展出来的节点开始位置定为第5位，因为如果下次再把第1个abc变换成efg的话就会和先变换第1个再变换第2个重复，可以剪枝。

这道题加入这两条剪枝后速度会快很多。

题三：自由落体（NOIPG3）【问题描述】在高为H的天花板上有N个小球，体积不计，位置分别为0, 1, 2, …, N-1。

在地面上有一个小车（长为L，高为K，距原点距离为S1）。

已知小球下落距离V前进。

小车与所有小球同时开始运动，当小球距小车的距离<＝0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）请你计算出小车能接受到多少个小球。

数据范围：1<=H，S1，V，L，K，N<=100000输入：文件名： G3.In只有1行，为6个数H，S1，V，L，K，N（1<= H，S1，V，L，K，N<=100000,中间用空格分开）输出：文件名：G4.In只有1行，为小车能接受到的小球个数。

输入输出样例：G3.In5.0 9.0 5.0 2.0 1.8 5G3.Out1【问题分析】如上图：题中给了我们N个小球和一辆小车，小球的位置分别为0，1，2，……，N－1，距地面H，体积不计，小车宽L，高K。

小车和小球都从0时刻开始运动，小球做自由落体运动，小车从S1开始以速度V向O做匀速直线运动，当小球与小车的距离≤10-5时，任为小球被小车接受，问给出H，S1，V，L，K，N后，有多少个小球被小车接受。

因为小球是按顺序排列的，且开始下落的时间、高度，下落时的加速度都是相同的，若且d I表示小车到达第I个小球所在位置时第I个小球所下落的距离，t I表示小车到达小球I所在位置的时间，由d=1/2*g*t2得：d I=1/2*g*t I2，d I+1=1/2*g*t I+12，d I+2=1/2*g*t I+22，因小车的方向不变，如果小车经过第I个、第I+1个和第I+2个小球，那么t I≥t I+1≥t I+2≥0，则d I≥d I+1≥d I+2，若小车能接住第I个和第I+2个小球，则它必能接住第I+1个小球。

同理，若小球能接住第I个小球和第I+K（K≥0）个小球，则它必能接住第I+1至第K-1个小球。

据此，我们只须求出小车能接住的第一个小球的时间和小车能接住的最后一个小球的时间即可求出小车能接住多少个小球。

对于找第一个和最后一个接住的球，直接计算可能会出现误差，所以不防用二分法。

即对于一个小球I，若小车到I时小球已落地，则第一个接住和最后一个被接住的必在小球I的右边，若小车离开位置I时小球I还在空中，则第一个和最后一个被接住的必在小球I的左边，否则，第一个被接住的小球是I或在I的右边，最后一个被接住的小球是I或在I的左边。

题四：矩形覆盖（NOIPG4）在平面上右N个点，每个点用一对整数坐标表示。

这些点可以用K个矩形全部覆盖，矩形的边平行于坐标轴。

当N个点的坐标和K给出后，怎样才能使得覆盖所有点的K个矩形的面积之和为最小呢。

约定：覆盖一个点的矩形面积为0；覆盖平行于坐标轴的直线上点的矩形面积也为0；各个矩形必须完全分开（边线与顶点也都不能重合）。

输入：文件名：G4.In第一行，为2个整数N K（1<=N<=50, 1<=K<=4，用空格分开）。

攻击第2～N＋1行，每行为2个整数X, Y, 为平面上1个点的坐标（0 <= X, Y <= 500，中间用空格分开）。

输出：文件名： G4.Out只有1行，为一个整数，即满足条件的最小的矩形面积之和。

输入输出样例：G4.In4 21 12 23 607G4.Out4【问题分析】本题给了我们平面上的n个点（n≤50），每个点用一对整数坐标表示，要求我们用k个矩形（1≤k≤4）将这些点全部覆盖，矩形的边平行于坐标轴。

并且：覆盖一个点的矩形面积为0；覆盖平行于坐标轴直线上点的矩形面积也为0。

各个矩形必须完全分开（边线与顶点也都不能重合）。

本题是此次竞赛中一道比较难的题目，因其是对平面上的点进行操作，若用搜索做，状态难以描述；用贪心做，不太可行……用动态规划做，也不能保证全对，但是，较之其他方法，动态规划也还能算得上“矮子里的高子”，因此，这道题目只好用动态规划来解决。

假设：符合题目要求的矩形压缩到坐标轴后（即在坐标轴上的射影）在X轴不相交或在Y轴不相交。

例如例点可如将矩形压缩成如下形式：其中，绿色表示S1的射影，蓝色表示S2的射影。

虽然我们不能保证所有的情况都能满足，但是大部分情况它都能找出最优解。

这样，以X坐标或Y坐标为状态，我们就可以很快写出动态转移方程了：以X坐标为状态：F[I, J] = F[I – 1, K] + Cost1[K + 1, J]; 其中Cost1[A, B]表示按X 坐标排序后从PA到PB的矩形的面积。

以Y坐标为状态：F[I, J] = F[I – 1, K] + Cost2[K + 1, J]; 其中Cost2[A, B]表示按Y 坐标排序后从PA到PB的矩形的面积。

二、NOIP2003题一：神经网络（Network ）【问题描述】人工神经网络（Artificial Neural Network ）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。

合集下载

noip2005普及组解题报告

noip2005普及组解题报告

noip2005普及组解题报告陶陶摘苹果【文件名】: apple.pas/c/cpp【问题描述】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。

苹果成熟的时候，陶陶就会跑去摘苹果。

陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。

现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。

假设她碰到苹果，苹果就会掉下来。

【输入文件】输入文件apple.in包括两行数据。

第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。

第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。

【输出文件】输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。

【样例输入】100 200 150 140 129 134 167 198 200 111110【样例输出】5分析：拿到这道题，我觉得还是比较简单的。

由于数据范围都不超过200，用integer完全就足够了，具体步骤如下：1．读入2．循环 1 to 103．判断，找出最优解4．输出【程序清单】program apple;vari,n,s:integer;a:array[1..10] of integer;beginassign(input,'apple.in');reset(input);for i:=1 to 10 do read(a[i]);read(n);s:=0;for i:=1 to 10 doif n+30>=a[i] then s:=s+1;close(input);assign(output,'apple.out');rewrite(output);write(s);close(output);end.校门外的树【文件名】tree.pas/c/cpp【问题描述】某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。

NOIP2005 第3题 - MY OPERA

NOIP2005 第3题 - MY OPERA


一个例子

易证得M=所有可能的顺序中，不在位置 上的人员个数的最小值。
具体分析
1,2,3,4,5 3,5,4,1,2
S=3,3,3,4,2 则在这种情况下，我们很容易看出1，2，3 可同时达到目标状态（最多）。则可计算 出M=N-3=2
对于全部的数据，n <= 50000。
算法分析
初始状态：１，２，３．．．．，Ｎ
目标状态：A1,A2,A3,A4,A5….AN
算法分析
Байду номын сангаас

首先根据读入数据判断是否可能生成一 个要求的序列。 若存在，则求出目标序列 求M的值
一个例子
初始：1,2,3,4,5 目标：3,5,4,1,2
想一想，在已知目标的情况下应该如何求 M的值呢？
NOIP2005 第3题
篝火晚会 By:张萌
题目描述
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳， 很快得到了教官的赏识，成为了“小教官”。在军 训结束的那天晚上，佳佳被命令组织同学们进行篝 火晚会。一 共有n个同学，编号从1到n。一开始， 同学们按照1，2，……，n的顺序坐成一圈，而实际 上每个人都有两个最希望相邻的同学。如何下命令 调整同学的次序， 形成新的一个圈，使之符合同学 们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式 如下：
(b1, b2,... bm -1, bm)
题目描述
这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个 命令的作用是移动编号是b1，b2，…… bm –1，bm的这m个同学 的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要 求bm换到b1的位置上。 执行每个命令都需要一些代价。我们假定如果一个命令要移 动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用 最少的总代价实现同学们的意愿，你能帮助佳佳吗? 对于30%的数据，n <= 1000；
等价表达式_NOIP2005提高组第四题-解题报告...

等价表达式_NOIP2005提高组第四题-解题报告...


function data(l,r:longint):int64; var i:longint; begin data:=0; for i:=l to r do data:=data*10+ord(s[i])-48; end; function find(l,r:longint):int64; var i,min:longint; begin min:=maxlongint; find:=0; for i:=r downto l do if h[i]<min then begin min:=h[i]; find:=i; end; end; function opt(a,k,b:int64):int64; begin case s[k] of '+':opt:=(a+b) mod maxlongint; '-':opt:=(a-b) mod maxlongint; '*':opt:=(a*b) mod maxlongint; '^':opt:=power(a,b) mod maxlongint end; end; function work(L,r:longint):int64; var a,b:int64; k:longint; begin if s[l]='(' then inc(l); if s[r]=')' then dec(r); k:=find(l,r); if k=0 then exit(data(l,r)); a:=work(l,k-1); b:=work(k+1,r); work:=opt(a,k,b); end;
inc(i) end else begin if f[a[i][1]].wai=f[c[tc]].nei then begin tc:=tc-1; inc(i); end else if f[a[i][1]].wai>f[c[tc]].nei then begin inc(tc); c[tc]:=a[i][1]; inc(i); end else while (f[a[i] [1]].wai<f[c[tc]].nei) {and (c[tc]<>'#')} do begin case c[tc] of '+':n:=(num[tn]+num[tn-1]) mod maxlongint; '-':n:=(num[tn-1]-num[tn]) mod maxlongint; '*':n:=num[tn-1]*num[tn] mod maxlongint; '^':n:=power(num[tn1],num[tn]) mod maxlongint end; tn:=tn-1; tc:=tc-1; num[tn]:=n; end; end; until tc=0; work:=num[tn]; end; begin assign(input,'equal.in'); assign(output,'equal.out'); reset(input); rewrite(output);
信息学奥赛NOIP普和组历届试题分析报告

信息学奥赛NOIP普和组历届试题分析报告

普及组一般考查的动态规划：01背包，最长上升子序 列，一些简单的线性动规。
采药 （noip2005普及组第三题）
辰辰是个天资聪颖的孩子，他的梦想是成为世 界上最伟大的医师。为此，他想拜附近最有威 望的医师为师。医师为了判断他的资质，给他 出了一个难题。医师把他带到一个到处都是草 药的山洞里对他说：“孩子，这个山洞里有一 些不同的草药，采每一株都需要一些时间，每 一株也有它自身的价值。我会给你一段时间， 在这段时间里，你可以采到一些草药。如果你 是一个聪明的孩子，你应该可以让采到的草药 的总价值最大。”
试计算在区间1到n的所有整数中，数字x（0≤x≤9） 共出现了多少次？ 例如，在1到11中，即在1、2、3、4、5、6、7、8、 9、10、11中，数字1出现了4次。
输入：
输入共1行，包含2个整数n、x，之间用一个空格隔 开。 输出：
输出共1行，包含一个整数，表示x出现的次数。 输入示例： 11 1 输出示例： 4 其他说明：
输入 输入共1行，一个整数N。
输出 输出共1行，一个整数，表示反转后的新数。
样例输入
123 样例输出
321
统计单词个数 (noip2011普及组第二题)
一般的文本编辑器都有查找单词的功能，该功 能可以快速定位特定单词在文章中的位置，有 的还能统计出特定单词在文章中出现的次数。 现在，请你编程实现这一功能，具体要求 是：给定一个单词，请你输出它在给定的文章 中出现的次数和第一次出现的位置。注意：匹 配单词时，不区分大小写，但要求完全匹配， 即给定单词必须与文章中的某一独立单词在不 区分大小写的情况下完全相同（参见样例1）， 如果给定单词仅是文章中某一单词的一部分则 不算匹配（参见样例2）。
对于100%的数据，3 ≤ n ≤ 100 测验题给出的正整数大小不超过10,000。