首页 > ACM题库 > HDU-杭电 > HDU 4768-Flyer-分治-[解题报告]HOJ
2015
09-17

HDU 4768-Flyer-分治-[解题报告]HOJ

Flyer

问题描述 :

The new semester begins! Different kinds of student societies are all trying to advertise themselves, by giving flyers to the students for introducing the society. However, due to the fund shortage, the flyers of a society can only be distributed to a part of the students. There are too many, too many students in our university, labeled from 1 to 2^32. And there are totally N student societies, where the i-th society will deliver flyers to the students with label A_i, A_i+C_i,A_i+2*C_i,…A_i+k*C_i (A_i+k*C_i<=B_i, A_i+(k+1)*C_i>B_i). We call a student "unlucky" if he/she gets odd pieces of flyers. Unfortunately, not everyone is lucky. Yet, no worries; there is at most one student who is unlucky. Could you help us find out who the unfortunate dude (if any) is? So that we can comfort him by treating him to a big meal!

输入:

There are multiple test cases. For each test case, the first line contains a number N (0 < N <= 20000) indicating the number of societies. Then for each of the following N lines, there are three non-negative integers A_i, B_i, C_i (smaller than 2^31, A_i <= B_i) as stated above. Your program should proceed to the end of the file.

输出:

There are multiple test cases. For each test case, the first line contains a number N (0 < N <= 20000) indicating the number of societies. Then for each of the following N lines, there are three non-negative integers A_i, B_i, C_i (smaller than 2^31, A_i <= B_i) as stated above. Your program should proceed to the end of the file.

样例输入:

2
1 10 1
2 10 1
4
5 20 7
6 14 3
5 9 1
7 21 12

样例输出:

1 1
8 1

n个最多2W个社团发传单,因为传单不够,所有只能按照学生学号间隔着发……  比如发给A_i,A-i+k,A_i+2*k  ,只要不大于B_I就好;

而且已知收到传单的同学当中只有一个人收到奇数张;

这个题初看没有思路,但是仔细一想就挺简单了,在某个学号范围内比如说1-x范围内,根据社团发传单的数量,我们很容易知道他是按照等差数列来发送的,所以可能很容易算出这段区间内有多少张发出去,统计完所有的社团然后只要是奇数,那么那个唯一的收获奇数张的同学就在里面,然后利用二分的思想把这一段区间精确到1……

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

下面的代码是借用山科的

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=20010;
long long A[maxn],B[maxn],C[maxn];
long long cal(long long mid,int n){
    long long sum=0;
    for (int i=0;i<n;i++){
        long long up=min(mid,B[i]);
        if (up>=A[i])
        sum+=(up-A[i])/C[i]+1;
    }
//    cout<<mid<<" "<<sum<<endl;
    return sum;
}
int main()
{
    int n;
    while (scanf("%d",&n)==1)
    {
        for (int i=0;i<n;i++){
            cin>>A[i]>>B[i]>>C[i];
        }
        long long L=0,R=1LL<<31;
        while (L<R){
            long long mid=(L+R)/2;
            if (cal(mid,n)%2) R=mid;
            else L=mid+1;
        }
        if (L==1LL<<31)
            cout<<"DC Qiang is unhappy."<<endl;
        else {
            while (cal(L,n)%2==0) L--;
            cout<<L<<' '<<cal(L,n)-cal(L-1,n)<<endl;
        }
    }
    return 0;
}

参考:http://blog.csdn.net/zhangyanxing666/article/details/12143239