P8317 [FOI2021] 幸运区间

luckydrawbox · 2022-05-02 00:31:07 · 题解

\text{Link}

自己供的第一道题。

题意

给出 n 个数列，编号为 0\sim n-1，每个数列有 d 个正整数。

对于一段区间 [l,r]，从序列 l 到 r 中的数字中选出不超过 k 个数字，称之为幸运数字。若存在一种情况使每个区间至少包含一个选出的幸运数字，则称区间 [l,r] 为幸运区间，并且把这 n 个数列构成的区间中长度最大的幸运区间成为超级幸运区间。

求这 n 个数列的超级幸运区间。

分析

算法一

观察到 d,k 超级小，所以每次加入一个序列时只有看看该序列是否有幸运数字，没有则暴搜增加幸运数字。

枚举区间的起点，然后一直向右加数字知道不能加为止，其中用一个数组来记录幸运数字，然后统计答案。

时间复杂度 \text{O}(tn^2d^{k+1}k)，期望得分 \texttt{45-60} 分。

算法二

主要是枚举区间花了太多时间，于是我们考虑用分治减少枚举的区间。

设 \text{solve}(l,r) 表示计算区间左右端点都在 [l,r] 内的区间的答案，设 mid=\left\lfloor\dfrac{l+r}{2}\right\rfloor，则该问题可以分成以下几个子问题求解：

• 一定经过数列 mid 的幸运区间。

前两个子问题直接递归求解，第三个则按照算法一的方法进行计算，只不过可以从两个方向增加数列。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long read(){
    long long x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;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');
}
const int N=1e5+10;
int t,n,d,k,a[N][5],mx,ml,mr,luck[5],sum;
void dfs(int l,int r,int L,int R){
    bool f=0;
    do{//向左扩展
        if(L-1<l)
            break;
        f=0;
        for(int i=1;i<=d;i++)
            for(int j=1;j<=sum;j++)
                f|=(a[L-1][i]==luck[j]);
        if(f)
            L--;
    }while(f);
    do{//向右扩展
        if(R+1>r)
            break;
        f=0;
        for(int i=1;i<=d;i++)
            for(int j=1;j<=sum;j++)
                f|=(a[R+1][i]==luck[j]);
        if(f)
            R++;
    }while(f);
    if(mx<R-L+1||(mx==R-L+1&&L<ml)){
        mx=R-L+1;
        ml=L;
        mr=R;
    }
    if(sum==k||(l==L&&r==R))
        return;
    if(l!=L){//向左增加幸运数字
        for(int i=1;i<=d;i++){
            luck[++sum]=a[L-1][i];
            dfs(l,r,L-1,R);
            sum--;
        }
    }
    if(r!=R){//向右增加幸运数字
        for(int i=1;i<=d;i++){
            luck[++sum]=a[R+1][i];
            dfs(l,r,L,R+1);
            sum--;
        }
    }
}
void solve(int l,int r){
    if(l==r){
        if(mx<1||(mx==1&&l<ml)){//更新答案
            mx=1;
            ml=mr=l;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(l<=mid-1)
        solve(l,mid-1);
    if(mid+1<=r)
        solve(mid+1,r);
    sum=1;
    for(int i=1;i<=d;i++){
        luck[sum]=a[mid][i];
        dfs(l,r,mid,mid);
    }
}
int main(){
    t=read();
    for(int ii=1;ii<=t;ii++){
        n=read();d=read();k=read();
        for(int i=0;i<n;i++)
            for(int j=1;j<=d;j++)
                a[i][j]=read();
        mx=0;
        solve(0,n-1);
        printf("Case #%d: %d %d\n",ii,ml,mr);
    }
    return 0;
}

时间复杂度 \text{O}(tn\log n\ d^{k+1}k)，期望得分 \texttt{70} 分。不过开 \texttt{O2} 后足够过了。

算法三

其实还可以增加一个小优化，原来在向左右扩展的过程中我们都是用 dk 的时间来判断是否可以直接扩展，然而我们只要把用数组记录幸运数字改成用桶记录，就可以去掉 k。

你可能会问，k 不是 2 或 3 吗，你去了 k 和去常数有啥区别？不过搜索本来就十分玄学，去了 k 以后就可以玄学地节省许多时间了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long read(){
    long long x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;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');
}
const int N=1e5+10;
int t,n,d,k,a[N][5],mx,ml,mr,luck[5],sum;
bool v[N];//用桶记录某个数字是否是幸运数字
void dfs(int l,int r,int L,int R){
    bool f=0;
    do{
        if(L-1<l)
            break;
        f=0;
        for(int i=1;i<=d;i++)
            f|=v[a[L-1][i]];
        if(f)
            L--;
    }while(f);
    do{
        if(R+1>r)
            break;
        f=0;
        for(int i=1;i<=d;i++)
            f|=v[a[R+1][i]];
        if(f)
            R++;
    }while(f);
    if(mx<R-L+1||(mx==R-L+1&&L<ml)){
        mx=R-L+1;
        ml=L;
        mr=R;
    }
    if(sum==k||(l==L&&r==R))
        return;
    if(l!=L){
        for(int i=1;i<=d;i++){
            sum++;
            v[a[L-1][i]]=1;
            dfs(l,r,L-1,R);
            v[a[L-1][i]]=0;
            sum--;
        }
    }
    if(r!=R){
        for(int i=1;i<=d;i++){
            sum++;
            v[a[R+1][i]]=1;
            dfs(l,r,L,R+1);
            v[a[R+1][i]]=0;
            sum--;
        }
    }
}
void solve(int l,int r){
    if(l==r){
        if(mx<1||(mx==1&&l<ml)){
            mx=1;
            ml=mr=l;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(l<=mid-1)
        solve(l,mid-1);
    if(mid+1<=r)
        solve(mid+1,r);
    sum=1;
    for(int i=1;i<=d;i++){
        v[a[mid][i]]=1;
        dfs(l,r,mid,mid);
        v[a[mid][i]]=0;
    }
}
int main(){
    t=read();
    for(int ii=1;ii<=t;ii++){
        n=read();d=read();k=read();
        for(int i=0;i<n;i++)
            for(int j=1;j<=d;j++)
                a[i][j]=read();
        mx=0;
        solve(0,n-1);
        printf("Case #%d: %d %d\n",ii,ml,mr);
    }
    return 0;
}

时间复杂度 \text{O}(tn\log n\ d^{k+1})，期望得分 \texttt{100} 分。