一道神奇的题qwq
首先看题很容易想到把所有的点存下来然后暴力枚举...于是RE 20分
所以要找一种不用开那么大的数组的解法（然而我自己是不可能想出来的qwq
注意一个地方，人数为奇数的位置“最多也仅有一个”，说明奇偶性只根据这一个点改变
……也就是说，用前缀和的方法表示的时候，奇数点之前都是偶数，之后都是奇数
所以 正解是二分答案qwq
对于某个点，用一个cal函数判断这一点是否为偶数，如果是说明这个点在后面，否则在前面（或者就是这一点）
——二分的这个地方WA了5次！
这是原来写的
while(l <= r) {
mid = (l+r)/;
if (cal(mid)% == )l = mid+;
else r = mid-;
}
cnt = cal(mid)-cal(mid-);
printf("%lld %lld\n",mid,cnt);
为什么会WA呢... 举个例子，
当正确答案为3，l = 2, r = 4, mid = 3；
r = mid -1 = 2；l = mid +1 = 3
这时候就把3跳过去了qwq
所以要改成这样↓
while(l < r) {
mid = (l+r)/;
if (cal(mid)% == ) l = mid+;
else r = mid;
}
cnt = cal(l)-cal(l - );
printf("%lld %lld\n",l,cnt);
就可以啦w（感谢mrclr学长和jlSsy）
哦还有...bin哥说不放心的话可以用一个ans min来每次把它记下来qwq
以下是完整代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
long long s[],e[],d[];
long long t,n,l,r,mid,maxe,cnt; long long cal(long long p) {
long long sum = ;
for(long long j = ; j <= n; j++) {
if(p>=s[j])
sum += (min(p,e[j])-s[j])/d[j]+;
}
return sum;
}
int main() {
scanf("%lld",&t);
for(long long i = ; i <= t; i++) {
maxe = ;
cnt = ;
scanf("%lld",&n);
for(long long j = ; j <= n; j++) {
scanf("%lld%lld%lld",&s[j],&e[j],&d[j]);
maxe = max(maxe,e[j]);
}
if (cal(maxe)% == ) {
printf("Poor QIN Teng:(\n");
continue;
}
l = ;
r = maxe;
while(l < r) {
mid = (l+r)/;
//printf("%lld %lld \n",mid,cal(mid));
if (cal(mid)% == ) l = mid+;
else r = mid;
}
/*for(long long j = 1; j <= n; j++) {
if(mid>=s[j]&&mid<=e[j]&&((mid-s[j])%d[j]==0))
cnt++;
}*/
cnt = cal(l)-cal(l - );
printf("%lld %lld\n",l,cnt);
}
return ;
}