首页 > 代码库 > 2016 年末 QBXT 入学测试
2016 年末 QBXT 入学测试
背景
冬令营入学测试题,每三天结算一次成绩。参与享优惠
描述
这是一道有背景的题目,小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 }
背景
冬令营入学测试
描述
题目描述
小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 }
背景
冬令营入学测试
描述
题目描述
小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 }
背景
冬令营入学测试题
描述
题目描述
小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 }
背景
冬令营入学测试
描述
题目描述
小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 入学测试