Skip to content

ABC 265

比赛链接

A - Apple

如果 \(3 * x \le y\)，则答案为 \(x * n\)，否则为 \((n / 3) * y + (n \% 3) * x\)

B - Explore

从左往右遍历即可，使用 t 表示剩余时间，遇到一个 bouns room 则增加 t。直到 t 无法到达下一个房间。

C - Belt Conveyor

使用一个二维表记录每个位置是否走过，当走出地图外或者走到一个曾经走过的地方时就结束循环。

D - Iroha and Haiku

分三次DP，第一次只需要找合法的 \(y\)，然后第二次找合法的 \(z\)，以为对于每个合法的 \(z\)，其对应的 \(y\) 是固定的（所有元素都为正），所以直接考虑是否可以从这个 \(y\) 转移即可。第三次 DP 是类似的。

复杂度为 \(O(n\log n)\)，通过双指针可以优化到 \(O(n)\)。

void solve() {
  int n; ll p, q, r;
  cin >> n >> p >> q >> r;
  vector<ll> a(n + 1), s(n + 1);
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    s[i] = s[i - 1] + a[i];
  }
  vector<int> f(n + 1), d(n + 1), w(n + 1);
  map<ll, int> mp;
  mp[0] = 0;
  for(int i = 1; i <= n; i++) {
    if(mp.count(s[i] - p)) {
      f[i] = 1;
    }
    mp[s[i]] = i;
  }

  mp.clear(); mp[0] = 0;
  for(int i = 1; i <= n; i++) {
    if(mp.count(s[i] - q)) {
      int x = mp[s[i] - q];
      if(x > 0 && f[x]) {
        d[i] = 1;
      } 
    }
    mp[s[i]] = i;
  }
  mp.clear(); mp[0] = 0;
  for(int i = 1; i <= n; i++) {
    if(mp.count(s[i] - r)) {
      int x = mp[s[i] - r];
      if(x > 0 && d[x]) {
        cout << "Yes\n";
        return;
      }
    }
    mp[s[i]] = i;
  }

  cout << "No\n";
}

E - Warp

\(d[i][j][k]\) 表示进行了 \(i\) 次 1 操作，\(j\) 次 2 操作，\(k\) 次 3 操作后可行的方案数。而此时的坐标可以根据 \((i, j, k)\) 计算得到，通过查表可以知道该位置是否合法，如果不合法则不转移，否则：

  • d[i + 1][j][k] += d[i][j][k]
  • d[i][j + 1][k] += d[i][j][k]
  • d[i][j][k + 1] += d[i][j][k]

