首页 > 代码库 > 2016 年末 QBXT 入学测试

2016 年末 QBXT 入学测试

P4744 A’s problem(a)
时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试题,每三天结算一次成绩。参与享优惠

描述

这是一道有背景的题目,小A也是一个有故事的人。但可惜的是这里纸张太小,小A无法把故事详细地说给大家听。可能小A自己也讲不清楚自己的故事,因为如果讲清了,也就没有这道题目了……

小A的问题是这个样子,它找到了n份不同的工作,第i份工作每个月有ai的工资,每份工作需要小A每天工作8小时,一周工作7天。小A想知道性价比最高(一个月的工资除以总时长)的工作的编号是多少。如果有多份,输出编号最小的就可以了。

输入格式

第一行一个数n,表示有n份工作。

         接下来n个数表示ai。

输出格式

输出一个数表示答案。

备注

输入样例

5

3 3 4 5 5

输出样例

4

数据范围

对于100%的数据n<=100,1<=ai<=1000。

技术分享
 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int n,a[1000],ans,last; 6 int main() 7 { 8     scanf("%d",&n); 9     for(int i=1;i<=n;i++)10       scanf("%d",&a[i]);11     ans=1;last=a[1];12     for(int i=2;i<=n;i++)13     {14         if(a[i]>last)15         {16             ans=i;last=a[i];17         }18     }19     printf("%d",ans);20     21     return 0;22 }
P4745 B’s problem(b)
时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试

描述

题目描述

         小B生活在一个很奇怪的国家里,这个国家的钱的面值只有可能是25,50,100的。小B最近在做社会实践,这次它选择在一个餐厅里干这件事情。但今天发生了一件有趣的事,这件事情是这个样子的,餐厅里大家都在排队买饭,粗心的打饭阿姨忘记要带零钱,并且所有排队打饭的人只带了一张钱。

         具体地,第i个人带了一张面额为ai的钱,为了方便起见,我们规定每个人都想买价值25元的饭盒。阿姨显得不知所措。聪明的小B想到了一个方法,让带了25元的先买饭!这样阿姨就有了更多的零钱去找开一些面值较大的钱。

         但这样对于一些人来说仍有可能找不开零钱,小B想知道是否存在一种排队方案,能够对所有人找开零钱。如果可行输出“YES”,否则输出“NO”。

输入格式

第一行一个数n,表示有n个想买饭的人。

         接下来一行n个数ai,表示第i个人带着的钱的面额。

输出格式

输出“YES”或者“NO”。

备注

输入样例

3

25 50 100

输出样例

NO

数据范围

对于100%的数据n<=100,ai=25或者50或者100。

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,a[150],momo=1; 7 int main() 8 { 9     scanf("%d",&n);10     for(int i=1;i<=n;i++)11     {12         scanf("%d",&a[i]);13         a[i]/=25;14     }15     sort(a+1,a+n+1);16     int cnt=1;17     while(cnt<=n){18         if(a[cnt]==1) {19             momo++;20             cnt++;21         }22         if(a[cnt]>1){23             momo-=(a[cnt]-1);24             if(momo<0) {25                 printf("NO");26                 return 0;27             }28             cnt++;29         }30     }31     printf("YES");32     return 0;33 }
技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int n,m,cost[101],a,b,c; 6 int main() 7 { 8     scanf("%d",&n); 9     for(int i=1;i<=n;i++)10       scanf("%d",&cost[i]);11     for(int i=1;i<=n;i++)12     {13         if(cost[i]==25) a++;14         if(cost[i]==50) b++;15         if(cost[i]==100)c++;16     }17     int cnt=a-b;18     if(cnt<0){cout<<"NO"<<endl;return 0;}19     if(cnt==0&&c==0){cout<<"YES"<<endl;return 0;}20     if(cnt==0&&c!=0){cout<<"NO"<<endl;return 0;}21     else22     {23         if(c>b&&b+(c-b)*3<=cnt){cout<<"YES"<<endl;}24         if(c<=b&&c<=cnt){ cout<<"YES"<<endl;}25         else {cout<<"NO"<<endl;}26     }    27     return 0;28 }
枪‘
P4746 C’s problem(c)
时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试

描述

题目描述

         小C是一名数学家,由于它自制力比较差,经常通宵研究数学问题。

         这次它因为这个数学问题已经两天两夜没有睡觉了,再不研究出来就要出人命了!快帮帮它吧!

         这个问题是这样的,有一个数n,将其拆分成若干自然数之和,要求乘积最大!

         如果你以为问题仅仅这么简单,那你就太naive了。

         由于小C挑战自己的自我修养,它规定分成的自然数两两之间一定不能相等!

         它请你输出这个乘积最大是多少,但这个答案太大了,小C并没有兴趣看那么长的数字,它只想知道这个数对1000000007取模后的值是多少。

输入格式

一行一个数表示n

输出格式

一个数表示答案

备注

输入样例

6

输出样例

8

数据范围

对于30%的数据n<=10。

对于50%的数据n<=10000。

对于100%的数据1<=n<=1000000000。

技术分享
 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #define mod 1000000007 5 using namespace std; 6 long long n,ans=1; 7 long long a[1500],cur=0,num=2; 8 int main() 9 {10     scanf("%lld",&n);11     while(n>=num){12         n-=num;13         cur++;14         a[cur]=num;15         num++;16     }17     if(cur<n) a[1]+=n;18      else if(n!=0&&cur>=n){ a[cur-n+1]=num; }19     for(int i=1;i<=cur;i++){20         ans*=a[i];21         ans%=mod;22     }23     printf("%lld",ans);24     return 0;25 }
P4747 D’s problem(d)
时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试题

描述

