noip2005提高组解题报告(转)

1、第一题谁拿了最多奖学金第二题过河第三题篝火晚会第四题等价表达式v【问题描述【问题描述】 v某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：五种，获取的条件各自不同： v1) 院士奖学金，每人院士奖学金，每人8000元，期末平均成绩高于元，期末平均成绩高于80分（分（80），并且），并且在本学期内发表在本学期内发表1篇或篇或1篇以上论文的学生均可获得；篇以上论文的学生均可获得；2) 五四奖学金，每人五四奖学金，每人4000元，期末平均成绩高于元，期末平均成绩高于85分（分（85），并且），并且班

2、级评议成绩高于班级评议成绩高于80分（分（80）的学生均可获得；）的学生均可获得；3) 成绩优秀奖，每人成绩优秀奖，每人2000元，期末平均成绩高于元，期末平均成绩高于90分（分（90）的学生）的学生均可获得；均可获得；4) 西部奖学金，每人西部奖学金，每人1000元，期末平均成绩高于元，期末平均成绩高于85分（分（85）的西部）的西部省份学生均可获得；省份学生均可获得；5) 班级贡献奖，每人班级贡献奖，每人850元，班级评议成绩高于元，班级评议成绩高于80分（分（80）的学生干）的学生干部均可获得；部均可获得；v只要符合条件就可以得奖，每项奖学金的获奖人数没只要符合条件就可以得奖，每项奖学金

3、的获奖人数没有限制，每名学生也可以同时获得多项奖学金。有限制，每名学生也可以同时获得多项奖学金。例如例如姚林的期末平均成绩是姚林的期末平均成绩是87分，班级评议成绩分，班级评议成绩82分，同分，同时他还是一位学生干部，那么他可以同时获得五四奖时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是学金和班级贡献奖，奖金总数是4850元。现在给出若元。现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数干学生的相关数据，请计算哪些同学获得的奖金总数最高（最高（假设总有同学能满足获得奖学金的条件假设总有同学能满足获得奖学金的条件）。）。 v【输入文件【输入文件】输入文件输入文

4、件scholar.in的第一行是一个整数的第一行是一个整数N（1 = N = 100），表），表示学生的总数。接下来的示学生的总数。接下来的N行每行是一位学生的数据，行每行是一位学生的数据，从左向右依从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过母组成的长度不超过20的字符串（不含空格）；期末平均成绩和的字符串（不含空格）；期末平均成绩和班级评议成绩都是班级评议成绩都是0到到100之间的整数

5、（包括之间的整数（包括0和和100）；是否是学）；是否是学生干部和是否是西部省份学生分别用一个字符表示，生干部和是否是西部省份学生分别用一个字符表示，Y表示是，表示是，N表示不是；发表的论文数是表示不是；发表的论文数是0到到10的整数（包括的整数（包括0和和10）。）。每两个每两个相邻数据项之间用一个空格分隔。相邻数据项之间用一个空格分隔。【输出文件【输出文件】输出文件输出文件scholar.out包括三行，第一行是获得最多奖金的学生的包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以如果有两位或两位以上的学生获

6、得的奖金最多，输出他们之中在输入文件中出现最早上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。的学生的姓名。第三行是这第三行是这N个学生获得的奖学金的总数。个学生获得的奖学金的总数。v【样例输入【样例输入】4YaoLin 87 82 Y N 0ChenRuiyi 88 78 N Y 1LiXin 92 88 N N 0ZhangQin 83 87 Y N 1【样例输出【样例输出】ChenRuiyi900028700v这是一道标准的送分题（也称水题），这是一道标准的送分题（也称水题），算法就是纯粹的模拟。算法就是纯粹的模拟。v这道题唯一值得一提的就是怎样存储数据。这道题唯一

