(BC 一周年)hdu 5311 Hidden String

Posted by 111qqz on Tuesday, July 28, 2015

TOC

http://acm.hdu.edu.cn/showproblem.php?pid=5311 题意:问能否从一个给定的字符串中拿出三个不相交的字串(原串可以有剩余),组成字符串“anniversary” 思路:暴力。

比赛的时候没做出来,sad 我发现我有一个问题,就是不敢跑暴力 有不少题其实正解就是暴力 或者有的题,暴力不是标解,但是绝对可A,可我就不敢写… 就觉得不会是这样.. 说到底还是不自信吧…

思路是枚举两个间隔点,将 string tar="anniversary"分成三个不为空的部分 然后在给的字符串中按顺序查找这三部分 如果都能找到,直接YES 如果任何一种间隔的分段都无法YES 就NO…

妈蛋,if语句后面多写了个分号,调了半个多小时才发现(为啥总是这种傻逼错误….) 还有一点,因为是多组数据,而对于每组数据,将tar拆分的方法都是一样的,可以先预处理一下存到数组里.


   #define yn hez111qqz
   #define j1 cute111qqz
   #define tm crazy111qqz
   #define lr dying111qqz
   using namespace std;
   #define REP(i, n) for (int i=0;i<int(n);++i)  
   typedef long long LL;
   typedef unsigned long long ULL;
   const int N=1E2+5;
   int d[N];
   int len;
   string st,tar,s1,s2,s3;
   bool flag;
   
   void solve (string x,string y,string z)
   {
       int lx = x.length();
       int ly = y.length();
       int lz = z.length();
       bool debug = false;
       if (x=="anniv"&&y=="er"&&z=="sary")
       debug = true;
       int p;
       int k = 0;
       for ( int i = 0 ; i  < len-lx+1 ; i++ )
       {
       string tmps = st.substr(i,lx);
   //	if (debug) cout<<"tmaaaps:"<<tmps<<endl;
       if (tmps==x);
       {
           p = i;
          // cout<<"tmps1:"<<tmps<<endl;
           k++;
           break;
       }
       }
       if (k==0) return;
   
       for ( int i =  p+lx ;  i < len - ly +1 ;i++)
       {
       string tmps = st.substr(i,ly);
       //	if (debug) cout<<"tms2:"<<tmps<<endl;
       if (tmps==y)
       {
           p = i ;
         //  cout<<"tmps2:"<<tmps<<endl;
           k++;
           break;
       }
       }
       if (k==1) return ;
       for ( int i = p+ly;  i < len - lz +1 ; i ++)
       {
       string tmps = st.substr(i,lz);
       if (tmps==z)
       {
       //    cout<<"tmps3:"<<tmps<<endl;
           k++;
           break;
       }
       }
       if (k==3)
       {
       flag = true;
       return;
       }
   
   }
   int main()
   {
       int T; 
       cin>>T;
       while (T--)
       {
         flag = false;
         cin>>st;
         len = st.length();
         int k = 0;
         int num = 0;
         tar="anniversary";
         for ( int i = 1 ; i <=9 ;  i++ )
         {
           for ( int j = i+1 ; j <= 10 ; j++ )
           {
               s1 = tar.substr(0,i);
               s2 = tar.substr(i,j-i);
               s3 = tar.substr(j);
            //   cout<<i<<" "<<j<<" "<<s1<<" "<<s2<<" "<<s3<<endl;
               solve (s1,s2,s3);
               if (flag)
               {
               break;
               }
           }
           if (flag)
           break;
         }
         if (flag)
           {
           cout<<"YES"<<endl;
           }
         else
           {
           cout<<"NO"<<endl;
           }
   
       }
     
       return 0;
   }