Hidden String

Accepts: 437

Submissions: 2174

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

问题描述

今天是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".

输入描述

输入有多组数据. 第一行有一个整数T (1≤T≤100), 表示测试数据组数. 然后对于每组数据:

一行包含一个仅含小写字母的字符串s (1≤|s|≤100).

输出描述

对于每组数据, 如果Soda可以找到这样三个子串, 输出"YES", 否则输出"NO".

输入样例

2

annivddfdersewwefary

nniversarya

输出样例

YES

NO

这题想要总结的地方就是理解一下题意吧，分成三段。。。(单独的annniversary要输出YES)

改了很久也很low的代码，也不优化了，纪念一下吧

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

vector<int> wei_z[30];

vector<int> weizhi;

char test[200];

int len,i,flag;

void init()

{

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

	{

		wei_z[test[i]-'a'].push_back(i);

	}

}

bool pend()

{

	int result=0,temp=weizhi[0];

	for(i=1;i<weizhi.size();i++)

	{

		if(temp!=weizhi[i]-1)

			result++;

		temp=weizhi[i];

	}

	if(result<=2)

		return true;

	else

		return false;

}

void solve()

{

	int i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11;

	for(i1=0;i1<wei_z['a'-'a'].size();i1++)

	{

		for(i2=0;i2<wei_z['n'-'a'].size();i2++)

		{

			if(wei_z['n'-'a'][i2]<=wei_z['a'-'a'][i1])continue;

			for(i3=0;i3<wei_z['n'-'a'].size();i3++)

			{

				if(wei_z['n'-'a'][i3]<=wei_z['n'-'a'][i2])continue;

				for(i4=0;i4<wei_z['i'-'a'].size();i4++)

				{

					if(wei_z['i'-'a'][i4]<=wei_z['n'-'a'][i3])continue;

					for(i5=0;i5<wei_z['v'-'a'].size();i5++)

					{

						if(wei_z['v'-'a'][i5]<=wei_z['i'-'a'][i4])continue;

						for(i6=0;i6<wei_z['e'-'a'].size();i6++)

						{

							if(wei_z['e'-'a'][i6]<=wei_z['v'-'a'][i5])continue;

							for(i7=0;i7<wei_z['r'-'a'].size();i7++)

							{

								if(wei_z['r'-'a'][i7]<=wei_z['e'-'a'][i6])continue;

								for(i8=0;i8<wei_z['s'-'a'].size();i8++)

								{

									if(wei_z['s'-'a'][i8]<=wei_z['r'-'a'][i7])continue;

									for(i9=0;i9<wei_z['a'-'a'].size();i9++)

									{

										if(wei_z['a'-'a'][i9]<=wei_z['s'-'a'][i8])continue;

										for(i10=0;i10<wei_z['r'-'a'].size();i10++)

										{

											if(wei_z['r'-'a'][i10]<=wei_z['a'-'a'][i9])continue;

											for(i11=0;i11<wei_z['y'-'a'].size();i11++)

											{

												if(wei_z['y'-'a'][i11]<=wei_z['r'-'a'][i10])continue;

												weizhi.push_back(wei_z['a'-'a'][i1]);

												weizhi.push_back(wei_z['n'-'a'][i2]);

												weizhi.push_back(wei_z['n'-'a'][i3]);

												weizhi.push_back(wei_z['i'-'a'][i4]);

												weizhi.push_back(wei_z['v'-'a'][i5]);

												weizhi.push_back(wei_z['e'-'a'][i6]);

												weizhi.push_back(wei_z['r'-'a'][i7]);

												weizhi.push_back(wei_z['s'-'a'][i8]);

												weizhi.push_back(wei_z['a'-'a'][i9]);

												weizhi.push_back(wei_z['r'-'a'][i10]);

												weizhi.push_back(wei_z['y'-'a'][i11]);

												if(pend()==true)

												{

													flag=1;

													return;

												}

												weizhi.clear();

											}

										}

									}

								}

							}

						}

					}

				}

			}

		}

	}

}

int main()

{

	int Test1;

	cin>>Test1;

	while(Test1--)

	{

		cin>>test;

		for(i=0;i<=29;i++)

			wei_z[i].clear();

		weizhi.clear();

		flag=0;

		len=strlen(test);

		init();

		solve();

		if(flag)

			cout<<"YES"<<endl;

		else

			cout<<"NO"<<endl;

	}

	return 0;

}

巴特西

HDU 5311：Hidden String

Hidden String

最新文章

热门文章