牛客小白月赛105

QQ算竞小群：754883088

C-lz的蛋挞问题

lz买了一些奶贝和蛋挞，恰好可以放满一个两行$n$列的盒子。

假定在上下左右四个方向相邻的蛋挞之间有一条路径。定义蛋挞连通块为一组蛋挞，这组蛋挞中任意两个蛋挞都连通。

如下图，白色代表蛋挞，黑色方格代表奶贝。

现在lz只允许你吃掉一个蛋挞，并在其原来的位置上放一个奶贝，并要求蛋挞的连通块的数量发生变化。

例如上述情况，我们吃掉第一行的第一个蛋挞，则蛋挞的连通块的数量由3变为4。

现在lz想知道有多少个蛋挞被吃掉后可以改变蛋挞的联通块的数量

think

观察到有n*2个点 那么最多只有n*8条边

那么我们直接建图tarjan找割点

知识点

割点判断依据：

• 根节点：如果是DFS树的根节点，且至少有两个子节点，则它是割点。
• 非根节点：如果存在一个子节点v，使得low[v] >= dfn[u]，则u是割点。

code

#include <bits/stdc++.h>

using namespace std;
#define all(a) begin(a), end(a)
#define int long long
#define debug(x) cout << #x << " = " << x << "\n"

int n;
string row0, row1;
vector<vector<int>> adj;
vector<int> dfn, low;
int timer_;
vector<bool> is_ap;
void dfs(int u, int parentu, bool &flag) {
  dfn[u] = low[u] = ++timer_;
  int children = 0;
  for (auto &v : adj[u]) {
    if (v == parentu) continue;
    if (!dfn[v]) {
      children++;
      dfs(v, u, flag);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        if (parentu != -1) {
          is_ap[u] = true;
        } else {
          flag = (children > 1);
        }
      }
    } else {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

void solve() {
  cin >> n;
  cin >> row0 >> row1;
  adj.assign(2 * n, vector<int>());
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < n; j++) {
      if ((i == 0 && row0[j] != '.') || (i == 1 && row1[j] != '.')) continue;
      int u = i * n + j;
      // 上
      if (i == 1 && row0[j] == '.') {
        int v = (i - 1) * n + j;
        adj[u].push_back(v);
        adj[v].push_back(u);
      }
      // 左
      if (j > 0) {
        if (i == 0 && row0[j - 1] == '.') {
          int v = i * n + (j - 1);
          adj[u].push_back(v);
          adj[v].push_back(u);
        }
        if (i == 1 && row1[j - 1] == '.') {
          int v = i * n + (j - 1);
          adj[u].push_back(v);
          adj[v].push_back(u);
        }
      }
    }
  }
  dfn.assign(2 * n, 0);
  low.assign(2 * n, 0);
  is_ap.assign(2 * n, false);
  timer_ = 0;
  for (int u = 0; u < 2 * n; u++) {
    if (((u < n && row0[u % n] == '.') || (u >= n && row1[u % n] == '.')) &&
        !dfn[u]) {
      bool flag = false;
      dfs(u, -1, flag);
      if (flag) {
        is_ap[u] = true;
      }
    }
  }
  int res = 0;
  for (int u = 0; u < 2 * n; u++) {
    if (is_ap[u]) {
      res++;
    } else {
      if (u < n) {
        if (row0[u] == '.' and adj[u].size() == 0) {
          res++;
        }
      } else {
        if (row1[u % n] == '.' and adj[u].size() == 0) {
          res++;
        }
      }
    }
  }
  cout << res;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}

D-lz的染色问题

在$lz$的花园里有$n$朵花，每朵花都有自己的颜色$c_i$，在以后的$m$天里，他每天都会观察两朵花$i$和$j$，但他有强迫症，如果两朵花的颜色不同，他会生气。

你需要挑选最少数量的花，依次将他们重新染色，使得$lz$不会生气。输出最少的需要重新染色的花的数量。

think

维护联通块内最大颜色数

将同个并查集内的颜色全部替换为最大数量的颜色

code

#include <bits/stdc++.h>

using namespace std;
#define all(a) begin(a), end(a)
#define int long long
#define debug(x) cout << #x << " = " << x << "\n"
int n, m;

