头像

能鸽善武




离线:5天前


最近来访(133)
用户头像
陌丨落
用户头像
lihua777
用户头像
ᴍɪssɪᴏɴ
用户头像
33号花卷
用户头像
月色
用户头像
太雪菜
用户头像
锦木千束
用户头像
l_y_f
用户头像
Mike_88
用户头像
imnoob
用户头像
Lin_LL
用户头像
Fatin
用户头像
Q_83
用户头像
tratser
用户头像
Finn2009
用户头像
狼狐
用户头像
stan_ym
用户头像
hover_
用户头像
no_hard
用户头像
小鸡炖土豆


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;
}

不会字符串。




题目描述

有 $m$ 个评委,每个评委有两种喜欢的菜式,有 $n$ 种材料,可以做满式菜或者汉式菜,要你决定 $n$ 个材料每个是做汉式还是满式,使得 $m$ 个喜好都至少满足一个。

拆点,将每种材料 $i$ 拆成两个 $x, y$,分别表示满式和汉式,每个评委的限制条件为 $x \lor y$,转化为 $(\lnot x \rightarrow y) \land (\lnot y \rightarrow x)$,建图,跑 2-SAT。

#include <bits/stdc++.h>

using namespace std;

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

template <typename T>
class graph {
 public:
  struct edge {
    int from;
    int to;
    T cost;
  };

  vector<edge> edges;
  vector<vector<int>> g;
  int n;

  graph(int _n) : n(_n) {
    g.resize(n);
  }

  virtual int add(int from, int to, T cost) = 0;
};

template <typename T>
class digraph : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;

  digraph(int _n) : graph<T>(_n) {}

  int add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int)edges.size();
    g[from].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }
  digraph<T> reverse() const {
    digraph<T> rev(n);
    for (auto &e : edges) {
      rev.add(e.to, e.from, e.cost);
    }
    return rev;
  }
};

template <typename T>
vector<int> find_scc(const digraph<T> &g, int &cnt) {
  digraph<T> g_rev = g.reverse();
  vector<int> order;
  vector<bool> was(g.n, false);
  function<void(int)> dfs1 = [&](int v) {
    was[v] = true;
    for (int id : g.g[v]) {
      auto &e = g.edges[id];
      int to = e.to;
      if (!was[to]) {
        dfs1(to);
      }
    }
    order.push_back(v);
  };
  for (int i = 0; i < g.n; i++) {
    if (!was[i]) {
      dfs1(i);
    }
  }
  vector<int> c(g.n, -1);
  function<void(int)> dfs2 = [&](int v) {
    for (int id : g_rev.g[v]) {
      auto &e = g_rev.edges[id];
      int to = e.to;
      if (c[to] == -1) {
        c[to] = c[v];
        dfs2(to);
      }
    }
  };
  cnt = 0;
  // Kosaraju 
  for (int id = g.n - 1; id >= 0; id--) {
    int i = order[id];
    if (c[i] != -1) {
      continue;
    }
    c[i] = cnt++;
    dfs2(i);
  }
  return c;
  // c[i] <= c[j] for every edge i -> j
}

class twosat {
 public:
  digraph<int> g;
  int n;
  twosat(int _n) : g(digraph<int>(2 * _n)), n(_n) {}

  inline void add(int x, int value_x) {
    // (v[x] == value_x)
    assert(0 <= x && x < n);
    assert(0 <= value_x && value_x <= 1);
    g.add(2 * x + (value_x ^ 1), 2 * x + value_x);
  }

  inline void add(int x, int value_x, int y, int value_y) {
    // (v[x] == value_x || v[y] == value_y)
    assert(0 <= x && x < n && 0 <= y && y < n);
    assert(0 <= value_x && value_x <= 1 && 0 <= value_y && value_y <= 1);
    g.add(2 * x + (value_x ^ 1), 2 * y + value_y);
    g.add(2 * y + (value_y ^ 1), 2 * x + value_x);
  }

  inline vector<int> solve() {
    int cnt;
    vector<int> c = find_scc(g, cnt);
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
      if (c[2 * i] == c[2 * i + 1]) {
        return vector<int>();
      }
      res[i] = (c[2 * i] < c[2 * i + 1]);
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    twosat ts(n);
    for (int i = 0; i < m; i++) {
      char cx, cy;
      int x, y;
      cin >> cx >> x >> cy >> y;
      x--;
      y--;
      ts.add(x, cx == 'm', y, cy == 'm');
    }
    auto res = ts.solve();
    if (res.empty()) {
      cout << "BAD\n";
    } else {
      cout << "GOOD\n";
    }
  }
  return 0;
}


活动打卡代码 AcWing 255. 第K小数

#include <bits/stdc++.h>

using namespace std;

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

class psegtree {
 public:
  const int space = 5;

