1739.Bracket Query（2022上海CCPC-B题）题解

aHapBean · 2022-10-26 10:47:26 · 个人记录

题意:

给定条件： n, q, l, r, c 表示需要构造的括号序列长为n，有q个限制条件分别,每个条件： l, r , c.
存在合法解输出一组合法解，否则输出 "?"

前置知识:

差分约束
- 对于差分约束，可以参考 https://zhuanlan.zhihu.com/p/104764488 , 并完成洛谷差分约束模板题
权值并查集
- 并查集的一种，并查集比较常见，不会的同学可以自己查阅资料学习。

闲话:

Bracket Query 是9月份上海CCPC程设竞赛里的B题，赛场上属于一道银/金牌题
难点在想到差分约束并进行合理约束，同时需要控制加边数量使此题复杂度上界在O(n^2)而不是O(nm)
后者会被数据卡掉（不过好像部分O(nm)代码加上deque优化的SPFA可以通过）
出的非常合理，这部分别看了！快进到看题解 在AI专业~~数据结构作业题，~~（我来纠正一下，是算法设计与分析课程qwq）里面看到感觉挺惊讶的，不知道为什么出这个题，因为难度也不小（我是????，出题人就是CCPC出题人，你交ACM队教练），而且我看AI作业好像都不水，且跨度大，不知道助教具体知识讲解是否到位，如果不到位的话，出难度大，与知识跨度大的题可能有一丢丢不合理了，当然如果讲解到位，那还是挺合理的，~~可以让学生在痛苦中成长~~

题解：

tips:一定要知道差分约束相关知识，不然可能看不懂
简单来讲，对于一个合法的括号序列，记 '(' 为1，')' 为 -1，记一个前缀和pre[n],则该序列合法当且仅当 (i == 0) -> pre[i] == 0,(1 <= i < n) -> pre[i] >= 0,(i==n) -> pre[i] == 0
那么进一步我们就可以看这个题，首先约束括号序列合法参考上面一个叙述点，再加上给定的约束条件 pre[r] - pre[l - 1] == c 即可，这两个约束条件都加上跑差分约束就行
落实到具体的建图
- 对于l r c :
  
  pre[r] - pre[l -1] == c 可约束为 pre[r] - pre[l - 1] <= c and pre[l - 1] - pre[r] <= -c，相应连两条有向边即可
- 对于本身序列的合法性
  pre[n] - pre[0] == 0这个连两条有向边即可
  
  pre[i] - pre[0] >= 0连一条有向边
  
  此外为了约束 pre[0] == 0，我们直接从0开始跑差分约束，设置dis[0] = 0即可约束这个点
  - 不过，想要约束相邻项的合法性，我们需要pre[i + 1] - pre[i] == 1 或 -1，仔细思考不难发现，由于只能约束>= 和 <= 关系，所以此处变为 -1 <= pre[i + 1] - pre[i] <= 1 && pre[i + 1] - pre[i] != 0，这个关系约束不了
  - 解决方案 ：如果读者已经思考过约束不了的原因，那么容易知道，如果我们让前缀和记录的信息仅记录 '(' 的信息，那么就可以将约束pre[i + 1] - pre[i] == 1 或 -1 变为 pre[i + 1] - pre[i] == 1 或 0这样的不等式就变成了 0 <= pre[i + 1] - pre[i] <= 1，同时，不记录 ')'的-1也不会对最终结果的输出带来任何影响
- 这样的话，我们之前的约束也应该稍微改变一下
  
  pre[r] - pre[l - 1] == c + (len[l->r]（即 r - l + 1） - c) / 2
  
  pre[n] - pre[0] == n / 2(即必有n/2个前括号)
  
  pre[i] - pre[0] >= (i + 1) / 2
  
  pre[i + 1] - pre[i] >= 0 && pre[i + 1] - pre[i] <= 1
  - 根据上述四个式子相应建边就行
