08.29

QOJ141

A 没必要传度数 \(<8\) 的点。

因为双染色是容易的，A 把两种颜色压缩成一种颜色，B 再把每种颜色双染色，就是合法的八染色了。

每个点给度数和贡献至少 \(8\)，占 \(2\) bit，考虑到度数和的上限为 \(2m\)，至多需要 \(m/2\) bit。

std::vector <int> Alice(int n, int m, std::vector <int> u, std::vector <int> v, std::vector <int> c) {
  std::vector<int> deg(n);
  for (int i = 0; i < m; i++) {
    ++deg[u[i]], ++deg[v[i]];
  }
  std::vector<int> x;
  for (int i = 0; i < n; i++) if (deg[i] >= 8) {
    x.push_back(c[i] >> 2), x.push_back((c[i] >> 1) & 1);
  }
  return x;
}

std::vector <int> Bob(int n, int m, std::vector <int> u, std::vector <int> v, std::vector <int> x) {
  std::vector<int> deg(n);
  std::vector<std::vector<int>> e(n);
  for (int i = 0; i < m; i++) {
    ++deg[u[i]], ++deg[v[i]];
    e[u[i]].push_back(v[i]), e[v[i]].push_back(u[i]);
  }
  std::vector<int> c(n, -1);
  int cnt = 0;
  for (int i = 0; i < n; i++) if (deg[i] >= 8) {
    c[i] = x[cnt++], c[i] = 2 * c[i] + x[cnt++];
  }
  std::vector<int> col(n, -1);
  std::function<void(int)> dfs = [&](int u) {
    for (auto v : e[u]) if (col[v] == -1 && c[u] == c[v] && c[u] != -1)
      col[v] = col[u] ^ 1, dfs(v);
  };
  for (int i = 0; i < n; i++) if (col[i] == -1)
    col[i] = 0, dfs(i);
  for (int i = 0; i < n; i++) if (c[i] != -1) c[i] = 2 * c[i] + col[i]; 
  for (int i = 0; i < n; i++) if (c[i] == -1) {
    std::vector<int> col(8);
    for (auto v : e[i]) if (c[v] != -1) col[c[v]] = 1;
    for (int j = 0; j < 8; j++) if (!col[j])
      c[i] = j;
  }
  return c;
}

P10218

只要还有数字不在 \(S\) 集合中，答案就不会超过 \(2^k-1\)。因此当且仅当 \(\sum b_i \leq m\) 时答案大于 \(2^k-1\) 且为 \(\min\{b_i\}+2^k-1\)，否则答案恰有 \(k\) 位。

尝试逐位确定之。

那么把所有 \(a_i\) 插入 Trie，在 Trie 上考虑所有前 \(i\) 位与答案相同的数（不同的话，最高不同位必须大于答案对应位）。做 dfs，传入剩余的 \(m\)。在一个点处枚举 \(x\) 的当前位为 \(0\) 还是 \(1\)，事实上是对称的。假如是 \(0\)，则左子树中所有点必须被划入 \(S\) 集合，子树内点的 \(b_i\) 和不超过剩余的 \(m\)，且 \(a_i\) 的最小值经过 \(+x\) 后超过当前答案。递归另一侧确定后面位即可。

CF1887E

矩形不好处理，但点并不多。把 \((x, y)\) 的颜色为 \(c\) 处理成 \(x \to y+n\) 有一条 \(c\) 的边，抓一个初始边构成的环，每次从正中间劈开，一定至少一个子环没有重复颜色。这样做下去就行了。\(10 > \log_2 n\)，所以一定存在方案。

有人输入的颜色处理成 0-index 了。

#include <bits/stdc++.h>

int f[2000][2000];
char s[6];

