牛客 19-5-3 QAQ_牛客博客

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
int main()
{
    char a[6000];
    scanf("%s",a);
    LL s1=0,sum=0,len=strlen(a);
    if(a[0]=='Q') s1++;
    for(int i=1;i<len;i++)
    {
        if(a[i]=='Q'){s1++;}
        if(a[i]=='A'&&s1!=0)
        {
            LL s2=0,s=s1;
            if(a[i-1]=='Q') s--;// 小心越界
            for(int j=i+2;j<strlen(a);j++)
                if(a[j]=='Q') s2++;
            sum+=s*s2;
        }
    }
    cout<<sum<<endl;
}

// 超时代码
#include<iostream>
#include<string>
using namespace std;
int count=0;
void bfs(string s,int i,int flag)
{
    if(i>=(int)s.length()) return ;
    if(flag==1)
    {
        if(s[i]=='Q')
        {
            bfs(s,i+2,flag+1);
        }
        else bfs(s,i+1,flag);
    }
    if(flag==2)
    {
        if(s[i]=='A')
        {
            bfs(s,i+2,flag+1);
        }
        bfs(s,i+1,flag);
    }
    if(flag==3)
    {
        if(s[i]=='Q')
        {
            count++;
        }
        bfs(s,i+1,flag);
    }
}
int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.length()-4;i++)
        bfs(s,i,1);
    cout<<count<<endl;
}

相比两个方法第一个少了回溯次；

B题：

#include <iostream>
using namespace std;
#define N 'W'+ 'W' + '#'
#define FOR(i,l,r) for(int i = l;i < r;i++)
char a[4][4];
int judge()
{
    if(a[0][0] + a[1][1] + a[2][2] == N || a[0][2] + a[1][1] + a[2][0] == N)return 0;
    FOR(i,0,3)
    if(a[i][0]+a[i][1]+a[i][2]==N || a[0][i]+a[1][i]+a[2][i] == N)return 0;
    return 1;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int flag = 0;
        FOR(i,0,3)scanf("%s",a[i]);
        if(!judge()) 
        {
            FOR(i,0,3)FOR(j,0,3)
            if(a[i][j] == 'W')
            {
                a[i][j]='#';
                if(judge())flag = 1;
                a[i][j]='W';
            }
            flag?puts("Emmm"):puts("Alice");
        }
        else puts("Bob");
    }
    return 0;
}

代码精炼。正常要写100+；