记录编号	35478	评测结果	AAAAAAAA
题目名称	分球	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.707 s
提交时间	2012-02-22 14:53:29	内存使用	31.73 MiB

#include <cstdio>
#include <string>
using namespace std;
const int MAXN = 3000000;
string q[MAXN];
int p[MAXN], m, n, k, l, tail, head;
bool ok, in[MAXN*3];
void print(string s, int v) {
    if(v == 0)
        printf("%d %s\n", k++, s.c_str());
    else {
        print(q[v], p[v]);
        printf("%d %s\n", k++, s.c_str());
    }
}
bool right(string x) {
    int i = 0, r = 0, u = 0;
    while(x[i] != 'b' && i < 2*n)
        if(x[i++] == 'a')
            r++;
    if(r == n-1) return true; else return false;
}
int code(string x) {
    int r = 0, j = 1, i;
    for(i = x.length()-1; i >= 0; i--) {
        if(x[i] == 'b')
            r += j;
        else if(x[i] == ' ')
            r += 2 * j;
        j = j * 3;
    }
    return r;
}
void push(string x, int y) {
    q[++tail] = x;
    p[tail] = y;
    in[code(x)] = true;
}
string pop() {
    l = ++head;
    return q[head];
}
bool check(string x) {
    int i = 1;
    bool f = true;
    while (i <= tail && f)
        if(x == q[i++])
            f = false;
    return !f;
}
void BFS(string x, int y) {
    string t, r;
    int i = 0, j = 0;
    push(x, 0);
    while (head != tail && !ok) {
        t = r = pop();
        i = 0;
        while(t[i] != ' ') i++;
        for(j = 0; j < 2*n-1; j++) {
            t = r;
            if(t[j] != ' ' && t[j+1] != ' ') {
                t[i] = t[j];
                t[i+1] = t[j+1];
                t[j] = t[j+1] = ' ';
                if(right(t)) {
                    ok = true;
                    print(t, l);
                    return;
                } else if(!in[code(t)])
                    push(t, l);
            }
        }
    }
}
int main() {
    freopen("balls.in", "r", stdin);
    freopen("balls.out", "w", stdout);
    char c, s[20];
    string str;
    fgets(s, 20, stdin);
    sscanf(s, "%d", &m);
    for(int i = 1; i <= m; i++) {
        for(int j = 0; j < MAXN*3; j++) in[j] = false;
        fgets(s, 20, stdin);
        sscanf(s, "%d", &n);
        k = 0;
        ok = false;
        fgets(s, 20, stdin);
        str = "";
        for(int o=0; o<n*2; o++) str += s[o];
        fgets(s, 20, stdin);
        head = tail = 0;
        if(right(str)) {
            ok = true;
            printf("0 %s\n", str.c_str());
        } else
            BFS(str, 0);
        if(!ok)
            printf("NO SOLUTION\n");
        printf("\n");
    }
    return 0;
}