由于太菜了,所以只能讲简单的题,所以我只能准备两道题(来延长讲解时间)。。。
题面:一个一维区间上,从$s[i]$到$e[i]$这段上每隔$d[i]$的距离放一个防具($s[i]$必须放,$e[i]$不一定要放),执行$n$组,问是否存在一个点上有奇数个防具(数据保证最多只有一个点上为奇数个)。
暴力枚举???想多了吧,就凭这数据范围,我是觉得不合适的。
放弃,换思路(确实,我觉得这题唯一的难点就在想思路上)。
考虑分治,因为最多只有一个点上有奇数个防具,所以当它分成两块时,只有一块的防具总和为奇数个,没问题对吧,然后就可以二分了嘛。
枚举最左边到mid上的防具总和($\sum_{i=1}^{mid}(min(mid,e[i])-s[i])/d[i]+1$,前提为($s[i]<=mid$)),如果这个值为奇数,那么答案就缩小到l到mid中,如果不是,那答案只可能在mid到r中,一直搜到最小为止,输出答案的就是看搜到最小后当前位置r(代码是按照左开右闭写的),因为此时l=r-1,所以防具数就是最左边到r的防具数减去最左边到l的防具数,然后判断一下输出即可。
上代码
#include<bits/stdc++.h>
using namespace std;
#define fi(a) freopen(a,"r",stdin)
#define fo(a) freopen(a,"w",stdout)
#define sfd(n) scanf("%d",&n)
#define sfld(n) scanf("%lld",&n)
#define f1(i,l,r) for(int i=l;i<=r;++i)
#define pfdn(n) printf("%d\n",n)
#define plds(n) printf("%lld ",n)
const int N=2e5+10;
int t,n;
long long l,r;
long long s[N],e[N],d[N];
void freo(){fi("test.in"); fo("test.out");}
void init(){sfd(n); f1(i,1,n) sfld(s[i]),sfld(e[i]),sfld(d[i]);}
int che(long long k){
int sum=0; f1(i,1,n) if(s[i]<=k) sum+=(min(k,e[i])-s[i])/d[i]+1;
return sum;
}
void work(){
l=0; r=(1<<31)-1; while(l+1<r){
long long mid=(l+r)>>1; if(che(mid)&1) r=mid; else l=mid;
}
}
void prin(){
if(che(r)&1) plds(r),pfdn(che(r)-che(l));
else printf("There's no weakness.\n");
}
int main(){freo(); sfd(t); while(t--) init(),work(),prin(); return 0;}