最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

邮票设计

IT圈 admin 4浏览 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;}

 

邮票设计

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;}

 

与本文相关的文章

发布评论

评论列表 (0)

  1. 暂无评论