,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,NOIP2023提高组复赛题解,河南省试验中学 彭勃,题目描述：,笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率特殊大！这种方法的具体描述如下：假设maxn是单词中消逝次数最多的字母的消逝次数，minn是单词中消逝次数最少的字母的消逝次数，假设maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。,第一题 笨小猴,输入格式：,输入文件word.in只有一行，是一个单词，其中只可能消逝小写字母，并且长度小于100。,输出格式：,输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；其次行是一个整数，假设输入单词是Lucky Word，输出maxn-minn的值，否则输出0。,样例1,输入：,error,输出：Lucky Word,2,解释：,单词error中消逝最多的字母r消逝了3次，消逝次数最少的字母消逝了1次，3-1=2，2是质数。,样例2,输入：,olymipic,输出：,No Answer,0,解释：,单词olympic中消逝最多的字母i消逝了2次，消逝次数最少的字母消逝了1次，2-1=1，1不是质数。,思路：,统计单词中每个字母的消逝次数，挑出最多的次数和最少的次数不包括0次，相减推断是否为质数即可。,推断质数时可以写函数推断，也可以把100以内的质数列成常量数组直接推断，由于单词最多只有100个字母。,需要留意的是输出时的LWNA四个字母要大写。,总结：,这是一道送分题，没有什么难度，需要留意的细节也不多，所以在竞赛中是确定要拿总分值的。,参考样程,#include#include#include#define I_F“word.in“#define O_F“word.out“usingnamespacestd;strings;shortans;voidInput;voidSearch;boolPd;voidOutput;intmainInput;Search;Output;return0;voidInputifstreamfin(I_F);fins;fin.close;,voidSearch/统计字母消逝次数shorti,max=0,min=200;shortf26=0;for(i=0;i0)if(fimax)max=fi;if(fimin)min=fi;ans=max-min;voidOutputofstreamfout(O_F);if(Pd)fout“Lucky Wordn“ansendl;elsefout“No Answern0n“;fout.close;,boolPd/推断质数if(ans=1)returnfalse;elseif(ans=2)returntrue;elseif(ans%2=0)returnfalse;elsefor(shorti=3;i=0,3.n根火柴棍必需全部用上,其次题 火柴棒等式,输入格式：,输入文件matches.in共一行，有一个整数nnn;fin.close;,intMatches(intx)/计算摆出x所需的火柴棒intt=x,s=0;if(x=0)return6;elsewhile(t0)s+=matcht%10;t/=10;returns;voidSearchinti,j;n-=4;for(i=0;iMAX;i+)for(j=0;j=i;j+)/这样对于A+B和B+A就只会搜寻到一次，可以节省一半时间if(Matches(i)+Matches(j)+Matches(i+j)=n)if(i!=j)ans+=2;elseans+;,/Output函数略,问题描述：小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素养拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进展沟通。纸条要经由很多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进展中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说假设此人在小渊递给小轩纸条的时候帮助，那么在小轩递给小渊的时候就不会再帮助。反之亦然。还有一件事情需要留意，全班每个同学情愿帮助的好感度有高有低留意：小渊和小轩的好心程度没有定义，输入时用0表示，可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮助传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的两条路径。,第三题 传纸条,输入格式：输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列1=m,n=50。接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。,输出格式：输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。,样例输入：3 3 0 3 9 2 8 5 5 7 0输出：34,数据规模：30%的数据满足：1=m,n=10 100%的数据满足：1=m,n1)fi,j,k,l=min fi-1,j,k,l-1(i1)+si,j+sk,l fi,j-1,k-1,l(j1)且(ki+1)fI,j-1,k,j-1(j1)同时，由于两条线不能穿插，有ki。,状态压缩由于两条路线长度相等，所以有i+j=k+l，则状态可以压缩为三维，压缩后的转移方程为：fi-1,j,k-1(i1)fi,j,k=min fi-1,j,k(i1)+si,j+sk,i+j-k fi,j-1,k-1(j1)且(ki+1)fI,j-1,k(j1),关于ki+1：当k=i+1时，(i,j-1)和(k-1,i+j-k)是同一点，由于两条路线不行穿插，所以两条路线的状态不行能由同一点进展而来。,总结：这是一道较高难度的动规题，有一个小陷阱假设把两条线分开做动态规划则会由于两条线路可能穿插而出错，边界条件也较为简洁，并且需要状态压缩才能拿总分值。在竞赛中遇到这种题假设一时无法找到适宜的算法，最好先做下一题，由于即使写搜寻也无法过多少数据。同时在考虑动态转移方程时确定要留意边界条件，否则极易出错。,参考样程,#include#define I_F“message.in“#define O_F“message.out“usingnamespacestd;shortn,m;shorts6060;longf606060;voidInput;longmax(longa,longb);voidDyna;voidOutput;intmainInput;Dyna;Output;return0;voidInputshorti,j;ifstreamfin(I_F);finnm;for(i=0;isij+);fin.close;,voidOutputofstreamfout(O_F);foutfn-2m-1n-1b)returna;elsereturnb;voidDynashorti,j,k;for(i=0;in;i+)for(j=0;jm;j+)for(k=i+1;k=i+j;k+)if(k=i+1)/需要特殊留意边界条件if(i=0)fijk=fij-1k+sij+ski+j-k;elseif(j=0)fijk=max(fi-1jk,fi-1jk-1)+sij+ski+j-k;elsefijk=max(max(fi-1jk,fi-1jk-1),fij-1k)+sij+ski+j-k;elseif(i=0)fijk=max(fij-1k-1,fij-1k)+sij+ski+j-k;elseif(j=0)fijk=max(fi-1jk,fi-1jk-1)+sij+ski+j-k;elsefijk=max(max(fi-1jk,fi-1jk-1),max(fij-1k-1,fij-1k)+sij+ski+j-k;,第四题 双栈排序,问题描述：Tom最近在争论一个好玩的排序问题。通过2个栈S1和s2，Tom希望借助以下4种操作实现将输入序列升序排序。操作a 假设输入序列不为空，将第一个元素压入栈S1,操作b 假设栈S1不为空，将Sl栈顶元素弹出至输出序列,操作c 假设输入序列不为空，将第一个元素压入栈s2,操作d 假设栈S2不为空，将S2栈顶元素弹出至输出序列假设一个ln的排列P可以通过一系列操作使得输出序列为l,2,(n-1)，n，Tom就称P是一个“可双栈排序排列”。例如(1，3，2，4)就是一个“可双栈排序排列”，而(2，3，4，1)不是。以以下图描述了一个将(1，3，2，4)排序的操作序列：固然,这样的操作序列有可能有多个，对于上例(1，3，2，4)，是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。,输入格式：输入文件twostack.in的第一行是一个整数n。,其次行有n个刚空格隔开的正整数，构成一个1n的排列。,输出格式：输出文件twostack.out共一行，假设输入的排列不是“可双栈排序排列”，输出数字0；,否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。,数据规模：30%的数据满足：n=10 50%的数据满足：n=50 100%的数据满足：n=1000,样例,1,输入：,41 3 2 4,输出：,a b a a b b a b,样例,2,输入：,42 3 4 1,输出：,0,样例,3,输入：,32 3 1,输出：,a c a b b d,分析：输入的数据确定是1n的整数且不会重复，因而对于给定的n，其排序后的序列确定是1,2,3,n。进一步可以推出两个栈中的元素确定是越靠近栈顶越小。依据这种想法，我们可以制定一个贪心策略：当输出序列中已有m个数时，在每次操作之前进展一次推断：假设数字m+1仍在输入序列中，那么本次操作确定入栈，当入栈的数不为m+1且该数比两个栈的栈顶元素都要大时无解，否则入栈假设两栈都能入则入1栈；假设m+1已在栈中则出栈，该元素必定在栈顶。这种贪心可以通过全部数据，但是是错误的。对于这个输入序列：5724163，贪心所得出的操作序列并不是字典序最小的。,正确解法首先要推断是否有解：设输入序列为S，Si,Sj两个元素不能进入同一个栈自始至终不能进入同一个栈 存在k,满足ijk,使得SkSiSj证明略。把每个元素依据输入序列中的挨次编号，看作一个图中的每个顶点。这时，我们对全部的(i,j)满足ij,推断是否满足上文结论，即Si,Sj两个元素能否进入同一个栈。假设满足，则在i,j之间连接一条边。由于只有两个栈，所以连完之后得到的图必需是二部图，否则无解。,