CF Round #556 (Div.2)

分类:题解, 发布于:2019-04-30 00:48:30, 更新于:2019-05-01 21:17:53 CC-BY-NC-SAv4 评论

太菜了连Div.2都不会做……

A - Stock Arbitraging

你有$r$元,早上有$n$种某买商品的价格,晚上有$m$种售出商品的价格,问你晚上最多拥有多少钱。

贪心,最便宜的买(尽可能多的买),最贵的卖;如果不赚钱就不买了。

B - Tiling Challenge

$n \times n$的地面有部分格子已经被占用了,问是否能用$+$形状的木板填满剩余部分。

超级大暴力,完全手速题。

C - Prefix Sum Primes

你有长度为$n$$\{ 1, 2 \}$构成的序列;问如何排列使前缀和中的质数最多。

贪心,偶数的质数只有2,所以序列最前面两个一定是2和1(不能就算了),接下来全部排2,最后排1。

D - Three Religions

一个单词和三个动态更新的字符串,问每次更新后,三个字符串是否构成互不相交的单词的子串(if their descriptions form disjoint subsequences of the Word of Universe)。

看别人的代码是DP……完全没想到

先倒叙处理单词,找到每个位置对应字符下一次出现的位置。然后对每次查询,维护一个DP数组$dp[a][b][c]$,表示匹配三个字符串前$a, b, c$个字符所需要的最小长度。

状态转移方程为 $$dp[a][b][c] = \min \begin{cases} next(dp[a - 1][b][c], s_a[a-1]), \\ next(dp[a][b - 1][c], s_b[b-1]), \\ next(dp[a][b][c - 1], s_c[c-1]). \end{cases}$$

如果某个字符串变长了,只需要固定新增的那个字符,对其他两个字符串DP,复杂度为$O(n^2)$而不是$O(n^3)$;如果某个字符串变短了,则不需要重新DP。

#include <bits/stdc++.h>
using namespace std;

int n = 0, q = 0;
string s;

vector<int> d[4];
int nex[100005][26] = {};
int dp[255][255][255] = {};

void prepare() {
  memset(dp, -1, sizeof(dp));
  for (int c = 0; c < 26; ++c) {
    nex[n][c] = nex[n + 1][c] = n;
  }
  for (int i = n - 1; i >= 0; --i) {
    for (int c = 0; c < 26; ++c) {
      nex[i][c] = nex[i + 1][c];
    }
    nex[i][s[i] - 'a'] = i;
  }
}

void solve(int r) {
  int la = (r == 1) ? d[1].size() : 0, ma = d[1].size();
  int lb = (r == 2) ? d[2].size() : 0, mb = d[2].size();
  int lc = (r == 3) ? d[3].size() : 0, mc = d[3].size();
  for (int a = la; a <= ma; ++a) {
    for (int b = lb; b <= mb; ++b) {
      for (int c = lc; c <= mc; ++c) {
        int &val = dp[a][b][c];
        val = n;
        if (a > 0) {
          val = min(val, nex[dp[a - 1][b][c] + 1][d[1][a - 1]]);
        }
        if (b > 0) {
          val = min(val, nex[dp[a][b - 1][c] + 1][d[2][b - 1]]);
        }
        if (c > 0) {
          val = min(val, nex[dp[a][b][c - 1] + 1][d[3][c - 1]]);
        }
      }
    }
  }
}

void handle() {
  char t = 0, ch = 0;
  int r = 0, c = 0;
  cin >> t >> r;
  if (t == '+') {
    cin >> ch;
    c = ch - 'a';
    d[r].push_back(c);
    solve(r);
  } else {
    d[r].pop_back();
  }
}

int main() {
  cin.sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> q >> s;
  prepare();
  for (int i = 0; i < q; ++i) {
    handle();
    if (dp[d[1].size()][d[2].size()][d[3].size()] < n) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }
  return 0;
}

E - Tree Generator TM

用括号表示一棵树,每次交换两个括号,问每次更新后树的直径是多少。

想到了是线段树,然后抄完模板发现样例都过不了……唯一一个过的线段树非常骚

对括号从左到右遍历可以获得每一个节点的深度,那么两个节点之间的距离就是 $$dis_{u, v} = depth_u - 2depth_{lca(u, v)} + depth_v$$ 其中$lca(u,v)$是从左往右遍历时深度最小的那个点。

那么就可以用线段树记录以下信息:

  • $\delta$: 这段区间上左端点和右端点深度的差值(线段树求和);
  • $\min depth$: 区间上最小的深度(线段树求最小值)
  • $\max depth$: 区间上最大的深度(线段树求最大值)
  • $\max (depth_u - 2depth_{lca})$: 左端点深度减去两倍最小深度(两个区间的最大值、左端点深度减去右区间最小深度的三者最大者)
  • $\max (depth_v - 2depth_{lca})$: 右端点深度减去两倍最小深度(两个区间的最大值、右端点深度减去左区间最小深度的三者最大者)
  • $\max (depth_u - 2depth_{lca} + depth_v$: 所求答案(两个区间的最大值、左区间最大差值+右区间最大深度、左区间最大深度+右区间最大差值四者取最大)

看题解学到了线段树的新写法和C++max的新用法,开心然而代码一团乱

#include <bits/stdc++.h>
using namespace std;

class Tree {
 public:
  class Node {
   public:
    int delta;
    int mind, maxd;
    int maxlm, maxmr, maxlmr;

    static Node empty() { return {0, 0, 0, 0, 0, 0}; }
    static Node character(char ch) {
      if (ch == '(') {
        return { 1,  0, 1, 0, 1, 1};
      } else {
        return {-1, -1, 0, 2, 1, 1};
      }
    }
    Node shift(int d) const {
      return {delta + d, mind + d,  maxd + d,
              maxlm - d, maxmr - d, maxlmr};
    }
    static Node merge(const Node &l, const Node &r) {
      Node shifted = r.shift(l.delta);
      Node ret = empty();
      ret.delta = shifted.delta;
      ret.mind = min(l.mind, shifted.mind);
      ret.maxd = max(l.maxd, shifted.maxd);
      ret.maxlm = max({l.maxlm, shifted.maxlm, l.maxd - 2 * shifted.mind});
      ret.maxmr = max({l.maxmr, shifted.maxmr, shifted.maxd - 2 * l.mind});
      ret.maxlmr = max({
        l.maxlmr, shifted.maxlmr,
        l.maxlm + shifted.maxd, shifted.maxmr + l.maxd
      });
      return ret;
    }
  };

  vector<Node> data;
  int Base;

  Tree (int N) : Base(1) {
    while (Base < N + 1) { Base *= 2; }
    data.resize(Base * 2, Node::empty());
  }

  void replace(int pos, char ch) {
    pos += Base;
    data[pos] = Node::character(ch);

    do {
      pos >>= 1;
      data[pos] = Node::merge(data[pos << 1], data[pos << 1 | 1]);
    } while (pos > 1);
  }

  int getAns() const {
    return data[1].maxlmr;
  }
};

int n, q;
string s;

int main() {
  cin.sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> q >> s;
  --n;

  Tree tree(n << 1);
  for (int i = 0; i < (n << 1); ++i) {
    tree.replace(i, s[i]);
  }
  cout << tree.getAns() << endl;

  int u = 0, v = 0;
  for (int i = 0; i < q; ++i) {
    cin >> u >> v;
    --u, --v;

    swap(s[u], s[v]);
    tree.replace(u, s[u]);
    tree.replace(v, s[v]);

    cout << tree.getAns() << endl;
  }
}

评论