HDU (杭电) 计算机学院大学生程序设计竞赛（2015’11）

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块转都要分开）。作为资深搬运工，小明总是每次将一堆砖分为两堆，这时候，所消耗的体力是分完之后两堆砖数目的差值。   现在，已知卡车运来的砖的数目，请告诉小明最少要花费多少体力才能完成包工头所要求的任务呢？

Input

输入数据第一行是一个正整数T（T<=100），表示有T组测试数据。 接下来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 #include #include #include #include #include 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件，需要你帮忙计算出小明在过去这段时间洗衣服一共花了多少钱。

Input

输入包含多组测试数据。 每组数据第一行是4个正整数 n (1<=n<=10000) 、a 、b 、c (1<=a

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 #include #include #include #include #include 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&&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最接近的质方数是多少？

Input

输入数据第一行是一个正整数T（T<=20），表示有T组输入数据。 接下来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 #include #include #include #include #include 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])

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}是同一种组队情况。

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

【思路】OEIS大法~~，不过这个习惯不好，待续验证

代码：

/** Problem: ACM组队安排* Running time: 0MS* Complier: G++* Author: herongwei* Create Time: 2015/11/29*/#include #include #include #include #include #include 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 属于同一个家族。

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 #include #include #include #include #include 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）。

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 #include #include #include #include #include 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 valk) { 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。