JZTXT

2022 Shanghai Collegiate Programming Contest B

发布时间 2023-04-15 16:37:40作者: Luckyblock

知识点：差分约束

Link：https://codeforces.com/gym/103931/problem/B。

被卡 SPFA 了呃呃。

一看出题人是这个人：
如何看待 SPFA 算法已死这种说法？ - fstqwq 的回答 - 知乎，那没事了。

简述

给定参数 \(n, q\)，表示有一个长度为 \(n\) 的合法括号序列，且有 \(q\) 组限制。每组限制均为 \(l_i, r_i, c_i\) 的形式，表示括号序列区间 \([l_i, r_i]\) 中，左括号数减去右括号数得到的差值为 \(c_i\)。要求判断是否存在一个满足所有限制的合法括号序列，若存在则构造任意一组合法的解。
\(2\le n\le 3000\)，\(0\le q\le \min\left( \binom{n+1}{2}, 5\times 10^5\right)\)，\(1\le l_i\le r_i\le n\)，\(-n\le c_i\le n\)。
2S，1024MB。

分析

给定限制为数量关系，考虑把括号序列合法的条件也抽象成数量关系。记一个左括号的权值为 1，右括号权值为 -1，记 \(s_i\) 表示序列的前缀 \([1, i]\) 的权值之和，则一个长度为 \(n\) 的括号序列合法，则等价于：

  • \(s_0 = s_n = 0\)。
  • \(\forall 1\le i\le n,\ s_i\ge 0\)。
  • \(\forall 1\le i\le n,\ |s_i - s_{i - 1}| = 1\)。

则本题中给定的限制 \((l_i, r_i, c_i)\) 可以表示为 \(s_r - s_{l - 1} = c_i\) 的形式。对于一组满足限制的 \(s\) 的取值，通过差分我们可以唯一确定这组值对应的括号序列。问题变为是否存在一组 \(s\) 的取值满足上述所有限制。

考虑差分约束，记 \(\operatorname{dis}_i\) 表示到达节点 \(i\) 的最短路长度，将上述所有限制转化为三角不等式形式：

  • \(s_0 = s_n = 0\)，考虑以节点 0 为起点，且向节点 \(n\) 连一条权值为 0 的边。
  • \(\forall 1\le i\le n,\ s_i\ge 0\)，即 \(s_i\ge s_0\)，从 \(i\) 向 0 连一条权值为 0 的边。
  • 对于给定限制 \(s_r - s_{l - 1} = c_i\)，即 \(c_i \le s_r - s_{l - 1} \le c_i\)，从 \(l-1\) 向 \(r\) 连一条权值为 \(c_i\) 的边，从 \(r\) 向 \(l-1\) 连一条权值为 \(-c_i\) 的边。
  • \(\forall 1\le i\le n,\ |s_i - s_{i - 1}| = 1\)，可以发现如果 \(q\) 个限制均满足偶数长度的限制区间的 \(c_i\) 为偶数，奇数长度的限制区间的 \(c_i\) 为奇数，则 \(s_{i} \not= s_{i-1}\) 一定成立。则可考虑先判断给定限制是否符合上述条件，再将该条件放松为 \(-1\le s_i - s_{i - 1}\le 1\)，从 \(i-1\) 向 \(i\) 连一条权值为 1 的边，从 \(i\) 向 \(i-1\) 连一条权值为 1 的边。

建图后运行差分约束算法，若存在负环则无解，否则根据 \(\operatorname{dis}\) 即可构造一组合法解。

此时如果直接使用 Bellman-Ford/SPFA 算法朴素地实现，则复杂度上界为 \(O(nq)\) 级别，在出题人的特别关照下，使用朴素的 SPFA 算法无法通过本题。

使用 SLF SPFA 可通过本题，且实际运行效率较高。std 则在此基础上采用了一种复杂度稳定的 \(O(n^2)\) 算法，详见下文：

代码

大力 SLF SPFA 爆炒：

//知识点：负环 
/*
By:Luckyblock
*/
// #pragma GCC optimize(2) 
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 3e3 + 10;
const int kM = 5e6 + 10;
//=============================================================
int n, q;
int e_num, head[kN], v[kM], w[kM], ne[kM];
int dis[kN], cnt[kN];
bool vis[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
void AddEdge(int u_, int v_, int w_) {
  v[++ e_num] = v_;
  w[e_num] = w_;
  ne[e_num] = head[u_];
  head[u_] = e_num;
}
void Init() {
  e_num = 0;
  memset(head, 0, sizeof (head));
}
bool SpfaBfs(int s_) {
  std::deque <int> q;
  memset(cnt, 0, sizeof (cnt));
  memset(vis, 0, sizeof (vis));
  memset(dis, 63, sizeof (dis));
  q.push_front(s_);
  dis[s_] = 0;
  vis[s_] = true;
  
  while (! q.empty()) {
    int u_ = q.front();
    q.pop_front();
    vis[u_] = false;
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i], w_ = w[i];
      if (dis[u_] + w_ < dis[v_]) {
        dis[v_] = dis[u_] + w_;
        cnt[v_] = cnt[u_] + 1;
        if (cnt[v_] > n) return true;
        if (! vis[v_]) {
          if (!q.empty() && dis[v_] > dis[q.front()]) q.push_back(v_);
          else q.push_front(v_);
          vis[v_] = true;
        }
      }
    }
  }
  return false;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read(), q = read();
  for (int i = 1; i <= q; ++ i) {
    int l_ = read(), r_ = read(), c_ = read();
    if ((r_ - l_ + 1) % 2 != (abs(c_) % 2)) {
      printf("?\n");
      return 0;
    }
    AddEdge(l_ - 1, r_, c_);
    AddEdge(r_, l_ - 1, -c_);
  }
  for (int i = 1; i <= n; ++ i) {
    AddEdge(i, 0, 0);
    AddEdge(i - 1, i, 1); //(i - 1) <= i + 1
    AddEdge(i, i - 1, 1); //i <= (i - 1) + 1
  }

  AddEdge(0, n, 0);
  if (SpfaBfs(0)) {
    printf("?\n");
    return 0;
  }
  printf("! ");
  for (int i = 1; i <= n; ++ i) {
    // printf("%d ", dis[i]);
    if (dis[i] - dis[i - 1] == 1) {
      printf("(");
    } else {
      printf(")");
    }
  }
  return 0;
}