题目描述

         小D是一名魔法师,它最喜欢干的事就是对批判记者了。

         这次记者招待会上,记者对于小D的数学很好奇。于是小D找了个方法把记者批判了一番。

         它对记者抛出了这么一个问题:我有n点能量,写下数字i(1<=i<=9)需要花费a{i}点能量,我用这n点能量最多能写出什么数来?(当然可以不用光n点能量,具体看样例)

         记者们一脸懵逼,于是来求助于你。

输入格式

一行10个数,表示n,a1,a2,a3,…,a9。

输出格式

一个数表示答案。

备注

输入样例1

10 2 2 1 2 2 2 2 2 2

输出样例1

3333333333

输入样例2

10 4 11 11 11 11 11 11 11 10

输出样例2

11    

数据范围

对于30%的数据n,ai<=10。

对于60%的数据n,ai<=100。

对于100% 的数据1<=n,ai<=1000000,n>=min{ai}。

技术分享
 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 int n,minn=0x7fffffff,tmp;  6 int ans[100001]; 7 struct node 8 { 9     int w;//写下p需要w点能量 10     int p;11     bool operator <(const node &a)const12     {13         return p>a.p;14     } 15 }a[11];16 int main()17 {18     scanf("%d",&n);19     for(int i=1;i<=9;i++)20     {21         scanf("%d",&a[i].w);22         a[i].p=i;23         if(a[i].w<=minn)//minn当前耗费最小的能量 24         {25             minn=a[i].w;26             tmp=a[i].p;//耗费能量minn写下的最大的数 27         }28     }29     int cnt=n%minn,cur=n/minn;//cur:ans的位数,cnt:写下cur位tmp后剩下的能量 30     sort(a+1,a+10);31     int k=1;//从最高为开始更新当然更优  并且能换就换成 可以改成的数字中的最大值 32     for(int i=1;i<=cur;i++) ans[i]=tmp;//写下cur位tmp 33     while(cnt)// 还有能量 34     {35         bool ok=false; 36         for(int i=1;i<=9;i++)37           if(a[i].p<=tmp) break; 38           else if(a[i].w-minn<=cnt)39           {40                 ans[k]=a[i].p;//先更新,k再++ 41                 k++;42                 cnt=cnt-(a[i].w-minn);// 能量作差 43                 ok=1;44                 break;45           }46         if(ok) continue; 47         else break;48     }49     for(int i=1;i<=cur;i++) cout<<ans[i];50     return 0;51 }

 

P4748 E’s problem(e)
时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试

描述

题目描述

         小B生活在一个很奇怪的国家里,这个国家的钱的面值只有可能是25,50,100的。小B最近在做社会实践,这次它选择在一个餐厅里干这件事情。但今天发生了一件有趣的事,这件事情是这个样子的,餐厅里大家都在排队买饭,粗心的打饭阿姨忘记要带零钱,并且所有排队打饭的人只带了一张钱。

         具体地,第i个人带了一张面额为ai的钱,为了方便起见,我们规定每个人都想买价值25元的饭盒。阿姨显得不知所措。聪明的小B想到了一个方法,让带了25元的先买饭!这样阿姨就有了更多的零钱去找开一些面值较大的钱。

         但这样对于一些人来说仍有可能找不开零钱,小B想知道是否存在一种排队方案,能够对所有人找开零钱。

         但这个故事是关于小E的。

         所以它并不关心能否有这么一种排队方案,它关心的是存在多少这样的排队方案。对于两个持有25元纸币的人,我们认为他们两个人交换位置仍然是同一种排队方案。(也就是说持有同一种纸币的人都可以看作相同的人)

         由于答案很大,你只需输出答案对1000000007取模后的结果就可以了。

输入格式

第一行一个数n,表示有n个想买饭的人。

         接下来一行n个数ai,表示第i个人带着的钱的面额。

输出格式

输出一个数表示答案。

备注

输入样例

5

25 25 25 50 100

输出样例

5

数据范围

对于30%的数据n<=8。

对于60%的数据n<=20。

对于100%的数据n<=40,ai=25或者50或者100。

技术分享
 1 #include<cstdio> 2 using namespace std; 3 int n,ga,gb,gc,x,s; 4 // now 记录人数 aa bb cc阿姨手里的钱的各种面值的张数  5 // a b c人群中钱的各种面值的张数  6 void dfs(int now,int aa,int bb,int cc,int a,int b,int c) 7 { 8     if(now==n){ 9         s++;//排完最后一个人了 10         s%=1000000007;11         return;12     }13     if(a>0){//还有手持25元的 14         dfs(now+1,aa+1,bb,cc,a-1,b,c);//排上队,卖菜阿姨手里多了1张25,手持25的人减1个 15     }16     if(b>0&&aa>0)//还有手持50元的,同时满足卖菜阿姨能找开钱 17     {18         dfs(now+1,aa-1,bb+1,cc,a,b-1,c);19     }20     if(c>0)21     {22         int f=0;23         if(bb>0&&aa>0) f=1;//卖菜阿姨有50找钱先找50的 24         else if(aa>=3) f=2;//没有50的找钱找3张25 25         if(f==1) dfs(now+1,aa-1,bb-1,cc+1,a,b,c-1);//找钱找1张50,1张25, 26         else if(f==2) dfs(now+1,aa-3,bb,cc+1,a,b,c-1); //找钱找3张25 27     }28     29 }30 int main()31 {32     scanf("%d",&n);33     for(int i=1;i<=n;i++)34     {35         scanf("%d",&x);36         if(x==25) ga++;//分别统计25、50、100的有几张 37         else if(x==50) gb++;38         else gc++;39     }40     dfs(0,0,0,0,ga,gb,gc);41     printf("%d",s);42 }43 // 期望得分————60  悬 >_< >_<

 

2016 年末 QBXT 入学测试