zoj 3818 2014牡丹江ネット試合
6956 ワード
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5350
昨日は全部WAと書きましたが、今日は列挙a、b、cの長さとstring類の関数substr、1 Aを押します.
それともシステム関数コードの呼び出しが短くて、コードが短いということは、エラーが少ないということと、思考のロジックが容易であることを意味しています.
昨日のWAコードを貼ります. なぜか分かりません.
昨日は全部WAと書きましたが、今日は列挙a、b、cの長さとstring類の関数substr、1 Aを押します.
それともシステム関数コードの呼び出しが短くて、コードが短いということは、エラーが少ないということと、思考のロジックが容易であることを意味しています.
昨日のWAコードを貼ります. なぜか分かりません.
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define ls(rt) rt*2
#define rs(rt) rt*2+1
//#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
//const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const int INF = 100000000;
const int MAXN = 1000+100;
char str[MAXN],ss[MAXN],aa[MAXN],bb[MAXN],cc[MAXN];
int posa[MAXN],len,acnt;
void cala()
{
acnt=0;
for(int i=0;i<len;i++)
if(str[i]==str[0])
posa[acnt++]=i;
}
int test1()
{
if(len<5)return 0;
for(int i=acnt-1;i>1;i--)
{
int pos=posa[i],flag=1;
if(pos%2 || pos<4)continue;
strcpy(aa,str+pos);
int lena=strlen(aa),pp=pos/2,j;
if(lena>=pp)continue;
for(j=0;j<lena;j++)
if(str[j]!=str[pos+j])
{
flag=0;
break;
}
if(!flag)continue;
int lenb=0;
for(j=lena;j<pp;j++)
bb[lenb++]=str[j];
bb[lenb]='\0';
if(lenb==0 || lena==0 || strcmp(aa,bb)==0 || lena*3+lenb*2!=len)continue;//
for(int j=pp;j<pos;j++)
if(str[j-pp] != str[j])
{
flag=0;
break;
}
if(flag)
{
//printf("oo#first# %d a=%d b=%d pos=%d
",i,lena, lenb,pos);
return 1;
}
}
return 0;
}
int test2()
{
if(len<7)return 0;
for(int i=acnt-1;i>1;i--)
{
int pos=posa[i],flag=1;
strcpy(aa,str+pos);
int lenab=strlen(aa),j;
if(lenab<2 || lenab*3>=len || lenab>=pos-1)continue;//
for(j=0;j<lenab;j++)
if(str[j] != str[j+lenab])
{
flag=0;
break;
}
if(!flag || lenab*2>=pos)continue;
for(j=lenab;j<lenab*2;j++)//
if(str[j] != str[j-lenab])
{
flag=0;
break;
}
if(!flag)continue;
int lenc=0;
for(int j=lenab*2;j<pos;j++)
cc[lenc++]=str[j];
cc[lenc]='\0';
int f2=0;
int lena=0,lenb=0;
for(int j=1;j<lenab;j++)
{
lena=0,lenb=0;
for(int k=0;k<j;k++)
{
aa[lena++]=str[k];
}
aa[lena]='\0';
for(int k=j;k<lenab;k++)
bb[lenb++]=str[k];
bb[lenb]='\0';
if(strcmp(aa,bb)==0 || strcmp(bb,cc)==0 || strcmp(aa,cc)==0 || lenb==0 || lena==0 || lenc==0 || lena*3+lenb*3+lenc!=len)continue;
f2=1;
break;
}
if(flag && f2)
{
//printf("#second# lenab=%d lena=%d lenb=%d lenc=%d
",lenab,lena,lenb,lenc);
return 1;
}
}
return 0;
}
int main()
{
//IN("J.txt");
int ncase;
int cnt;
scanf("%d",&ncase);
while(ncase--)
{
scanf("%s",ss);
int ll = strlen(ss);
cnt=0;
for(int i=0;i<ll;i++)
if(isalpha(ss[i]))
str[cnt++]=ss[i];
str[len=cnt]='\0';
///////////
// printf("## %s %d
",str,len);
///////////
cala();
if(test1() || test2())
puts("Yes");
else
puts("No");
}
return 0;
}
ACコードをもう一つ貼ります //#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const int INF = 100000000;
int test1(string s)
{
if(s.size()<5)return 0;
int lena=0,lenb=0;
for(lena=1;lena<s.size()/2;lena++)
{
lenb=0;
string a=s.substr(0,lena);
for(int j=lena;j<s.size()/2 && (lenb=j-lena+1) && lena*3+lenb*2<=s.size();j++)
{
string b=s.substr(lena,lenb);
string a2=s.substr(lena+lenb,lena);
string b2=s.substr(lena*2+lenb,lenb);
string a3=s.substr(lena*2+lenb*2,lena);
if(lena*3+lenb*2==s.size() && a!=b && a==a2 && a==a3 && b==b2)return 1;
}
}
return 0;
}
int test2(string s)
{
if(s.size()<7)return 0;
int lena,lenb,lenc;
for(lena=1;lena<s.size()/2;lena++)
{
string a=s.substr(0,lena);
for(lenb=1;lenb<s.size()/2 && (lena+lenb)*3<s.size();lenb++)
{
string b=s.substr(lena,lenb);
string a2=s.substr(lena+lenb,lena);
string b2=s.substr(lena*2+lenb,lenb);
if(a==a2&& b==b2 && a!=b)
for(lenc=1;lenc<s.size()/2 && (lena+lenb)*3+lenc<=s.size();lenc++)
{
string c=s.substr((lena+lenb)*2,lenc);
string a3=s.substr((lena+lenb)*2+lenc,lena);
string b3=s.substr(lena*3+lenb*2+lenc,lenb);
if(a==a3 && b==b3 && a!=c && b!=c && (lena+lenb)*3+lenc==s.size())return 1;
}
}
}
return 0;
}
int main()
{
//IN("J.txt");
int ncase;
scanf("%d",&ncase);
while(ncase--)
{
string ss,str;
cin >> ss;
for(int i=0;i<ss.size();i++)
if(isalpha(ss[i]))
str+=ss[i];
if(test1(str) || test2(str))
puts("Yes");
else
puts("No");
}
return 0;
}