首页 > ACM题库 > HDU-杭电 > HDU 4610-Cards-最小生成树-[解题报告]HOJ
2015
09-17

HDU 4610-Cards-最小生成树-[解题报告]HOJ

Cards

问题描述 :

Given some cards each assigned a number, you’re required to select EXACTLY K cards among them.
While you select a card, I will check the number assigned to it and see if it satisfies some of the following conditions:
1. the number is a prime number;
2. the amount of its divisors is a prime number;
3. the sum of its divisors is a prime number;
4. the product of all its divisors is a perfect square number. A perfect square number is such a kind of number that it can be written as a square of an integer.
The score you get from this card is equal to the amount of conditions that its number satisfies. The total score you get from the selection of K cards is equal to the sum of scores of each card you select.
After you have selected K cards, I will check if there’s any condition that has never been satisfied by any card you select. If there is, I will add some extra scores to you for each unsatisfied condition. To make the game more interesting, this score may be negative.
After this, you will get your final score. Your task is to figure out the score of each card and find some way to maximize your final score.
Note that 1 is not a prime number. In this problem, we consider a number to be a divisor of itself. For example, considering the number 16, it is not a prime. All its divisors are respectively 1, 2, 4, 8 and 16, and thus, it has 5 divisors with a sum of 31 and a product of 1024. Therefore, it satisfies the condition 2, 3 and 4, which deserves 3 points.

输入:

The first line of the input contains the number of test cases T.
Each test case begins with two integers N and K, indicating there are N kinds of cards, and you’re required to select K cards among them.
The next N lines describes all the cards. Each of the N lines consists of two integers A and B, which denote that the number written on this kind of card is A, and you can select at most B cards of this kind.
The last line contains 4 integers, where the ith integer indicates the extra score that will be added to the result if the ith condition is not satisfied. The ABSOLUTE value of these four integers will not exceed 40000.
You may assume 0<N≤103,0<K≤104,1≤A≤106,1≤B≤104,T≤40 and the total N of all cases is no more than 20000. In each case there are always enough cards that you’re able to select exact K cards among them.

输出:

The first line of the input contains the number of test cases T.
Each test case begins with two integers N and K, indicating there are N kinds of cards, and you’re required to select K cards among them.
The next N lines describes all the cards. Each of the N lines consists of two integers A and B, which denote that the number written on this kind of card is A, and you can select at most B cards of this kind.
The last line contains 4 integers, where the ith integer indicates the extra score that will be added to the result if the ith condition is not satisfied. The ABSOLUTE value of these four integers will not exceed 40000.
You may assume 0<N≤103,0<K≤104,1≤A≤106,1≤B≤104,T≤40 and the total N of all cases is no more than 20000. In each case there are always enough cards that you’re able to select exact K cards among them.

样例输入:

1
5 3
1 1
2 1
3 1
4 1
5 1
1 2 3 4

样例输出:

1 3 2 2 2
11

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by—cxlove

题目:每个数,有4个评估

1、是素数 2、约数个数是素数 3、约数的和是素数 4、约数的乘积是完全平方数

从n个中选出k个,使得分数最高,如果选的k个中没有一个满足某个条件,则有另外的分值

http://acm.hdu.edu.cn/showproblem.php?pid=4610

首先因为数据范围不大,1-1e6,可以预处理,用到的数是20000个

第一次把1e6的所有数的各项评估都完成,直接TLE,N * sqrt(N)的复杂度,其实用到的只有2W,不需要全部预处理,打好素数表就行了。

第一项直接利用素数表,2、3项枚举约数后利用素数表,第4项不能直接保存乘积再判断,可以发现sqrt(n)枚举约数的时候,每次两个约数 i , n / i 他们的乘积是n,所以约数乘积是n ^ y * (n 是平方数? sqrt(n) : 1) 。

所以可以边乘边化简。

处理完之后,对于所有的数,可以分为2 ^ 4类。

第一次做法是:枚举哪几种评估不选,然后 贪心,WA,对拍后发现问题,这样选可能某个评估的值还是没有选到,但是额外值没有加入,而额外值又可能是负的。

