邮票设计
【problem description】
邮局发行一套票面有四种不同值的邮票,如果每封信所贴邮票张数不超过三枚,存在整数r,使得用不超过三枚的邮票,可以贴出连续的整数1,2,3,……,r来,找出这四种面值数,使得r值最大。
输入格式
无
输出格式
第一行输出,所选在四个邮票面值。由小到大排列,用空格隔开。
第二行输出最大的r值。
【analysis】
此题的条件,我觉得可以把一些常量换成字母的话,就可以改编成一个题目。
对于此题,题目条件较少,枚举的范围,不是一眼即可看出的,首要要解决的问题就是枚举范围。
设四个面值为a,b,c,d(a<b<c<d)因为1,2,3。。。连续,所以a=1。
因不得超过3枚。根据这个条件,即可把a,b,c,d确定一个范围。
A+1<=B<=3*A+1
B+1<=C<=3*B+1
C+1<=D<=3*C+1.
推出这个就好办了。在其中在嵌套一个枚举个数。
而后即可AC.。
【time complexity】
A ------1
B-------2~4
C-------3~13
D-------4~40
O(1*3*11*37*3*3*3*3)
【code】
#include<bits/stdc++.h>using namespace std;void work(){int a=1;int ansr=0,ansa=0,ansb=0,ansc=0,ansd=0;for(int b=a+1;b<=3*a+1;b++)for(int c=b+1;c<=3*b+1;c++)for(int d=c+1;d<=3*c+1;d++){//按照分析中所说枚举int vhash[111111];memset(vhash,0,sizeof(vhash));for(int i=0;i<=3;i++)for(int j=0;j<=3-i;j++)for(int k=0;k<=3-i-j;k++)for(int l=0;l<=3-i-j-k;l++){//枚举每个面值邮票的数量vhash[i*a+j*b+k*c+l*d]=1;}int top=1;while (vhash[top]==1) {//算出最大连续到哪top++;}top--;if(top>ansr){ansr=top;ansa=a;ansb=b;ansc=c;ansd=d;}//找出最大值}cout<<ansa<<" "<<ansb<<" "<<ansc<<" "<<ansd<<endl;cout<<ansr<<endl;}int main(){freopen(“test.in”,”r”,stdin);freopen(“test.out”,”w”,stdout);readp();work();return 0;}
邮票设计
【problem description】
邮局发行一套票面有四种不同值的邮票,如果每封信所贴邮票张数不超过三枚,存在整数r,使得用不超过三枚的邮票,可以贴出连续的整数1,2,3,……,r来,找出这四种面值数,使得r值最大。
输入格式
无
输出格式
第一行输出,所选在四个邮票面值。由小到大排列,用空格隔开。
第二行输出最大的r值。
【analysis】
此题的条件,我觉得可以把一些常量换成字母的话,就可以改编成一个题目。
对于此题,题目条件较少,枚举的范围,不是一眼即可看出的,首要要解决的问题就是枚举范围。
设四个面值为a,b,c,d(a<b<c<d)因为1,2,3。。。连续,所以a=1。
因不得超过3枚。根据这个条件,即可把a,b,c,d确定一个范围。
A+1<=B<=3*A+1
B+1<=C<=3*B+1
C+1<=D<=3*C+1.
推出这个就好办了。在其中在嵌套一个枚举个数。
而后即可AC.。
【time complexity】
A ------1
B-------2~4
C-------3~13
D-------4~40
O(1*3*11*37*3*3*3*3)
【code】
#include<bits/stdc++.h>using namespace std;void work(){int a=1;int ansr=0,ansa=0,ansb=0,ansc=0,ansd=0;for(int b=a+1;b<=3*a+1;b++)for(int c=b+1;c<=3*b+1;c++)for(int d=c+1;d<=3*c+1;d++){//按照分析中所说枚举int vhash[111111];memset(vhash,0,sizeof(vhash));for(int i=0;i<=3;i++)for(int j=0;j<=3-i;j++)for(int k=0;k<=3-i-j;k++)for(int l=0;l<=3-i-j-k;l++){//枚举每个面值邮票的数量vhash[i*a+j*b+k*c+l*d]=1;}int top=1;while (vhash[top]==1) {//算出最大连续到哪top++;}top--;if(top>ansr){ansr=top;ansa=a;ansb=b;ansc=c;ansd=d;}//找出最大值}cout<<ansa<<" "<<ansb<<" "<<ansc<<" "<<ansd<<endl;cout<<ansr<<endl;}int main(){freopen(“test.in”,”r”,stdin);freopen(“test.out”,”w”,stdout);readp();work();return 0;}