[算进] 防线 题解

题目地址

ACwing题目地址

Solution

套路题。不会做只是我没见过这个套路而已

突破口： 但是整条防线上也最多只有一个位置有奇数个防具

我们知道一个原理 ：偶+偶=偶，奇+偶=奇。

又因为我们可以快速算出一个前缀和，比如说算出 \(x\) 之前有多少个防具，（用等差数列的一些公式快速\(O(1)\)算出，因为有 \(n\) 个等差数列所以算一次前缀和的的时间是 \(O(n)\)）。记 \(x\) 的前缀和为 \(S(x)\)

我们又发现如果答案（奇数）在 \(p\) 这个位置，\(\forall x \in [0,p)\) \(S(x)\) 都是偶数，而 \(\forall x \in [p,R)\) \(S(x)\) 都是奇数（\(R\) 是右边界）。这样就有了一个分界点，可以二分了。二分答案的位置。

时间复杂度 \(O(n \log L)\) \((n<=200000,L<=2^{31}-1)\)，可以过。

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 200007;
int n,pos,ans;
int S[N],E[N],D[N];
int check(int x) {
    int res = 0, sum;
    for(int i=1;i<=n;++i) {
        if(x < S[i]) sum = 0;
        else sum = ((min(E[i],x)-S[i])/D[i]) + 1;
        res += sum;
    }
    return res;
}
void work() {
    int l = 1, r = -INF, mid, tmp;
    n = read();
    for(int i=1;i<=n;++i) S[i] = read(), E[i] = read(), D[i] = read(), r = max(r,E[i]);
    pos = -1;
    while(l <= r) {
        mid = (l+r)>>1;
        if(check(mid) & 1) {
            pos = mid, ans = check(mid) - check(mid-1);
            r = mid - 1;
        } else l = mid + 1;
    }
    if(pos==-1) puts("There's no weakness.");
    else printf("%d %d\n",pos,ans);
}
int main()
{
    int T = read();
    while(T--) work();
    return 0;
}

Summary

• 这个题目让我学会了从奇偶性推导出单调性的套路

• 让我学会了等差数列的一些小性质