7、值得一提的就是怎样存储数据。v从从输入格式输入格式可以看出人名需要一个字符串来存可以看出人名需要一个字符串来存储，成绩需要整型存储，剩下的需要字符来存储，成绩需要整型存储，剩下的需要字符来存储。由此可以想到储。由此可以想到用一个用一个记录类型记录类型来存储来存储是个不错的选择，当然，用是个不错的选择，当然，用5个数组个数组来存储也是来存储也是可以的。可以的。v接下来的就是一个一个数据来模拟算出第接下来的就是一个一个数据来模拟算出第n个人个人可以得到的奖学金数，比较一下是否是最多的，可以得到的奖学金数，比较一下是否是最多的，然后在累计器上加上这个奖学金数。然后在累计器上加上这个奖学金数。v最后按

8、格式输出。最后按格式输出。（注意文末换行）（注意文末换行）v正如开始所说的，这是一道水题，是一定要拿满正如开始所说的，这是一道水题，是一定要拿满分的。分的。v【问题描述【问题描述】 v在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：能到达的点看成数轴上的一串整点：0，

9、1，L（其中（其中L是桥是桥的长度）。坐标为的长度）。坐标为0的点表示桥的起点，坐标为的点表示桥的起点，坐标为L的点表示桥的终点。的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到到T之间的任意正整数（包括之间的任意正整数（包括S,T）。）。当青蛙跳到或跳过坐标为当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度题目给出独木桥的长度L，青蛙跳跃的距离范围青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙，桥上石子的位置。你的任务是确定

10、青蛙要想过河，最少需要踩到的石子数。要想过河，最少需要踩到的石子数。 v输入格式输入格式 v输入文件的第一行有一个正整数输入文件的第一行有一个正整数 L （ 1 = L = 109 ），表示独），表示独木桥的长度。第二行有三个正整数木桥的长度。第二行有三个正整数 S ， T ， M ，分别表示青蛙一，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中次跳跃的最小距离，最大距离，及桥上石子的个数，其中 1 = S = T = 10 ， 1 = M = 100 。第三行有。第三行有 M 个不同的正整数分别个不同的正整数分别表示这表示这 M 个石子在数轴上的位置（数据保证桥的起点和终点

11、处没个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。有石子）。所有相邻的整数之间用一个空格隔开。 v输出格式输出格式 v输出文件只包括一个整数，表示青蛙过河最少需要踩到的石子数。输出文件只包括一个整数，表示青蛙过河最少需要踩到的石子数。v样例输入样例输入 ：v10v2 3 5v2 3 5 6 7 v样例输出样例输出 ：v2v数据范围：数据范围：v对于对于30%的数据，的数据，L = 10000；对于全部的数据，对于全部的数据，L = 109。 v如果要求出跳到第如果要求出跳到第L个点踩到石子的最小值，就个点踩到石子的最小值，就要涉及到两个量要涉及到两

12、个量（1）.第第L个点是否有石子；个点是否有石子；（2）.跳到第跳到第L-s个点个点第第L-t个点（就是可以个点（就是可以跳到跳到L点的点）需要踩到的最少石子数。也就是点的点）需要踩到的最少石子数。也就是说说fL与与fL-s,fL-s-1,fL-s-2，fL-t有关，有关，由此很容易联想到使用动态规划。由此很容易联想到使用动态规划。v依据题意可以得到依据题意可以得到DP状态转移方程为：状态转移方程为：v fk-s v fk-s-1 vfk=max fk-s-2 + datak (石子数石子数)v .v fk-tv即即: fk=maxfk-j+datak (s=j=t)v但是仔细考虑一下如果把所

13、有的点都算一下的话，时间但是仔细考虑一下如果把所有的点都算一下的话，时间复杂度为复杂度为O（L*（t-s+1）,空间复杂度为空间复杂度为O（L*2），），当当L=109时，无论是空间，还是时间，都无法承受。时，无论是空间，还是时间，都无法承受。然而然而M却又却又t且且l mod t0，那么我们就可以，那么我们就可以将第二个石子挪到将第二个石子挪到以第一个石子为原点以第一个石子为原点l mod t 的位置的位置,即将第二个石子即将第二个石子向前挪向前挪 （l div t）*t 个个 位置，但是要注位置，但是要注意：不光要挪动第二个石子，还要挪动后面的所有石子。意：不光要挪动第二个石子，还要挪动后

