首页 > ACM题库 > HDU-杭电 > hdu 3989 Harry Potter and the Polyjuice Potion待解决[解题报告]C++
2015
04-14

hdu 3989 Harry Potter and the Polyjuice Potion待解决[解题报告]C++

Harry Potter and the Polyjuice Potion

问题描述 :

Polyjuice potion is one of the most famous magic medicines in Harry Porter which had been made by our talented witch Hermione Jean Granger when she was a little girl. But at the very beginning, she didn’t know the prescription, so she had to try several materials to make it up. After that, she found there were only twenty materials which could possibly make the polyjuice potion. And she also noticed that some combination of the materials of the twenty materials will get an effect Ei(-1000 < Ei < 1000).If she choose a subset S of the materials, the final effect will be the sum of effect values of all combinations appeared in S. Because Hermione is very clever, she calculated all the effect value of the combinations. So what’s the maximum effect value the polyjuice potion will get?
Harry Potter and the Hide Story

输入:

Input contains multiple test cases(at most 10).
For each test case, the first line contains a positive integer N(N <= 100000) indicate the number of the combinations.
Then N lines follow, each line contains two number c (0 <= c < 2^20), v(-1000 < v < 1000),indicate the effect value of the combination c (binary representation).
Input ends with a negtive number.

输出:

Input contains multiple test cases(at most 10).
For each test case, the first line contains a positive integer N(N <= 100000) indicate the number of the combinations.
Then N lines follow, each line contains two number c (0 <= c < 2^20), v(-1000 < v < 1000),indicate the effect value of the combination c (binary representation).
Input ends with a negtive number.

样例输入:

3
1 9
2 -10
3 300
-1

样例输出:

299


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  4. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  5. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  6. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  7. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  8. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?