(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;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付