防具布置

解题思路

设S（i）为0~i的位置上一共的防具数
对每组防具分类讨论
若S（231-1）为偶
则无破绽
否则二分答案

AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
int T,n,s[200005],e[200005],d[200005];
int S(int x)//S（i）
{
   
	int answer=0;
	for(int i=1;i<=n;i++)
	 if(s[i]<=x)answer+=(min(x,e[i])-s[i])/d[i]+1;
	return answer; 
}
int main()
{
   
	scanf("%d",&T);
	while(T--)
	{
   
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		 scanf("%d%d%d",&s[i],&e[i],&d[i]);
		if(S(2147483647)%2==0){
   printf("There's no weakness.\n");continue;}//特判
		int l=0,r=2147483647;
		while(l<r)//二分答案
		{
   
			int mid=(1ll*l+1ll*r)/2;
			if(S(mid)%2==0)l=mid+1;
			else r=mid;
		}
		printf("%d %d\n",l,S(l)-S(l-1));
	}
	return 0;
}

谢谢