时间复杂度为 \(O(n^3\log m)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
constexpr int P = 998244353;
// assume -P <= x < 2P
int norm(int x) { if (x < 0) x += P; else 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 Int {
    int x;
    Int(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Int operator-() const { return Int(norm(P - x)); }
    Int inv() const { assert(x != 0); return power(*this, P - 2); }
    Int &operator*=(const Int &rhs) { x = ll(x) * rhs.x % P; return *this; }
    Int &operator+=(const Int &rhs) { x = norm(x + rhs.x); return *this; }
    Int &operator-=(const Int &rhs) { x = norm(x - rhs.x); return *this; }
    Int &operator/=(const Int &rhs) { return *this *= rhs.inv(); }
    friend Int operator*(const Int &lhs, const Int &rhs) { Int res = lhs; res *= rhs; return res; }
    friend Int operator+(const Int &lhs, const Int &rhs) { Int res = lhs; res += rhs; return res; }
    friend Int operator-(const Int &lhs, const Int &rhs) { Int res = lhs; res -= rhs; return res; }
    friend Int operator/(const Int &lhs, const Int &rhs) { Int res = lhs; res /= rhs; return res; }
    friend ostream& operator << (ostream& out, const Int &x) { out << x.val(); return out; }
};
Int d[301][301][301];
void solve() {
  int n, m;
  ll A, B, C, D, E, F;
  cin >> n >> m;
  cin >> A >> B >> C >> D >> E >> F;
  map<pair<ll, ll>, int> mp;
  for(int i = 1; i <= m; i++) {
    int x, y; cin >> x >> y;
    mp[make_pair(x, y)] = 1;
  }

  d[0][0][0] = 1;
  Int res = 0;
  for(int i = 0; i <= n; i++) {
    for(int j = 0; j + i <= n; j++) {
      for(int k = 0; i + j + k <= n; k++) {
        ll x = i * A + j * C + k * E;
        ll y = i * B + j * D + k * F;
        if(mp.count({x, y})) continue;
        if(i + j + k == n) {
          res += d[i][j][k];
          break;
        }
        d[i + 1][j][k] += d[i][j][k];
        d[i][j + 1][k] += d[i][j][k];
        d[i][j][k + 1] += d[i][j][k];
      }
    }
  }
  cout << res << "\n";
}

F - Manhattan Cafe

设 \(f[x][y]\) 为 \(d(p,r) = x, d(q, r) = y\) 时的方案数。我们可以构造一个类似背包DP的转移，复杂度为 \(O(nd^3)\)。

优化思路是，每个阶段转移时，物品体积是有规律的。设当前 \(s = abs(p[i] - q[i])\)，那么转移有： 1. \((s, 0),(s-1, 1),\cdots, (0, s)\) 2. \((s+1, 1), (s+2, 2), \cdots\) 3. \((1, s+1), (2, s+2), \cdots\)

可以发现，这三组中的每一组，对应于二维矩阵中的一条斜线。所以可以使用前缀和优化转移。

时间复杂度为 \(O(nd^2)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
void solve() {
  int n, d;
  cin >> n >> d;
  vector<int> p(n), q(n);
  for(int i = 0; i < n; i++) cin >> p[i];
  for(int i = 0; i < n; i++) cin >> q[i];

  vector<vector<Int>> f(d + 1, vector<Int>(d + 1, 0));
  f[0][0] = 1;

  for(int i = 0; i < n; i++) {
    int s = abs(p[i] - q[i]);
    vector<vector<Int>> g(d + 1, vector<Int>(d + 1, 0));
    auto sum = f;
    for(int x = 0; x <= d; x ++) {
      for(int y = 0; y <= d; y++) {
        if(x - 1 >= 0 && y + 1 <= d) {
          sum[x][y] += sum[x - 1][y + 1];
        }

        if(x + y < s) continue;
        int xx = x, yy = y - s;
        if(yy < 0) {
          xx += yy;
          yy = 0;
        }
        if(xx >= 0 && xx <= d && yy >= 0 && yy <= d) g[x][y] += sum[xx][yy];

        xx = x - s - 1, yy = y + 1;
        if(xx >= 0 && xx <= d && yy >= 0 && yy <= d) g[x][y] -= sum[xx][yy];
      }
    }

    sum = f;
    for(int x = 0; x <= d; x ++) {
      for(int y = 0; y <= d; y ++) {
        if(x > 0 && y > 0) sum[x][y] += sum[x - 1][y - 1];
        if(x - (s + 1) >= 0 && y - 1 >= 0) g[x][y] += sum[x - (s + 1)][y - 1];
        if(x - 1 >= 0 && y - (s + 1) >= 0) g[x][y] += sum[x - 1][y - (s + 1)];
      }
    }

    f = g;
  }

  Int res = 0;
  for(auto &v : f) for(auto &x : v) res += x;
  cout << res << "\n";
}

G - 012 Inversion

线段树单个节点维护一个二维矩阵 \(pairs\)，\(pairs[i][j]\) 对应的值表示该节点表示的区间中形成前面是 \(i\)，后面是 \(j\) 的对数。另外，还需要一个数组 \(cnt[i]\) 表示区间中 \(i\) 的个数。

struct Info {
  vector<vector<ll>> pairs;
  vector<ll> cnt;
  Info(): pairs(3, vector<ll>(3, 0)), cnt(3, 0) {}
  ll sum() {
    return pairs[1][0] + pairs[2][1] + pairs[2][0];
  }
};

// 两个节点合并时对应的操作
struct Merge {
  Info operator () (const Info &l, const Info &r) const {
    Info t;
    for(int i = 0; i < 3; i++) {
      for(int j = 0; j < 3; j++) {
        t.pairs[i][j] = l.pairs[i][j] + r.pairs[i][j] + l.cnt[i] * r.cnt[j];
      }
    }
    for(int i = 0; i < 3; i++) t.cnt[i] = l.cnt[i] + r.cnt[i];
    return t;
  }
};

LazyTag 维护一个映射关系，用一个长度为 3 的数组表示。

struct LazyTag {
  vector<int> trans;
  LazyTag(): LazyTag(0, 1, 2) {}
  LazyTag(int S, int T, int U): trans(3, 0) {
    trans[0] = S; trans[1] = T; trans[2] = U;
  }
};

// tag 作用于节点
struct Mapping {
  void operator () (const LazyTag& tag, Info& info) const {
    if(tag.trans != vector<int>{0, 1, 2}) {

      vector<vector<ll>> pairs(3, vector<ll>(3, 0));
      for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
          int u = tag.trans[i], v = tag.trans[j];
          pairs[u][v] += info.pairs[i][j]; // 注意这里是 += 而非 =
        }
      }
      info.pairs = pairs;

      vector<ll> cnt(3);
      for(int i = 0; i < 3; i++) cnt[tag.trans[i]] += info.cnt[i]; // 同理是 += 而非 =
      info.cnt = cnt;
    }
  }
};


// 再加一层映射
struct Composition {
  void operator ()(const LazyTag& x, LazyTag& y) const {
    if(x.trans != vector<int>{0, 1, 2}) {
      // dbg(x.trans);
      for(int i = 0; i < 3; i++) {
        y.trans[i] = x.trans[y.trans[i]];
      }
    }
  }
};

其他代码： 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
template<class Info, class LazyTag, 
  class Merge, class Mapping, class Composition>
struct LazySegTree{
  int n;
  Merge merge;
  Mapping mapping;
  Composition composition;
  vector<Info> info;
  vector<LazyTag> lazyTag;
  LazySegTree(int n): n(n), merge(Merge()), mapping(Mapping()), 
    composition(Composition()), info(4 * n), lazyTag(4 * n) {}
  LazySegTree(int n, vector<Info> &init): LazySegTree(n) {
    function<void(int,int,int)> build = [&](int p, int l, int r) {
      if(l == r) {
        info[p] = init[l];
        return;
      }
      int m = (l + r) / 2;
      build(2 * p, l, m);
      build(2 * p + 1, m + 1, r);
      pull(p);
    };
    build(1, 0, n - 1);
  }

  void pull(int p) {
    info[p] = move(merge(info[2 * p], info[2 * p + 1]));
  }

  void push(int p, const LazyTag& tag) {
    mapping(tag, info[p]);
    composition(tag, lazyTag[p]);
  }

  void pushdown(int p) {
    push(2 * p, lazyTag[p]);
    push(2 * p + 1, lazyTag[p]);
    lazyTag[p] = LazyTag();
  }
  // 这里是 LazyTag
  void modify(int p, int l, int r, int L, int R, const LazyTag &v) {
    if(l >= L && r <= R) {
      push(p, v);
      return;
    }
    pushdown(p);
    int m = (l + r) / 2;
    if(L <= m) modify(p * 2, l, m, L, R, v);
    if(R > m) modify(2 * p + 1, m + 1, r, L, R, v);
    pull(p);
  }

  void modify(int l, int r, const LazyTag &v) {
    modify(1, 0, n - 1, l, r, v);
  }

  Info rangeQuery(int p, int l, int r, int x, int y) {
    if(l > y || r < x) {
      return Info();
    }
    if(l >= x && r <= y) return info[p];
    int m = (l + r) / 2;
    pushdown(p);
    return merge(rangeQuery(p * 2, l, m, x, y), rangeQuery(p * 2 + 1, m + 1, r, x, y));
  }

  Info rangeQuery(int l, int r) {
    return rangeQuery(1, 0, n - 1, l, r);
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  vector<Info> info(n);
  for(int i = 0; i < n; i++) {
    int x; cin >> x;
    info[i].cnt[x] ++;
  }
  LazySegTree<Info, LazyTag, Merge, Mapping, Composition> seg(n, info);
  while(q--) {
    int op, l, r, s, t, u;
    cin >> op >> l >> r;
    if(op == 1) {
      cout << seg.rangeQuery(l - 1, r - 1).sum() << "\n";
    } else {
      cin >> s >> t >> u;
      seg.modify(l - 1, r - 1, LazyTag(s, t, u));
    }
  }
}

本文访问 次