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

zhouwc · 2019-11-10 14:58:20 · 题解

官方题解

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;