但是，SPFA()上界是O(nm)的，所以这么跑数量级是3000 * 5e5 的上界可能会被卡掉，
解决方法：由线性代数知识，pre[i]有 n + 1个之间至多有n + 1个约束，其余约束要么没用要么矛盾，我们用权值并查集处理这一部分，排除重复的约束，遇到与之前矛盾的约束直接无解，这样最多加O(n)条边，复杂度是O(n^2)的，能够通过此题
至于权值并查集的具体做法，~~我好懒，就不写了~~可以看我的代码或者自己实现，逻辑上非常好想到
跑差分约束后，得到的dis数组即为一组可行解，pre[i] - pre[i - 1] == 0则是右括号，== 1则是左括号，如果有负环那就无解。中间有一些特判的小细节，可以自己考虑，也可以看我的代码

代码部分

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e6 + 10;
int fst[maxn],nxt[maxn << 1],cnt,n,m,a,b,c;
ll dis[maxn];
struct edge{
    int u,v,w;
}side[maxn << 1];
void add(int u,int v,int w) {
    side[++cnt] = {u,v,w};
    nxt[cnt] = fst[u];
    fst[u] = cnt;
}
int q[maxn << 4],head = 0,tail = -1,in[maxn],cir[maxn];
bool SPFA() {
    memset(dis,0x3f,sizeof(dis));
    head = 0,tail = -1;
    q[++tail] = 0;dis[0] = 0;in[0] = 1;
    while(head <= tail) {
        int u = q[head++];in[u] = 0;
        for(int i = fst[u]; i; i = nxt[i]) {
            int v = side[i].v,w = side[i].w;
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cir[v] = cir[u] + 1;
                if(!in[v]) {
                    //cir[v] += 1;
                    q[++tail] = v;
                    in[v] = 1;
                }
                if(cir[v] > n) return false;
            } 
        }
    }
    return true;
}
int f[maxn],val[maxn];  //val dsu !权值并查集
int find(int x) {
    if(x == f[x]) return f[x];
    int fx = find(f[x]);
    val[x] = val[x] + val[f[x]];
    return f[x] = fx;
}
inline void ret() {
    cout << "?";
    exit(0);
}
int main() {
    cin >> n >> m;
    for(int i = 0; i <= n; ++i)
        f[i] = i;
    if(n & 1) ret();
    while(m--) {//并查集去重
        scanf("%d%d%d",&a,&b,&c);
        if(c > b - a + 1 || (b - a + 1 - c) % 2 != 0)
            ret();
        int l = (b - a + 1 - c) / 2 + c;
        int x = find(a - 1),y = find(b);
        if(x == y) {
            if(val[b] - val[a - 1] != l) ret();
        } else {
            f[x] = y;
            val[x] = val[b] - val[a - 1] - l;
            //添加约束
            add(a - 1,b,l);
            add(b,a - 1,-l);
        }
    }
    //添加约束
    add(0,n,n / 2);
    add(n,0,-(n / 2));
    for(int i = 0; i <= n - 1; ++i) {
        add(i,i + 1,1);
        add(i + 1,i,0);
    }
    for(int i = 1; i <= n; ++i)
        add(i,0,- (i + 1) / 2);
    if(!SPFA()) ret();
    else {
        cout << "! ";
        for(int i = 1; i <= n; ++i)
            if(dis[i] - dis[i - 1] == 1) printf("(");
            else printf(")");
    }
    return 0;
}

写在最后

由于markdown用的不太熟练，同时洛谷markdown有些效果弄不出来，所以排版比较乱，凑合着看
代码我有空的话可能加点注释，不过能懂题解里面讲的东西，代码也应该可以自己实现了
这个题建议自己写写，别复制粘贴（个人建议）
~~我是22级的一名数学专业的同学，不要试图寻找我！qoq~~
这也是我第一篇题解博客。也是因为看到这个题比较兴奋（CCPC比赛时我没学差分约束，这题是队友大哥过的），所以写了这么一篇博客，码字 + 排版大概40分钟，如果对你有帮助那是最好，~~没有帮助的话我也不会伤心~~，吼吼，不过我以后估计也不太会写题解博客了，因为我今天一写发现会比想象的多好多字，~~还不如自己刷刷题，~~=最后，感觉有帮助的话就点点小赞，please

1739.Bracket Query（2022上海CCPC-B题） 题解

1739.Bracket Query（2022上海CCPC-B题）题解