Problem G. Inscryption

其实就是括号序列。。首先考虑是否有解，那么肯定待定位置都填 '('。
那么接下来就是保证合法的情况下，尽可能多的将待定位置填成 ')'。。那么这个肯定尽可能选一段后缀去填更优。
上面的观察已经足够写一个基于二分答案的解了，不过我们可以做的更好。。。

对于每个待定序列，我们都贪心的首先将其设置成 ‘)’，再之后遇到不合法的情况时，再进行调整，
而这只需要记录我们前面有多少待定的位置被填成 ')' 即可。

const int N = int(1e6) + 9;
int a[N];
int n;

bool ok() {
    int p = 1, q = 1, o = 0; REP(i, n) {
        if (a[i] == 1) {
            ++p; ++q;
        } else if (a[i] == -1) {
            if (q > 1) {
                --q;
            } else if (o) {
                --o; ++p; ++q;
            } else {
                return 0;
            }
        } else {
            if (q > 1) {
                --q; ++o;
            } else {
                ++p; ++q;
            }
        }
    }

    int d = __gcd(p, q); p /= d; q /= d;
    printf("%d %d\n", p, q);
    return 1;
}


int main(){

#ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
#endif

    Rush {
        RD(n); REP(i, n) RD(a[i]);
        if (!ok()) puts("-1");
    }
}

Posted by xiaodao
Category: 日常