ZOJ 3818-Pletty Poem(暴力列挙)
1681 ワード
タイトルリンク
題意:与えられた文字列がABABAまたはABABCABの形式に合致するかどうかを求め、できればYesを出力し、できなければNoとする.
考え方:暴力はAとBの長さを列挙し、長さから3倍のABの長さ、すなわちCの長さを減算して、組み合わせた文字列が与えられたものと等しいかどうかを見る.ここでstringのsubstr関数は良いものです.
コード:
題意:与えられた文字列がABABAまたはABABCABの形式に合致するかどうかを求め、できればYesを出力し、できなければNoとする.
考え方:暴力はAとBの長さを列挙し、長さから3倍のABの長さ、すなわちCの長さを減算して、組み合わせた文字列が与えられたものと等しいかどうかを見る.ここでstringのsubstr関数は良いものです.
コード:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
char str[55];
int main() {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%s", str);
string s;
int len = strlen(str);
for (int i = 0; i < len; i++)
if (isupper(str[i]) || islower(str[i]))
s += str[i];
len = s.length();
int flag = 0;
for (int i = 1; i < len / 2 && !flag; i++) {
for (int j = 1; j < len / 2 && !flag; j++) {
string A = s.substr(0, i);
string B = s.substr(i, j);
if (A == B)
continue;
if (A + B + A + B + A == s) {
flag = 1;
break;
}
if (len - (i + j) * 3 > 0) {
string AB = A + B;
string C = s.substr(2 * (i + j), len - (i + j) * 3);
if (A == C || B == C)
continue;
if (AB + AB + C + AB == s) {
flag = 1;
break;
}
}
}
}
if (flag)
printf("Yes
");
else
printf("No
");
}
return 0;
}