$T1$ 防线

思路：首先，这题既然要二分，就一定有二段性，那么我们就可以用前缀和来做，这样就可以让弱点前面都是偶数，弱点后面都是奇数。

由于数据过大，我们不能直接直接预处理，而是用一个函数算出每组防具在x前面有多少个，最后直接二分即可。

代码：

#include <bits/stdc++.h>
#define int long long
#define qwq ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
using namespace std;
const int N=2e5+50;
int n;
struct P{
    int s,e,d;
};
P a[N];
int get(int x){ // 数组存不下，所以用前缀和函数
    int sum=0;
    for(int i=1;i<=n;i++){
        // 算出x前面一共有多少个防具
        if(a[i].s<=x) sum+=(min(x,a[i].e)-a[i].s)/a[i].d+1; // 取min是因为防具位置可能没到x，至于+1，请参考植树问题
    }
    return sum;
}
bool check(int mid){
    return get(mid)%2;
}
signed main(){
    qwq;
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i=1;i<=n;i++){
            int aa,b,c;
            cin >> aa >> b >> c;
            a[i].s=aa;
            a[i].e=b;
            a[i].d=c;
        }
        int l=0,r=(1ll<<31)-1;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        int ans=get(l)-get(l-1);// ans表示l有多少个防具，跟前缀和同理
        if(ans%2){
            cout << l << " " << ans << endl;
        }else{
            cout << "There's no weakness." << endl;
        }
    }
}

$T2$ 最佳牛围栏

思路：直接二分答案，每次找出最大平均值是大于mid还是小于mid，最后输出即可。

小技巧：算前缀和时可以直接将所有a[i]减mid，方便直接判断。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
double a[N];
double s[N];
int n,f;
bool check(double mid){
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+(a[i]-mid);// 为什么减mid呢？因为mid表示平均值，全减mid后还大于0表示平均值>mid，反之亦然
    }
    double mn=0;
    for(int j=f;j<=n;j++){
    	mn=min(mn,s[j-f]);
        if(s[j]-mn>=0) return 1;
    }
    return 0;
}
signed main(){
    cin >> n >> f;
    double r;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        s[i]=s[i-1]+a[i];
        r=max(r,a[i]);
    }
    double l=1e-8;
    while(r-l>1e-5){
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout << (int)(r*1000);//注意是 r 不是 l 
}

$T3$ 赶牛入圈

思路：先离散化所有的下标，再二分答案即可，其中check要用前缀和维护边长。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+50;
vector<int> lsh;
int s[N][N];
int c,n;
pair<int,int> a[N];
//由于下标有序，所以离散函数get_zb直接用二分查找即可
int get_zb(int x){
    int l=0,r=lsh.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(lsh[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r;
}
bool check(int mid){
    for(int x1=1,x2=1;x2<lsh.size();x2++){
        while(lsh[x2]-lsh[x1]+1>mid) x1++;
        for(int y1=1,y2=1;y2<lsh.size();y2++){
            while(lsh[y2]-lsh[y1]+1>mid) y1++;
            if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]>=c) return 1;
        }
    }
    return 0;
}
signed main(){
    cin >> c >> n;
    lsh.push_back(0);
    for(int i=1;i<=n;i++){
        cin >> a[i].first >> a[i].second;
        lsh.push_back(a[i].first);
        lsh.push_back(a[i].second);
    }
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    for(int i=1;i<=n;i++){
        int x=get_zb(a[i].first),y=get_zb(a[i].second);
        // 以上均是离散化模板
        s[x][y]++;
    }
    for(int i=1;i<lsh.size();i++){
        for(int j=1;j<lsh.size();j++){
            s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
        }
    }
    int l=1,r=10000;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
	cout << l;
}