题解 | #结婚改口#

#include <bits/stdc++.h>
using namespace std;
char s[(int)2e5+5];
long long c[(int)2e5+5];//从前往后 到i位置之前的合法的qc的个数
long long y[(int)2e5+5];//从后往前 i位置及之后的y的个数
long long j[(int)2e5+5];//从后往前 i位置及之后的j的个数
long long q[(int)2e5+5];//从前往后 到i位置之前的q的个数
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d%*c", &n);//不要漏掉%*c，不然会读出来一个换行符
        for (int i=0; i<n; i++)
        {
            char ch;
            scanf("%c", &ch);
            s[i]=ch;
        }
        if (n<=3) //特判一下
        {
            printf("qcjj\n");
            continue;
        }
        y[n-1]=(s[n-1]=='y'?1:0);
        j[n-1]=(s[n-1]=='j'?1:0);
        y[n]=y[n-1]; //为了避免访问越界
        j[n]=j[n-1];
        for (int i=n-2; i>=0; i--)
        {
            y[i] = y[i+1]+(s[i]=='y'?1:0);
            j[i] = j[i+1]+(s[i]=='j'?1:0);
        }
        c[0]=0;//0位置可以忽略掉，因为它前面没有字符，所以到它为止一定没有qc
        q[0]=(s[0]=='q'?1:0);
        c[1]=(s[1]=='c'?q[0]:0);//当且仅当0位置为q，1位置为c时，到1为止存在一个qc
        q[1]=(s[1]=='q'?q[0]+1:q[0]);
        long long jj=0, ay=0;
        for (int i=2; i<n-1; i++)
        {
            q[i]=q[i-1]+(s[i]=='q'?1:0);//q的个数
            c[i]=c[i-1]+(s[i]=='c'?q[i]:0);//qc的个数
            if (s[i]=='a') ay+=c[i]*y[i];//a字符前面的qc的个数乘后面的y的个数，就是这个a所能组成的qcay的个数
            else if (s[i]=='j') jj += c[i]*j[i+1];//qcjj的个数
        }
        
        if (ay>=jj) printf("qcay\n");//测试发现，数量相等时好像也只能是两个中的一个
        else printf("qcjj\n");
    }
}