  struct node {
    int l, r;
    // extra variables...
    int cnt;
  };

  inline void apply_change(node &nd) {
    nd.cnt += 1;
  }

  inline void pull(node &nd) {
    nd.cnt = tree[nd.l].cnt + tree[nd.r].cnt;
  }

  int n, lb, rb;
  int idx;
  vector<node> tree;
  vector<int> ptr;

  int build(int l, int r) {
    int v = idx++;
    if (l == r) {
      return l;
    }
    int y = (l + r) >> 1;
    tree[v].l = build(l, y);
    tree[v].r = build(y + 1, r);
    return v;
  }

  template<typename T>
  T update(int old, int l, int r, T val) {
    int v = idx++;
    tree[v] = tree[old];
    if (l == r) {
      apply_change(tree[v]);
      return v;
    }
    int y = (l + r) >> 1;
    if (val <= y) {
      tree[v].l = update(tree[old].l, l, y, val);
    } else {
      tree[v].r = update(tree[old].r, y + 1, r, val);
    }
    pull(tree[v]);
    return v;
  }

  int find_kth(int prst, int hist, int l, int r, int k) {
    if (l == r) {
      return l;
    }
    int left = tree[tree[prst].l].cnt - tree[tree[hist].l].cnt;
    int y = (l + r ) >> 1;
    if (k <= left) {
      return find_kth(tree[prst].l, tree[hist].l, l, y, k);
    } else {
      return find_kth(tree[prst].r, tree[hist].r , y + 1, r, k - left);
    }
  }

  inline void make_root() {
    assert(idx == 0);
    int root = build(lb, rb);
    ptr.push_back(root);
  }

  template<typename T>
  psegtree(const vector<T>& v, int lb, int rb) : lb(lb), rb(rb) {
    n = (int) v.size();
    idx = 0;
    tree.resize(n << space);
    make_root();
  }

  psegtree(int _n) : n(_n) {
    idx = 0;
    tree.resize(n << space);
    make_root();
  }

  template<typename T>
  int update(int l, int r, T val) {
    int nd = update(ptr.back(), l, r, val);
    ptr.push_back(nd);
    return nd;
  }

  int find_kth(int l, int r, int k) {
    assert(l > 0 && r < (int) ptr.size());
    return find_kth(ptr[r], ptr[l - 1], lb, rb, k);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n), all;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    all.push_back(a[i]);
  }  
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());

  auto find = [&](int x) {
    return lower_bound(all.begin(), all.end(), x) - all.begin();
  };
  psegtree st(a, 0, (int) all.size() - 1);
  for (int x : a) {
    st.update(0, (int) all.size() - 1, find(x));
  }
  while (m--) {
    int l, r, k;
    cin >> l >> r >> k;
    int pos = st.find_kth(l, r, k);
    cout << all[pos] << '\n';
  }
  return 0;
}


活动打卡代码 AcWing 1277. 维护序列

#include <bits/stdc++.h>

using namespace std;

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

int P = 998244353;
// 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();
  }
};

class segtree {
 public:
  struct node {
    Z add = 0;
    Z mul = 1;
    Z sum = 0;
    void apply(int l, int r, Z v, Z m = 1) {
      sum = sum * m + (r - l + 1) * v;
      mul *= m;
      add = add * m + v;
    }
  };

  node unite(const node &a, const node &b) const {
    node res;
    res.sum = a.sum + b.sum;
    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.val() != 0 || tree[x].mul.val() != 1) {
      tree[x + 1].apply(l, y, tree[x].add, tree[x].mul);
      tree[z].apply(y + 1, r, tree[x].add, tree[x].mul);
      tree[x].add = 0;
      tree[x].mul = 1;
    }
  }

  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;
  cin >> n >> P;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  segtree st(a);
  int m;
  cin >> m;
  while (m--) {
    int opt, l, r, c;
    cin >> opt >> l >> r;
    l--;
    r--;
    if (opt == 3) {
      cout << st.get(l, r).sum << '\n';
    } else {
      cin >> c;
      if (opt == 1) {
        st.modify(l, r, 0, c);
      } else {
        st.modify(l, r, c, 1);
      }
    }
  }
  return 0;
}



#include <bits/stdc++.h>

using namespace std;

class segtree {
 public:
  struct node {
    long long d = 0;
    long long sum = 0;
    void apply(int l, int r, long long v) {
      sum += v;
      d = sum;
    }
  };
  node unite(const node &a, const node &b) const {
    node res;
    res.sum = a.sum + b.sum;
    res.d = __gcd(a.d, b.d);
    return res;
  }
  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    // push from x into (x + 1) and z