14、面的所有石子。v这是一个简单的优化，处理出来的数组数据量最多会这是一个简单的优化，处理出来的数组数据量最多会比比10000稍大一点，这样的话时间和空间便都可以优稍大一点，这样的话时间和空间便都可以优化了。但优化的方法也不只这一个，网上还有其他方化了。但优化的方法也不只这一个，网上还有其他方法：比如在法：比如在llcm(s,t)或或l100+2*t进行压缩状态，其进行压缩状态，其本质是一样的，这里就不再多提。本质是一样的，这里就不再多提。vfor k:=1 to m dov beginv ak:=ak-s;v if (ak-ak-1-1)mod t0 then j:=(ak-ak-1-1)div

15、 t)*tv else if ak-ak-1-1t then j:=(ak-ak-1-1)div t)-1)*tv else j:=0; j用于记录第k个石子需要向前挪动的位置v ak:=ak-j;v bak:=1;v s:=s+j; s用于记录前面的k个石子一共向前挪动的位置v end;v注意事项：注意事项：v注意题目中给的条件注意题目中给的条件“当青蛙跳到或跳过坐标当青蛙跳到或跳过坐标为为L的点时，就算青蛙已经跳出了独木桥。的点时，就算青蛙已经跳出了独木桥。” v这是什么意思呢？这是什么意思呢？v就是说就是说fL不一定是要求的结果，这个结果可以不一定是要求的结果，这个结果可以是是fL+1,

16、fL+2,.这到什么时候是个头呢？这到什么时候是个头呢？v其实很简单，和上面压缩状态一样，只需找到其实很简单，和上面压缩状态一样，只需找到min(fL+k) (0=kt)即可。即可。v还要注意的一点是：还要注意的一点是：v不要以为样例中给出的石子位置是不要以为样例中给出的石子位置是升序的就忘了把石子数升序的就忘了把石子数排序排序。v这不是一道非常简单的动规题，这道题用朴素的动态规这不是一道非常简单的动规题，这道题用朴素的动态规划只能得到划只能得到L=10000的的30分，而加上压缩状态后就可分，而加上压缩状态后就可以轻松以轻松AC，所以这一点技巧是应当掌握的。，所以这一点技巧是应当掌握的。v【

17、问题描述【问题描述】v佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了教官的赏识，成为了“小教官小教官”。在军训结束的那天晚上，佳佳。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有被命令组织同学们进行篝火晚会。一共有 n 个同学，编号从个同学，编号从 1 到到 n 。一开始，同学们按照。一开始，同学们按照 1 ， 2 ， n 的顺序坐成一圈，而的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使

18、之符合同学们的意愿，成为摆在佳的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。佳面前的一大难题。 佳佳可向同学们下达命令，每一个命令的形式如下：佳佳可向同学们下达命令，每一个命令的形式如下： (b 1 , b 2 ,. b m -1 , b m ) v这里这里 m 的值是由佳佳决定的，每次命令的值是由佳佳决定的，每次命令 m 的值都可以不同。的值都可以不同。这这个命令的作用是移动编号是个命令的作用是移动编号是 b 1 ， b 2 ， b m 1 ， b m 的的这这 m 个同学的位置。要求个同学的位置。要求 b 1 换到换到 b 2 的位置上，的位置上， b 2 换到

