Flyer-（HDU_4768）

Flyer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3452    Accepted Submission(s): 1301

Problem Description

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!

 

Input

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.

 

Output

For each test case, if there is no unlucky student, print "DC Qiang is unhappy." (excluding the quotation mark), in a single line. Otherwise print two integers, i.e., the label of the unlucky student and the number of flyers he/she gets, in a single line.

 

Sample Input

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

 

Sample Output

1 1 8 1

题意说的是：

给你        a[1~n]    ,    b[1~n]    ,    c[1~n];

其中对任意的若满足        a[i]+c[i]<=b[i];       vis[     a[i]+c[i]    ]++;

若找一个奇数，还是很容易的，用异或运算来处理。清楚明白;

但是正解应该是二分区间;

示例二中：

1    2    3    4    5    6    7    8    9    10    11    12    13    14    15    16    17    18    19    20

0    0    0    0    2    2    2    1    2      0      0      2       0      0      0        0      0      0       2     0

答案就是8   1            //第八个同学，拿了一张传单

二分区间就是给定了（区间中左端点   和   右端点给你，其中里面    多少张   传单是可以算出来的）

二分区间是需要找到奇数的那个区间，虽然不好想，可以看一看代码就会更加清楚了。

方法一：异或

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int L=20005;
ll a[L],b[L],c[L];
int main()
{
     int i,j,n;
     while(~scanf("%d",&n))
     {
          for(i=0;i<n;i++)
          scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
          ll ans=0,cnt=0;
          for(i=0;i<n;i++)
              for(j=a[i];j<=b[i];j+=c[i])
                  ans^=j;
          if(ans)
          {
             for(i=0;i<n;i++)
                 for(j=a[i];j<=b[i];j+=c[i])
                    if(ans==j)cnt++;
              printf("%lld %lld\n",ans,cnt);
          }
          else
          printf("DC Qiang is unhappy.\n");
     }
      return 0;
}

方法二:    等差数列+二分区间:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=20010;
ll A[maxn],B[maxn],C[maxn],n;
ll cal(ll mid){
    ll sum=0;
    for (int i=0;i<n;i++){
        ll up=min(mid,B[i]);        //每个区间上限  和  mid 比较     确定上限
        if (up>=A[i])
        sum+=(up-A[i])/C[i]+1;
    }
//    cout<<mid<<" "<<sum<<endl;
    return sum;
}
int main()
{
    while(~scanf("%lld",&n)){
        for (int i=0;i<n;i++){
            cin>>A[i]>>B[i]>>C[i];
        }
        long long L=0,R=1LL<<31;
        while (L<R){
            ll mid=(L+R)/2;
            if (cal(mid)%2) R=mid;
            else L=mid+1;
        }
        if (L==1LL<<31)
            cout<<"DC Qiang is unhappy."<<endl;
        else {
            while (cal(L)%2==0) L--;
            cout<<L<<' '<<cal(L)-cal(L-1)<<endl;
        }
    }
    return 0;
}