NOIP题解.ppt

《NOIP题解.ppt》由会员分享，可在线阅读，更多相关《NOIP题解.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 首先，第一题是四道题中最简单的，直接写代码，注意一些细节就可以了，一百分也是一定要拿到手的，因为后面的分都不是很好拿。 然后是第二题，第二题就要用动态规划了，可以用最朴素的BFS来过那30%的比较弱的数据，用最朴素的动态规划只能拿到50%左右的分，需要对动态规划的状态进行优化，方可拿到一百分。 对于第三题，用搜索很快可拿30，代码复杂度也极低，看到规律的枚举+BFS（floodfill）拿80分，会优化的二分（二分枚举）+BFS拿满分，只是代码稍微麻烦些，或者有思路的用贪心+并查集也可拿满分，代码也要比二分+BFS简单一点。 然后关于本题，数据的反复查找与读取很耗时，想不超时的一些同学需要考

2、虑图论中无向联通图的存储方式，邻接矩阵和完善的静态邻接表直接爆内存零分，所以只能用动态邻接表或者双链表，笔者偷懒，用的不完善静态链表+直接查找数据所以，学学动态邻接表和双链表存储图看来迫在眉睫 最后是第四题，思路比较难，搜索的可以稳拿拿到30分，没有思路就搜索吧。分析过后可以发现最后一题就是一个搜索+“线段覆盖”问题，对于搜索，本体其实用DFS会比BFS快很多，对于“线段覆盖”，用动规解决就好了。 四道题的分值都是100，总分400，而分数线是200，这就意味着只要拿到半数的分就可以达到我们的目的。 回头看看这四道题，首先第一题的100分果断拿到手无疑问，剩下还有三道题，只要再凑100分就行了

3、。 对于这三题都用搜索的算法就可以拿到90分，离分数线还差那么10分，所以，明显不能够这么做在上考场前也应该清楚，既然大家都会搜，就不能想着只用搜索去过联赛，而要对其中的某一偏难题用非搜索的更先进的方式进行解答，这次的分数线就最能作为一个例子。 后两题暂且不说，题都不简单，就暂且用搜索的方法吧，这就可以拿到60分，那剩下的就在第二题了，第二题比其后两题简单得多，其实用足够优化的搜索就可以多拿20分，但是，这是不保险的，正如上段所分析，所以，绞尽脑汁去想这个明显要用动态规划去做的题吧，相信其实过线并不难。 下面，让我们来看看去年我省的过线情况吧：按照选手成绩由高到低排列，“*”为往届获奖选手或初

4、中选手 河南省一共过线43人，其中省实验过线人数为14人。 两个的数字告诉我们，实验的信息学奥赛是全省教的最棒的，我们所处的地方正是学习信息学奥赛最佳的场所，由水平全省领先的老师亲自领导，加上历届NOIP选手经验的支持，再加上是最后一届有保送考试资格的学生，条件可谓空前绝后，我们再不努力过联赛，真就说不过去了，Isnt it？ 好了，不多说了，下面就来看一下每道题详细的分析吧： 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内

5、存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。 假设内存中有M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。 假设一篇英语文章的长度为N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。【数据范围】对于10%的数据有M=1，N 5。对于100%的数据有0

6、M 100，0N 1000。 看过题后也许大家都不禁感慨，这不就是队列的基本操作么？没错，没有想错，对于这道题，这样的数据规模，最一般的方法就行了。基本方法应该已经在大家的心里定了形了，开一个一维数组作为队列，实现题中要求的“先进先出”的操作，再在每次入队时判重并计数就可以了。输入文件：translate.in 输入文件共2 行。每行中两个数之间用一个空格隔开。 第一行为两个正整数M 和N，代表内存容量和文章的长度。 第二行为N 个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文 单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。输出文件：translate.

7、out 共1 行，包含一个整数，为软件需要查词典的次数。 这里其实又给定了一个重要的条件：“每个数（大小不超过1000）代表一个英文”。对此，很快头脑中便会闪出一个对程序“查询内存”（即判重）优化的念头：哈希。【输入输出样例1】 3 7 1 2 1 5 4 4 1【输入输出样例1】 5【输入输出样例2】 2 10 8 824 11 78 11 78 11 78 8 264【输入输出样例2】 6#include using namespace std;int main(void) ifstream input(translate.in); ofstream output(translate.ou