19、换到 b 3 的位置上，的位置上，要求，要求 b m 换到换到 b 1 的位置上。的位置上。 执行每个命令都需要一些代价。我们假定如果一个命令要移动执行每个命令都需要一些代价。我们假定如果一个命令要移动 m 个人的位置，那么这个命令的代价就是个人的位置，那么这个命令的代价就是 m 。我们需要佳佳用。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？最少的总代价实现同学们的意愿，你能帮助佳佳吗？v输入格式输入格式 v输入文件输入文件 的第一行是一个整数的第一行是一个整数 n （ 3 = n = 50000 ），），表示表示一共有一共有 n 个同学。其后个同学。其后 n 行每行包括两个不

20、同的正整数，以一行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是个空格隔开，分别表示编号是 1 的同学最希望相邻的两个同学的同学最希望相邻的两个同学的编号，编号是的编号，编号是 2 的同学最希望相邻的两个同学的编号，的同学最希望相邻的两个同学的编号，编号是编号是 n 的同学最希望相邻的两个同学的编号。的同学最希望相邻的两个同学的编号。 输出格式输出格式 v输出文件输出文件 包括一行，这一行只包含一个整数，为最小的总代价。包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出如果无论怎么调整都不能符合每个同学的愿望，则输出 -1 。 v样例输入

21、样例输入 ：v4v3 4v4 3v1 2v1 2v样例输出样例输出 ：v2v刚开始看到这道题的时候我们可能会觉得无从下手，搜索的方法刚开始看到这道题的时候我们可能会觉得无从下手，搜索的方法肯定超时肯定超时动态规划？贪心？找不出思路动态规划？贪心？找不出思路但认真读题，再模拟但认真读题，再模拟样例，我们可以发现这道题就要是从一个样例，我们可以发现这道题就要是从一个起始状态起始状态转换到满足输转换到满足输入数据的入数据的目标状态目标状态，而结果正是这个状态转换过程中所要进行移，而结果正是这个状态转换过程中所要进行移动的最小次数。动的最小次数。v起始状态：起始状态：v所谓的起始状态便是所谓的起始状态

22、便是1，2，3，n这这n个节点组成的一个节点组成的一个环，而这个环有个环，而这个环有n种正序读法，和种正序读法，和n种倒序读法。种倒序读法。v目标状态：目标状态：v目标状态也是一个环，但我们最好把它转换成目标状态也是一个环，但我们最好把它转换成2*n条链，条链，只要满足这些链的关系，便称为达到了目标状态。只要满足这些链的关系，便称为达到了目标状态。v构造起始状态：构造起始状态：vFor t:=1 to n dov beginv at:=t;v at+n:=t; end;将环转换成链，枚举起点将环转换成链，枚举起点t，便可得到终点，便可得到终点t+n-1的序列的序列v构造目标状态：构造目标状态：

23、vl1:=1; j:=1; bo1:=1; 初始化，构建起点为初始化，构建起点为1的目标状态的目标状态vl为记录目标状态的数组，为记录目标状态的数组，bo判断某个节点是否在判断某个节点是否在l中出现过中出现过vrepeatv if (alj,1lj-1)and(alj,2lj-1)and(j1) then 在此前需构造临接表在此前需构造临接表v begin writeln(-1); halt; end; v 如果某两个点之间不能满足相邻关系，就无法构成目标状态如果某两个点之间不能满足相邻关系，就无法构成目标状态v for t:=1 to 2 dov if boalj,t=0 thenv beg

24、inv boalj,t:=1;v inc(j);v lj:=alj-1,t;v break;找到一个可以相邻的点即可，即找到一个目标状态即可找到一个可以相邻的点即可，即找到一个目标状态即可v end;vuntil j=n;v得到一个目标状态以后，便可以像转化初始状态那样处理目标状态得到一个目标状态以后，便可以像转化初始状态那样处理目标状态v认真分析佳佳的命令：认真分析佳佳的命令： v(b 1 , b 2 ,. b m -1 , b m ) 这里并没有指这这里并没有指这m个点必须是在一块的，只是说从原序列里找出了个点必须是在一块的，只是说从原序列里找出了m个点进行交换，交换代价为个点进行交换，交

