首页 > ACM题库 > HDU-杭电 > HDU 4574-Bombs-搜索-[解题报告]HOJ
2015
09-16

HDU 4574-Bombs-搜索-[解题报告]HOJ

Bombs

问题描述 :

  Terrorists are around everywhere, they always make troubles by detonating bombs. The terrorist have some gunpowder to make bombs, different gunpowder has different damage, every kind of gunpowder can use any times, and the power of one bomb is the product of the gunpowder it consists of. Let’s see how they make a bomb.
  At the beginning they decide to use X parts of gunpowder to make a bomb, and then choose X parts of gunpowder, every time the damage of the gunpowder they choose can’t be smaller than the last time they choose excepting the first time. After choosing X parts gunpowder terrorists get gunpowder[1], gunpowder[2] … gunpowder[X] ( gunpowder[1] <= gunpowder[2] <= … <= gunpowder[X]), and then mix the X parts gunpowder to generate a bomb with power of the product of the damage of the gunpowder. Terrorists make bombs in some order, if they make bomb_A before bomb_B one of the following conditions should meet.
(1)Terrorists use less parts gunpowder to make bomb_A than bomb_B.
(2)Terrorists both use X parts of gunpowders to make bomb_A and bomb_B. There exist an integer j(j <=X),for all i < j,gunpowder_A[i] = gunpowder_B[i] and gunpowder_A[j] < gunpowder_B[j].
  Now, the police get the gunpowder by some way, police find that the gunpowder’s damage is in the range of A to B(A, B included), police want to know the K-th bomb with the power in the range of L to R(L, R included).

输入:

  There are multiple cases, the first line is an integer T denoting the number of the case, for each case has five integers A, B, L, R, K in a line. A, B denote the damage range of the gunpowder. L, R denote the power range of the bomb, K denotes the K-th bomb with the power in the range L to R that police want to know.
2<=A <= B<=10^6
1<=L<=R<=10^9
1<=K<=10^6

输出:

  There are multiple cases, the first line is an integer T denoting the number of the case, for each case has five integers A, B, L, R, K in a line. A, B denote the damage range of the gunpowder. L, R denote the power range of the bomb, K denotes the K-th bomb with the power in the range L to R that police want to know.
2<=A <= B<=10^6
1<=L<=R<=10^9
1<=K<=10^6

样例输入:

4
2 2 1 4 1
2 5 1 4 4
73 23642 12 20903 29401
2 50 1 1000000000 815180

样例输出:

Case #1: 2
2
Case #2: 4
2 2
Case #3: -1
Case #4: 59200
4 4 5 20 37
Hint
In the second case we have 4 kinds of gunpowder with damage 2, 3, 4, 5. the first bomb is “2”with power of 2 The second bomb is “3” with power of 3 The third bomb is “4” with power of 4 The fouth bomb is “5” with power of 5 The fifth bomb is “2 2” with power of 2 * 2 = 4 So the 4-th bomb with power in the range of 1 to 4 is “2 2”.

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

基本上想到了解法 ,但是一直在想[a,b]中乘积在[l,r]的组合有多少种怎么预处理。。。。

觉得当b – a + 1很大的时候,个数很少,大概可以承受n * m 的DP预处理。。。

结果结果就是个爆搜嘛。。。。不过加了些优化 。。。

取的数中最小是2,2 ^ 30 > 1e9 。所以个数不多

首先枚举长度,然后爆搜得到个数,确定长度之后,依旧是按位确定。

枚举每一位的数,继续爆搜判断是否满足第k大。。。。

有一些优化 :

1、当个数为1的时候,就不用枚举了,分析下上下界,O(1)可以得到结果

2、考虑剩下的c – 1个数都取上界,然后利用区间的下界可以得到当前数的下界,考虑剩下的c – 1个数都取下界,然后 利用区间的上界可以得到当前数的上界,这个剪枝很重要吧。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#define mp(a , b) make_pair(a , b)
using namespace std;
typedef long long LL;
const LL inf = 1000000000LL;
int a , b , l , r , k;
// a ^ b
int pow (int a , int b) {
    int ret = 1;
    for (int i = 0 ; i < b ; i ++) {
        ret = ret * a;
        if (ret > inf || ret <= 0)
            return inf + 1;
    }
    return ret;
}
int gao (int c , int a , int b , int l , int r , int k) {
    if (c == 0) return l <= r;
    if (c == 1) {
        if (l > r) return 0;
        return max (0 , min(r , b) - max (l , a) + 1);
    }
    //上下界
    int down = max(a , l / pow(b , c - 1));
    int up = min (b , r / pow(a , c - 1));
    int ret = 0;
    for (int i = down ; i <= up ; i ++) {
        ret += gao (c - 1 , i , b , (l + i - 1) / i , r / i , k - ret);
        if (ret > k) return ret;  //剪枝
    }
    return ret;
}
int ret , ans[50];
void fuck (int c , int a , int b , int l , int r , int k) {
    if (c == 0) return;
    if (c == 1) {
        int num = k + max(l , a) - 1;
        ret = ret * num;
        ans[c] = num;
        return ;
    }
    // 上下界
    int down = max(a , l / pow(b , c - 1));
    int up = min (b , r / pow(a , c - 1));
    for (int i = down ; i <= up ; i ++) {
        int cnt = gao (c - 1 , i , b , (l + i - 1) / i , r / i , k);
        if (k > cnt) {
            k -= cnt;
            continue;
        }
        ret = ret * i;
        ans[c] = i;
        fuck (c - 1 , i , b , (l + i - 1) / i , r / i , k);
        return ;
    }
}
int main () {
    #ifndef ONLINE_JUDGE
        freopen ("input.txt" , "r" , stdin);
    #endif
    int t , cas = 0;
    scanf ("%d" , &t);
    while (t --) {
        bool ok = false;
        scanf ("%d %d %d %d %d" , &a , &b , &l , &r , &k);
        printf ("Case #%d: " , ++ cas);
        //枚举长度
        for (int i = 1 ; i <= 30 ; i ++) {
            int cnt = gao (i , a , b , l , r , k);
            if (k > cnt) {
                k -= cnt;
                continue;
            }
            ret = 1;
            fuck (i , a , b , l , r , k);
            printf ("%d\n" , ret);
            for (int j = i ; j >= 1 ; j --) {
                printf ("%d%c" , ans[j] , j == 1 ? '\n' : ' ');
            }
            ok = true;
            break;
        }
        if (!ok) puts("-1");
    }
    return 0;
}

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

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