A

jls出的题😍😍😍。

给一个环形 $01$ 串，多次询问。可以选择一个 $1$ 删除它和它左右两边的数。如果可以完全删完则是 good 的。每次询问字串 $s[l, r]$ 是不是 good。

考虑 $1$ 不相邻的情况，明显可以删完。

如果有 $x$ 个 $1$ 相邻，不管用其中哪个 $1$ 进行删除操作，会同时带走旁边的某些 $1$。所以实际上有用的 $1$ 经过计算是 $\lceil \frac{x}{2} \rceil$ 个。

不想再想了，我选择线段树暴力搞。

需要注意每个区间的连续 $1$ 的分布情况，左边有多少个，右边有多少个，中间有多少个（由于是环注意不能重复计算），可以用最大子区间和的方法维护。

答案是区间长度 / 3 - 有必要删除的 $1$ 的个数（上取整），造数据发现会变成负的，估计是选了左右两个端点上的 $1$。

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "/Users/aaron/Documents/template/debug.hpp"
#else
#define debug(...) 42
#endif

class segtree {
 public:
  struct node {
    int l1, r1, cs;
    bool all;
    void apply(int l, int r, int v) {
      if (v == 1) {
        l1 = 1;
        r1 = 1;
        cs = 0;
        all = true;
      } else {
        l1 = r1 = cs = 0;
        all = false;
      }
    }
  };

  node unite(const node &a, const node &b) const {
    node res;
    if (a.all) {
      if (b.all) {
        res.all = true;
        res.l1 = a.l1 + b.l1;
        res.r1 = a.r1 + b.r1;
        res.cs = 0;
      } else {
        res.all = false;
        res.l1 = a.l1 + b.l1;
        res.r1 = b.r1;
        res.cs = b.cs;
      }
    } else {
      if (b.all) {
        res.all = false;
        res.l1 = a.l1;
        res.r1 = a.r1 + b.r1;
        res.cs = a.cs;
      } else {
        res.all = false;
        res.l1 = a.l1;
        res.cs = a.cs + b.cs + (a.r1 + b.l1 + 1) / 2;
        res.r1 = b.r1;
      }
    }
    return res;
  }

  inline void push(int x, int l, int r) {
    // int y = (l + r) >> 1;
    // int z = x + ((y - l + 1) << 1);
    // if (tree[x].add != 0) {
    //   tree[x + 1].apply(l, y, tree[x].add);
    //   tree[z].apply(y + 1, r, tree[x].add);
    //   tree[x].add = 0;
    // }
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }

  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }

  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }

  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }

  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    a[i] = s[i] - '0';
  }
  segtree st(a);
  while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    auto nd = st.get(l, r);
    int x;
    if (nd.l1 == r - l + 1) {
      x = (nd.l1 + 1) / 2;
    } else {
      x = nd.cs + (nd.l1 + nd.r1 + 1) / 2;
    }
    long long ans = ((r - l + 1) - x * 3 + 2) / 3;
    cout << max(0ll, ans) << '\n';
  }
  return 0;
}

C

两个操作都相当于每次去掉一个点，但是只有叶子需要 delete 才能去掉，其他所有点都可以通过 shrink 去掉。

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "/Users/aaron/Documents/template/debug.hpp"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    if (n == 1) {
      cout << "1\n";
      continue;
    }
    vector<int> deg(n);
    for (int i = 1; i < n; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      deg[u]++;
      deg[v]++;
    }
    cout << count(deg.begin(), deg.end(), 1) << '\n';
  }
  return 0;
}

D

$T$ 组询问，每次给一个区间 $[l, r]$，求区间中有没有某个数 $x$ 满足 $ctz(x) = popcount(x)$。

考虑构造一个答案：

看 $l$ 的二进制表示，记 $末尾0, 全部1$ 的个数分别为 $cnt_0, cnt_1$，如果 $cnt_1 > cnt_0$，将 $l$ 的最后一位 $1$ 通过进位消掉，重复进行直到 $cnt_0 \ge cnt_1$ 就可以得到一个 $lower_bound(l)$ 的候选答案。