    /*
        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, m;
  cin >> n >> m;
  vector<long long> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  adjacent_difference(a.begin(), a.end(), b.begin());
  segtree st(b);
  while (m--) {
    char opt;
    int l, r;
    long long x;
    cin >> opt >> l >> r;
    l--;
    r--;
    if (opt == 'C') {
      cin >> x;
      if (r + 1 < n) {
        st.modify(r + 1, r + 1, -x);
      }
      st.modify(l, l, +x);
    } else {
      long long x = st.get(0, l).sum;
      long long y;
      if (l + 1 <= r) {
        y = st.get(l + 1, r).d;
      } else {
        y = 0;
      }
      cout << abs(__gcd(x, y)) << '\n';
    }
  }
  return 0;
}



能鸽善武
1个月前

1001 - Winner Prediction

有 $n$ 个人打比赛,其中 $m_1$ 场已经比完且知道输赢,还剩 $m_2$ 场没有比,问你 $1$ 号选手能不能成为冠军。成为冠军的条件是胜场最多,如果胜场并列每个人都是冠军。

显然第一件事情是所有有关 $1$ 的比赛让 $1$ 号赢。对于一个选手 $i$,记胜场为 $win_i$,如果有 $win_i > win_1$ 那么输出 $NO$。否则他接下来还能赢 $win_1 - win_i$ 场。

考虑建网络流:

  • 每一场未进行的比赛用一个新的点表示,源点向其连边
  • 第 $i$ 场比赛向他的两个参赛选手连容量为 $1$ 的边
  • 对于第 $i$ 个参赛选手向汇点连容量为 $win_1 - win_i$ 的边

跑最大流,若最大流等于 $m_2场比赛-有关1的比赛场数$ 即为 $YES$,否则为 $NO$。

观察到这个网络的结构:源点-> 比赛节点 -> 选手节点 -> 汇点。实际上是一个二分图,dinic的复杂度是 $O(m\sqrt n)$。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class flow_graph {
 public:
  static constexpr T eps = (T) 1e-9;

  struct edge {
    int from;
    int to;
    T c;
    T f;
  };

  vector<vector<int>> g;
  vector<edge> edges;
  int n;
  int st;
  int fin;
  T flow;

  flow_graph(int _n, int _st, int _fin) : n(_n), st(_st), fin(_fin) {
    assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);
    g.resize(n);
    flow = 0;
  }

  void clear_flow() {
    for (const edge &e : edges) {
      e.f = 0;
    }
    flow = 0;
  }

  int add(int from, int to, T forward_cap, T backward_cap) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int) edges.size();
    g[from].push_back(id);
    edges.push_back({from, to, forward_cap, 0});
    g[to].push_back(id + 1);
    edges.push_back({to, from, backward_cap, 0});
    return id;
  }
};

template <typename T>
class dinic {
public:
  flow_graph<T> &g;

  vector<int> ptr;
  vector<int> d;
  vector<int> q;

  dinic(flow_graph<T> &_g) : g(_g) {
    ptr.resize(g.n);
    d.resize(g.n);
    q.resize(g.n);
  }

  bool expath() {
    fill(d.begin(), d.end(), -1);
    q[0] = g.fin;
    d[g.fin] = 0;
    int beg = 0, end = 1;
    while (beg < end) {
      int i = q[beg++];
      for (int id : g.g[i]) {
        const auto &e = g.edges[id];
        const auto &back = g.edges[id ^ 1];
        if (back.c - back.f > g.eps && d[e.to] == -1) {
          d[e.to] = d[i] + 1;
          if (e.to == g.st) {
            return true;
          }
          q[end++] = e.to;
        }
      }
    }
    return false;
  }

  T dfs(int v, T w) {
    if (v == g.fin) {
      return w;
    }
    int &j = ptr[v];
    while (j >= 0) {
      int id = g.g[v][j];
      const auto &e = g.edges[id];
      if (e.c - e.f > g.eps && d[e.to] == d[v] - 1) {
        T t = dfs(e.to, min(e.c - e.f, w));
        if (t > g.eps) {
          g.edges[id].f += t;
          g.edges[id ^ 1].f -= t;
          return t;
        }
      }
      j--;
    }
    return 0;
  }

  T max_flow() {
    while (expath()) {
      for (int i = 0; i < g.n; i++) {
        ptr[i] = (int) g.g[i].size() - 1;
      }
      T big_add = 0;
      while (true) {
        T add = dfs(g.st, numeric_limits<T>::max());
        if (add <= g.eps) {
          break;
        }
        big_add += add;
      }
      if (big_add <= g.eps) {
        break;
      }
      g.flow += big_add;
    }
    return g.flow;
  }

  vector<bool> min_cut() {
    max_flow();
    vector<bool> ret(g.n);
    for (int i = 0; i < g.n; i++) {
      ret[i] = (d[i] != -1);
    }
    return ret;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<int> win(n);
    for (int i = 0; i < m1; i++) {
      int u, v, z;
      cin >> u >> v >> z;
      u--; v--;
      win[z ? u : v]++;
    }
    int st = n + m2, fin = st + 1;
    flow_graph<int> g(n + m2 + 2, st, fin);
    int flow = 0;
    for (int i = 0; i < m2; i++) {
      int u, v;
      cin >> u >> v;
      u--; v--;
      if (!u || !v) {
        win[0]++;
        flow++;
      } else {
        g.add(i + n, u, 1, 0);
        g.add(i + n, v, 1, 0);
        g.add(st, i + n, 1, 0);
      }
    }
    bool ok = true;
    for (int i = 1; i < n; i++) {
      if (win[i] > win[0]) {
        ok = false;
        break;
      }
    }
    if (!ok) {
      cout << "NO\n";
      continue;
    }
    for (int i = 1; i < n; i++) {
      g.add(i, fin, win[0] - win[i], 0);
    }
    dinic<int> d(g);
    cout << (d.max_flow() == m2 - flow ? "YES" : "NO") << '\n';
  }
  return 0;
}



能鸽善武
1个月前

J-Number Game

签到题。

给你四个数 $A, B, C,x$,可以进行以下任意一种操作任意次,问能不能把 $C$ 变成 $x$。

  • 把 $B$ 变成 $A-B$
  • 把 $C$ 变成 $B-C$

容易发现任意一个操作执行 $2$ 次之后 $B,C$ 其中一个会变回初始的数。手写几个找规律会发现 $x = k\times (A - 2B) + C$ or $x = k\times (A-2B)+B-C$。

改写一下就是 $x-c = 0 \mod{(A-2B)}$ 和 $x-B+C = 0\mod{(A-2B)}$

特判一下 $A-2B=0$。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    bool ok = false;
    if (2 * b == a) {
      ok |= (x - c == 0) || (x - b + c == 0);
    } else {
      ok |= (x - c) % (a - 2 * b) == 0;
      ok |= (x - b + c) % (a - 2 * b) == 0;
    }
    cout << (ok ? "Yes" : "No") << '\n';
  }
  return 0;
}

M-Z-Game on grid

两个人在 $n\times m$ 的网格上轮流移动一个棋子。棋子初始位为 $(1, 1)$,每次只能向某一维的正方向移动一格。网格上有一些特殊点,移到标 A 的点先手胜,移到标 B 的点先手败,没有移到特殊点且不能再移动棋子则为平局。问先手是否有必胜、必平局、必败的策略。

考虑 $dp$,$dp(i, j):= 用三位二进制数表示走到(i,j)的情况(001表示先手胜,010表示平局,100表示后手胜)$

将所有 A 初始化成 $1$,B 初始化成 $4$,转移时只用考虑右边和下边有没有先手胜的策略,分类讨论。

  • 轮到先手走棋,且右边和下边某一处有 A,先手胜 $dp(i, j) = dp(i + 1, j) \or dp(i, j + 1)$
  • 轮到后手走棋,且右边和下面两个都是 A,先手胜 $dp(i, j) = dp(i + 1, j) \and dp(i, j + 1)$
  • 其他情况同理。

最后判断 $dp(1, 1)$ 每一位是否可行。

#define _GLIBCXX_DEBUG

#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, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    int win = 1, draw = 2, lose = 4;
    vector dp(n, vector<int>(m, 0));
    auto get = [&](int i, int j) {
      if (a[i][j] == 'A') return win;
      else if (a[i][j] == '.') return draw;
      else return lose;
    };
    for (int i = n - 1; i >= 0; i--) {
      for (int j = m - 1; j >= 0; j--) {
        if (i == n - 1 && j == m - 1) {
          dp[i][j] = get(i, j);
          continue;
        }
        if (a[i][j] != '.') {
          dp[i][j] = get(i, j);
        } else if (i == n - 1) {
          dp[i][j] = dp[i][j + 1];
        } else if (j == m - 1) {
          dp[i][j] = dp[i + 1][j];
        } else {
          if ((i + j) & 1) {
            dp[i][j] = dp[i][j + 1] & dp[i + 1][j];
          } else {
            dp[i][j] = dp[i][j + 1] | dp[i + 1][j];
          }
        }
      }
    }
    for (int i = 0; i < 3; i++) {
      cout << ((dp[0][0] >> i & 1) ? "yes" : "no") << " \n"[i == 2];
    }
  }
  return 0;
}

B-Eezie and Pie

给定一棵树,根为 $1$,每个节点可以为它的 $0\sim d[i]$ 级祖先贡献 $1$ 的价值。求最终每个点的价值。

这题的所有树上路径都是从根节点到某个节点的,不需要考虑两个节点之间的路径,所以这不是树上差分模板题吗??

只要考虑怎么往上找第 $d[i]$ 级祖先就可以了,维护 dfs 栈就可以得到。这题允许 log,所以用树上倍增或者树剖什么的都行。

然后树上差分把点权 $+1$ 即可。

#define _GLIBCXX_DEBUG

#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 n;
  cin >> n;
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  vector<int> d(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> d[i];
  }
  vector<int> f(n + 1);
  vector<int> st(1, 0);
  function<void(int, int)> dfs = [&](int u, int pr) {
    st.push_back(u);
    f[u]++;
    int k = st.size() - 1 - min(d[u] + 1, (int)st.size() - 1);
    f[st[k]]--;
    for (int v : adj[u]) {
      if (v == pr) {
        continue;
      }
      dfs(v, u);
    }
    st.pop_back();
  };
  dfs(1, -1);
  dfs = [&](int u, int pr) {
    for (int v : adj[u]) {
      if (v == pr) {
        continue;
      }
      dfs(v, u);
      f[u] += f[v];
    }
  };
  dfs(1, -1);
  for (int i = 1; i <= n; i++) {
    cout << f[i] << " \n"[i == n];
  }
  return 0;
}

G-Icon Design

画画,n = 5 直接手玩




能鸽善武
1个月前

1003 - Counting Stickmen

给你一棵无根树,问你有多少个“火柴人”。(真的是火柴人)这题还挺有意思的

又是一个数数题。以下所有 $deg$ 为无向图度数,也就是有多少条边与其相连

可以发现对于每个火柴人,我们确定身体之后就可以进行计数。(图中 $3-5$ 这条边),记身体这条边靠头的点为 $x$,靠腿的点为 $y$。

我们在点 $y$ 处计算腿的方案数,在点 $x$ 处计算头和手的方案数。

腿较简单,考虑 $y$ 下方的 $k$ 条边即可 $k \choose 2$,等价于 $deg_y - 1\choose 2$。减去 $y - x$ 这条边。

头的方案数也较简单,是 $deg_x - 3$,减去两条手臂 + 一个身子。

考虑手臂的方案数,只需要考虑最外侧的点就可以确定一条手臂,形如图中 $6、10$ ,为 $\sum_\limits{u\in son(x)}(deg_u - 1)$。

但由于 $x$ 的子节点中有一个特殊的点 $y$,他下面的点是做腿的,所以还要再减掉 $deg_y - 1$。

到目前为止手臂的方案数为 $\sum_\limits{u\in son(x)}(deg_u - 1) - deg_y + 1\choose 2$

由于我们考虑最外侧的点,有一种情况是两个手从一个胳膊里伸出来。。。所以还要在减掉所有一个胳膊里两只手的情况,也就是 $\sum_\limits{u\in son(x), u\neq y} {deg_u - 1\choose 2}$。

综上,预处理出
$$
f(u) = deg_u - 1 , g(u) = {deg_u - 1\choose 2}
$$
$$
f_{sum} = \sum_\limits{u\in son(x)}f(u)
$$
$$
g_{sum} = \sum_\limits{u\in son(x), u\neq y} {g(u)}
$$
最后 dfs 把每部分乘起来即可。其中 $y$ 是 $u$ 的邻点。
$$
ans =\sum[(deg_u-3) * g(y) * \left[{f_{sum} - f(y)\choose 2} - (g_{sum} - g(y))\right]
$$

#pragma GCC optimize(3)

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

...

Mint binom2(Mint x) {
  return x * (x - 1) / 2;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    vector<int> deg(n);
    for (int i = 1; i < n; i++) {
      int u, v;
      cin >> u >> v;
      u--; v--;
      adj[u].push_back(v);
      adj[v].push_back(u);
      deg[u]++;
      deg[v]++;
    }
    vector<Mint> f(n), g(n); // sum of (deg[u] - 1) and sum of (deg[u] - 1 choose 2)
    for (int i = 0; i < n; i++) {
      f[i] = deg[i] - 1;
      if (deg[i] - 1 >= 0) {
        g[i] = binom2(deg[i] - 1);
      }
    }
    Mint ans = 0;
    function<void(int, int)> dfs = [&](int u, int pr) {
      Mint f_sum = 0, g_sum = 0;
      for (int v : adj[u]) {
        f_sum += f[v];
        g_sum += g[v];
        if (v == pr) continue;
        dfs(v, u);
      }
      for (int v : adj[u]) {
        if (deg[u] - 3 >= 0) {
          ans += (deg[u] - 3) * g[v] * (binom2(f_sum - f[v]) - (g_sum - g[v]));
        }
      }
    };
    dfs(0, -1);
    cout << ans << '\n';
  }
  return 0;
}


活动打卡代码 AcWing 4347. 转换

能鸽善武
1个月前
#pragma GCC optimize(3,"Ofast","inline")

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { Modular result(*this); *this += 1; return result; }
  Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
    uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
    asm(
      "divl %4; \n\t"
      : "=a" (d), "=d" (m)
      : "d" (xh), "a" (xl), "r" (mod())
    );
    value = m;
#else
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
    long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  friend const Type& abs(const Modular& x) { return x.value; }

  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}

// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

/*
using ModType = int;

struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/

constexpr int md = 10007;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

// vector<Mint> fact(1, 1);
// vector<Mint> inv_fact(1, 1);

// Mint C(int n, int k) {
//   if (k < 0 || k > n) {
//     return 0;
//   }
//   while ((int) fact.size() < n + 1) {
//     fact.push_back(fact.back() * (int) fact.size());
//     inv_fact.push_back(1 / fact.back());
//   }
//   return fact[n] * inv_fact[k] * inv_fact[n - k];
// }


class segtree {
 public:
  struct node {
    long long add = 0;
    long long mul = 1;
    Mint s1 = 0;
    Mint s2 = 0;
    Mint s3 = 0;
    array<Mint, 3> sum{0, 0, 0};
    void apply(int l, int r, long long v, long long m) {
      sum[2] = sum[2] * m * m * m + sum[1] * 3 * m * m * v  + sum[0] * 3 * m  * v * v + (r - l + 1) * v * v * v;
      sum[1] = sum[1] * m  * m + sum[0] * 2 * m  * v + (r - l + 1) * v * v;
      sum[0] = sum[0] * m + (r - l + 1) * v;
      add = (add * m + v) % md;
      mul = (mul * m) % md;
    }
  };

  node unite(const node &a, const node &b) const {
    node res;
    res.sum[0] = a.sum[0] + b.sum[0];
    res.sum[1] = a.sum[1] + b.sum[1];
    res.sum[2] = a.sum[2] + b.sum[2];
    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[x].mul);
      tree[z].apply(y + 1, r, tree[x].add, tree[x].mul);
      tree[x].add = 0;
      tree[x].mul = 1;
    // }
  }

  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);
  cout.tie(0);
  int n, m;
  while (cin >> n >> m && n) {
    segtree st(n);
    while (m--) {
      int op, l, r, x;
      cin >> op >> l >> r >> x;
      l--;
      r--;
      if (op == 1) {
        st.modify(l, r, x, 1);
      } else if (op == 2) {
        st.modify(l, r, 0, x);
      } else if (op == 3) {
        st.modify(l, r, x, 0);
      } else {
        x--;
        cout << st.get(l, r).sum[x] << '\n';
      }
    }
  }  
  return 0;
}



能鸽善武
1个月前

1006 - Maex

给你一棵 $n$ 个点的树,点权未知,你需要标上不重复的点权 $(0,1,2,…$),使得 $\sum_\limits{i=1}^nb_i$ 最大。其中 $b_i$ 表示以 $i$ 为根的子树的所有点权的 $MEX$。

签到题,考虑 dp,$dp[u]$ 表示以 $u$ 为根的子树的最大 $\sum_\limits{v\in Son(u)}b_v$

由于只有一棵子树里面有 $0$,如果 $0$ 在 $u$ 的子树中,那么 $dp[u] = sz[u]$,其余子树的 $MEX$ 全部为 $0$。所以 $dp[u] = sz[u] + max(dp[u], dp[v])$。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
      int u, v;
      cin >> u >> v;
      u--; v--;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    vector<int> sz(n);
    vector<long long> f(n, 0);
    function<void(int, int)> dfs = [&](int u, int pr) {
      sz[u] = 1;
      for (int v : adj[u]) {
        if (v == pr) {
          continue;
        }
        dfs(v, u);
        sz[u] += sz[v];
        f[u] = max(f[u], f[v]);
      }
      f[u] += sz[u];
    };
    dfs(0, -1);
    cout << f[0] << '\n';
  }
  return 0;
}

1007 - Shinobu loves trip

签到题。实质是让你找到一个 $k$ 使得 $s_i\times a^k \equiv x \pmod P$。

数据范围都很小,每个样例都暴力处理出 $200000$ 以内的所有 $a^k\mod P$;

对于每次询问,遍历的 $s_i$,求出 $a^k \equiv x \times s_i^{-1}\pmod P$,看存不存在 $\le d_i$ 的 $k$。

注意处理 $x = 0$ 和 $s_i =0$ 的情况。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

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

int P;
// 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 bool operator==(const Z &lhs, const Z &rhs) {
    return lhs.val() == rhs.val();
  }
  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);
  int tt;
  cin >> tt;
  while (tt--) {
    int a, n, q;
    cin >> P >> a >> n >> q;
    vector<Z> s(n);
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
      cin >> s[i] >> d[i];
    }
    map<int, int> mp;
    long long pow = 1;
    for (int i = 0; i <= 200000; i++) {
      if (mp.count(pow)) break;
      mp[pow] = i;
      pow = pow * a % P;
    }
    while (q--) {
      int x;
      cin >> x;
      int ans = 0;
      if (x == 0) {
        cout << count(s.begin(), s.end(), Z(0)) << '\n';
        continue;
      }
      for (int i = 0; i < n; i++) {
        if (s[i] == Z(0)) {
          continue;
        }
        int y = (x / s[i]).val();
        if (!mp.count(y)) {
          continue;
        }
        ans += mp[y] % P <= d[i];
      }
      cout << ans << '\n';
    }
  }
  return 0;
}

1009 - Map

求地图压缩映射后的不动点。

$AB\perp AD$ ,用大地图的两条垂直边做基,设
$$
\boldsymbol{OP}=\boldsymbol{OA}+\lambda\boldsymbol{AB} + \mu\boldsymbol{AD}
$$
$$
\boldsymbol{OP}=\boldsymbol{Oa}+\lambda\boldsymbol{Aa} + \mu\boldsymbol{ad} \
$$

$$
\lambda(\boldsymbol{AB}-\boldsymbol{ab})+\mu(\boldsymbol{AD}-\boldsymbol{ad}) = \boldsymbol{Oa}-\boldsymbol{OA}
$$
高斯消元

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-9;

bool IsZero(double v) {
  return abs(v) < eps;
}

enum GAUSS_MODE {
  DEGREE, ABS
};

// int solution = 0;

template <typename T>
void GaussianElimination(vector<vector<T>>& a, int limit, GAUSS_MODE mode = DEGREE) {
  if (a.empty() || a[0].empty()) {
    return;
  }
  int h = static_cast<int>(a.size());
  int w = static_cast<int>(a[0].size());
  for (int i = 0; i < h; i++) {
    assert(w == static_cast<int>(a[i].size()));
  }
  assert(limit <= w);
  vector<int> deg(h);
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      deg[i] += !IsZero(a[i][j]);
    }
  }
  int r = 0;
  for (int c = 0; c < limit; c++) {
    int id = -1;
    for (int i = r; i < h; i++) {
      if (!IsZero(a[i][c]) && (id == -1 || (mode == DEGREE && deg[i] < deg[id]) || (mode == ABS && abs(a[id][c]) < abs(a[i][c])))) {
        id = i;
      }
    }
    if (id == -1) {
      continue;
    }
    if (id > r) {
      swap(a[r], a[id]);
      swap(deg[r], deg[id]);
      for (int j = c; j < w; j++) {
        a[id][j] = -a[id][j];
      }
    }
    vector<int> nonzero;
    for (int j = c; j < w; j++) {
      if (!IsZero(a[r][j])) {
        nonzero.push_back(j);
      }
    }
    T inv_a = 1 / a[r][c];
    for (int i = r + 1; i < h; i++) {
      if (IsZero(a[i][c])) {
        continue;
      }
      T coeff = -a[i][c] * inv_a;
      for (int j : nonzero) {
        if (!IsZero(a[i][j])) deg[i]--;
        a[i][j] += coeff * a[r][j];
        if (!IsZero(a[i][j])) deg[i]++;
      }
    }
    ++r;
  }
  for (r = h - 1; r >= 0; r--) {
    for (int c = 0; c < limit; c++) {
      if (!IsZero(a[r][c])) {
        T inv_a = 1 / a[r][c];
        for (int i = r - 1; i >= 0; i--) {
          if (IsZero(a[i][c])) {
            continue;
          }
          T coeff = -a[i][c] * inv_a;
          for (int j = c; j < w; j++) {
            a[i][j] += coeff * a[r][j];
          }
        }
        break;
      }
    }
  }
}

template <typename T>
vector<T> SolveLinearSystem(vector<vector<T>> a, const vector<T>& b, int w) {
  int h = static_cast<int>(a.size());
  assert(h == static_cast<int>(b.size()));
  if (h > 0) {
    assert(w == static_cast<int>(a[0].size()));
  }
  for (int i = 0; i < h; i++) {
    a[i].push_back(b[i]);
  }
  GaussianElimination(a, w);
  vector<T> x(w, 0);
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (!IsZero(a[i][j])) {
        x[j] = a[i][w] / a[i][j];
        break;
      }
    }
  }
  return x;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  cout << fixed;
  cout.precision(10);  
  while (tt--) {
    const int n = 4;
    vector<double> X(n), Y(n);
    for (int i = 0; i < 4; i++) {
      cin >> X[i] >> Y[i];
    }
    vector<double> x(n), y(n);
    for (int i = 0; i < 4; i++) {
      cin >> x[i] >> y[i];
    }
    double X1 = X[1] - X[0] - x[1] + x[0], X2 = X[3] - X[0] - x[3] + x[0];
    double Y1 = Y[1] - Y[0] - y[1] + y[0], Y2 = Y[3] - Y[0] - y[3] + y[0];
    vector<vector<double>> coeff(2, vector<double>(2));
    coeff[0][0] = X1, coeff[0][1] = X2;
    coeff[1][0] = Y1, coeff[1][1] = Y2;
    vector<double> b{x[0] - X[0], y[0] - Y[0]};
    auto res = SolveLinearSystem(coeff, b, 2);
    double px = x[0] + res[0] * (x[1] - x[0]) + res[1] * (x[3] - x[0]);
    double py = y[0] + res[0] * (y[1] - y[0]) + res[1] * (y[3] - y[0]);
    cout << px << ' ' << py <<'\n';
  }
  return 0;
}

1010 - Planar graph

给你一个平面图 $G$,你需要删掉一些边使得所有连通分量两两可达。问最少删掉多少条边,以及边的编号。如果有多种答案,输出字典序最小的答案。

题目背景是平面图欧拉定理的证明。$V - E + F = k + 1,k为连通分量数量$。

如果一个连通分量有圈,那么他一定与外部不连通,不符合题意。$G$ 最多删掉 $V - k$ 条边,剩余 $E - V + k$ 条边,结果是一棵树。

构造一个新图 $\overline G$,点为 $G$ 中的面(连通分量),如果两个面被平面图某条边分割,就在 $\overline G$ 中连一条边。根据平面图欧拉定理,$\overline G$ 的点数是面的数量 $F = k + 1 + E - V$,$G$ 的隧道数量(删边数量)为 $E - (V - k) = F - 1$。考虑 $G$ 中剩余的边在 $\overline G$ 中的对应边,在 $\overline G$ 中删去这些剩余边,剩下来 $F - 1$ 条边,且连通,构成一棵 $\overline G$ 的最小生成树。

所以需要求 $\overline G$ 的字典序最小的生成树,等价于 $\overline G$ 的 $MST$。由于 $\overline G$ 中的边是 $G$ 中删去的边,所以 $G$ 中的边的权值全部都较大,构成 $G$ 的最大生成树。最大生成树中不存在的边就是 $\overline G$ 中 $MST$ 的边。

答案要求字典序最小,所以倒序 kruskal。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

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

class DSU {
public:
  vector<int> p;
  int n;

  DSU(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int find(int x) {
    return (x == p[x] ? x : (p[x] = find(p[x])));
  }

  inline bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    DSU d(n);
    vector<array<int, 2>> e(m);
    for (int i = 0; i < m; i++) {
      cin >> e[i][0] >> e[i][1];
      e[i][0]--;
      e[i][1]--;
    }
    vector<int> ans(m, 0);
    for (int i = m - 1; i >= 0; i--) {
      int u = e[i][0], v = e[i][1];
      bool in_tree = d.unite(u, v);
      ans[i] = !in_tree;
    }
    cout << accumulate(ans.begin(), ans.end(), 0) << '\n';
    for (int i = 0; i < m; i++) {
      if (ans[i]) {
        cout << i + 1 << ' ';
      }
    }
    cout << '\n';
  }
  return 0;
}

1012 - Loop

给你一个数组 $a$,需要进行 $k$ 次操作,每次操作相当于选择一个区间 $[l, r]$,取出 $a[l]$,将区间中剩余数向左移动一位,再将取出的数放入 $a[r]$,求字典序最大的结果。

贪心的从前往后找第一个 $a_i > a_{i-1}$(单调栈),将 $a_{i-1}$ 放到第一个小于 $a_{i-1}$ 的数前面。

注意到每次操作本质是将一个元素拿出,然后把后面所有元素往前移,最后再把拿出的元素插入到拿出位置的后面的任意位置。

可以先弹出 $k$ 个元素最后再一起插入回去。用堆维护,最后插入的时候用归并。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    priority_queue<int> que;
    vector<int> st;
    for (int i = 0; i < n; i++) {
      while (!st.empty() && st.back() < a[i] && k) {
        k--;
        que.push(st.back());
        st.pop_back();
      }
      st.push_back(a[i]);
    }
    vector<int> ans(n);
    int j = 0;
    assert(k == 0);
    for (int i = 0; i < n; i++) {
      int choose;
      if (j >= st.size()) {
        choose = que.top();
        que.pop();
      } else if (que.empty()) {
        choose = st[j++];
      } else {
        if (que.top() > st[j]) {
          choose = que.top();
          que.pop();
        } else {
          choose = st[j++];
        }
      }
      ans[k++] = choose;
    }
    for (int i = 0; i < n; i++) {
      cout << ans[i] << " \n"[i == n - 1];
    }
  }
  return 0;
}