USACO open 2024 铜组 T1

EnofTaiPeople · 2024-03-25 09:12:57 · 题解

需要我来讲一下铜组该怎么通过吗？

对于一次 [l,r] 的查询，考虑将 [1,l) 和 (r,n] 表示出来，如果能很方便的查询当前的运算值，这道题就能做了。

由于先进行与运算，所以我们可以想象一下将若干用与运算连接的数并在一起，用一个 std::vector 存起来，其中两个数之间的运算符都是或。

如果 vector 的大小很大，复杂度就会变得很劣质，但我们发现当 vector 的大小超过 3 时，可以将中间的所有数字或起来合并。

于是暴力处理前后缀的 vector，暴力查询即可，时空复杂度线性：

int T,n,K,b[N];
string s;
struct dat{
    vector<int>a;
    void rec(){
        if(a.size()>3){
            int i,k=0;
            for(i=a.size()-2;i;--i)k|=a[i];
            a={a[0],k,a.back()};
        }
    }
    dat operator&(const dat &z){
        vector<int>res=a;
        res.back()&=z.a[0];
        int r=z.a.size(),i;
        for(i=1;i<r;++i)res.push_back(z.a[i]);
        dat rp={res};
        rp.rec();return rp;
    }
    dat operator|(const dat &z)const{
        vector<int>res=a;
        for(int p:z.a)res.push_back(p);
        dat rp={res};
        rp.rec();return rp;
    }
    int val(){
        int res=0;
        for(auto &p:a)res|=p;
        return res;
    }
}f[N],g[N];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int i,j,k,l,r,x,y,z,v1,v2;
    cin>>n>>T;
    for(x=1;x<=n;++x){
        cin>>s;
        b[x]=s[0]==(x&1?'t':'a');
    }
    f[1]={{b[1]}};
    for(x=3;x<=n;x+=2){
        if(b[x-1])f[x]=f[x-2]&(dat){{b[x]}};
        else f[x]=f[x-2]|(dat){{b[x]}};
    }
    g[n]={{b[n]}};
    for(x=n-2;x>=1;x-=2){
        if(b[x+1])g[x]=(dat){{b[x]}}&g[x+2];
        else g[x]=(dat){{b[x]}}|g[x+2];
    }
    while(T--){
        cin>>l>>r>>s;
        k=s[0]=='t';
        dat rp={{k}};
        if(l>1){
            if(b[l-1])rp=f[l-2]&rp;
            else rp=f[l-2]|rp;
        }
        if(r<n){
            if(b[r+1])rp=rp&g[r+2];
            else rp=rp|g[r+2];
        }
        putchar(rp.val()==k?'Y':'N');
    }
    return 0;
}