void solve() {
  int n; scanf("%d", &n);
  std::vector<std::vector<int>> e(2 * n);
  for (int i = 1, u, v; i <= 2 * n; i++) {
    scanf("%d %d", &u, &v), --u, --v, v += n;
    e[u].push_back(v), e[v].push_back(u);
    f[u][v] = f[v][u] = i;
  }
  std::vector<int> stk, path, vis(2 * n);
  std::function<void(int, int)> dfs = [&](int u, int f) {
    if (vis[u]) {
      if (!path.size()) {
        while (stk.size() && stk.back() != u)
          path.push_back(stk.back()), stk.pop_back();
        path.push_back(u), stk.pop_back();
      }
      return;
    }
    assert(u < (int)vis.size());
    vis[u] = 1;
    stk.push_back(u);
    for (auto v : e[u]) if (v != f)
      dfs(v, u);
    if (stk.size() && stk.back() == u) stk.pop_back();
  };
  for (int i = 0; i < n; i++) if (!vis[i])
    dfs(i, -1);
  while ((int)path.size() > 4) {
    int h = path.size() % 4 == 0 ? path.size() / 2 - 1 : path.size() / 2;
    int u = path[0], v = path[h];
    if (u > v) printf("? %d %d\n", v + 1, u - n + 1);
    else printf("? %d %d\n", u + 1, v - n + 1);
    fflush(stdout);
    int t; scanf("%d", &t);
    f[u][v] = f[v][u] = t;
    bool c = 1;
    for (int i = 0; i < h; i++)
      c &= (f[path[i]][path[i + 1]] != t);
    if (c) 
      path = std::vector<int>(path.begin(), path.begin() + h + 1);
    else
      path = std::vector<int>(path.begin() + h, path.end()), path.push_back(u);
  }
  int a = path[0], b = path[1], c = path[2], d = path[3];
  if (a < n) printf("! %d %d %d %d\n", a + 1, c + 1, b - n + 1, d - n + 1);
  else printf("! %d %d %d %d\n", b + 1, d + 1, a - n + 1, c - n + 1);
  fflush(stdout);
  scanf("%s", s);
}

int main() {
  int T; scanf("%d", &T); while (T--) {
    solve();
  }
}

agc044D

编辑距离可以做什么呢？对于一个全 A 的串，编辑距离可以求出来密码中有几个 A（只使用替换删除）；对于 \(T\) 和 \(S\)，二者为子序列当且仅当编辑距离 \(=|S|-|T|\)（只插入）。

于是求 \(f(S)\) 表示只保留 \(S\) 中的字符密码是什么样子的，合并 \(f(A)\) 和 \(f(B)\) 需要 \(|A|+|B|-1\) 次操作，哈夫曼树优化合并（不优化好像也行）就行了。

至于这个合并，跑一个归并排序，枚举下一位来自哪个串就行了。也可以把一个串的每一位往另一个串里面插。

#include <bits/stdc++.h>

struct cmp {
  bool operator () (const std::string &x, const std::string &y) {
    return x.length() > y.length();
  }
};

int main() {
  std::priority_queue<std::string, std::vector<std::string>, cmp> q;
  auto qry = [&](std::string s) {
    std::cout << "? " << s << std::endl;
    int t; std::cin >> t; return t;
  };
  int l = 0;
  std::vector<char> ch;
  for (int i = 0; i < 26; i++)
    ch.push_back(i  + 'a'), ch.push_back(i + 'A');
  for (int i = 0; i < 10; i++)
    ch.push_back(i + '0');
  for (auto c : ch) {
    int x = 128 - qry(std::string(128, c));
    if (x) q.push(std::string(x, c));
    l += x;
  }
  while (q.size() > 1) {
    std::string a = q.top(); q.pop();
    std::string b = q.top(); q.pop();
    int n = a.length(), m = b.length();
    int i = 0, j = 0;
    std::string c;
    while (i < n && j < m) {
      std::string s = c + a[i] + std::string(b.begin() + j, b.end());
      if (qry(s) == l - s.length())
        c = c + a[i++];
      else
        c = c + b[j++]; 
    }
    while (i < n) c = c + a[i++];
    while (j < m) c = c + b[j++];
    q.push(c);
  }
  std::cout << "! " << q.top() << std::endl;
}