[COCI2018-2019#3] NLO

· · 题解

原题链接

考虑最后的麦田图形，可以发现，如果一个格子最后一次被飞碟降落是在第 i 天，那么最后的数字是 k-i。

可以知道每个圆对一行的影响是一段区间，因此对每一行分别处理。

对于每一行，从后面的圆开始考虑，一次次将该圆的区间覆盖，统计本次新覆盖了多少个点，使答案加上点数乘以本次的权值，即 k-i，再将区间覆盖。最后再统计没有被覆盖的点数量乘上 k。

显然可以将每行要操作的区间边界离散化从而加速考虑区间。

时间复杂度 O(nk^2)。但是由于不是每一次都会完整覆盖每一行，所以跑不满。

由于 k 很小，这里采用 \log 级别的数据结构优化可能不会快多少。

如果手写 bitset 来进行每一次的区间统计和修改操作，则可以将时间复杂度优化到 O(\frac{nk^2}{w})。

空间复杂度 O(n)。

Code

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define pow(x) ((x)*(x))
#define mset(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
const int SIZE=2e2+10,EXTRA=1e5+10;
typedef long long ll;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x*10)+(ch^48),ch=getchar();
    return x;
}
int n,m,k,X[SIZE],Y[SIZE],R[SIZE],bin[SIZE],trans[EXTRA],s[SIZE],t[SIZE],top;
ll ans;
bool use[SIZE];
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=k;i++)X[i]=read(),Y[i]=read(),R[i]=read();
    for(int l=1,uniq;l<=n;l++)
    {
        mset(bin,0),top=0,mset(use,0),s[0]=0,t[0]=m,bin[++top]=s[0],bin[++top]=t[0];
        for(int i=1,len;i<=k;i++)
        {
            if(R[i]<abs(X[i]-l))continue;
            len=sqrt(pow(R[i])-pow(X[i]-l)),s[i]=Y[i]-len-1,t[i]=Y[i]+len,bin[++top]=s[i],bin[++top]=t[i];
        }
        sort(bin+1,bin+top+1),uniq=unique(bin+1,bin+top+1)-bin-1;
        for(int i=1;i<=uniq;i++)trans[bin[i]]=i;
        for(int i=0,ts,tt;i<=k;i++)ts=trans[s[i]],tt=trans[t[i]],s[i]=ts,t[i]=tt;
        int res;
        for(int i=k;i;i--)
        {
            if(R[i]<abs(X[i]-l))continue;
            res=0;
            for(int j=s[i]+1;j<=t[i];j++)if(!use[j])res+=bin[j]-bin[j-1],use[j]=true;
            ans+=(k-i)*res;
        }
        res=0;
        for(int j=2;j<=uniq;j++)if(!use[j])res+=bin[j]-bin[j-1];
        ans+=k*res;
    }
    printf("%lld",ans);
    return 0;
}