题解 | #网球打网球#

这道题是一个典型的自动机的题目，根据当前字母以及当前所处的比分状态可以唯一确定下一个比分状态。而且所有的可能的字母和比分状态的组合的数量是极其有限的，因此简单的写出所有可能的if-elseif分支即可。例如这个题解。下面给出一个自动机的“标准”解法，使用数组记录所有的可能性（由于偷懒，这里其实用的是STLmap）。

#include <bits/stdc++.h>
using namespace std;
 
string solute(const string & input){
    using pii = pair<int, int>;
    using ppic = pair<pii, char>;
    using mpp = map<ppic, pii>;
 
    static mpp dfa = {
        {{{-1, -1}, 'A'}, {-1, -1}}, {{{-1, -1}, 'B'}, {-1, -1}},
 
        {{{0, 0}, 'A'}, {15, 0}}, {{{0, 0}, 'B'}, {0, 15}},
        {{{0, 15}, 'A'}, {15, 15}}, {{{0, 15}, 'B'}, {0, 30}},
        {{{0, 30}, 'A'}, {15, 30}}, {{{0, 30}, 'B'}, {0, 40}},
        {{{0, 40}, 'A'}, {15, 40}}, {{{0, 40}, 'B'}, {0, 100}},
        {{{0, 100}, 'A'}, {-1, -1}}, {{{0, 100}, 'B'}, {-1, -1}},
        
        {{{15, 0}, 'A'}, {30, 0}}, {{{15, 0}, 'B'}, {15, 15}},        
        {{{15, 15}, 'A'}, {30, 15}}, {{{15, 15}, 'B'}, {15, 30}},
        {{{15, 30}, 'A'}, {30, 30}}, {{{15, 30}, 'B'}, {15, 40}},
        {{{15, 40}, 'A'}, {30, 40}}, {{{15, 40}, 'B'}, {15, 100}},
        {{{15, 100}, 'A'}, {-1, -1}}, {{{15, 100}, 'B'}, {-1, -1}},
        
        {{{30, 0}, 'A'}, {40, 0}}, {{{30, 0}, 'B'}, {30, 15}},
        {{{30, 15}, 'A'}, {40, 15}}, {{{30, 15}, 'B'}, {30, 30}},
        {{{30, 30}, 'A'}, {40, 30}}, {{{30, 30}, 'B'}, {30, 40}},
        {{{30, 40}, 'A'}, {40, 40}}, {{{30, 40}, 'B'}, {30, 100}},
        {{{30, 100}, 'A'}, {-1, -1}}, {{{30, 100}, 'B'}, {-1, -1}},
 
        {{{40, 0}, 'A'}, {100, 0}}, {{{40, 0}, 'B'}, {40, 15}},
        {{{40, 15}, 'A'}, {100, 15}}, {{{40, 15}, 'B'}, {40, 30}},
        {{{40, 30}, 'A'}, {100, 30}}, {{{40, 30}, 'B'}, {40, 40}},
        {{{40, 40}, 'A'}, {50, 40}}, {{{40, 40}, 'B'}, {40, 50}},
        {{{40, 100}, 'A'}, {-1, -1}}, {{{40, 100}, 'B'}, {-1, -1}},
 
        {{{50, 40}, 'A'}, {100, 40}}, {{{50, 40}, 'B'}, {40, 40}}, 
        {{{40, 50}, 'A'}, {40, 40}}, {{{40, 50}, 'B'}, {40, 100}},
 
        {{{100, 0}, 'A'}, {-1, -1}}, {{{100, 0}, 'B'}, {-1, -1}},
        {{{100, 15}, 'A'}, {-1, -1}}, {{{100, 15}, 'B'}, {-1, -1}},
        {{{100, 30}, 'A'}, {-1, -1}}, {{{100, 30}, 'B'}, {-1, -1}},
        {{{100, 40}, 'A'}, {-1, -1}}, {{{100, 40}, 'B'}, {-1, -1}}       
    };
 
 
    pii state = {0, 0};
    for(char ch : input){
        auto it = dfa.find({state, ch});
        assert(it != dfa.end());
        state = it->second;
    }
    if(state.first == -1){
        assert(state.second == -1);
        return "INVALID";
    }
    if(state.first == 100){
        assert(0 <= state.second && state.second <= 40);
        return "A won";
    }
    if(state.second == 100){
        assert(0 <= state.first && state.first <= 40);
        return "B won";
    }
    string a = to_string(state.first);
    string b = to_string(state.second);
    if(state.first == 50) a = "AD";
    if(state.second == 50) b = "AD";
    assert(state.first != 50 || state.second != 50);
    return a+":"+b;
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("1.txt", "r", stdin);
#endif
    string s; getline(cin, s);
	cout << solute(s) << endl;
	return 0;
}

另外一个解法，把所有状态分为合法与非法两大类，发现其实还是比较容易区分的，只需要根据赢球的数量简单判断即可。合法状态中又需要区分A、B的得分，其实也很容易区分，因为球数多于一定数量，比分的可能性非常少。

#include <bits/stdc++.h>
using namespace std;
 
char A[110];
 
char T[][12] = {"0", "15", "30", "40", "AD"};
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("1.txt", "r", stdin);
#endif
    fgets(A, 110, stdin);
    int acnt = 0, bcnt = 0;
    int n = strlen(A);
    A[n - 1] = '\0';
    --n;
    int flag = 0;
    for(int i=0;i<n;++i){
        if('A' == A[i]) ++acnt;
        else if('B' == A[i]) ++bcnt;
        else assert(0);
 
        if(acnt >= 4 && acnt - bcnt >= 2){ // A won
            if(i != n - 1){
                flag = 1; // invalid
                break;
            }
            flag = 2; // A won;
        }
        if(bcnt >= 4 && bcnt - acnt >= 2){
            if(i != n - 1){
                flag = 1;
                break;
            }
            flag = 3; // B won
        }
    }
    if(1 == flag) printf("INVALID\n");
    else if(2 == flag) printf("A won");
    else if(3 == flag) printf("B won");
    else {
        if(acnt >= 4 || bcnt >= 4){
            if(acnt == bcnt) acnt = bcnt = 3;
            else if(acnt - bcnt == 1) acnt = 4, bcnt = 3;
            else if(bcnt - acnt == 1) bcnt = 4, acnt = 3;
            else assert(0);
        }
        printf("%s:%s\n", T[acnt], T[bcnt]);
    }
	return 0;
}