Acwing 120

题面

题目大意就是给定 \(N\) 个等差数列的首项 \(s\) , 公差 \(D\) , 有 \(K+1\) 项 , 要求 \(s + k \times D \leq E\) , \(s + (k + 1) \times > E\) , 其中 \(E\) 是每个数列都特有的. 对于数轴上的点 , 数据保证要么所有点被覆盖偶数次( \(0\) 也算偶数) , 要么有且只有一个点被覆盖奇数次 , 其余被覆盖偶数次 . 不存在第三种情况. 如果是情况 \(1\) 输出 \(0\) \(0\) , 第二种情况则输出被覆盖奇数次点的位置和它被覆盖的次数.

要观察这两种情况的特性 , 我们考虑任意区间 \([a,b]\) , 如果那个被覆盖奇数次的点在这个区间上 , 那么所有的数列在这个区间的覆盖次数总和一定为奇数 (先考虑所有点覆盖的次数为偶数 , 相当于多加一个覆盖在一个点上) , 不在的话总和就为偶数 , 二分区间去找这个点就行了.

#include
#include
#include
#include
using namespace std;
const int N = 2e5+1;
const int inf = 2147483647;
int T,n;
struct node{int s,e,d;} Dot[N];
long long getsum(int x){
	long long ans = 0;
	for(int i=1;i<=n;++i)
		if(Dot[i].s <= x){
			int t = min(x , Dot[i].e) - Dot[i].s + 1;
			if(t % Dot[i].d) ans += t/Dot[i].d + 1;
			else ans += t / Dot[i].d;
	}
	return ans;
}
bool check(int l,int r){
	return ( ( getsum(r) - getsum(l-1) ) & 1);
}
int main()
{
	scanf("%d",&T);
	while(T--){
		int Min = inf , Max = -1;
		scanf("%d",&n);	
		for(int i=1;i<=n;++i){
			scanf("%d%d%d",&Dot[i].s,&Dot[i].e,&Dot[i].d);
			Min = min(Min , Dot[i].s) , Max = max(Max , Dot[i].e);
		}
		if ( !(getsum(Max) & 1)	) {printf("There's no weakness.\n"); continue;}
		int l = Min , r = Max;
		while(l>1;
			if(check(l , mid)) r = mid;
			else l = mid + 1;
		}
		printf("%d %d\n",l,getsum(l) - getsum(l-1));
	}
	return 0;
}