struct DSU {
    vector<int> parent, size;
    DSU(int N){
        parent.resize(N+1);
        size.resize(N+1,1);
        for(int i=0;i<=N;i++) parent[i]=i;
    }
    int find_set(int x){
        if(parent[x]!=x) parent[x]=find_set(parent[x]);
        return parent[x];
    }
    void union_set(int x, int y){
        int fx = find_set(x);
        int fy = find_set(y);
        if(fx == fy) return;
        if(size[fx] < size[fy]){
            parent[fx] = fy;
            size[fy] += size[fx];
        }
        else{
            parent[fy] = fx;
            size[fx] += size[fy];
        }
    }
};

void solve() {
    cin >> n >> m;
    vector<int> c(n+1);
    for(int i=1;i<=n;i++) cin >> c[i];
    DSU dsu(n);
    for(int i=0;i<m;i++){
        int u, v;
        cin >> u >> v;
        dsu.union_set(u, v);
    }
    unordered_map<int, vector<int>> groups;
    for(int i=1;i<=n;i++) {
        int f = dsu.find_set(i);
        groups[f].push_back(i);
    }
    int res =0;
    for(auto &[k, v] : groups){
        unordered_map<int, int> cnt;
        int mx =0;
        for(auto x : v){
            cnt[c[x]]++;
            if(cnt[c[x]] > mx) mx = cnt[c[x]];
        }
        res += v.size() - mx;
    }
    cout << res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

E-lz的括号问题

给定一个由$n$对括号组成的字符串，按每个$($出现的先后顺序给每对括号编号，比如$((()))(())$，编号后为$1233214554$。

每两个相同的数字代表的是原字符串中匹配的括号，每对匹配上的括号会直接删除（括号匹配的定义为：你可以从给定字符串中任意选择一个长度为$2$且为$()$的连续子序列删除，并将删除位置后面的所有下标减$2$）。

按顺序输出每对括号删除之前至多可以删除多少对括号，如果不能匹配上所有括号则输出$-1$。

THINK

如果一个括号在另一个内

那就建边跑拓扑排序

code

#include <bits/stdc++.h>

using namespace std;
#define all(a) begin(a), end(a)
#define int long long
#define debug(x) cout << #x << " = " << x << "\n"

int n;
string s;
vector<pair<int, int>> pairs;
int deletions_before_max = 0;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n;
  cin >> s;
  if (s.size() != 2 * n) {
    cout << "-1";
    return 0;
  }
  stack<pair<int, int>> st;
  pairs.assign(n + 1, {-1, -1});
  int current_num = 1;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '(') {
      if (current_num > n) {
        cout << "-1";
        return 0;
      }
      st.emplace(current_num, i);
      current_num++;
    } else if (s[i] == ')') {
      if (st.empty()) {
        cout << "-1";
        return 0;
      }
      pair<int, int> top = st.top();
      st.pop();
      int num = top.first;
      int start = top.second;
      pairs[num] = {start, i};
    } else {
      cout << "-1";
      return 0;
    }
  }
  if (!st.empty()) {
    cout << "-1";
    return 0;
  }
  vector<pair<int, int>> sorted_pairs;
  sorted_pairs.reserve(n);
  for (int i = 1; i <= n; i++) sorted_pairs.emplace_back(pairs[i]);
  sort(sorted_pairs.begin(), sorted_pairs.end(),
       [&](const pair<int, int> &a, const pair<int, int> &b) -> bool {
         if (a.first != b.first) return a.first < b.first;
         return a.second < b.second;
       });
  stack<pair<int, int>> anc_stack;  // pair of (start, end)
  vector<int> ancestors(n + 1, 0);  // 1-based
  vector<tuple<int, int, int>> sorted_with_num;
  sorted_with_num.reserve(n);
  for (int i = 1; i <= n; i++)
    sorted_with_num.emplace_back(pairs[i].first, pairs[i].second, i);
  sort(sorted_with_num.begin(), sorted_with_num.end(),
       [&](const tuple<int, int, int> &a,
           const tuple<int, int, int> &b) -> bool {
         if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
         return get<1>(a) < get<1>(b);
       });
  for (auto &[start, end, num] : sorted_with_num) {
    while (!anc_stack.empty() && anc_stack.top().second < start) {
      anc_stack.pop();
    }
    ancestors[num] = anc_stack.size();
    anc_stack.emplace(start, end);
  }
  vector<int> deletions_before(n + 1, 0);
  for (int i = 1; i <= n; i++) deletions_before[i] = n - 1 - ancestors[i];
  for (int i = 1; i <= n; i++) {
    cout << deletions_before[i] << " \n"[i == n];
  }
  return 0;
}

F-lz的序列问题

定义一段区间$[l,r]$的美丽值为$(a_{l} + a_{l} * a_{l +1} +a_{l} * a_{l +1} * a_{l + 2} +......+a_{l}*…*a_{r})$。

