zoj 3818 2014牡丹江ネット試合

6956 ワード

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5350
昨日は全部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;

}