专栏文章

题解：P8407 [COCI 2021/2022 #6] Superpozicija

CClaire0918
P8407题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjuy7f
此快照首次捕获于
2025/12/02 03:36
3 个月前
此快照最后确认于
2025/12/02 03:36
3 个月前
查看原文
我们知道一个括号序列合法，当且仅当将 (\texttt{(} 当作 11，)\texttt{)} 当作 −1-1 时序列每个位置前缀和非负，且最后和为 00。
如果 zai=zbi=(z_{a_i} = z_{b_i} = \texttt{(}，那么选哪个对于最后和的影响是相同的，而选较小的一个可以使更多的前缀和增加 11，显然不劣，于是选择较小的一个。zai=zbi=)z_{a_i} = z_{b_i} = \texttt{)} 的情况是对称的。
如果 zai=(,zbi=)z_{a_i} = \texttt{(}, z_{b_i} = \texttt{)}，选择 aia_i 时对 [ai,2n][a_i, 2n] 的贡献时 11，对 [bi,2n][b_i, 2n] 的贡献是 00；选择 bib_i 时对 [ai,2n][a_i, 2n] 的贡献是 00，对 [bi,2n][b_i, 2n] 的贡献是 −1-1。我们想优先使最后的和尽量小，于是我们选择 bib_i，并且保留一种操作 (ai,bi)(a_i, b_i)，可以将 [ai,2n][a_i, 2n] 和 [bi,2n][b_i, 2n] 的贡献加上 11。zai=),zbi=(z_{a_i} = \texttt{)}, z_{b_i} = \texttt{(} 的情况是对称的。
我们现在确定了每个位置的贡献，枚举 ii 顺着往后扫。如果当前的前缀和 si<0s_i < 0，那么我们要选择一对 (ak,bk)(a_k, b_k) 进行操作。不妨设 ak≤bka_k \leq b_k，显然有 ak≤ia_k \leq i，而我们选择哪一对操作对于最后和的影响都是 22，于是我们选择 bkb_k 最小的一对显然不劣。将 (ak,bk)(a_k, b_k) 挂在 aka_k 上，维护一个堆表示最小的 bkb_k 即可，区间加 11 直接打标记 O(1)\mathcal{O}(1) 处理，时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。
Code：
CPP
#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 1e5 + 10;

int t, n;
char s[maxn << 1];
int a[maxn << 1], tag[maxn << 1], res[maxn];
vector<pair<int, int> > ad[maxn << 1];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > q;

int main(){
    scanf("%d", &t);
    while (t--){
        scanf("%d %s", &n, s + 1), res[0] = 0;
        for (int i = 1; i <= n << 1; a[i] = tag[i] = 0, ad[i].clear(), i++);
        for (;!q.empty(); q.pop());
        for (int i = 1; i <= n; i++){
            int x, y;
            scanf("%d %d", &x, &y);
            if (s[x] == '(' && s[y] == '('){
                res[i] = x > y, a[min(x, y)] = 1;
            }else if (s[x] == ')' && s[y] == ')'){
                res[i] = x < y, a[max(x, y)] = -1;
            }else{
                const bool tmp = s[x] == '(';
                x > y && (swap(x, y), 1538), a[s[x] == '(' ? y : x] = -1, res[i] = tmp, ad[x].push_back(make_pair(y, tmp ? i : -i));
            }
        }
        for (int i = 1; i <= n << 1; i++){
            a[i] += a[i - 1] + tag[i];
            for (auto x: ad[i]){
                q.push(x);
            }
            if (a[i] < 0){
                if (q.empty()){
                    res[0] = 1;
                    break;
                }
                a[i]++, (q.top().first > i ? tag[q.top().first] : a[i])++, res[abs(q.top().second)] = q.top().second < 0, q.pop();
            }
        }
        if (res[0] || a[n << 1]){
            printf("-1\n");
        }else{
            for (int i = 1; i <= n; i++){
                printf("%d ", res[i]);
            }
            putchar('\n');
        }
    }

return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...