【CSGRound2】逐梦者的初心(洛谷11月月赛 II & CSG Round 2 T3)

题目描述#

给你一个长度为\(n\)的字符串\(S\)。

有\(m\)个操作,保证\(m≤n\)。

你还有一个字符串\(T\),刚开始为空。

共有两种操作。

第一种操作:

在字符串\(T\)的末尾加上一个字符。

第二种操作:

在字符串\(T\)的开头加上一个字符。

每次操作完成后要求输出有几个\(l∈[1,T.size]\)满足以下条件:

对于\(∀i∈[1,l]\)有\(T_{T.size−l+i}≠S_i\)

\(Tip:\)字符串下标从\(1\)开始。\(T.size\)表示\(T\)的长度。

输入格式#

第一行两个正整数\(n,m\)。

第二行\(n\)个正整数,用空格隔开,第\(i\)个整数表示\(S_i\)。

接下来\(m\)行,每行两个数字 \(opt,ch\),\(opt=0\)表示在\(T\)的末尾加一个字符\(ch\),\(opt=1\)表示在\(T\)的开头加一个字符\(ch\)。

输出格式#

共\(m\)行,每行一个非负整数表示第\(m\)操作后的输出。

输入输出样例#

输入 #1

10 3
1 2 3 1 2 3 2 3 2 3
0 1
1 2
0 3

输出 #1

0
1
1

说明/提示#

注意:本题采用捆绑测试,只有当你通过一个\(subtask\)的所有点后,你才能拿到这个\(subtask\)的分数

对于所有的数据 \(n≤10^6,m≤3.3333×10^4,|∑|≤10^3,S_i∈[1,|∑|]。(∑表示字符集)\)

\(subtask1(17\%):m≤333\)

\(subtask2(33\%):m≤3333\)

\(subtask3(20\%):|∑|≤2∣\)

\(subtask4(30\%):\)无特殊条件​

样例解释:#

第一次操作后,\(T=“1”\),

\(l=1\)时\(T[1]=S[1]\),所以答案为\(0\)

第二次操作后,\(T=“21”\),

\(l=1\)时,\(T[2]=S[1]\)

\(l=2\)时,\(T[1]!=S[1]\),\(T[2]!=S[2]\),所以答案为\(1\)

第三次操作后,\(T=“213”\),

\(l=1\)时,\(T[3]!=S[1]\);

\(l=2\)时,\(T[2]=S[1]\);

\(l=3\)时,\(T[3]=S[3]\),所以答案为\(1\)


\(PS:\) 以下是我们机房的一个蒟蒻(文化课大佬%%%)lqx在博主的指导下撰写的。

\(O(m^3)\)的做法很容易想,按照题意模拟即可。

预计得分\(17pts\)。

对于\(O(m^2)\)的做法,因为这个题实际上是查找\(S\)的前\(l\)个和\(T\)的后\(l\)个是否每个都不相等,我们考虑记录\(dp[l]\)表示在上述意义下\(l\)是否合法(\(0\)表示都不相等,\(1\)表示至少有一个等)。容易知道,在\(T\)串最后插入一个字符时,因为\(S\)串始终不变,\(T\)串的最后\(l\)个字符从原本\(T\)串的后\(l\)个字符变成了原本\(T\)串的后\(l−1\)个字符加上新加入的字符,所以为了比较新的\(T\)串后\(l\)个字符是否合法,我们只需要比较新字符、原本\(T\)串的后\(l−1\)个字符是否有相等即可。即\(dp[i]=dp[i−1]|(ch==S[i])\)。这样,对于每个加入的字符,只需要用\(O(1)\)的复杂度检查每个枚举到的\(l\)是否合法即可。

在\(T\)串最前面插入一个字符时,因为原本的\(i\)个后缀依然没有变化,只是增加了一个新的后缀\(i+1\),所以我们只需暴力\(check\)新加入的后缀,对于每一位枚举是否有相等的即可。

时间复杂度\(O(m^2)\),预计得分\(50pts\)。

