HDU 5311 Hidden String （暴力）

题意：今天是BestCoder一周年纪念日. 比赛管理员Soda有一个长度为n的字符串s. 他想要知道能否找到s的三个互不相交的子串s[l1..r1], s[l2..r2], s[l3..r3]满足下列条件:

  1. 1≤l1≤r1<l2≤r2<l3≤r3≤n

  2. s[l1..r1], s[l2..r2], s[l3..r3]依次连接之后得到字符串"anniversary".

特别注意：式子中红色符号！！！

思路：其实就是要在一个串中找可能存在的3个连续子串来构成这个"anniversary"，穷举第一个串的大小，再穷举第2个串的大小，剩下的由第3个串来搞定。每个串必须大于等于1的大小才行，而且不能重叠到。

如果用的是string自带的find，还需要特别注意的是OJ上string::npos可能并不是你机器上定义的那样，可能是-1，可能是unsigned的无穷大！总之最好避开这些东西~ 就是这里wa到怕了，因为BC和HDU上的并不一样，所以我在BC上交就过了，而HDU没过。

BC上交的：

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x7f7f7f7f

 using namespace std;

 const int N=;

 string str;

 string tmp="anniversary";

 int cal(int len)

 {

     if(len<tmp.size())  return false;//不可能

     if(str.find( tmp )!= string::npos) return true;

     if(len==tmp.size()) //相同串

     {

         if(str.find( tmp )!= string::npos) return true;

         else    return false;

     }

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

     {

         unsigned int s1=str.find(tmp.substr(, i));

         if( s1+tmp.size()>=len || s1==string::npos )  continue;

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

         {

             unsigned int s2=str.find( tmp.substr(i, j), s1+i  );

             if( s2==string::npos )  continue;

             int k=-j-i;

             if( str.find( tmp.substr(i+j, k), s2+j )!=string::npos)

             {

                 return true;

             }

         }

     }

     return false;

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int n, m, t, p, q;

     cin>>t;

     while(t--)

     {

         cin>>str;

         bool tmp=cal(str.size());

         if(tmp)     puts("YES");

         else        puts("NO");

     }

     return ;

 }

AC代码

HDU 上的：

#include <bits/stdc++.h>

#define LL long long

#define pii pair<int,int>

#define INF 0x7f7f7f7f

using namespace std;

const int N=;

string str;

string tmp="anniversary";

int cal(int len)

{

    for(int i=; i+<=tmp.size(); i++)

    {

        int s1=str.find(tmp.substr(, i), );

        if( s1< )  continue;

        for(int j=; j+i+<=tmp.size(); j++)

        {

            int s2=str.find( tmp.substr(i, j), s1+i  );

            if( s2< )  continue;

            int k=tmp.size()-j-i;

            if(k<) continue;

            if( str.find( tmp.substr(i+j, k), s2+j )< )

                return true;

        }

    }

    return false;

}

int main()

{

    freopen("input.txt", "r", stdin);

    int n, m, t, p, q;

    cin>>t;

    while(t--)

    {

        cin>>str;

        if( cal(   str.size()  ) )     printf("YES\n");

        else                      printf("NO\n");

    }

    return ;

}

AC代码