算法 – 二分位置
此题有一个比较好的性质,至多有一个位置是奇数。比较灵活的点在于如何利用这个性质将整个区间变成一个具有“二段性”的区间。
考虑在奇数点的左边全为偶数,因此和为偶数;而在奇数点右边(包括奇数点),因为有且仅有一个奇数,所以右边的和为奇数。因此整个区间可以分为2部分,进而可以利用二分解决。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
int n,t;
struct range{
int s,e,d;
} a[N];
long long get_sum(int mid)
{
long long res = 0;
for(int i = 0; i<n; i++){
if (a[i].s > mid) continue;
int e = min(a[i].e, mid);
res += (e - a[i].s) / a[i].d + 1;
}
return res;
}
int main()
{
cin>>t;
while(t--){
int mid, l = 0, r = 0;
cin>>n;
for(int i = 0; i<n; i++){
cin>>a[i].s>>a[i].e>>a[i].d;
r = max(r, a[i].e);
}
while(l<r){
mid = l+r>>1;
if(get_sum(mid) & 1) r = mid;
else l = mid+1;
}
if(get_sum(r) & 1) cout<<r<<' '<<get_sum(r) - get_sum(r-1)<<endl;
else cout<<"There's no weakness."<<endl;
}
return 0;
}