题解：P10460 防线

· · 题解

P10460 防线

题目链接

二分 and 一点数学知识

这道题题目看着很长，但只要把握重点内容，就可以轻松解决。

题目中正向枚举很明显会 TLE，所以我们想到二分答案。再观察题目发现，只有一个地方有奇数个防具，所以我们只需判断 1 至 mid 的防具总数是否为奇数。如果是,则说明防具在 mid 之前，则 right 应减小，否则，应增大 left。

代码如下

#include <bits/stdc++.h>
using namespace std;
int a[1000001],b[1000001],c[1000001],n;
int pd(int x)//判断x之前的防具个数
{
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=x)
        ans+=(min(x,b[i])-a[i])/c[i]+1;//利用等差数列公式求防具和
    }
    return ans;
}
long long read()
{
    char ch=getchar();
    int x=0,f=1;
    while(!isdigit(ch)){
        if(ch=='-') 
        f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-'0',ch=getchar();
    }
    return x*f; 
}//快读模版
void write(long long x)
{
    if(x<0)
    putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}//快写模版
int main()
{
    int T;
    T=read();
    for(int i=1;i<=T;i++){
        n=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            b[i]=read();
            c[i]=read();
        }
        if(pd(2147483647)%2==0)
        {
            printf("There's no weakness.\n");
            continue;
        }//如果所有防具和为偶数，则说明没有破绽
        int l=0,r=2147483647;//题目数据int范围
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(pd(mid)&1)
            r=mid;
            else
            l=mid+1;
        }//二分模版
        write(l);
        printf(" ");
        write(pd(l)-pd(l-1));//位置l上的防具数量,用前缀和实现
        printf("\n");
    }
}

码风不佳，请勿见怪。

欢迎 dalao 们提出改进建议。