6.7枚举试题
测试说明
4个题目，3.5小时
以姓名命名文件夹，下存4个文件，分别命名。
1、洛谷P1865 A % B Problem
题目背景
题目名称是吸引你点进来的 实际上该题还是很水的
题目描述
区间质数个数
输入输出格式
输入格式：
一行两个整数 询问次数n，范围m
接下来n行，每行两个整数 l,r 表示区间
输出格式：
对于每次询问输出个数 t，如l或r∉[1,m]输出 Crossing the line
输入输出样例
输入样例#1：
2 5
1 3
2 6
输出样例#1：
2
Crossing the line
说明
【数据范围和约定】
对于20%的数据 1<=n<=10 1<=m<=10
对于100%的数据 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000
主要算法及思路：前缀和+筛法求素数
/* 1、对于100%的数据 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000 决定了我们必须用筛法求素数，才不可能TLE 2、题目明确给出 if(l<1||r>m) printf("Crossing the line ");（注意换行符） 3、不超界情况下，结果输出 尽量用前缀和计算，因为不用前缀和 point14会TLE 我的tag[i]表示前i个数中素数的个数 4、综合评价：水！ （不过第一次朴素的ans++<俗称 一个一个数>，就被坑了，得了 93分） */ #include<cstdio> #include<cmath> #include<iostream> using namespace std; #define N 1001000 int check[N]={1,1,0}; int tag[N]; int n,m,ans,tot; int main(){ scanf("%d%d",&n,&m); for(int i=2;i<=m;i++){//筛法求素数 if(!check[i]){ for(int j=2;i*j<=m;j++){ check[i*j]=1; } } } for(int i=2;i<=m;i++){//前缀和 if(!check[i]) tag[i]=tag[i-1]+1; else tag[i]=tag[i-1]; } for(int i=1,l,r;i<=n;i++){ scanf("%d%d",&l,&r); if(l>r) swap(l,r); if(l<1||r>m){//判断是否出界 printf("Crossing the line "); continue; } printf("%d ",tag[r]-tag[l-1]); } return 0; }
2、codevs 2669 简单的试炼
题目描述 Description
已知一个数S，求X和Y，使得2^X+3^Y=S.
输入描述 Input Description
(多组数据)
每行一个整数S，当S=0时输入结束.
输出描述 Output Description
X和Y，以2^X+3^Y=S的形式输出,若有多组解，输出X最小的那组.
样例输入 Sample Input
13
33
0
样例输出 Sample Output
2^2+3^2=13
2^5+3^0=33
数据范围及提示 Data Size & Hint
对于30%的数据 S≤50,000,000 , 数据组数≤5000
对于50%的数据 S≤3,000,000,000 , 数据组数≤20000
对于80%的数据 S≤3,000,000,000,000 , 数据组数≤50000
对于100%的数据 S≤200,000,000,000,000, 数据组数≤80000
主要算法及思路：快速幂+枚举
/* 1、本题不难，就用到 一个快速幂 开long long即可过（第一次做的时候，没看数据范围，忘了这茬了，只得了53分，少的可怜） 2、枚举时 保守起见 i:0->51 j:0->35 也许你觉得在你的电脑上 大于2^31 就输不出来了（我也这样认同）； 但是，如果小了，一定会TLE(也就60分)。 */ #include<cstdio> #include<iostream> #include<cmath> using namespace std; long long s; long long quick_pow(long long x,int n){//快速幂 if(n==0) return 1; else{ while((n&1)==0){ n>>=1; x*=x; } } long long result=x; n>>=1; while(n!=0){ x*=x; if((n&1)!=0){ result*=x; } n>>=1; } return result; } int main(){ while(scanf("%lld",&s)==1&&s){ for(int i=0;i<=51;i++){ for(int j=0;j<=35;j++){ long long x=quick_pow(2,i); long long y=quick_pow(3,j); if(x+y==s){ printf("2^%d+3^%d=%lld ",i,j,s); i=52; break; } if(y>s) break; } } } return 0; }
3、洛谷 P1021 邮票面值设计
题目描述
给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。
例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。
输入输出格式
输入格式：
2个整数，代表N，K。
输出格式：
2行。第一行若干个数字，表示选择的面值，从小到大排序。
第二行，输出“MAX=S”，S表示最大的面值。
输入输出样例
输入样例#1：
3 2
输出样例#1：
1 3
MAX=7
主要算法及思路：回溯枚举+dp验证
/* 1、一上来，没想很多，以为这是一个找规律的题，推出<1>直接开始写， 写完自己编了几组较大的测试数据，都不对（不对的代码下面也有），但<1>推导对了。就赶紧改呀~~ 还好迷途知返，AC了 2、正解思路： 采用回溯枚举的方法，枚举k种邮票，再用动规求出这k种邮票 能组成出来的面值，进行取大处理。 a[]储存枚举出来的邮票，ans[]储存最终答案（“1”不需要有） f[i]表示当总面值为i时，至少用多少张a[]中的邮票 */ #include<cstdio> #include<iostream> #define INF 9999999 #define N 1000001 #define M 47 using namespace std; int ans[M],a[M],f[N],maxl,n,k; void dp(){ int i=0; f[0]=0; while(f[i]<=n){//组成i这个面值所需的邮票数一定<=n,否则不满足题意 i++; f[i]=INF;//赋最大值，之后取小 for(int j=0;j<k&&i>=a[j];j++)//i>=a[j]组成面值i，其组成邮票a[j]必定<=i;由于a[]是按升序排列的，所以一旦a[j]>i，a[]后面的便都不符合要求 f[i]=min(f[i],f[i-a[j]]+1); if(i-1>maxl){//事前不知道f[i](i++了)是否<=n，所以不能用i来更新 maxl=i-1;//但是，i-1一定<=n for(int j=0;j<k;j++) ans[j]=a[j];//更新答案 } } } void dfs(int t){//遍历 邮票种数 if(t==k){//[0..k-1]即k种邮票的一种方案已经产生，dp()去检验 dp();//所有情况都会被检验 return; } for(int i=a[t-1]+1;i<=a[t-1]*n+1;i++){//这个范围需要自己推导 见下<1> a[t]=i;//就好比 样例答案中的 1 3（1首先一定会先被储存，并不会被更改，这一点毋庸置疑） //3是不知道的，你要储存起来，维护到k种，去检验，更新 dfs(t+1);//回溯 过程 } } int main(){ scanf("%d%d",&n,&k); a[0]=1;//习惯[0..k-1] dfs(1);//从第1种邮票开始遍历 for(int i=0;i<k;i++) printf("%d ",ans[i]); printf(" "); printf("MAX=%d",maxl); return 0; } /* 第一次代码： #include<cstdio> #include<iostream> using namespace std; #define N 10010000 int n,k,p; int f[N]; int main(){ scanf("%d%d",&n,&k); if(k==1){ printf("MAX=%d ",n); return 0; } f[1]=1; for(int i=2;i<=k;i++) f[i]=(i-1)*n+1;//<1>这里推导的规律是对的，不会自己想吧 for(int i=1;i<=k;i++) printf("%d ",f[i]); printf(" "); printf("MAX=%d ",f[k]+n-1); return 0; }*/
4、洛谷 P1120 小木棍
题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入输出格式
输入格式：
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
输出格式：
输出文件仅一行，表示要求的原始木棍的最小可能长度
输入输出样例
输入样例#1：
9
5 2 1 5 2 1 5 2 1
输出样例#1：
6
主要算法及思路：搜索+剪枝
/* 1、本题朴素枚举长度一般得40--70分，所以，我们必须要剪枝，才能AC 所标 //+.+ 为剪枝部分 2、简述各变量的意义 下面 i:maxx->sum中 m:大木棍的长度（题目要求大木棍的长度的最小值） num:大木棍的个数 dfs中 len:当前凑出的大木棍的数量 s:当前操作木棍的长度 pre:上一次选的小木棍的编号 3、实在听不明白：（原谅我尽力给你们讲明白了） 自己手动模拟一遍，应该就好了 */ #include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define N 210 int n,m,x,num,a[N],ans,sum,flag,maxx; bool f[N]; void dfs(int len,int s,int pre){//pre +.+ if(flag) return;//+.+ if(s==m){//又凑出一根来，个数+1，其余清零 len++;s=0;pre=0; } if(len==num-1){//+.+ 剩下一根一定可以组成该长度 flag=1;return ;//有合法答案 } for(int i=pre+1;i<=n;i++){ if(f[i]==1||s+a[i]>m) continue;//+.+ if(a[i]==a[i-1]&&f[i-1]==0) continue;//+.+ f[i]=1;//可以被选 dfs(len,s+a[i],i);//递归搜索 if(flag) return ;//+.+ f[i]=0;//回溯标记未选 if(s==0) break;//+.+ } } int main(){ //freopen("sticka.in","r",stdin);//看题目要求 //freopen("sticka.out","w",stdout); scanf("%d",&n); for(int i=1,x;i<=n;i++){ scanf("%d",&x); if(x>50) m++;//Codevs--x>100;其余一般--x>50(注意看题) else a[++num]=x; } n-=m;//减去不合法元素个数 for(int i=1;i<=n;i++){ sum+=a[i]; maxx=max(maxx,a[i]);//小棍中最长值 } sort(a+1,a+n+1,greater<int>());//+.+ for(int i=maxx;i<=sum;i++){//大木棍长度一定在此范围内 if(sum%i==0){//必定成倍数关系 m=i;num=sum/i;flag=0; dfs(0,0,0); if(flag){ printf("%d ",m);//答案 return 0; } } } return 0; }