bzoj 1271 秦騰與教學評估 題解

【題目】在秦騰進入北京大學學習的第一個學期，就不幸遇到了前所未有的教學評估。在教學評估期間，同學們被要求八點起床，十一點回宿捨睡覺，不 准曠課，上課不准遲到，上課不准睡覺……甚至連著名的北大三角地也在教學評估期間被以影響校容的理由被拆除。這些“變態”規定令習慣了自由自在隨性生活學 習的北大同學叫苦不迭。這一天又到了星期五，一大早就是秦騰最不喜歡的高等代數課。可是因為是教學評估時期，不能遲到，於是他在八點五分的 時候掙扎著爬出了宿捨，希望能趕快混進在八點鐘已經上課了的教室。可是，剛一出宿捨樓門他就傻眼了: 從宿捨到教學樓的路上已經站滿了教學評估團的成員。他們的目的就是抓住像他這樣遲到的學生，扣除學校的分數。秦騰當然不能讓評估團得逞。他經過觀察發現，整個評估團分成了N個小組，每個小組的成員都分布在從宿捨樓到教學樓的路上的某一段，並且同一小組的成員間的距離是相等的。於是，我們可以用三個整數S, E, D來描述評估團的小組: 既該小組的成員在從宿捨到教學樓的路上的:S, S + D, S + 2D, …, S + KD (K ∈ Z, S + KD ≤ E, S + (K + 1)D > E)位置。觀 察到了教學評估團的這一特點，又經過了認真的思考，秦騰想出了對策: 如果在路上的某一位置有奇數個教學評估團成員，他就可以運用調虎離山，聲東擊西，隔山打牛，暗度陳倉……等方法，以這一地點為突破口到達教學樓。但是由於 教學評估團的成員的十分狡猾，成員位置安排的設計極其精妙，導致在整條路上幾乎沒有這樣的位置出現。即使由於安排不慎重出現了這樣的位置，最多也僅有一 個。現在秦騰觀察出了所有小組的安排，但是由於整個教學評估團的人數太多，他實在看不出這樣的位置是否存在。現在，你的任務是寫一個程序，幫助他做出判 斷。
輸入
輸入文件的第一行為一個整數T，接下來輸入T組相互獨立的測試數據。每組測試數據的第一行包含一個整數，代表N接下來的N行，每行三個整數Si, Ei, Di, 代表第i個小組對應的三個參數。
輸出

對於每個測試數據，如果題目中所求的位置不存在，既任意位置都有偶數個教學評估團的成員存在，在輸出文件的中打印一行:"Poor QIN Teng:(" (不包含引號)否則打印兩個整數Posi, Count，代表在唯一的位置Posi，有Count個教學評估團的成員。根據題意，Count應為奇數。

樣例輸入
3
2
1 10 1

2 10 1
2
1 10 1
1 10 1
4
1 10 1
4 4 1
1 5 1
6 10 1
樣例輸出
1 1
Poor QIN Teng:(
4 3
提示
教學評估團的總人數不大於10^8
Si ≤ Ei
1 ≤ T ≤ 5
N ≤ 200000
0 ≤ Si, Ei, Di ≤ 2^31 – 1
輸入文件的大小不大於2048KB

【分析】利用奇數最多就一個的限制，我們可以二分答案假驗證。顯然，如果坐標0到當前枚舉到的坐標ans間有奇數個人，那麼那個奇數點一定在這中間。然後再迭代驗證。注意要用int64來二分。

【代碼】

#include
using namespace std;
typedef long long big;
const big INF=2147483647;
const int maxn=200005;
int test,n,i;
big s[maxn],e[maxn],d[maxn],ans,max;
inline bool check(big now)
{
  big count=0;
  for (int i=1;i<=n;i++)
    if (s[i]<=now)
    {
      if (e[i]<=now) count+=(e[i]-s[i])/d[i]+1;
      else count+=(now-s[i])/d[i]+1;
    }
  if (count%2==0) return false;
  return true;
}
inline big erfen(big l,big r)
{
  if (l==r) return l;
  big mid=(l+r)/2;
  if (check(mid)) return erfen(l,mid);
  return erfen(mid+1,r);
}
inline void print()
{
  big count=0;
  for (int i=1;i<=n;i++)
    if ((s[i]<=ans)&&(ans<=e[i])&&((ans-s[i])%d[i]==0)) count++;
  if (count%2==0) printf("Poor QIN Teng:(");else printf("%lld %lld",ans,count);
  printf("\n");
}
int main()
{
  scanf("%d",&test);
  while (test)
  {
    test--;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
      scanf("%lld%lld%lld",&s[i],&e[i],&d[i]);
      if (e[i]>max) max=e[i];
    }
    ans=erfen(0,max);
    print();
  }
  return 0;
}