T434199 「LAOI-4」Mex Tower (Hard ver.)

/*
	和上题一样只不过，是换成了检验答案，还是找规律，
	自己看看吧awa
*/
// O(n)
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <ctime>

using namespace std;

int n, m;
string s;

char get(char a, char b)
{
    int sum = 0;
    if (a == '0' || b == '0') sum ++ ;
    if (sum == 1 && (a == '1' || b == '1')) sum ++ ;
    return sum + '0';
}

string make(string s1)
{
    string s2;
    int len = s1.size() - 1;
    for (int i = 0; i < len; i ++ )
    {
        s2 += get(s1[i], s1[i + 1]);
    }
    return s2;
}

int main()
{
	freopen("out.txt", "r", stdin);
	freopen("ans.txt", "w", stdout);
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        s.clear();
        for (int i = 0; i < n; i ++ ) 
        {
            char c[2];
            scanf("%s", c);
            if (c[0] > '1') c[0] = '2';
            s += c[0];
            
        }
        n -= 1;
        s = make(s);
        
        if (n & 1)
        {
        	n /= 2;
        	s = s.substr(n, 1);
        }
        else 
        {
        	n /= 2;
        	n -- ;
        	s = s.substr(2, 2);
        	make(s);
        }
        
        if (s.size() == 1 && s.compare("2") == 0) cout << "Yes";
        else cout << "No";
        puts("");
    }
    cout << clock();
}


/*
O(n^2)
#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
string s;

char get(char a, char b)
{
    int sum = 0;
    if (a == '0' || b == '0') sum ++ ;
    if (sum == 1 && (a == '1' || b == '1')) sum ++ ;
    return sum + '0';
}

string make(string s1)
{
    string s2;
    int len = s1.size() - 1;
    for (int i = 0; i < len; i ++ )
    {
        s2 += get(s1[i], s1[i + 1]);
    }
    return s2;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        s.clear();
        for (int i = 0; i < n; i ++ ) 
        {
            char c;
            cin >> c;
            s += c;
            // cout << c;
        }
        // cout << s << endl;
        while ( -- n) s = make(s);
        if (s[0] == '2') cout << "Yes";
        else cout << "No";
        puts("");
    }
}
*/