题目链接：https://www.acwing.com/problem/content/description/122/
给定 \(n\) 个等差数列，每个数字的位置上存在一个盾牌，保证最多有一个位置的盾牌数量是奇数，找到这个位置
对于一个等差数列，设其首项为 \(A\), 公差为\(D\), 则该数列在 \(X\) 之前共有 \((X - A) / D\) 个元素，如果规定了上限 \(E\)，
那就是 \([min(X,E) - A] / D\) 个元素
因为最多只有一个位置是奇数，于是我们发现二分性：对于一个位置$ X $, 如果 \(X\)之前的盾牌数和为奇数，那这个位置
一定在 \(X\) 之前，如果为偶数，那这个位置就在 \(X\) 之后
时间复杂度 \(O(NlogN)\)
注意二分的写法和边界细节
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 200010;
int T,n;
ll S[maxn], E[maxn], D[maxn];
bool Check(ll x){
int cnt = 0;
for(int i = 1; i <= n; ++i){
if(x >= S[i]){
cnt += ((min(E[i], x) - S[i]) / D[i]) + 1;
}
}
if(cnt % 2 == 0) return true;
else return false;
}
void solve(){
ll L = 1, R = (1ll << 31ll);
while(L < R){
ll Mid = (L + R) >> 1;
if(Check(Mid)){
L = Mid + 1;
}else{
R = Mid;
}
}
int ans = 0;
for(int i = 1; i <= n; ++i) if(L >= S[i] && L <= E[i] && ((L - S[i]) % D[i] == 0)) ++ans;
if(R == (1ll << 31ll)) printf("There‘s no weakness.\n");
else{
printf("%lld %d\n",L,ans);
}
}
ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); } return s*f; }
int main(){
T = read();
while(T--){
n = read();
for(int i=1;i<=n;++i){ S[i] = read(), E[i] = read(), D[i] = read(); }
solve();
}
return 0;
}