此时末尾 $0$ 的数量不比 $1$ 少，用类似隔板的方法，添加一个 $1$ 分割末尾 $0$，使得加完之后 $cnt_0 = cnt_1$ 。添加了第一个 $1$ 之后末尾 $0$ 就不能再减少了，只能继续往高位添加。一定能找到一个合法解，但不一定在区间内。找规律发现需要添加的是 1 << (__builtin_popcount(l) + 1)

最后看一下在不在 $[l, r]$ 之间即可。

不知道为啥要打表。。我感觉打表还容易 T 啊。

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "/Users/aaron/Documents/template/debug.hpp"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int l, r;
    cin >> l >> r;
    int cnt1 = __builtin_popcount(l), cnt0 = __builtin_ctz(l);
    while (cnt1 > cnt0) {
      l += (l & -l);
      cnt1 = __builtin_popcount(l);
      cnt0 = __builtin_ctz(l);
    }
    while (cnt0 > cnt1) {
      l += (1 << (1 + __builtin_popcount(l)));
      cnt1 = __builtin_popcount(l);
      cnt0 = __builtin_ctz(l); 
    }
    assert(cnt0 == cnt1);
    cout << (l <= r ? l : -1) << '\n';
  }
  return 0;
}

H

有一套语法，问你 library 搞了多少次。

模拟。碰到 repeat 就递归。

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "/Users/aaron/Documents/template/debug.hpp"
#else
#define debug(...) 42
#endif
constexpr int P = 20220911;
// assume -P <= x < 2P
int norm(int x) {
  if (x < 0) {
    x += P;
  }
  if (x >= P) {
    x -= P;
  }
  return x;
}
template<class T>
T power(T a, int b) {
  T res = 1;
  for (; b; b /= 2, a *= a) {
    if (b % 2) {
      res *= a;
    }
  }
  return res;
}
struct Z {
  int x;
  Z(int x = 0) : x(norm(x)) {}
  int val() const {
    return x;
  }
  Z operator-() const {
    return Z(norm(P - x));
  }
  Z inv() const {
    assert(x != 0);
    return power(*this, P - 2);
  }
  Z &operator*=(const Z &rhs) {
    x = (long long)x * rhs.x % P;
    return *this;
  }
  Z &operator+=(const Z &rhs) {
    x = norm(x + rhs.x);
    return *this;
  }
  Z &operator-=(const Z &rhs) {
    x = norm(x - rhs.x);
    return *this;
  }
  Z &operator/=(const Z &rhs) {
    return *this *= rhs.inv();
  }
  friend Z operator*(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res *= rhs;
    return res;
  }
  friend Z operator+(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res += rhs;
    return res;
  }
  friend Z operator-(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res -= rhs;
    return res;
  }
  friend Z operator/(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res /= rhs;
    return res;
  }
  friend istream &operator>>(istream &is, Z &a) {
    long long v;
    is >> v;
    a = Z(v);
    return is;
  }
  friend ostream &operator<<(ostream &os, const Z &a) {
    return os << a.val();
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  Z ans = 0;
  function<int()> dfs = [&]() {
    Z cnt = 0;
    string b;
    while (cin >> b && b != "fin") {
      if (b[0] == 'l') {
        cnt += 1;
      }
      if (b[0] == 'r') {
        cnt += dfs();
      }
      if (b[0] == 'f') {
        assert(b == "for");
        int x;
        cin >> x;
        cnt *= x;
        return cnt.val();
      }
    }
    return 0;
  };
  while (cin >> s, s != "fin") {
    if (s[0] == 'l') {
      ans += 1;
    }
    if (s[0] == 'r') {
      ans += dfs();
    }
  }
  cout << ans << '\n';
  return 0;
}

不会字符串。