25、换代价为m。v由此我们可以想到，由此我们可以想到，如果起始状态和目标状态的某一位置是相同如果起始状态和目标状态的某一位置是相同的数字，那么这个数字便可以不进行交换，也不计入代价；而若的数字，那么这个数字便可以不进行交换，也不计入代价；而若这一位置上的数字不是相同的数字，那么这个数字就必须进行交这一位置上的数字不是相同的数字，那么这个数字就必须进行交换来达到目标状态，这个交换的最小代价是换来达到目标状态，这个交换的最小代价是1。v于是，我们的任务便是找出起始状态和目标状态之间的最小差异，于是，我们的任务便是找出起始状态和目标状态之间的最小差异，这个差异便可以成为这种转换的最小代价这个差异便可以成

26、为这种转换的最小代价。For t:=1 to n do for x:=1 to n do begin j:=0; for k:=t to t+n-1 do if aklx+k-t then inc(j); if jmin then min:=j; end; 仔细分析一下这个代码只枚举了两种状态的正序读法，倒序还没有仔细分析一下这个代码只枚举了两种状态的正序读法，倒序还没有枚举，如果再加上倒序，时间复杂度就是枚举，如果再加上倒序，时间复杂度就是O（2n*2n*n）,即即O（4*n3），），就算是稍加优化，固定某个状态，也只能优化到就算是稍加优化，固定某个状态，也只能优化到O（2*N2），），如果

27、代入如果代入50000的话，结果可想而知，最多过前的话，结果可想而知，最多过前3个点。个点。所以这个算法仍需要优化！所以这个算法仍需要优化！v究竟该怎么优化呢？究竟该怎么优化呢？v这里我们通过一个例子来分析：这里我们通过一个例子来分析：v如初始环为如初始环为1 2 3 4 5 6 7 8 9 10，目标环若为，目标环若为1 8 2 7 5 3 6 4 10 9，则可通，则可通过命令（过命令（1，8，10）使之变成）使之变成8 2 3 4 5 6 7 10 9 1，再通过命令（，再通过命令（7，4，5，3）使之变成）使之变成8 2 7 5 3 6 4 10 9 1（这就是目标环），总代价为（这就

28、是目标环），总代价为7。 v上述的总代价上述的总代价7可以这样得出：由目标环可得到可以这样得出：由目标环可得到2*n个不同的目标序列，个不同的目标序列，v即：即： 1 8 2 7 5 3 6 4 10 9、8 2 7 5 3 6 4 10 9 1、2 7 5 3 6 4 10 9 1 8、7 5 3 6 4 10 9 1 8 2、5 3 6 4 10 9 1 8 2 7、及及9 10 4 6 3 5 7 2 8 11 9 10 4 6 3 5 7 2 8、8 1 9 10 4 6 3 5 7 2、2 8 9 10 4 6 3 5 7、 初始初始状态状态12345678910目标目标状态状态18

29、275364109是否是否相同相同TFFFTFFFFF初始初始状态状态12345678910目标目标状态状态82753641091是否是否相同相同FTFFFTFFTF初始初始状态状态12345678910目标目标状态状态27536410918是否是否相同相同FFFFFFFFFF初始初始状态状态12345678910目标目标状态状值差值0693079619初始初始状态状态12345678910目标目标状态状态82753641091差值差值7041807201初始初始状态状态12345678910目标目标状态状态27536410918差值差值1529183128v由以上两

30、个表格可以得出这个结论：由以上两个表格可以得出这个结论：v将目标环顺时针移动将目标环顺时针移动1步，或移动步，或移动2步，步，3步时得到的结果是不一样步时得到的结果是不一样的，但是拥有相同差值的数在每次移动后差值改变但仍相同。的，但是拥有相同差值的数在每次移动后差值改变但仍相同。所所以以拥有相同差值的数总会在移动拥有相同差值的数总会在移动k步后使差值成为步后使差值成为0，即达到，即达到目标状态目标状态。将初始状态和目标状态转换，这样目标状态就迅速压。将初始状态和目标状态转换，这样目标状态就迅速压缩到两个，缩到两个，一个是以一个是以1为起点的正序序列，一个是以为起点的正序序列，一个是以n为起点的

