首页 > ACM题库 > HDU-杭电 > hdu 2607 Let the Balloon Rise II-分治-[解题报告]C++
2014
02-12

hdu 2607 Let the Balloon Rise II-分治-[解题报告]C++

Let the Balloon Rise II

问题描述 :

Contest will be end at 17:00! How excited it is to see balloons floating around.

I knew you had solved the HDOJ 1004 Let the Balloon Rise already, so please settle the another version quickly. I have a lot of balloons and each has a color and I give each of them a number, same color has the same number. For example, red balloon is No.1, pink is No.2, black is No.3 . etc. I also have many rooms to store all the balloons.
There are some rules :
1. Every room stores several balloons but no two have the same color.
2. Collect all the balloons, we can find each color has even number of times of balloons except one.

Your task is to find which is the odd color and calculate its number of times.

输入:

Input file consists from multiple data sets separated by one or more empty lines.
Each data set represents a sequence of 32-bit (positive) integers (references) which are stored in compressed way.
Each line of input set consists from three single space separated 32-bit (positive) integers X Y Z and they represent following sequence of No.X, X+Z, X+2*Z, X+3*Z, …, X+K*Z, …(while (X+K*Z)<=Y). This line represents that in this room there exists (K+1) balloons whose No. is No.X, No.X+Z, No.X+2*Z, No.X+3*Z, …, No.X+K*Z, …etc.

输出:

Input file consists from multiple data sets separated by one or more empty lines.
Each data set represents a sequence of 32-bit (positive) integers (references) which are stored in compressed way.
Each line of input set consists from three single space separated 32-bit (positive) integers X Y Z and they represent following sequence of No.X, X+Z, X+2*Z, X+3*Z, …, X+K*Z, …(while (X+K*Z)<=Y). This line represents that in this room there exists (K+1) balloons whose No. is No.X, No.X+Z, No.X+2*Z, No.X+3*Z, …, No.X+K*Z, …etc.

样例输入:

1 10 1
1 10 1

1 5 1
6 10 1
1 10 1
4 4 1

1 5 1
2 5 1
2 5 1
2 5 1

样例输出:

None.
4 3
1 1

Problem Address:http://acm.hdu.edu.cn/showproblem.php?pid=2607

【题意】

给定一种数据压缩的格式,

比如1、10、2,表示从1开始,相隔为2且小于10的数的集合,即1、3、5、7、9。

给定n组数据,求所有数中出现次数为奇数的唯一一个数是多少及出现的次数。或者所有数出现次数都为偶数。

【思路】

二分。

下界为所有开始的数的最小值减一。

上届为可能取得的最大的数加一。

对于某个数,求出位于它左边的所有数的次数。

若为奇数,则继续二分计算其左边。

否则二分计算其右边。(或者同时计算出其右边,若左右同为偶数则说明不存在这样的数)

得到该数后再扫描一遍计算其次数。

我承认因为忘了改成_int64而TLE了无数次= =

巨恶心的还有它的输入格式,居然是以n多空行间隔case的,而且文件结尾也扑朔迷离,在TLE无数的情况下确实给我增加了不少压力!

【代码】

#include <iostream>
using namespace std;

const int maxn = 50000;

__int64 a[maxn+5], b[maxn+5], c[maxn+5];
__int64 d[maxn+5];
char str[maxn+5];

inline __int64 max(__int64 a, __int64 b)
{
    if (a>=b) return a;
    else return b;
}

inline __int64 min(__int64 a, __int64 b)
{
    if (a<=b) return a;
    else return b;
}

inline __int64 get(__int64 x, __int64 y, __int64 z)
{
    return (y-x)/z+1;
}

int solve(__int64 mid, int n)
{
    int i;
    int al = 0, ar = 0;
    int t, ct;
    for (i=0; i<n; i++)
    {
        ct = 0;
        if (mid>=a[i])
        {
            t = min(mid, b[i]);
            ct += get(a[i], t, c[i]);
        }
        al += ct;
        ar += d[i] - ct;
    }
    if (al%2==1) return 1;
    else if (ar%2==1) return -1;
    else return 0;
}

int main()
{
    int i;
    int n;
    __int64 low, high, mid;
	__int64 ans, act;
    bool flag = true;
    while(flag)
    {
        i = 0;
        flag = false;
        while(gets(str) && (flag=true))
        {
            if (str[0]>='0' && str[0]<='9') break;
            flag = false;
        }
        if (!flag) break;
		flag = false;
        do
        {
            sscanf(str, "%d %d %d", &a[i], &b[i], &c[i]);
            i++;
			flag = false;
        }while(gets(str) && (flag=true) && str[0]>='0' && str[0]<='9');
        n = i;
        for (i=0; i<n; i++) d[i] = get(a[i], b[i], c[i]);
        low = (__int64)INT_MAX*2;
        high = (__int64)INT_MIN;
        for (i=0; i<n; i++)
        {
            low = min(low, a[i]);
            high = max(high, (d[i]-1)*c[i]+a[i]);
        }
        low--;
        high++;
        bool f = false;
        while(low<=high)
        {
            mid = (low+high)>>1;
            switch(solve(mid, n))
            {
            case -1:
                low = mid + 1;
                break;
            case 0:
                f = true;
                break;
            case 1:
                ans = mid;
                high = mid-1;
                break;
            }
            if (f) break;
        }
        if (f) printf("None.\n");
        else
        {
            act = 0;
            for (i=0; i<n; i++)
            {
                if (ans>=a[i] && ans<=b[i] && (ans-a[i])%c[i]==0)
                    act++;
            }
            printf("%I64d %I64d\n", ans, act);
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/human_ck/article/details/7005476


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。