搜索
NOIP基础算法综合重庆巴蜀中学黄新军第一部分第一部分第一部分第一部分第一部分第一部分第一部分第一部分枚举策略枚举策略枚举策略枚举策略枚举策略枚举策略枚举策略枚举策略一、枚举法的基本思想一、枚举法的基本思想一、枚举法的基本思想一、枚举法的基本思想一、枚举法的基本思想一、枚举法的基本思想一、枚举法的基本思想一、枚举法的基本思想�枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。�枚举结构：循环+判断语句。二、枚举法的条件二、枚举法的条件二、枚举法的条件二、枚举法的条件二、枚举法的条件二、枚举法的条件二、枚举法的条件二、枚举法的条件::::::::�虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：�⑴可预先确定每个状态的元素个数n；�⑵状态元素a1，a2，…，an的可能值为一个连续的值域。三、枚举法的框架结构三、枚举法的框架结构三、枚举法的框架结构三、枚举法的框架结构三、枚举法的框架结构三、枚举法的框架结构三、枚举法的框架结构三、枚举法的框架结构�设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofora2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1，…，ai，…，an)满足检验条件then输出问题的解；枚举法的优点枚举法的优点枚举法的优点枚举法的优点�⑴由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；�⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点枚举法的缺点枚举法的缺点枚举法的缺点�枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。四、枚举法的优缺点四、枚举法的优缺点四、枚举法的优缺点四、枚举法的优缺点�“直译”枚举：直接根据题意设定枚举对象、范围和约束条件。�注意认真审题，不要疏漏任何条件例题例题例题例题1111：砝码称重：砝码称重：砝码称重：砝码称重(noip1996)(noip1996)(noip1996)(noip1996)【【【【问题描述问题描述问题描述问题描述】】】】设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重=1000），求用这些砝码能称出不同的重量个数。【【【【文件输入文件输入文件输入文件输入】】】】输入1g、2g、3g、5g、10g、20g的砝码个数。【【【【文件输出文件输出文件输出文件输出】】】】输出能称出不同重量的个数。【【【【样例输入样例输入样例输入样例输入】】】】110000【【【【样例输出样例输出样例输出样例输出】】】】3333【【【【分析分析分析分析】】】】根据输入的砝码信息，每种砝码可用的最大个数是确定的，而且每种砝码的个数是连续的，能取0到最大个数，所以符合枚举法的两个条件，可以使用枚举法。枚举时，重量可以由1g,2g,……,20g砝码中的任何一个或者多个构成，枚举对象可以确定为6种重量的砝码，范围为每种砝码的个数。判定时，只需判断这次得到的重量是新得到的，还是前一次已经得到的，即判重。由于重量=1000g，所以，可以开一个a[1001]的数组来判重。核心参考代码：核心参考代码：核心参考代码：核心参考代码：核心参考代码：核心参考代码：核心参考代码：核心参考代码：readln(a,b,c,d,e,freadln(a,b,c,d,e,freadln(a,b,c,d,e,freadln(a,b,c,d,e,f))))forc[1]:=0toado//1gforc[1]:=0toado//1gforc[1]:=0toado//1gforc[1]:=0toado//1g砝码的个数forc[2]:=0tobdo//2gforc[2]:=0tobdo//2gforc[2]:=0tobdo//2gforc[2]:=0tobdo//2g砝码的个数forc[3]:=0tocdo//3gforc[3]:=0tocdo//3gforc[3]:=0tocdo//3gforc[3]:=0tocdo//3g砝码的个数forc[4]:=0toddo//5gforc[4]:=0toddo//5gforc[4]:=0toddo//5gforc[4]:=0toddo//5g砝码的个数forc[5]:=0toedo//10gforc[5]:=0toedo//10gforc[5]:=0toedo//10gforc[5]:=0toedo//10g砝码的个数forc[6]:=0tofdo//20gforc[6]:=0tofdo//20gforc[6]:=0tofdo//20gforc[6]:=0tofdo//20g砝码的个数beginbeginbeginbeginsum:=0;sum:=0;sum:=0;sum:=0;fori:=1to6dosum:=fori:=1to6dosum:=fori:=1to6dosum:=fori:=1to6dosum:=sum+c[isum+c[isum+c[isum+c[i]]]]****w[iw[iw[iw[i];];];];a[suma[suma[suma[sum]:=1;//]:=1;//]:=1;//]:=1;//标记end;end;end;end;fori:=1to1000doiffori:=1to1000doiffori:=1to1000doiffori:=1to1000doifa[ia[ia[ia[i]=1then]=1then]=1then]=1theninc(numinc(numinc(numinc(num);//);//);//);//统计不同重量的个数Writeln(numWriteln(numWriteln(numWriteln(num););););【问题描述】给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：注意：1.加号与等号各自需要两根火柴棍2.如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C≥0）3.n根火柴棍必须全部用上【输入】输入文件matches.in共一行，又一个整数n（n≤24）。【输出】输出文件matches.out共一行，表示能拼成的不同等式的数目。例题例题例题例题2222：火柴棒等式（：火柴棒等式（：火柴棒等式（：火柴棒等式（NOIP2008NOIP2008NOIP2008NOIP2008））））例题例题例题例题2222：火柴棒等式（：火柴棒等式（：火柴棒等式（：火柴棒等式（NOIP2008NOIP2008NOIP2008NOIP2008））））【【【【问题简述问题简述问题简述问题简述】】】】给你n(n=24)根火柴棒,叫你拼出“A+B=C”这样的等式,求方案数。【【【【思路点拨思路点拨思路点拨思路点拨】】】】本题主要考查对枚举法的掌握，可以枚举A和B的取值，考查等式是否刚好用了24根火柴棒。1S的时限对枚举的范围有所要求，必须要仔细分析A和B的取值。例题例题例题例题2222：火柴棒等式（：火柴棒等式（：火柴棒等式（：火柴棒等式（NOIP2008NOIP2008NOIP2008NOIP2008））））�本题最多24根火柴，等号和加号共用4根火柴，所以A,B,C这3个数字需用20根火柴。我们考查A和B的最大的取值可能：0~9这10个数字所用的火柴数为6,2,5,5,4,5,6,3,7,6，很明显数字1用的火柴棒最少只要2根，不妨让B为1，那么A和C最多可以使用18根火柴，而C=A，满足条件的A的最大取值为1111。所以枚举A和B的范围是从0~1111。�为了加快速度，可以将为了加快速度，可以将为了加快速度，可以将为了加快速度，可以将0000到到到到2222222222222222的所有整数需要的所有整数需要的所有整数需要的所有整数需要的火柴棒数目提前算好保存在数组中。的火柴棒数目提前算好保存在数组中。的火柴棒数目提前算好保存在数组中。的火柴棒数目提前算好保存在数组中。五、枚举算法的优化枚举算法的优化枚举算法的优化枚举算法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时。�⑴提取有效信息；�⑵减少重复计算；�⑶将原问题化为更小的问题；�⑷根据问题的性质进行截枝；�⑸引进其他算法【【【【例题例题例题例题3333】】】】给你给你给你给你n(nn(nn(nn(n=10=10=10=105555))))个整数，然后要有个整数，然后要有个整数，然后要有个整数，然后要有mmmm(m=10(m=10(m=10(m=105555))))个询问。每个询问两个整数个询问。每个询问两个整数个询问。每个询问两个整数个询问。每个询问两个整数iiii和和和和jjjj，问第，问第，问第，问第iiii个个个个数字到第数字到第数字到第数字到第jjjj个数字所有数字之和。个数字所有数字之和。个数字所有数字之和。个数字所有数字之和。【朴素算法】readln(n);readln(n);readln(n);readln(n);fori:=1tondoread(a[i]);fori:=1tondoread(a[i]);fori:=1tondoread(a[i]);fori:=1tondoread(a[i]);fori:=1tomdofori:=1tomdofori:=1tomdofori:=1tomdobeginbeginbeginbeginread(x,y);read(x,y);read(x,y);read(x,y);sum:=0;sum:=0;sum:=0;sum:=0;forj:=xtoydosum:=sum+a[j];forj:=xtoydosum:=sum+a[j];forj:=xtoydosum:=sum+a[j];forj:=xtoydosum:=sum+a[j];writeln(sumwriteln(sumwriteln(sumwriteln(sum););););end;end;end;end;时间复杂度为：O(nmO(nmO(nmO(nm))))【优化算法】先递推计算出s[is[is[is[i]=s[i-1]+a[i]]=s[i-1]+a[i]]=s[i-1]+a[i]]=s[i-1]+a[i]，再回答询问情况;;;;readln(nreadln(nreadln(nreadln(n););););fori:=1tondo{fori:=1tondo{fori:=1tondo{fori:=1tondo{统计求和}}}}beginbeginbeginbeginread(a[iread(a[iread(a[iread(a[i]);]);]);]);s[is[is[is[i]:=s[i-1]+a[i];]:=s[i-1]+a[i];]:=s[i-1]+a[i];]:=s[i-1]+a[i];end;end;end;end;fori:=1tomdofori:=1tomdofori:=1tomdofori:=1tomdobeginbeginbeginbeginread(x,yread(x,yread(x,yread(x,y););););writeln(s[y]-s[x-1]);writeln(s[y]-s[x-1]);writeln(s[y]-s[x-1]);writeln(s[y]-s[x-1]);end;end;end;end;【【【【例题例题例题例题4444】】】】对于给定的对于给定的对于给定的对于给定的NNNN****MMMM的矩形，在其中找一个的矩形，在其中找一个的矩形，在其中找一个的矩形，在其中找一个RRRR****CCCC的