对于每个测试数据，如果题目中所求的位置不存在，既任意位置都有偶数个教学评估团的成员存在，在输出文件的中打印一行:"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<cstdio>
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;
}bzoj 1271 秦腾与教学评估 题解,布布扣,bubuko.com
原文：http://blog.csdn.net/jiangshibiao/article/details/21479405