Atcoder ABC 454

2026-04-252026-04-25

Info

42:38 做完D题 结束 后面看看补一下E?

C 题

搜索，找到最长路径的大小

void solve() {
  int n, m;
  cin >> n >> m;
  auto g = vector(n + 1, vector<int>());
  for (int i = 0; i < m; i ++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
  }

  int ans = 0;
  vector<int> vis(n + 1);
  vis[0] = 1;
  auto dfs = [&](auto &self, int fa, int u) {
    if (vis[u]) return;
    vis[u] = 1;
    ans ++;
    debug(fa);debug(u);
    for (auto v : g[u]) {
      self(self, u, v);
    }
  };
  dfs(dfs, 0, 1);
  cout << ans << endl;
}

D 题

第一次遇到字符串的题，第一反应是会不会是dp，但后来发现就是玩一下他的规则，等价于把所有的(xx)都缩成xx，然后看两个字符串一不一样，缩的方法试错了2种，第一次是扫描(xx)，发现会错过前面的(，然后又想有点类似括号匹配，但是栈的大小没有这么大，最后想到了是在每次遇到)的时候做判断。

void solve2() {
  string a, b;
  cin >> a >> b;
  int n = a.size(), m = b.size();
  string aa, bb;
  for (int i = 0; i < n; i ++) {
    if (a[i] != ')') aa += a[i];
    else {
      if (aa.size() >= 3 && aa.substr(aa.size() - 3, 3) == "(xx") {
        aa.erase(aa.end() - 3, aa.end() - 2);
      } else aa += ')';
    }
  }

  for (int i = 0; i < m; i ++) {
    if (b[i] != ')') bb += b[i];
    else {
      if (bb.size() >= 3 && bb.substr(bb.size() - 3, 3) == "(xx") {
        bb.erase(bb.end() - 3, bb.end() - 2);
      } else bb += ')';
    }
  }
  debug(aa);debug(bb);
  cout << (aa == bb ? "Yes\n" : "No\n");
}

E 题（补题）

想象成国际象棋的棋盘，(1, 1)是黑色，根据n的奇偶性，可以推出(n,n)的颜色和走\(n^2 - 2\)步后最后一步的颜色。

• n奇，(n,n)黑，\(n^2 - 2\)奇，最后一步白
• n偶，(n,n)黑，\(n^2 - 2\)偶，最后一步黑

n为奇时必不可达

路径中点的个数是\(n^2 - 1\)个，\(\frac{n^2}{2} - 1\)个黑，\(\frac{n^2}{2}\)个白，所以跳过点只能是白，即\(a + b\)为奇数

然后如何构造路径？蛇形走位

1. 在跳过点之前：先往右走到头，再回头
2. 在跳过点那两行，用上下的蛇形走位
3. 在跳过点之后，先往左到头，再往右