UVALive 5052 Genome Evolution —

　　本以为这题n=3000，随便n方一下就能过。于是我先枚举长度len再枚举起点，不断增加新的点并删除原来的点，判断在b中的r-l+1是不是等于len即可，这个过程显然要用set维护比较方便，但是貌似卡了这个log，T了= =。

　　然后修改了一下思路，先枚举左端点，再不断的向有扩张，并用两个变量l和r来标记在b中的最左和最右的位置，然后如上做法即可。这样的好处在于不需要删除点的信息，因此可以直接借用变量来维护边界了。具体差别见代码吧。

　　T的代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <set>

 using namespace std;

 const int N =  + ;

 typedef long long ll;

 int n,a[N],b[N];

 int pos[N];

 int main()

 {

     while(scanf("%d",&n) ==  && n)

     {

         for(int i=;i<=n;i++) scanf("%d",a+i);

         for(int i=;i<=n;i++) scanf("%d",b+i), pos[b[i]] = i;

         ll ans = ;

         for(int len=;len<=n;len++)

         {

             set<int> S;

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

             {

                 S.insert(pos[a[i]]);

             }

             if(*S.rbegin() - *S.begin() +  == len) ans++;

             for(int i=len+;i<=n;i++)

             {

                 S.insert(pos[a[i]]);

                 S.erase(pos[a[i-len]]);

                 if(*S.rbegin() - *S.begin() +  == len) ans++;

             }

         }

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

     }

     return ;

 }

T的代码

　　AC的代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <set>

 using namespace std;

 const int N =  + ;

 typedef long long ll;

 int n,a[N],b[N];

 int pos[N];

 int main()

 {

     while(scanf("%d",&n) ==  && n)

     {

         for(int i=;i<=n;i++) scanf("%d",a+i);

         for(int i=;i<=n;i++) scanf("%d",b+i), pos[b[i]] = i;

         ll ans = ;

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

         {

             int l = pos[a[i]];

             int r = pos[a[i]];

             for(int j=i+;j<=n;j++)

             {

                 l = min(l, pos[a[j]]);

                 r = max(r, pos[a[j]]);

                 if(r - l == j - i) ans++;

             }

         }

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

     }

     return ;

 }

AC的代码

巴特西

UVALive 5052 Genome Evolution ——（xjbg）

最新文章

热门文章