考虑优化\(O(m^2)\)的做法,我们找到了状压神器——\(bitset\),它可以将复杂度优化到原来 \(\dfrac{1}{w}\)(\(w\)为计算机字长,一般为\(32\)或\(64\))。如果常数优秀一些这个方法可以过。

考虑刚才的方法算过了哪些不可能合法的状态,我们知道所有的字符其存在位置都是独立的,所以我们用\(|∑|\)个\(bitset\)数组\(ch[x]\)记录字符\(x\)在\(S\)中的哪些位置上出现过。只要加入的新字符\(x\)对应的位置是\(ch[x]\)上\(1\)的位置,则该状态肯定不合法。

所以这样优化的关键在于同时算出了所有合法的状态。所以我们用\(dp\)的第\(i\)位的\(0/1\)表示后缀长度为\(i\)时是否有相等的字符。

如果在\(T\)串尾部加入新的字符,则对于长度是\(i\)的情况一定是由\(i−1\)的情况和新加入位的情况同时转移来(见上述\(O(m^2)\)做法),而所有新加入的位对应与\(S\)串中哪些位相同已经存储好,假设加入的字符是\(x\),则\(dp=(dp<<1)|ch[x]\)。

如果在\(T\)串头部加入新的字符,设原来\(T\)串有效的后缀长度有\(l\)位,则新的\(T\)串后\(l\)位是否合法状态不变,所以新旧\(T\)串前面\(l\)位答案一样;

在\(T\)串头部插入新字符时,我们将问题拆成两部分:

第一,我们发现在头部加入字符时,后面的所有字符都往后移了一位。

第二,我们需要比较加入的新字符和第一个字符是否相同。

很明显困难在于解决第一个问题。因为我们如果要想比较移动之后的字符和\(S\)的关系,在不知道其它任何东西的情况下,需要另用一个\(O(m)\)检查。

解决这个问题的方法是一个非常重要的思想:费用提前。在每次加入一个字符时,我们将这个字符所能贡献的答案都记在\(dp\)中。方法很简单,假设我们每次加进的字符是\(x\),考虑这一位对应到\(S\)串的所有可能。如果\(x\)对应到的某一位上\(ch[x]\)在同样的位上恰好是\(1\),说明加入字符使当前这个\(x\)恰好对应到刚才的那一位上,则这样的方案肯定是不合法的。

考虑如何进行这样的操作。假设\(x\)是在第\(i\)位加入队列并且对应的\(ch\)值在第\(k\)位上是\(1\),\(dp[i-1+k]\)一定不合法(假设没有从后插入的)。这时\(x\)距离队尾的距离是\(i−1\),所以当\(x\)取到\(k\)时,队尾应该到\(k+(i-1)\)位,但是注意在\(bitset\)里是反着存的,所以:

\(dp=dp|(ch[x]<<i−1)\)
时间复杂度为\(O(\dfrac{m^2}{w})\)

代码实现:

#include&lt;iostream&gt;
#include&lt;cmath&gt;
#include&lt;cstring&gt;
#include&lt;cstdio&gt;
#include&lt;ctime&gt;
#include&lt;climits&gt;
#include&lt;algorithm&gt;
#include&lt;bitset&gt;
using namespace std;
const int M=40000;
bitset&lt;M&gt; ch[1010],dp,limit;
int n,m;
int main()
{
    int i,t,x;
    scanf(&quot;%d%d&quot;,&amp;n,&amp;m);
    for(i=1;i&lt;=m;i++) scanf(&quot;%d&quot;,&amp;x),ch[x].set(i);
    for(;i&lt;=n;i++) scanf(&quot;%d&quot;,&amp;x);
    limit.set();
    for(i=1;i&lt;=m;i++)
    {
        scanf(&quot;%d%d&quot;,&amp;t,&amp;x);
        limit.reset(i);
        if(t==0) dp=(dp&lt;&lt;1)|ch[x];
        else dp=dp|(ch[x]&lt;&lt;i-1);
        printf(&quot;%d\n&quot;,(~(dp|limit)).count());
    }
    return ~~(0-0);
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。