#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+;