zhouwc 的博客

题解 P5640 【【CSGRound2】逐梦者的初心】

官方题解

subtask1

对于每次操作,枚举 $l$,枚举 $i$,判断一下。考察了循环语句和分支语句的简单应用。

时间复杂度 $O(m^3)$

subtask2

记录下每次操作后每个 $i$满不满足条件。

考虑在末尾加一个字符

不难发现原来的 $i$变成了现在的 $i+1$,再把新加入的字符对状态的影响处理一下。

再考虑在开头加一个字符

原来的状态不用变,只要把新加入的字符对状态的影响处理。

时间复杂度 $O(m^2)$

subtask3

字符集非常小,答案只有在特殊情况下才存在,可能存在什么神奇的做法。

subtask4

每个位子和每种字符都是独立的,对每种字符都记录一下位子。

用 $f[i]=0 or 1$表示长度为 $i$的后缀可不可以,0表示可以,1表示不行。

考虑f只有0和1,可以用bitset优化,对每种字符都开一个bitset记录是不是该字符。

在末尾加一个字符时,左移后做or运算。

在开头加一个字符时,直接or上该字符出现的状态左移长度减一位。

答案就是范围内0的个数。

复杂度 $O(m^2/w)$

std:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<bitset>
using namespace std;
int n,m,opt,S[1000005],dt;
bitset<35005> f,id[1005],now;
int read(){
    int ans=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch<='9'&&ch>='0'){
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
        S[i]=read();
    for(int i=1;i<=m;i++)
        id[S[i]].set(i);
    now.set();
    for(int i=1;i<=m;i++){
        opt=read();
        dt=read();
        now.reset(i);
        if(opt==0)
            f=(f<<1)|id[dt];
        else
            f=f|(id[dt]<<(i-1));
        printf("%d\n",(~(f|now)).count());
    }
    return 0;
}

附录:

关于如何使用bitset

简单的来说,bitset就是压位优化的0/1数组。

定义一个长度为 $len$的bitset:

bitset<len> f;

把f的每一位都改为1

f.set();

把f的第i位改为1

f.set(i);

把f的每一位都改为0

f.reset();

把f的第i位改为0

f.reset(i);

求f有几个1

f.count();

各类位运算和整数类型一样

f=f<<1;
f=f>>1;
f=f&f;
f=f|f;
f=f^f;
f=~f;

2019-11-10 14:58:20 in 题解