NOIP2005提高组解题报告带标程(天津南开中学 薛原)
- 格式：doc
- 大小：35.50 KB
- 文档页数：11
文档推荐
-
天津南开中学2021届高三第三次月考数学页数:4
-
天津南开中学小卷页数:9
-
天津重点高中排名页数:4
-
天津南开中学高一英语语法专向练习及答案页数:7
-
天津南开中学镜鉴页数:1
-
南开中学校史页数:23
下载文档原格式
合集下载
NOI提高组解题报告
第七届（2001）分区联赛复赛解题报告（提高组）俞玮赵爽第一题：一元三次方程求解给出一个三次方程32()0f x ax bx cx d =+++=，试求它所有的三个根。
这里所有的根都在区间[100,100]-中，并保证方程具有三个实根，且它们之间的差不小于1。
分析：如果是一般的求三次方程根的问题，那么只能直接使用求根公式，但这是非常复杂的。
由于题目要求只精确到0.01，故我们考虑一下是否可以应用数值方法进行计算。
由题目给出的方程在区间内存在根的条件可知，我们可以用一个变量i 从-100.000到100.000以步长0.001做循环。
若()(0.001)0f i f i ⋅+<，则可知在区间(,0.001)i i +内存在方程的解。
这样无论这个区间内的解是什么，在取两位小数的精度后都与i 取两位小数的结果是一样的。
故我们就可以把取两位小数精度的i 作为问题的解。
另外还有可能方程的根在区间端点i 的情况，我们可以通过判断()f i 是否为0来获得。
但这种方法由于用到了题目所要求的数值精度小的特殊性，故无法扩展。
而在用数值方法求方程根的时候，我们最常用的方法就是二分法。
该方法的应用在于如果确定了方程()0f x =在区间(,)a b 内如果存在且只存在一个根，那么我们可以用逐次缩小根可能存在范围的方法确定出根的某精度的数值。
该方法主要利用的就是题目所给的若在区间(,)a b 内存在一个方程的根，则()()0f a f b ⋅<这个事实，并重复执行如下的过程： ● 取当前可能存在解的区间(,)a b ； ● 若0.001a b +>或()20a bf +=，则可确定根为2a b+并退出过程； ● 若()2()0a b f a f+⋅<，则由题目给出的定理可知根在区间()2,a b a +中，故对区间()2,a ba +重复该过程；若()2()0a b f a f+⋅>，则必然有()2()0a b f f b +⋅<，也就是说根在()2,a bb +中，应该对此区间重复该过程。
NOIP2002-2005解题报告
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）。
等价表达式_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);
高中信息技术 NOIP2005信息学奥林匹克提高组解题报告
NOIP2005信息学奥林匹克分区联赛解题报告第一题：谁拿了最多的奖学-S cholar[问题评估]这个题目据问题本身而言是相当简单的，没有牵涉到过多的算法，属于普及型试题。
同时也是对实际问题一种分析和判断。
总的来看，本题在方向上，向现实问题迈出了一步，是信息学和生活有了更多的联系。
问题的算法是模拟。
当中唯一的难点就是数据处理，考察点为数据库的建立和统计。
[程序实现]由于程序数据范围只有100，当中不牵涉到数据移动，所以用一个纪录型数组，或者多个数组均可，在这里我们使用纪录型来描述。
对于输入数据有两种方式来实现。
法一〉逐个字符累加。
首先定义C:char;然后利用Until c=‘ ’;作为终止符，将读入的字符连接存储到a[i].name中。
代码为：Repeat read(c); a[i].name:=a[i].name+c; until c=’ ‘;a[i].name:=copy(a[i].name,1,length(a[i].s)-1);这样做的好处是，后面的值可以直接用read语句读入。
但是最后一个值后，要记得readln;法二〉一次读入,然后分离。
这样做需要逐个分离，对本题来说稍显复杂，但对NOIP来说此方法必须掌握，有的时候一定要用。
具体实现，读入一个字符串S。
利用pos(‘ ‘,s);找出空格位置。
再利用Copy函数，和Val 函数进行截取，和转换。
部分代码：(s:string;j,ok:integer)readln(s);j:=pos(‘ ‘,s);a[i].name:=copy(s,1,j-1);s:= copy(s,j+1,50); //当长度〉字符串长度是，为后面全部截取。
j:=pos(‘ ‘,s);Val(copy(s,1,j-1),a[i].qp,ok);s:= copy(s,j+1,50);…..对于符号用if语句作一下判断就是了，太easy不写了，后面还有几个值，用同样方法处理就可以了。
NOIP2023提高组解题报告
NOIP2023提高组解题报告1. 前言NOIP（全国信息学奥林匹克竞赛）是中国非常重要的信息学竞赛之一，旨在选拔和培养高中阶段的优秀信息学人才。
在NOIP中，提高组是一个相对较高难度的组别，要求选手具备扎实的编程基础和复杂问题的解决能力。
在本文档中，将对NOIP2023提高组的解题情况进行详细的报告和分析。
2. 题目概览本次NOIP2023提高组共计有以下几道题目：1.田忌赛马（Tianji Race）2.矩阵乘法（Matrix Multiplication）3.数字问题（Number Problem）4.字符串排序（String Sort）下面将对每道题目的解题思路和实现进行详细说明。
3. 田忌赛马田忌赛马是第一道题目，题目要求给出两组马匹的速度，分别是田忌的马匹和齐王的马匹，然后判断田忌最多能赢齐王多少场比赛。
解题思路非常简单，只需要对田忌和齐王的马匹进行排序，从最快的马开始进行配对比赛。
如果田忌的马比齐王的马快，那么田忌赢得这场比赛，分数加一；否则，田忌选择最慢的马匹进行比赛。
通过这样的遍历方式，最后的得分就是田忌能够赢得比赛的场数。
具体实现代码如下：def solve(Tianji, QiWang):Tianji.sort()QiWang.sort()t_index =0q_index =0score =0while t_index < len(Tianji) and q_index < len(QiWang):if Tianji[t_index] > QiWang[q_index]:score +=1t_index +=1q_index +=1else:t_index +=1return score4. 矩阵乘法矩阵乘法是第二道题目，题目需要实现一个矩阵乘法的算法。
解题思路比较直接，使用两层循环对两个矩阵进行迭代计算，然后累加乘积，得到最终结果。
具体实现代码如下：def multiply_matrix(A, B):row_A = len(A)col_A = len(A[0])col_B = len(B[0])C = [[0] * col_B for _ in range(row_A)]for i in range(row_A):for j in range(col_B):for k in range(col_A):C[i][j] += A[i][k] * B[k][j]return C5. 数字问题数字问题是第三道题目，题目要求给出一个正整数n，判断是否存在一个正整数x，使得n的位数的立方和等于x。
noip2005(提高组)讲解
For t:=1 to n do for x:=1 to n do begin j:=0; for k:=t to t+n-1 do if a[k]<>l[x+k-t] then inc(j);
if j<min then min:=j;
存储结构：
这道题唯一值得一提的就是怎样存储数据。 从输入格式可以看出人名需要一个字符串来存 储，成绩需要整型存储，剩下的需要字符来存 储。由此可以想到——用一个记录类型来存储
是个不错的选择，当然，用5个数组来存储也是
可以的。
接下来的就是一个一个数据来模拟算出第n个人 可以得到的奖学金数，比较一下是否是最多的， 然后在累计器上加上这个奖学金数。
由此我们可以想到，如果起始状态和目标状态的某一位置是相同
的数字，那么这个数字便可以不进行交换，也不计入代价；而若
这一位置上的数字不是相同的数字，那么这个数字就必须进行交 换来达到目标状态，这个交换的最小代价是1。
于是，我们的任务便是找出起始状态和目标状态之间的最小差异， 这个差异便可以成为这种转换的最小代价。
最后按格式输出。（注意文末换行） 正如开始所说的，这是一道水题，是一定要拿满 分的。
第二题：过河
【问题描述】
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一 侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长 度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可 能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥 的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。 青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是 S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L 的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L， 青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙 要想过河，最少需要踩到的石子数。
NOIP2000-2009提高组解题报告(c语言)
NOI分区联赛- 2000年第六届提高组试题解析注意：解析和源程序均为OIBH站长刘汝佳所写，疏漏在所难免，但至少程序均通过了比赛时使用的测试数据，所以还是可以一看。
第一题：大家对正数进制的转换应该比较熟悉吧！（不会的看我的《循序渐进》）负数进制一样。
每次取的余数保证在0~-m-1之间。
（例如m=-16,则余数应该在0~15）就可以直接输出。
所以用系统的“mod”运算符的时候必须注意检查是不是在该范围（可能在m+1~0），否则就调整。
调整的方法是：if 余数<0 thenbegin余数=余数-m;商=商+1;end;程序见附件。
第二题：很明显的动态规划。
令d[i,j,k]为第i个数字到第j个数字加k个乘号所能够达到的最大值。
状态转移方程是：d[i,j,k]=max{num[i,t]*d[t+1,j,k-1]} (枚举t, 满足i<=t<=j-1)注意到状态转移的时候总是使k减小（或不变）的，所以把k作为阶段来递推（节约空间）。
在每个状态中，l=j-i越来越小，所以从l=0递推到l=n即：for k:=1 to c dofor l:=0 to n dofor i:=1 to n do递推d[i,j,k]显然，用两个数组记录d[i,j,k]和d[i,j,k-1],就可以只用两维：d[i,j]于是算法框架就是(请对照我的源程序)：初始化d1[i,j]for k:=1 to c dobeginfor l:=0 to n dofor i:=1 to n do用d1[i,j](k-1阶段)递推d2[i,j]（k阶段）d1:=d2; {节省空间，因为递推的时候只与上个阶段有关，故只保留相邻两个阶段}end;高精度乘法的方法我不是用的模拟手算的过程（这个大家会做吧），而用了类似多项式乘法的方法，因为我觉得这种写法很好记！(大家仔细看看我的mul过程)程序见附件。
第三题：搜索。
数据很小，因此回溯就可以了。
NOIP2005提高组初赛试题与答案
r[1] = r[r[0] / p % 2];
else
r[1] = q % p; printf(“%d\n”, r[0] – r[1]); return 0;
} 输入：100 7 3 输出：
2． #include <stdio.h> #include <math.h> int a[50]; void work(int p, int r) { if (p < r) { int i = p - 1, j, temp; for (j = p; j < r; j++) { if (a[j] >= a[r]) { i++; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
15. 下列外设接口中可以通过无线连接的方式连接设备的是（ ）。 A. USB 2.0 高速版 B. 红外 C. 蓝牙 D. 串口 E. IEEE 802.11g 无线网卡
16. 处理器 A 每秒处理的指令数是处理器 B 的 2 倍。某一特定程序 P 分别编译为处理器 A 和处理器 B 的指令，编译结果处理器 A 的指令数是处理器 B 的 4 倍。已知程序 P 的算 法时间复杂度为 O(n2)，如果处理器 A 执行程序 P 时能在一小时内完成的输入规模为 n， 则处理器 B 执行程序 P 时能在一小时内完成的输入规模为（ ）。 A. 4 * n B. 2 * n C. n D. n / 2 E. n / 4
３
© 中国计算机学会
NOIP2005 提高 C
temp = a[i + 1]; a[i + 1] = a[r]; a[r] = temp; work(p, i); work(i + 2, r); } } int main() { int n, i, sum = 0; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &(a[i])); work(0, n - 1); for (i = 0; i < n - 1; i++) sum += abs(a[i + 1] - a[i]); printf("%d\n", sum); return 0; } 输入：10 23 435 12 345 3123 43 456 12 32 -100 输出：
else
r[1] = q % p; printf(“%d\n”, r[0] – r[1]); return 0;
} 输入：100 7 3 输出：
2． #include <stdio.h> #include <math.h> int a[50]; void work(int p, int r) { if (p < r) { int i = p - 1, j, temp; for (j = p; j < r; j++) { if (a[j] >= a[r]) { i++; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
15. 下列外设接口中可以通过无线连接的方式连接设备的是（ ）。 A. USB 2.0 高速版 B. 红外 C. 蓝牙 D. 串口 E. IEEE 802.11g 无线网卡
16. 处理器 A 每秒处理的指令数是处理器 B 的 2 倍。某一特定程序 P 分别编译为处理器 A 和处理器 B 的指令，编译结果处理器 A 的指令数是处理器 B 的 4 倍。已知程序 P 的算 法时间复杂度为 O(n2)，如果处理器 A 执行程序 P 时能在一小时内完成的输入规模为 n， 则处理器 B 执行程序 P 时能在一小时内完成的输入规模为（ ）。 A. 4 * n B. 2 * n C. n D. n / 2 E. n / 4
３
© 中国计算机学会
NOIP2005 提高 C
temp = a[i + 1]; a[i + 1] = a[r]; a[r] = temp; work(p, i); work(i + 2, r); } } int main() { int n, i, sum = 0; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &(a[i])); work(0, n - 1); for (i = 0; i < n - 1; i++) sum += abs(a[i + 1] - a[i]); printf("%d\n", sum); return 0; } 输入：10 23 435 12 345 3123 43 456 12 32 -100 输出：
NOIP2005提高组第一、二题解题报告
过河
(river.pas/c/cpp)
【问题描述】
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一 侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石 子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我 们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点： 0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥 0 1 …… L L 0 的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始， 不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意 正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就 算青蛙已经跳出了独木桥。 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥 上石子的位置。你的任务是确定青蛙要想过河，最少需要踩 到的石子数。
法一〉一次读入 然后分离 然后分离。 法一〉一次读入,然后分离。
具体实现，读入一个字符串S。利用pos(‘ ‘,s);找出空 格位置。再利用Copy函数，和Val函数进行截取，和 转换。 部分代码：(s:string;j,ok:integer) readln(s); j:=pos(‘ ‘,s); a[i].name:=copy(s,1,j-1); s:= copy(s,j+1,50); //当长度〉字符串长度是， 为后面全部截取。 j:=pos(‘ ‘,s); Val(copy(s,1,j-1),a[i].qp,ok); s:= copy(s,j+1,50);
但是，以上的讨论是建立在S<T的基础上，如果S ＝T，则由于青蛙没有选择，直接统计所有石子位置 是S（或T）倍数的个数就是问题的解。 【解题步骤】 <数据结构>： • 符号常量skip表示青蛙的有效跳跃数，值为80； • 数组stone保存由输入文件读入的石子的位置； • 数组b保存距离压缩后每一个位置是否有石子，“1” 表 示有，“0”表示无； • 数组c保存路经压缩后的石子位置； • 数组f保存抵达每一个位置所经历的最小石子数。
NoiP2003提高组复赛试题分析_天津南开中学滕伟
我看了李学武教授写的《关于NOIP复赛的若干问题的思考》一文，有很大触动，深刻感受到天津市信息学奥赛基础薄弱。
我从事奥赛培训工作十三年，培训的学生在全国取得了一些好成绩，一块国际银牌，四块全国奥赛金牌，三块银牌，十块铜牌。
我认为我有责任将我的培训工作介绍给同人和其他学校的同学，来推动天津市奥赛的发展。
下面是我写的今年分区联赛高中组复赛的解题分析，供大家参考，并恳切希望能与“OIER”交流共勉。
天津南开中学滕伟（邮编：300100，电子邮箱：fnoi2003@或tjnkzx2000@ ）第一题：神经网络【试题分析】一、题意分析1、任务描述：从输入层开始，各节点按照传递公式，一层一层向下传递。
输出输出层中信号大于零的节点编号和信号大小。
（节点编号由小到大）如果没有满足条件的编号则输出NULL。
信号传递公式：∑∈-=Ei jijjiiUCWC),(公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。
当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。
当神经元处于兴奋状态时，下一秒它会向其它神经元传递信号，信号的强度为Ci。
2、输入：两个整数n（1≤n≤20）和p。
n表示节点的个数；p表示有向边的条数。
下面n行表示1-n号节点的状态和阈值。
下面p行表示有向边及其权值。
3、输出：输出输出层状态大于零的神经元编号和状态，并且按照编号有小到大顺序输出！若输出层的神经元最后状态小于等于0，则输出NULL。
二、问题分析1、题目中给出每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。
所以不必进行拓扑排序，一层一层的向下传递信号即可。
输出最后一层中信号大于零的节点编号。
2、可以建立一个队列，将输入层节点入队。
3、取队首节点出队，寻找此节点有向边，如果有有向边：1）则记录此节点不是输出层；2）再判断此节点信号大于零则向下传递信号，将指向的节点入队（防止重复入队）。
再出队再传递，直至全部出队。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
NOIP2005提高组解题报告天津南开中学薛原谁拿了最多奖学金(scholar)题目概述：已知每个学生的个人信息，求出获得奖学金最多的学生姓名、金额，以及全部奖学金金额。
算法分析：模拟其中涉及简单的字符处理，特别要注意数据类型的应用。
如：学生姓名可采用char和string相结合的方法处理，奖学金金额用longint较为适宜。
程序：program scholar;var name:array[1..100] of string;a1,a2,a5:array[1..100] of longint;a3,a4:array[1..100] of char;n,i,max,total,p:longint;maxname:string;ch:char;f:text;beginassign(f, 'scholar.in ');reset(f);readln(f,n);for i:=1 to n dobeginread(f,ch);while ch<> ' ' dobeginname[i]:=name[i]+ch;read(f,ch);end;readln(f,a1[i],a2[i],ch,a3[i],ch,a4[i],ch,a5[i]);end;close(f);for i:=1 to n dobeginp:=0;if (a1[i]>80) and (a5[i]>=1) then inc(p,8000);if (a1[i]>85) and (a2[i]>80) then inc(p,4000);if (a1[i]>90) then inc(p,2000);if (a1[i]>85) and (a4[i]= 'Y ') then inc(p,1000);if (a2[i]>80) and (a3[i]= 'Y ') then inc(p,850);if p>max thenbeginmax:=p;maxname:=name[i];end;inc(total,p);end;assign(f, 'scholar.out ');rewrite(f);writeln(f,maxname);writeln(f,max);writeln(f,total);close(f);end.过河(River)题目概述：在一条长为L数轴上有若干障碍点，每次前进距离为S到T之间的任意正整数（包括S,T），求走过L或大于L的距离，遇到最少的障碍点。
算法分析：看到题目首先想到的是时间复杂度为O(L)的递推算法。
但是L的上限为10^9，这种算法显然是不行的。
仔细思考，可以得到下面的结论：存在N0，当n> N0时，n可以由若干S到T之间的正整数（包括S,T）组成。
因此，将障碍点按升序排列，当两相邻障碍点之间距离较大时，可适当缩小两障碍点之间距离，但不影响最终结果。
根据上述结论，改进递推算法。
由于障碍点之间距离大大缩减，算法的复杂度是可以承受的。
特别地，当S=T时需要单独处理。
程序：program river;const max=105;var a,a1:array[0..101] of longint;b:array[0..100] of boolean;c,d:array[0..10000] of longint;l,s,t,m,ans,low,i,j,k,temp:longint;flag:boolean;f:text;procedure init;beginassign(f, 'river9.in ');reset(f);readln(f,l);readln(f,s,t,m);for i:=1 to m do read(f,a[i]);a[0]:=0;a[m+1]:=l;for i:=1 to m-1 dofor j:=i+1 to m doif a[i]>a[j] thenbegintemp:=a[i];a[i]:=a[j];a[j]:=temp; end;close(f);end;procedure work1;beginfor i:=1 to m doif a[i] mod s=0 then inc(ans);end;procedure work2;beginfillchar(b,sizeof(b),false);b[0]:=true;for i:=s to t dobeginfor j:=0 to 100 doif b[j] thenbegink:=1;while k*i+j<=100 dobeginb[k*i+j]:=true;inc(k);end;end;end;for i:=1 to 100 dobeginflag:=true;for j:=0 to t-1 doif not b[i+j] then begin flag:=false;break;end; if flag thenbeginlow:=i;break;end;end;if low<t then low:=t;for i:=1 to m+1 dobegina1[i]:=(a[i]-a[i-1]-low) mod low+a1[i-1]+low; end;a:=a1;for i:=1 to m do d[a[i]]:=1;l:=a[m+1];for i:=1 to l+t-1 do c[i]:=max;for i:=1 to l+t-1 dofor j:=s to t doif (i-j>=0) and (c[i]>c[i-j]+d[i]) thenc[i]:=c[i-j]+d[i];ans:=max;for i:=l to l+t-1 doif ans>c[i] then ans:=c[i];end;begininit;if s=t then work1else work2;assign(f, 'river.out ');rewrite(f);writeln(f,ans);close(f);end.篝火晚会（fire）题目概述：根据一定的移动规则，将初始圆环转化为满足一定条件的目标圆环。
算法分析：从第一个人处断开，将圆环的问题转化为序列的问题。
如果可以，求出目标序列。
求出目标序列复杂度O(n).求出目标序列右移0至n-1位置时，不需要移动的人数。
将目标序列反转，再求出目标序列右移0至n-1位置时，不需要移动的人数。
不需要移动的人数最大等价于需要移动的人数最小。
复杂度O(n)。
程序：program fire;var a:array[1..50000] of longint;b:array[1..50000,1..2] of longint;d:array[1..50000] of longint;w:array[0..50000] of longint;n,ans,i,j,t,max:longint;flag:boolean;f:text;procedure init;beginassign(f, 'fire.in ');reset(f);readln(f,n);for i:=1 to n dobeginreadln(f,b[i,1],b[i,2]);inc(d[b[i,1]]);inc(d[b[i,2]]);end;close(f);for i:=1 to n doif d[i]<>2 then begin flag:=false;exit;end; end;procedure circle;begina[1]:=1;a[2]:=b[1,1];for i:=3 to n doif b[a[i-1],1]<>a[i-2] then a[i]:=b[a[i-1],1] else a[i]:=b[a[i-1],2];if a[n]<>b[1,2] then flag:=false;end;procedure min;beginfillchar(w,sizeof(w),0);for i:=1 to n doinc(w[(a[i]-i+n) mod n]);for i:=0 to n-1 doif max<w[i] then max:=w[i];for i:=1 to (n+1) div 2 dobegint:=a[i];a[i]:=a[n+1-i];a[n+1-i]:=t;end;fillchar(w,sizeof(w),0);for i:=1 to n doinc(w[(a[i]-i+n) mod n]);for i:=0 to n-1 doif max<w[i] then max:=w[i];ans:=n-max;end;beginflag:=true;init;if flag then circle;if flag then min;assign(f, 'fire.out ');rewrite(f);if flag then writeln(f,ans) else writeln(f,-1);close(f);end.等价表达式题目概述：判断两表达式是否等价。
算法分析：用栈的方法求表达式的值是经典的算法。
考虑到多项式的处理比较麻烦，不妨对变量a进行多次赋值以判断表达式是否等价。
值得注意，由于进行数值运算，采用哪种数据类型成为程序是否正确的关键。
下面的程序，采取mod m的方法，其中m为任意正整数。
当对a多次赋值，且m取不同的较大的正整数时，可以保证算法的正确性。
程序：program equal;const max=maxlongint;const com:array[1..7,1..7] of char=(( '> ', '> ', '< ', '< ', '< ', '> ', '> '),( '> ', '> ', '< ', '< ', '< ', '> ','> '),( '> ', '> ', '> ', '< ', '< ', '> ', '> '),( '> ', '> ', '> ', '> ', '< ', '> ', '> '),( '< ', '< ', '< ', '< ', '< ', '= ', 'X '),( '> ', '> ', '> ', '> ', 'X ', '> ', '> '),( '< ', '< ', '< ', '< ', '< ', 'X ', 'X '));var there:char;oped:array[1..1000] of longint;optr:array[1..1000] of char;ned,ntr:int64;a,b:int64;flag:boolean;s:array[0..26] of string;value:array[0..26,-4..4] of int64;ans:array[0..26] of boolean;n,i,j,p,q:longint;f:text;function compare(w1,w2:char):char;var x1,x2:integer;begincase w1 of'+ ':x1:=1;'- ':x1:=2;'* ':x1:=3;'^ ':x1:=4;'( ':x1:=5;') ':x1:=6;'# ':x1:=7;end;case w2 of'+ ':x2:=1;'- ':x2:=2;'* ':x2:=3;'^ ':x2:=4;'( ':x2:=5;') ':x2:=6;'# ':x2:=7;end;compare:=com[x1,x2];end;function operation(a:int64;there:char;b:int64):int64; var i:longint;begincase there of'+ ':operation:=(a+b) mod max;'- ':operation:=(a-b) mod max;'* ':operation:=(a*b) mod max;'^ ':begin operation:=1;for i:=1 to b do operation:=operation*a mod max;end;end;end;function exp(s:string;aa:int64):int64;var i:int64;begins:=s+ '# ';i:=1;ned:=0;ntr:=1;fillchar(oped,sizeof(oped),0);optr:= ' ';optr[1]:= '# ';flag:=false;while not ((s[i]= '# ')and (optr[ntr]= '# ')) do beginif s[i] in [ '0 '.. '9 '] thenbeginif not flag thenbeginned:=ned+1;oped[ned]:=ord(s[i])-ord( '0 ');flag:=true;inc(i);endelsebeginoped[ned]:=oped[ned]*10+ord(s[i])-ord( '0 ');inc(i);end;endelseif s[i]= 'a ' thenbegininc(ned);oped[ned]:=aa;inc(i);endelse if s[i]= ' ' then inc(i)elsebeginflag:=false;case compare(optr[ntr],s[i]) of'< ':begin ntr:=ntr+1;optr[ntr]:=s[i];inc(i);end; '> ':beginthere:=optr[ntr];ntr:=ntr-1;b:=oped[ned];ned:=ned-1;a:=oped[ned];oped[ned]:=operation(a,there,b);end;'= ':begin ntr:=ntr-1;inc(i);end;end;end;end;exp:=oped[1];end;beginassign(f, 'equal.in ');reset(f);readln(f,s[0]);readln(f,n);for i:=1 to n do readln(f,s[i]);fillchar(ans,sizeof(ans),true);close(f);for i:=0 to n doif ans[i] thenfor j:=-4 to 4 dobeginvalue[i,j]:=exp(s[i],j);if value[i,j]<>value[0,j] then begin ans[i]:=false;break;end; end;assign(f, 'equal.out ');rewrite(f);for i:=1 to n doif ans[i] then write(f,chr(ord( 'A ')+i-1));writeln(f);close(f);end.。