CF778A：String Game

给出字符串s和t，以及s的长度n的一个全排列，求按照这个排列依次删除s的字符，删到何时s中不含子序列t。

解法一：

t中的每个字符的位置在s中跳啊跳，合法的情况下t中的字符在s中的位置应该是单调递增的，因此让t中的字符在s中建的邻接表里跳啊跳就好了。

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 using namespace std;

 #define maxs 200011

 char s[maxs];int ls;

 char t[maxs];int lt;

 int first[],next[maxs],P[maxs];

 bool vis[maxs];

 bool Play(int x)

 {

     if (x==lt-) return ;

     if (P[x+]<=P[x])

     {

         while (P[x+]!=- && (P[x+]<=P[x] || vis[P[x+]])) P[x+]=next[P[x+]];

         if (P[x+]==-) return ;

         return Play(x+);

     }

     return ;

 }

 int x;

 int find(int x)

 {

     int L=,R=lt-;

     while (L<R)

     {

         int mid=(L+R)>>;

         if (x<=P[mid]) R=mid;

         else L=mid+;

     }

     return L;

 }

 int main()

 {

     scanf("%s",s);ls=strlen(s);

     scanf("%s",t);lt=strlen(t);

     memset(first,-,sizeof(first));

     for (int i=ls-;i!=-;i--)

     {

         int now=s[i]-'a'+;

         next[i]=first[now];

         first[now]=i;

     }

     int ans=;

     for (int i=;i<lt;i++)

         P[i]=first[t[i]-'a'+];

     bool flag=;

     for (int i=;i<lt-;i++)

         if (!Play(i)) {flag=;break;}

     if (flag)

     {

         memset(vis,,sizeof(vis));

         for (int i=;i<ls;i++)

         {

             scanf("%d",&x);x--;

             vis[x]=;

             int pos=find(x);

             if (P[pos]==x)

             {

                 P[pos]=next[P[pos]];

                 while (P[pos]!=- && vis[P[pos]]) P[pos]=next[P[pos]];

                 if (P[pos]==-) break;

                 if (!Play(pos)) break;

             }

             ans++;

 //            for (int j=0;j<ls;j++) cout<<vis[j]<<' ';cout<<endl;

 //            for (int j=0;j<lt;j++) cout<<P[j]<<' ';cout<<endl;

         }

     }

     printf("%d\n",ans);

     return ;

 }

该代码在随机数据下表现良好，因此如果是oi赛制可以拿到不错的分数。但是理论复杂度是n2的，而且存在aaaa……这样的数据使得t中每个字符都要跳n次。

解法二：

我们要在排列中找一个位置，它左边的都符合某个条件，而右边都不符合。二分！！

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 //#include<iostream>

 using namespace std;

 #define maxs 200011

 char s[maxs];int ls;

 char t[maxs];int lt;

 int a[maxs];

 bool vis[maxs];

 int main()

 {

     scanf("%s%s",s,t);

     ls=strlen(s),lt=strlen(t);

     for (int i=;i<ls;i++) scanf("%d",&a[i]),a[i]--;

     int L=,R=ls-;

     while (L<R)

     {

         int mid=(L+R+)>>;

         memset(vis,,sizeof(vis));

         for (int i=;i<mid;i++) vis[a[i]]=;

         int j=;

         for (int i=;i<ls;i++)

             if (j<lt && s[i]==t[j] && !vis[i]) j++;

         if (j==lt) L=mid;

         else R=mid-;

     }

     printf("%d\n",L);

     return ;

 }

巴特西

CF778A：String Game

最新文章

热门文章