本文主要是介绍HDU (杭电) 计算机学院大学生程序设计竞赛(2015’11),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
比赛链接:click here~~
搬砖
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
小明现在是人见人爱,花见花开的高富帅,整天沉浸在美女环绕的笙歌妙舞当中。但是人们有所不知,春风得意的小明也曾有着一段艰苦的奋斗史。
那时的小明还没剪去长发,没有信用卡没有她,没有24小时热水的家,可当初的小明是那么快乐,尽管甚至没有一把破木吉他…
之所以快乐,是因为那时的小明心怀逆袭梦想。有一天,小明为了给他心目中的女神买生日礼物,来到了某建筑工地搬砖挣钱。就在这个时候,工地上又运来了一卡车的砖,包工头让小明把卡车卸下来的那堆砖分成一块一块的(要求任何2块转都要分开)。作为资深搬运工,小明总是每次将一堆砖分为两堆,这时候,所消耗的体力是分完之后两堆砖数目的差值。
现在,已知卡车运来的砖的数目,请告诉小明最少要花费多少体力才能完成包工头所要求的任务呢?
那时的小明还没剪去长发,没有信用卡没有她,没有24小时热水的家,可当初的小明是那么快乐,尽管甚至没有一把破木吉他…
之所以快乐,是因为那时的小明心怀逆袭梦想。有一天,小明为了给他心目中的女神买生日礼物,来到了某建筑工地搬砖挣钱。就在这个时候,工地上又运来了一卡车的砖,包工头让小明把卡车卸下来的那堆砖分成一块一块的(要求任何2块转都要分开)。作为资深搬运工,小明总是每次将一堆砖分为两堆,这时候,所消耗的体力是分完之后两堆砖数目的差值。
现在,已知卡车运来的砖的数目,请告诉小明最少要花费多少体力才能完成包工头所要求的任务呢?
Input
输入数据第一行是一个正整数T(T<=100),表示有T组测试数据。
接下来T行每行一个正整数N(N<=10000000),表示卡车运来的砖块的数目。
接下来T行每行一个正整数N(N<=10000000),表示卡车运来的砖块的数目。
Output
对于每组数据,请输出小明完成任务所需的最少体力数。
Sample Input
2 4 5
Sample Output
0 2
【思路】:分为n-2,和n-n/2
代码:
/*
* Problem: 搬砖
* Running time: 0MS
* Complier: G++
* Author: herongwei
* Create Time: 2015/11/29
*/#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
using namespace std;const int maxn=1e5+10;
const int MOD=1e9+7;
typedef long long LL;
char str[maxn],T[maxn];
typedef long long LL;
LL n,m,a,b,ans;
LL get(LL n)
{if(n<3) return 0;LL ans=n%2;return ans+get(n/2)+get(n-n/2);
}
int main()
{//freopen("1.txt","r",stdin);int t;scanf("%d",&t);while(t--){scanf("%lld",&n);LL ans=0;printf("%lld\n",get(n));}return 0;
}
投币洗衣机
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
如今大学生的生活条件越来越好了,近期,内蒙某高校在每个寝室楼都添置了一台投币洗衣机。
小明作为经常参加训练的ACM队员,非常忙(Lan)碌(Duo),当然非常乐意把衣服丢给洗衣机解决啦。根据要洗的衣服数量,投币洗衣机每次需要投入2-4 枚硬币。
小明是一个非常容易出汗的男生,夏天就要到了,每天都要洗澡,所以也就有大量衣服需要洗。
小明是这么制定投币洗衣机计划的:当屯积的衣服数量大于等于a且小于b的时候,他就会马上全部拿去给洗衣机洗,并且投入2枚硬币;当屯积的衣服数量大于等于b且小于c的时候,他就会马上全部拿去给洗衣机洗,并且投入3枚硬币;当屯积的衣服数量大于等于c的时候,他就会马上全部拿去给洗衣机洗,并且投入4枚硬币。其他细节见样例。
现在知道,小明过去n 天每天换下的衣服数量v件,需要你帮忙计算出小明在过去这段时间洗衣服一共花了多少钱。
小明作为经常参加训练的ACM队员,非常忙(Lan)碌(Duo),当然非常乐意把衣服丢给洗衣机解决啦。根据要洗的衣服数量,投币洗衣机每次需要投入2-4 枚硬币。
小明是一个非常容易出汗的男生,夏天就要到了,每天都要洗澡,所以也就有大量衣服需要洗。
小明是这么制定投币洗衣机计划的:当屯积的衣服数量大于等于a且小于b的时候,他就会马上全部拿去给洗衣机洗,并且投入2枚硬币;当屯积的衣服数量大于等于b且小于c的时候,他就会马上全部拿去给洗衣机洗,并且投入3枚硬币;当屯积的衣服数量大于等于c的时候,他就会马上全部拿去给洗衣机洗,并且投入4枚硬币。其他细节见样例。
现在知道,小明过去n 天每天换下的衣服数量v件,需要你帮忙计算出小明在过去这段时间洗衣服一共花了多少钱。
Input
输入包含多组测试数据。
每组数据第一行是4个正整数 n (1<=n<=10000) 、a 、b 、c (1<=a<b<c<=300),具体含义见题目描述。
每组数据第二行包含n个正整数,按顺序表示过去n天每天产生的衣服数量v(1<=v<=1000)。
每组数据第一行是4个正整数 n (1<=n<=10000) 、a 、b 、c (1<=a<b<c<=300),具体含义见题目描述。
每组数据第二行包含n个正整数,按顺序表示过去n天每天产生的衣服数量v(1<=v<=1000)。
Output
每组数据输出一个整数,表示小明过去n天中洗衣服一共花了多少钱。
每组输出占一行。
每组输出占一行。
Sample Input
3 2 4 6 2 2 1
Sample Output
4
【思路】:模拟
代码:
/*
* Problem: 投币洗衣机
* Running time: 0MS
* Complier: G++
* Author: herongwei
* Create Time: 2015/11/29
*/#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
using namespace std;const int maxn=1e5+10;
const int MOD=1e9+7;
typedef long long LL;
char str[maxn],T[maxn];
typedef long long LL;
int n,m,a,b,c,ans;
int arr[maxn];
int main()
{//freopen("1.txt","r",stdin);while(~scanf("%d%d%d%d",&n,&a,&b,&c)){int sum=0;for(int i=1; i<=n; ++i){scanf("%d",&arr[i]);}int value=0;for(int i=1; i<=n; ++i){sum+=arr[i];if(sum>=a&&sum<b) {value+=2,sum=0;}else if(sum>=b&&sum<c) {value+=3,sum=0;}else if(sum>=c) {value+=4,sum=0;}}printf("%d\n",value);}return 0;
}
质方数
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
小明天生对数字比较敏感,3岁的时候就能背诵圆周率一百位。
现在,小明慢慢长大了,但依然很喜欢数字,最近,他迷上了质数和平方数,并且自己把质数的平方命名为“质方数”。
现在,他在研究这样一个问题:距离一个正整数N最接近的质方数是多少?
现在,小明慢慢长大了,但依然很喜欢数字,最近,他迷上了质数和平方数,并且自己把质数的平方命名为“质方数”。
现在,他在研究这样一个问题:距离一个正整数N最接近的质方数是多少?
Input
输入数据第一行是一个正整数T(T<=20),表示有T组输入数据。
接下来T行,每行输入一个正整数N(1<=N<=10^8)。
接下来T行,每行输入一个正整数N(1<=N<=10^8)。
Output
对于每组数据,请输出距离N最接近的质方数,每组输出占一行。
Sample Input
2 1 10
Sample Output
4 9
代码:
/*
* Problem: 质方数
* Running time: 0MS
* Complier: G++
* Author: herongwei
* Create Time: 2015/11/29
*/#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
using namespace std;const int maxn=2*1e5+100;
const int MOD=1e9+7;
typedef long long LL;
char str[maxn],T[maxn];
typedef long long LL;
int n,m,a,b,c,ans;
int prime[1000000];
bool Prime[1000000];
int tot = 0;
void getPrime()
{int i,j;long long temp;for(i = 2; i < 20000; i++){if(!Prime[i]) prime[tot++] = i;for(j = 0; j < tot && (temp = (long long)i*prime[j]) < 20000; j++){Prime[temp] = true;if(i%prime[j] == 0) break;}}
}
int num[maxn];
int Binary_search(int val)
{int l = 1,r =2333;while(l<=r){int mid = (l+r)/2;if(num[mid]>val) r = mid-1;else l = mid+1;}return l;
}
int main()
{//freopen("1.txt","r",stdin);getPrime();int sum = 1;for(int i = 0 ; i< tot; ++i){num[sum++] = prime[i]*prime[i];}int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);if(n<4){puts("4");continue;}int val = Binary_search(n);if(abs(n-num[val-1])<abs(num[val]-n)){printf("%d\n",num[val-1]);}else{printf("%d\n",num[val]);}}return 0;
}
ACM组队安排
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
ACM亚洲区比赛结束,意味着开始备战明年的浙江省大学生程序设计竞赛了!
杭州电子科技大学ACM集训队也准备开始组队。
教练想把所有的n个队员组成若干支队伍,原则是每支队伍至少一人,最多三人。
现在问题来了:如果已知集训队队员的数量n,请你帮教练计算出所有可能的组队方案有多少种。
特别说明:
队伍没有编号,即如果有A,B,C三人,{A}{BC}与{BC}{A}是同一种组队情况。
杭州电子科技大学ACM集训队也准备开始组队。
教练想把所有的n个队员组成若干支队伍,原则是每支队伍至少一人,最多三人。
现在问题来了:如果已知集训队队员的数量n,请你帮教练计算出所有可能的组队方案有多少种。
特别说明:
队伍没有编号,即如果有A,B,C三人,{A}{BC}与{BC}{A}是同一种组队情况。
Input
输入包含多组测试数据(约1000组),每组数据占一行,包含一个数字n(0<=n<=20),表示ACM集训队的队员人数;n为0,表示输入结束。
Output
请输出n个队员所有可能的组队方案数,每组输出占一行。
Sample Input
1 2 3 4 5 0
Sample Output
1 2 5 14 46
代码:
/*
* Problem: ACM组队安排
* Running time: 0MS
* Complier: G++
* Author: herongwei
* Create Time: 2015/11/29
*/#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
using namespace std;
const int maxn=1e5+100;
const int MOD=1e9+7;
const int inf=0x3f3f3f3f;
typedef long long LL;
char str[maxn],T[maxn];
typedef long long LL;
int n,m;
LL a[maxn],b[maxn];
void init()
{// a(n) = G(n,3) with G(0,i) = 1, G(n,i) = 0 for n>0 and i<1, otherwise G(n,i) = Sum_{j=0..floor(n/i)} G(n-i*j,i-1) * n!/(i!^j*(n-i*j)!*j!)a[1]=1;a[2]=2;a[3]=5;for(int i=4; i<=20; ++i)a[i]=a[i-1]+a[i]+a[i-2]*(i-1)+a[i]+a[i-3]*(i-1)*(i-2)/2;
}
int main()
{//freopen("1.txt","r",stdin);init();while(~scanf("%d",&n)&&n){printf("%lld\n",a[n]);}return 0;
}
油菜花王国
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
程序设计竞赛即将到来,作为学校ACM集训队主力,小明训练一直很努力。今天天气不错,教练也心情大好,破例给各位队员放假一天,小明就骑着自己的小电驴到郊外踏青去了。
出城不久,小明看到一大片油菜花,忍不住眼前美景的诱惑,就拐了进去,谁曾想,这一拐却误入了油菜花王国!
油菜花王国生存着一大批油菜花精灵,这是一种特别热爱斐波那契数列的生物。在这个国度里,有若干个家族,每只精灵都只属于一个家族。精灵出生时,身上都会印着一个编码,表示这只精灵的能力值,如果这个能力值正好存在于斐波那契数列,那么他就会为所在的家族增加一点威望。小明通过和精灵们聊天,知道了所有精灵之间的关系。
现在,小明想知道油菜花王国里威望值最大的家族的威望值是多少,你能帮帮他吗?小明会把精灵们之间的关系网络告诉你,由于整个关系网络实在太庞大,所以小明很有可能重复介绍其中一些关系。
出城不久,小明看到一大片油菜花,忍不住眼前美景的诱惑,就拐了进去,谁曾想,这一拐却误入了油菜花王国!
油菜花王国生存着一大批油菜花精灵,这是一种特别热爱斐波那契数列的生物。在这个国度里,有若干个家族,每只精灵都只属于一个家族。精灵出生时,身上都会印着一个编码,表示这只精灵的能力值,如果这个能力值正好存在于斐波那契数列,那么他就会为所在的家族增加一点威望。小明通过和精灵们聊天,知道了所有精灵之间的关系。
现在,小明想知道油菜花王国里威望值最大的家族的威望值是多少,你能帮帮他吗?小明会把精灵们之间的关系网络告诉你,由于整个关系网络实在太庞大,所以小明很有可能重复介绍其中一些关系。
Input
输入包含多组数据。
每组数据第一行包含两个整数 n (1 <= n <= 1000) 、 m (1 <= m <= 5000) ,分别表示油菜花王国精灵数量和精灵之间关系组数。
第二行包含 n 个整数,表示精灵们的能力值 k (1 <= k <= 1000000000)。
接下去有 m 行,每行有两个不同的整数 u 、 v (1 <= u, v <= n) ,表示精灵 u 和精灵 v 属于同一个家族。
每组数据第一行包含两个整数 n (1 <= n <= 1000) 、 m (1 <= m <= 5000) ,分别表示油菜花王国精灵数量和精灵之间关系组数。
第二行包含 n 个整数,表示精灵们的能力值 k (1 <= k <= 1000000000)。
接下去有 m 行,每行有两个不同的整数 u 、 v (1 <= u, v <= n) ,表示精灵 u 和精灵 v 属于同一个家族。
Output
请输出威望值最大的家族的威望值,每组数据对应一行输出。
Sample Input
2 1 1 4 1 2
Sample Output
1
【思路】并查集判断是否属于一个家族,然后是斐波那契的数判断即可,累加,最后排序即可。
代码:
/*
* Problem: 油菜花王国
* Running time: 0MS
* Complier: G++
* Author: herongwei
* Create Time: 2015/11/29
*/#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
using namespace std;
const int maxn=1e5+100;
const int MOD=1e9+7;
const int inf=0x3f3f3f3f;
typedef long long LL;
char str[maxn],T[maxn];
typedef long long LL;
int n,m;
LL st[maxn];
LL fib[maxn];
LL vis[maxn];
LL father[maxn];
LL Find(int x)
{if(x==father[x]) return x;return father[x]=Find(father[x]);
}
LL Union(int x,int y)
{LL fx=Find(x);LL fy=Find(y);if(fx!=fy) father[fy]=fx;
}
LL get(LL x)
{for(int i=1; i<=50; ++i){if(fib[i]==x) return 1;}return 0;
}
int main()
{// freopen("1.txt","r",stdin);while(~scanf("%d%d",&n,&m)){for(int i=1; i<=n; ++i) father[i]=i;for(int i=1; i<=n; ++i){scanf("%lld",&st[i]);}for(int i=1; i<=m; i++){LL x,y;scanf("%lld%lld",&x,&y);LL fx=Find(x);LL fy=Find(y);if(fx!=fy) Union(fx,fy);}LL sum[maxn];memset(sum,0,sizeof(sum));for(int i=1; i<=n; i++){if(get(st[i])) sum[Find(i)]++;}sort(sum+1,sum+1+n);printf("%lld\n",sum[n]);}return 0;
}
游乐场
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
小时候,因为家里经济困难,小明从未去过游乐场,所以直到现在,他还心存遗憾。
最近,杭州刚建了一座游乐场,为了弥补儿时的遗憾,小明带了一笔钱迫不及待地要去体验一番。
由于是第一次来到这种地方,小明也不知哪些项目比较好玩,因此他想体验尽可能多的项目。来之前,小明还向朋友打听了一下关于游乐场的情况,只要是朋友推荐过的,他一定要体验。当然,每个项目都需要一定的花费,当小明的钱不够时就不能再玩了。
现在,已知小明身上的钱以及每个游戏项目的花费,请问小明最多能体验多少个项目?
最近,杭州刚建了一座游乐场,为了弥补儿时的遗憾,小明带了一笔钱迫不及待地要去体验一番。
由于是第一次来到这种地方,小明也不知哪些项目比较好玩,因此他想体验尽可能多的项目。来之前,小明还向朋友打听了一下关于游乐场的情况,只要是朋友推荐过的,他一定要体验。当然,每个项目都需要一定的花费,当小明的钱不够时就不能再玩了。
现在,已知小明身上的钱以及每个游戏项目的花费,请问小明最多能体验多少个项目?
Input
输入第一行为一个整数T,表示有T组测试数据。
对于每组数据:
第一行是三个整数n, m, k,分别表示游乐场里的游戏项目数,朋友推荐的游戏项目数,小明身上的钱数(1<=m<=n<=10000, 1<=k<=10^9)。
第二行是n个整数,第i个整数xi表示第i个游戏项目的费用(1<=xi<=10^9)。
第三行是m个整数pi,表示朋友推荐第pi个游戏项目(1<=pi<=n)。
对于每组数据:
第一行是三个整数n, m, k,分别表示游乐场里的游戏项目数,朋友推荐的游戏项目数,小明身上的钱数(1<=m<=n<=10000, 1<=k<=10^9)。
第二行是n个整数,第i个整数xi表示第i个游戏项目的费用(1<=xi<=10^9)。
第三行是m个整数pi,表示朋友推荐第pi个游戏项目(1<=pi<=n)。
Output
如果小明带的钱连朋友推荐的项目都无法全部体验,请输出-1;否则,请输出小明最多能体验的项目数。
每组输出占一行。
每组输出占一行。
Sample Input
2 5 2 10 4 3 8 1 12 1 2 5 2 10 4 3 8 1 12 1 3
Sample Output
3 -1
【思路】模拟,注意如果朋友的推荐项目可以浏览,则之后要求最多的必须先减去推荐的在判断。
代码:
/*
* Problem: 游乐场
* Running time: 0MS
* Complier: G++
* Author: herongwei
* Create Time: 2015/11/29
*/#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
using namespace std;
const int maxn=1e5+100;
const int MOD=1e9+7;
const int inf=0x3f3f3f3f;
typedef long long LL;
char str[maxn],T[maxn];
typedef long long LL;
int a[maxn],b[maxn];
int tot = 0;
struct node
{int id,val;bool operator < (const node &t)const{return val<t.val;}
} st[maxn];
int main()
{//freopen("1.txt","r",stdin);int t;scanf("%d",&t);while(t--){int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1; i<=n; ++i){scanf("%lld",&st[i].val);st[i].id=i;}bool ok=0;LL sum_val=0;for(int i=1; i<=m; ++i){scanf("%lld",&b[i]);sum_val+=st[b[i]].val;}if(sum_val>k){puts("-1");}else{for(int i=1; i<=m; ++i) st[b[i]].val=inf;sort(st+1,st+n+1);LL s=m;k-=sum_val;for(int i=1; i<=n-m; ++i){k-=st[i].val;if(k>=0) s++;else break;}printf("%lld\n",s);}}return 0;
}
这篇关于HDU (杭电) 计算机学院大学生程序设计竞赛(2015’11)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!