31、倒为起点的倒序序列序序列，我们要求的结果便是在这两个序列里差值相同的数最多我们要求的结果便是在这两个序列里差值相同的数最多的数个数的数个数max，然后是其他数都移动到这个差值。而要输出的结，然后是其他数都移动到这个差值。而要输出的结果果便是便是n-max。vprocedure search;vvar t,k,o,max:longint;vbeginvo:=0; max:=0;vfor k:=1 to n do 正序序列正序序列v beginv o:=lk-k; if omax then max:=so;v end;vo:=0; fillchar(s,sizeof(s),0) ;vfor k:=

32、1 to n do 倒序序列倒序序列v beginv o:=ln-k+1-k; if omax then max:=so;v end;vmin:=n-max;vend;v由此这个问题完美解决，时间复杂度迅速降低到由此这个问题完美解决，时间复杂度迅速降低到 O（k*n）vk为不超过为不超过4的正整数，包括了做状态的正整数，包括了做状态(O(2*n)和求值和求值(O(2*n)两个部分，而且这里的状态不必包括做初始状态两个部分，而且这里的状态不必包括做初始状态v【问题描述【问题描述】v明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻

33、烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。断选项中哪些代数表达式是和题干中的表达式等价的。 这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？任务吗？这个选择题中的每个表达

34、式都满足下面的性质：这个选择题中的每个表达式都满足下面的性质：v1 表达式只可能包含一个变量表达式只可能包含一个变量a。2 表达式中出现的数都是正整数，而且都小于表达式中出现的数都是正整数，而且都小于10000。3 表达式中可以包括表达式中可以包括四种运算四种运算+（加），（加），-（减），（减），*（乘），（乘），（乘幂），以及小括号（乘幂），以及小括号(，)。小括号的优先级最高，其次是。小括号的优先级最高，其次是，然后是然后是*，最后是，最后是+和和-。+和和-的优先级是相同的。相同优先的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符级的运算从左到右进行。（注意：运算符+，-

35、，*，以及小括以及小括号号(，)都是英文字符）都是英文字符）4 幂指数只可能是幂指数只可能是1到到10之间的正整数（包括之间的正整数（包括1和和10）。）。5 表达式内部，头部或者尾部都可能有一些多余的空格。表达式内部，头部或者尾部都可能有一些多余的空格。下面是一些合理的表达式的例子：下面是一些合理的表达式的例子：(a1) 2)3，a*a+a-a，(a+a)，9999+(a-a)*a，1 + (a -1)3，1109v输入格式输入格式 ：v输入文件输入文件 的第一行给出的是题干中的表达式。第二行是一个整数的第一行给出的是题干中的表达式。第二行是一个整数 n （ 2 = n ,),v -(,),

36、v *(,),v (,),v (,),v )(,=,),v (,);v 这种优先级关系也可以通过将符号这种优先级关系也可以通过将符号“赋值赋值”来实现来实现v p+:=3; p-:=3; p*:=2; p/:=2; p:=1;v2.过滤字符串中的空格，替换未知数的值。过滤字符串中的空格，替换未知数的值。v 遇到空格可以直接跳过，不作处理。遇到未知数要将遇到空格可以直接跳过，不作处理。遇到未知数要将其替换成数字，存在数字栈中。其替换成数字，存在数字栈中。v3.谨防负数。谨防负数。v 如果遇到这样的表达式（如果遇到这样的表达式（-1），最好在处理表达），最好在处理表达式前先扫描一遍，在式前先扫描一遍，在-前加上前加上0就好处理了。就好处理了。v4.未知数的假设。未知数的假设。v如果程序中只枚举了如果程序中