已知一段序列有 $n$ 个数，第 $i$ 个数为$a_{i}( 1 \leq a_{i} \leq 10^{9})$。你需要对序列进行 $q$ 次操作。

每次可进行以下两种操作中的一种：

1、将区间 $[l,r]$ 内每一个数都改为 $x$ 。

2、输出区间 $[l,r]$ 的美丽值。

THINK

线段树维护区间积和前缀积

code

#include <bits/stdc++.h>

using namespace std;
#define all(a) begin(a), end(a)
#define int long long
#define debug(x) cout << #x << " = " << x << "\n"

const int MOD = 1000000007;

int pow_mod_func(int x, int y) {
  int res = 1;
  x %= MOD;
  while (y > 0) {
    if (y & 1) {
      res = res * x % MOD;
    }
    x = x * x % MOD;
    y >>= 1;
  }
  return res;
}

int inverse(int x) { return pow_mod_func(x, MOD - 2); }

struct Node {
  int sum;
  int product;
  int length;
  bool to_set;
  int set_val;

  Node() : sum(0), product(1), length(1), to_set(false), set_val(0) {}
} tree_node;

vector<Node> tree;
int n, q;
vector<int> a;

void build(int idx, int l, int r) {
  tree[idx].length = r - l + 1;
  if (l == r) {
    tree[idx].product = a[l] % MOD;
    tree[idx].sum = a[l] % MOD;
    return;
  }
  int mid = (l + r) / 2;
  build(2 * idx, l, mid);
  build(2 * idx + 1, mid + 1, r);
  tree[idx].product = (tree[2 * idx].product * tree[2 * idx + 1].product) % MOD;
  tree[idx].sum = (tree[2 * idx].sum +
                   (tree[2 * idx].product * tree[2 * idx + 1].sum) % MOD) %
                  MOD;
}

void apply_set(int idx, int x) {
  tree[idx].to_set = true;
  tree[idx].set_val = x % MOD;

  tree[idx].product = pow_mod_func(x, tree[idx].length) % MOD;

  if (x == 1) {
    tree[idx].sum = tree[idx].length % MOD;
  } else {
    int numerator = (pow_mod_func(x, tree[idx].length) - 1 + MOD) % MOD;
    int denominator = (x - 1 + MOD) % MOD;
    tree[idx].sum = ((x * numerator) % MOD * inverse(denominator)) % MOD;
  }
}

void push_down(int idx, int l, int r) {
  if (tree[idx].to_set) {
    int mid = (l + r) / 2;
    apply_set(2 * idx, tree[idx].set_val);
    apply_set(2 * idx + 1, tree[idx].set_val);
    tree[idx].to_set = false;
  }
}

void update_set(int idx, int l, int r, int ql, int qr, int x) {
  if (ql > r || qr < l) {
    return;
  }
  if (ql <= l && r <= qr) {
    apply_set(idx, x);
    return;
  }
  push_down(idx, l, r);
  int mid = (l + r) / 2;
  update_set(2 * idx, l, mid, ql, qr, x);
  update_set(2 * idx + 1, mid + 1, r, ql, qr, x);

  tree[idx].product = (tree[2 * idx].product * tree[2 * idx + 1].product) % MOD;
  tree[idx].sum = (tree[2 * idx].sum +
                   (tree[2 * idx].product * tree[2 * idx + 1].sum) % MOD) %
                  MOD;
}

pair<int, int> query(int idx, int l, int r, int ql, int qr) {
  if (ql > r || qr < l) {
    return {0, 1};
  }
  if (ql <= l && r <= qr) {
    return {tree[idx].sum, tree[idx].product};
  }
  push_down(idx, l, r);
  int mid = (l + r) / 2;
  pair<int, int> left = query(2 * idx, l, mid, ql, qr);
  pair<int, int> right = query(2 * idx + 1, mid + 1, r, ql, qr);

  int combined_sum = (left.first + (left.second * right.first) % MOD) % MOD;
  int combined_product = (left.second * right.second) % MOD;
  return {combined_sum, combined_product};
}

void solve() {
  cin >> n >> q;
  a.resize(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];

  tree.resize(4 * n + 4);
  build(1, 1, n);

  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      update_set(1, 1, n, l, r, x);
    } else if (op == 2) {
      int l, r;
      cin >> l >> r;
      pair<int, int> res = query(1, 1, n, l, r);
      cout << res.first << "\n";
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}