8、t);int i,maxmemory,wordnumber,newword,tail=0,head=-1,que1000; bool existed1001=false; /记录单词是否已经存在（哈希）inputmaxmemorywordnumber;for (i=1;inewword; /读入新单词if (!existednewword) /判断单词是否存在head+; /existednewword=true; /quehead=newword;/若单词不存在，入队并标记为已存在（若存在，不入队）if (head-tail=maxmemory) /判断队列是否已满existedquetai

9、l=false; /tail+;/若已满，删除队尾元素，标记删除了的队尾元素为不存在 outputhead+1endl;input.close(); output.close(); return(0); 小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。1 2 3 4 5 N 乌龟棋中M 张爬行卡片，分成4 种不同的类型（M 张卡片中不一定包含所有4 种类型的卡片，见样例），每种类型的卡片上分别标有1、2、3、4 四个数字之一，表示使用这种卡片

10、后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。 游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。 很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。 现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？【输入】输入文件名tortoise.in。输入文件的每行中两个数之间用

11、一个空格隔开。第1 行2 个正整数N 和M，分别表示棋盘格子数和爬行卡片数。第2 行N 个非负整数，a1, a2, , aN，其中ai 表示棋盘第i 个格子上的分数。第3 行M 个整数，b1,b2, , bM，表示M 张爬行卡片上的数字。输入数据保证到达终点时刚好用光M 张爬行卡片。【输出】输出文件名tortoise.out。输出只有1 行，1 个整数，表示小明最多能得到的分数。【数据范围】对于30%的数据有1 N 30，1 M 12。对于50%的数据有1 N 120，1 M 50，且4 种爬行卡片，每种卡片的张数不会超过20。对于100%的数据有1 N 350，1 M 120，且4 种爬行卡

12、片，每种卡片的张数不会超过40；0 ai 100，1 i N；1 _bi 4，1 i M。【输入输出样例1】9 56 10 14 2 8 8 18 5 171 3 1 2 173【输入输出样例 1 说明】小明使用爬行卡片顺序为1，1，3，1，2，得到的分数为6+10+14+8+18+17=73。注意，由于起点是1，所以自动获得第1 格的分数6。【输入输出样例2】13 84 96 10 64 55 13 94 53 5 24 89 8 301 1 1 1 1 2 4 1455 拿到这道题，首先想到排列组合问题，因此可以直接用最简单的思路，用搜索的方法把所有可能的排列枚举出来，再求其最优。 不过，

13、明显的看出，这样只能过那30%的简单数据，见到另外70%的数据，12个以上的卡片，估计就要超时了。 判断出是排列问题，那这道题似乎就显得简单一些了，根据这个思路再进一步，因为只有四种类型的卡片，且不需要输出具体的步骤，可以想到，其实用动态规划解决这道题是可行的。 在我的动规算法中，状态之一是每种卡片使用的情况，状态之二是当前状态可以所得的最大分数。 开数组card 来存储四种卡片的个数，其下标表示卡片的使用效果，即用一张该种卡片可以走几格。 开数组step 来存储每一格的分数情况，其下标表示该格是第几格，以step 1 为第一格。 开数组a i j k l 来存储用某种方式所得的最大分数，其中

14、i，j，k，l分别表示当前第一，二，三，四种卡片的使用张数，则其初始状态为a 0 0 0 0 （= step 1 ），目标状态为a card 1 card 2 card 3 card 4 。中间的状态转移规则为（在不越界的情况下）：a i j k l = step i*4+k*3+j*2+i+1 +max a i-1 j k l ， a i j-1 k l ， a i j k-1 l ， a i j k l-1 在这里，因为四种卡片的张数、当前走到底几格五个量中“知四求一”，所以还用另外一种动态规划的方法。 开数组f i , a , b , c ，其中i表示前i格，a表示第一种卡片剩余数量，b

15、表示第二种，c表示第三种，可用计算公式 （ i-1-a-2b-3c ）div 4 得出第四种卡片剩余数量。 于是dp（ 动态规划 ）求解 f i , a , b , c = step i +max f i-1 , a+1 , b , c , f i-2 , a , b+1 , c , f i-3 , a , b , c+1 , f i-4 , a , b , c ; 最后输出f n , 0 , 0 , 0 即可#include using namespace std;long long a41414141;int fm(int maxnum,int a,int b,int c) /函数fm（f

16、indmax）为找四个数中最大值并返回最大值的函数if (maxnuma)maxnum=a;if (maxnumb)maxnum=b;if (maxnumstepnumcardnum;for (i=1;istepi;for (i=1;item; cardtem+;a 0 0 0 0 =step 1 ;for (i=0;i=card1;i+)for (j=0;j=card2;j+)for (k=0;k=card3;k+)for (l=0;l=card4;l+) if (i=j&j=k&k=l&l=0) continue;if (i != 0) tem = a i-1 j k l + step l

17、*4+k*3+j*2+i+1 ;else tem = 0;if (j != 0) tem2 = a i j-1 k l + step l*4+k*3+j*2+i+1 ;else tem2 = 0;if (k != 0) tem3 = a i j k-1 l + step l*4+k*3+j*2+i+1 ;else tem3 = 0;if (l != 0) tem4 = a i j k l-1 + step l*4+k*3+j*2+i+1 ;else tem4 = 0;a i j k l = fm( tem , tem2 , tem3 , tem4 ); outputa card1 card2

18、card3 card4 endl; input.close(); output.close(); return(0); S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。 每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会

19、去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。 在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？ 输入格式 Input Format 输入文件的每行中两个数之间用一个空格隔开。第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的M 行每行为三个正整数aj，bj，cj，表示aj

20、号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证1=ajbjN,0cj=1,000,000,000 且每对罪犯组合只出现一次。 输出格式 Output Format 输出共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。 数据范围 对于30%的数据有N15。 对于70%的数据有N2000，M50000。 对于100%的数据有N20000，M100000。Sample Input4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 Sample Output3512 对于这道题，搜

21、索的思路一目了然，而对于其他思路其实笔者一直都未想到，也是看了其他人的分析后才恍然大悟。总结后，本体一共有三种解法，我将一一对其进行说明。 三种解法依次为： ：搜索（预期：30分） ：二分（二分枚举）+BFS（floodfill）（100分） ：贪心+并查集（100分） 搜索不是万能的，但没有搜索是万万不能的，多少个NOIP过来人告诉我们，不会了你就搜，搜索作为一种思路简单的“万能”法，只要不加时空限制，可以过所有题，所以，不行了就搜是绝对正确的。 看看这道题，有两个监狱，好样的，两个，这就有了“0-1背包”的感觉了：每个人不是FALSE监狱的就是TRUE监狱的。所以，对搜索，也用“0-1”式

22、的搜索吧，其核心代码如下：（对于下代码，默认所有罪犯在“再分配”前均在FALSE监狱）void sortit(int x,bool checkin) /x表示“罪犯编号” if (checkin) / checkin表示罪犯x被“再分配”后是否迁往了TRUE监狱prisonedx=true; / bool prisoned 是全局变量，含义同checkin，下标含义同xif (x=n) /判断罪犯是否已全部“再分配”（n表示罪犯个数）calculate(); /“计算”当前分法的“最大怨气值”elsesortit(x+1,false); /“再分配”下一个罪犯，让其留在FALSE监狱sorti

23、t(x+1,true); /“再分配”下一个罪犯，让其迁往TRUE监狱if (checkin)prisonedx=false; /若罪犯被迁往TRUE监狱，让其迁回（回溯）main函数中sortit(1,false);sortit(1,true);“计算”当前分法的“最大怨气值”代码如下：void calculate(void)int i,j,maxpower=0; /maxpower表示当前“最大怨气值”for (i=1;i=n;i+) /i和j各表示一个罪犯for (j=1;jmaxpower)/矩阵”的方式记录任意两个罪犯间的“怨气值”maxpower=relaij;if (maxpow

24、erminmaxpower)minmaxpower=maxpower;/int minmaxpower=“无限大” 为全局变量，记录最小的“最大怨气值” 显然，用不完全邻接矩阵就意味着过不全，之所用邻接矩阵是因为搜索能够承受的范围太小，邻接矩阵足矣搜索是够弱小的弱爆了 但是，并不是想到了新的方法这段搜索代码就用不着了，写一个刚学的变态的看着就欠扁的有偏分性质的分支结构就一目了然了：if (N=15)进行方法 else进行方法或。 【Tip：可避免“先进”反而全错的情况，这才是精华啊！】 接下来，来看看可以得满分的方法吧。 先来介绍二分+BFS详细的方法。 方法分为三大步，其中第三步为核心BFS

25、，将对其进行细化的分解与解释。1）读入数据，给“怨气值”升序快排（其“附属数据”跟着移动，即对第三列数据进行快排，前两列数据跟着移动）。 2）二分枚举出一个“最大怨气值”（“最大怨气值”=“mid怨气值”）直接取（l+r）/2为“mid怨气值”，其中l初值=0；r初值=N-1。 3）BFS（floodfill）：（具体又分为三个小部分）1、新开（或初始化）一个bool型一维数组“a ”，2、给“最大怨气值”对应的两“附属数据”（“附属数据”=“罪犯编号”）为下标的两个a 赋值为0，表示两犯人同在监狱0。【解释：这样，确定了一个可能的“最大怨气值”，剩下的比“最大怨气值”还大的“怨气值”所对应的

26、人必须不同监狱】【所以，接下来我们就要验证是否能够使“剩下的比最大怨气值还大的怨气值所对应的人不同监狱”】【若可以使“”，说明最终确定的“最大怨气值”小于或等于等于当前“最大怨气值”（l=l;r=“最大怨气值”的位置;）】【若不可以使“”，说明最终确定的“最大怨气值”一定还要大于当前“最大怨气值”（l=“最大怨气值”的位置+1;r=r;）】【以上两行应该稍后才会理解】【最后直到二分到无法二分时，输出当前“最大怨气值”就可以了】3、用queue（队列）进行floodfill，基本规则：a 拓展 =!a 拓展源 。【具体操作：让当前“最大怨气值”对应的两个“附属数据”（=“罪犯编号”）均入队】【具

27、体操作：拓展并删去队首节点：在“大于当前最大怨气值的数据”中找出与队首罪犯（“罪犯编号”）有“怨气值”的罪犯，让其入队，给a 入队罪犯 赋值为!a 队首罪犯 】【操作解释：“怨气值”更大的一对对罪犯们不允许在同一监狱，故罪犯必须和已确定位置的对应罪犯在不同监狱】【操作解释：“怨气值”更小的一对对罪犯们随便怎么样无所谓了，估致之不理即可】【细节：在赋值时还必须有以下规则：若第一次赋值，执行赋值操作。若不是第一次赋值，则“判断”后赋值】【“判断”规则：若值与原值相同，执行赋值操作，不做额外操作；若值不相同，说明出现了“冲突”，当前“最大怨气值”情况不存在，本系列操作“失败”（“失败”=不可以使“”

28、），应用二分规则进行下一步二分枚举并BFS检验】【冲突解释：一个人不可能既在“0监狱”，又在“1监狱”】【本系列操作“成功”（“成功”=可以使“”）前提：直到队空都没有“冲突”出现，此时还需进一步“验证”】【验证：没入过队的“怒气值”大于“最大怒气值”的罪犯们需要进一步用floodfill验证，需满足所有有关系的都不在同一监狱】【最终验证：如果确定了最后的“最大怨气值”为最小的，还需要判断怒气值是否可以是“0”】 对于方法，BFS（floodfill）是主体，二分（二分枚举）是关键，BFS必不可少，不理解二分枚举的同学可以改用普通枚举，但效率会大大降低，远远拿不到满分。 看过以上方法详细解释后

29、，估计可以理解个差不多，但是也会意识到代码的复杂程度看来不会很善良 笔者没有开分函数，很蛋疼的敲了近500行代码就没办法展示了。 与上述不同的是，实际操作时我把bool a 改为了int flag ，来更好的确定被分配到的监狱（是被分到了“-1”监狱还是“1”监狱，或者是还没被分配，用“0”来表示）。 这是第二种方法，可以保证过全（“RQNOJ”评测通过全部数据）。 其实用第三种方法会省很多代码的行数，第三种方法也是我认为最好的方法了。 这个，看了好多代码还是不懂，看了好多题解依然不懂。度娘不懂、谷哥不懂结果越看越不懂 别听那些神牛们的专业语言，这个思路，用越平凡朴素的语言叙述其实越好懂： 假

30、如自己是那个倒霉的警察局长，肯定不会写程序解决的，为了安全起见还是会手动去分：那怎么分呢？1）先给“怨气值”来个人类排序。2）找最大的“怨气值”，把对应的两人分到两所监狱去。3）找次大的“怨气值”：（对应的两个人这时有三种情况）1其中已经有一个人分好了监狱：另一个人分到另一个监狱。2两个人甲乙都还没分好监狱：找与甲乙有怨的已经在监狱里的所有人，发现其中与甲最怨的是丙，与乙最怨的是丁，找出丙丁中更怨（最怨、更怨：排序顺序靠近大的一段）一点的丙，发现丙在狱1，果断把甲放到狱2，乙放到狱1。3两个人的监狱都分好了：（又分两种情况）3两个人的监狱都分好了：（又分两种情况）1*两个人不同监狱：刚好，不用

31、分了。2*两个人同一个监狱：看来这俩会是最大的死冤家，今年的乌纱帽就算是押在他们手里了（“最终结果”求出）【若本次没有得出“最终结果”，反复执行第3）步】思路如上所示，相信方法一定很好理解，并查集的体现其实就相当于刚刚方法的bool a ，用来标记其属于哪一个集合（监狱），而贪心则体现在每次都先安排“怨气值”大的一对罪犯。 在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N 行M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，

32、分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。 由于第N 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。 其简图如右所示：输入格式 输入文件的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数N 和M，表示矩形

33、的规模。 接下来N 行，每行M 个正整数，依次代表每座城市的海拔高度。输出格式 输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少 建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有 几座干旱区中的城市不可能建有水利设施。数据规模 【输入输出样例1】 2 5 9 1 5 4 3 8 7 6 1 2【输入输出样例2】 3 6 8 4 5 6 4 4 7 3 4 3 3 3 3 2 2 1 1 2【输入输出样例1】 1 1【输入输出样例2】 1 3【样例1 说明】 只需要在海拔为9 的那座城市中建造蓄水厂，即可满足要求。【样例2 说明】 上图

34、中，在3 个粗线框出的城市中建造蓄水厂，可以满足要求。以这3 个蓄水厂为源头 在干旱区中建造的输水站分别用3 种颜色标出。当然，建造方法可能不唯一。 先假设第一行的所有的点都建设蓄水厂，即可求出第n行的点是否都可以被访问到。如果不行则输出此时剩余没有被访问到的点的个数。 如果可以，接下来的目的就是求最少的蓄水厂数。在已经确定最后一行都是可以访问到的情况下，可以证明，第一行访问到的最后一行的点都是连续的。 证明：如图，假设A可以访问的区域是蓝色部分，且中间有一个X标记的位置是不可访问的。在已经确定最后一行都是可以访问的情况下，假设有B这个点可以走到X的位置。路线是绿色的部分。因为A要走到X右边的的蓝色部分（红色的线），所以路线一定要穿过绿色的线，即表示可以从绿色的路线走到X点，与假设矛盾。所以能访问的一定是连续的。 接着可以用两边DFS，从最后一行出发来更新第一行的能够到达最后一行的左边界STi和右边界EDi。 最后，用DP求最少要用几段可以覆盖1.n。 Fi,j表示前i段，到达j位置的最小蓄水厂数。 fi,j=fi-1,sti-1+1(sti=j=edi); 可以降维至fj=fsti-1+1; 代码就不在幻灯片里展示了，用兴趣的可以参看“代码”文件夹中的本人的关于NOIP2010的代码。谢谢！谢谢！河南省实验中学河南省实验中学刘石坚刘石坚指导老师：王国正指导老师：王国正