内容提要:简单枚举包括了枚举整数,枚举连续子序列,枚举分数。
枚举整数:1.核心思想:有些题目没必要枚举所有的变量,而是枚举其一变量,后通过等式得出另一个变量,然后在判断另一个量是否在范围内即可。
2.典型例题:洛谷 P uva 725 Division
3.AC代码展示:
#include<bits/stdc++.h> using namespace std; int book[10]; int n; int main(){ int sum=0; while(scanf("%d",&n),n!=0){ sum++; if(sum>1){ cout<<endl; } int a,b,flag=0; //flag为标记变量 for(int i=n;i<100000;i++){ if(i%n==0){ //判断另一个数是否是整数 若是整数则接着进行 a=i,b=i/n; int flag1=0; memset(book,0,sizeof(book)); //book数组用来判断是否是全排列 vector<int>up,down; while(a){ //将各个数全部存入动态数组中去 up.push_back(a%10); book[a%10]=1; a=a/10; } while(b){ down.push_back(b%10); book[b%10]=1; b=b/10; } while(up.size()<5){ up.push_back(0); book[0]=1; } while(down.size()<5){ //补零 down.push_back(0); book[0]=1; } for(int i=0;i<=9;i++){ //如果不是全排列 if(book[i]==0){ flag1=1; //标记变量 break; } } if(flag1==0){ for(int i=4;i>=0;i--){ cout<<up[i]; } cout<<" / "; for(int i=4;i>=0;i--){ cout<<down[i]; } cout<<" = "<<n; cout<<endl; flag=1; } } } if(flag==0){ cout<<"There are no solutions for "<<n<<'.'<<endl; } } }
枚举连续子序列;1.核心思想:枚举连续子序列就是枚举开头和结尾,故用两个for循环即可,但是一定要注意开头要在结尾前面,也不要忘了子序列长度为一的时候。
2.典型例题:洛谷 P uva 11059 Maximum product
3.AC代码展示:
#include<bits/stdc++.h> using namespace std; int n; typedef long long ll; int main(){ int flag=0; while(scanf("%d",&n)!=EOF){ flag++; vector<ll>s; for(int i=0;i<n;i++){ int a; cin>>a; s.push_back(a); } ll maxn=0; //开long long 应为看到数据可能会超出int 数据最高可以到达10^18 for(int i=0;i<s.size();i++){ for(int j=i;j<s.size();j++){ //这里最好别i+1,这样就可以考虑到连续子序列为1的情况 ll k=1; for(int l=i;l<=j;l++){ //应上文,这里最好要<=j,原因上同。 k=k*s[l]; } maxn=max(maxn,k); } } cout<<"Case #"<<flag<<": The maximum product is "<<maxn<<'.'<<endl<<endl; } }
枚举分数:1.核心思想:为了避免分数无限细分下去,一般都要根据题意再用初中数学知识,推到出其一变量的上限(可能是某一会得出下限,某一得出上限,多试试就行)。
2.典型例题:洛谷 p uva 10976 fraction again?!
3.AC代码展示:
#include<bits/stdc++.h> using namespace std; int k; int main(){ while(scanf("%d",&k)!=EOF){ vector<int>xx; vector<int>yy; for(int y=k+1;y<=2*k;y++){ //跟题意可以用初中数学知识推出上限和下限 if(((k*y)%(y-k))==0){ int a=((k*y)/(y-k)); //这个不用开long long ,但是另一个方法就要开long long xx.push_back(a); yy.push_back(y); } } cout<<xx.size()<<endl; for(int i=0;i<xx.size();i++){ cout << "1/" << k << " = 1/" << xx[i] << " + 1/" << yy[i] << endl; } } }