第二次:枚举2 ^ 16种情况,表现选哪几种,要注意的时候,枚举了哪几种,那么就至少要取一个,否则还是会出现上面的情况。之后还是贪心就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000001;
const int M = 1005;
bool isprime[N << 2] = {false}, flag[N][4] = {false} , vis[N] = {false};
int score[N] = {0} , state[N];
int n , k , b[4] , cnt[1 << 4] , get[1 << 4] , id[1 << 4];
bool issquare (LL num) {
    LL t = sqrt(num + 0.0);
    if(t * t == num || (t + 1) * (t + 1) == num || (t - 1) * (t - 1) == num) return true;
    return false;
}
bool cmp (int a , int b) {
    return get[a] > get[b];
}
void Init() {
    for (int i = 0 ; i < N << 2; i ++) {
        isprime[i] = true;
    }
    isprime[1] = false;
    for (int i = 2 ; i < N << 2 ; i ++) {
        if (! isprime[i]) continue;
        for (int j = 2 ; i * j < N << 2 ; j ++) {
            isprime[i * j] = false;
        }
    }
    get[0] = 0;
    for (int i = 1 ; i < 1 << 4 ; i ++) {
        get[i] = get[i >> 1] + (i & 1);
    }
    for (int i = 0 ; i < 1 << 4 ; i ++) {
        id[i] = i;
    }
    sort (id , id + (1 << 4) , cmp);
}
void check(int i) {
    if (vis[i]) return ;
    flag[i][0] = isprime[i];
    int sum = 0 , cnt = 0;
    LL product = 1LL;
    for (int j = 1 ; j * j <= i ; j ++) {
        if(i % j == 0) {
            product = (LL)product * j;
            sum += j;
            cnt ++;
            if (j * j != i) {
                product *= i / j;
                sum += i / j;
                cnt ++;
            }
            if (product == (LL)i * i) {
                product = 1LL;
            }
        }
    }
    flag[i][1] = isprime[cnt];
    flag[i][2] = isprime[sum];
    flag[i][3] = issquare(product);
    for (int j = 0 ; j < 4 ; j ++) {
        score[i] += flag[i][j] ? 1 : 0;
        state[i] += (flag[i][j] ? 1 : 0) << j;
    }
    vis[i] = true;
}
int main () {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r" , stdin);
    #endif
    Init();
    int t;
    scanf ("%d", &t);
    while (t --) {
        scanf ("%d %d", &n, &k);
        for (int i = 0 ; i < 1 << 4; i ++) {
            cnt[i] = 0;
        }
        for (int i = 0 ; i < n ; i ++) {
            int a , b;
            scanf ("%d %d", &a, &b);
            check(a);
            cnt[state[a]] += b;
            printf("%d%c", score[a], i == n - 1 ? '\n' : ' ');
        }
        for (int i = 0 ; i < 4 ; i ++) {
            scanf ("%d", &b[i]);
        }
        int ans = - (1 << 20);
        for (int i = 0 ; i < 1 << 16 ; i ++) {
            int remain = k , ret = 0 , cur = 0;
            for (int j = 0 ; j < 1 << 4 ; j ++) {
                if(! (i & (1 << id[j]))) continue;
                if(cnt[id[j]]) {
                    remain --;
                    ret += get[id[j]];
                }
                else remain = -1;
            } 
            if (remain < 0) continue;
            for (int j = 0 ; j < 1 << 4 ; j ++) {
                if(! (i & (1 << id[j]))) continue;
                cur |= id[j];
                if(remain && remain > cnt[id[j]] - 1) {
                    remain -= cnt[id[j]] - 1;
                    ret += (cnt[id[j]] - 1) * get[id[j]];
                }
                else {
                    ret += remain * get[id[j]];
                    remain = 0;
                }
            }
            if (remain == 0) {
                for (int j = 0 ; j < 4 ; j ++) {
                    if(! ((1 << j) & cur) )
                        ret += b[j];
                }
                ans = max (ans , ret);
            }
        }
        printf ("%d\n", ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/9491289