Atcoder ABC 453

2026-04-122026-04-25

C 题

首先想到的是贪心策略，但wa一发以后发现贪心是错误的，看到n很小，所以这道题变成了一道搜索/回溯/二进制枚举

回溯写法

void solve1() {
  int n;
  cin >> n;
  vector<int> l(n);
  for (auto & x : l) cin >> x;
  int cnt = 0;
  int ans = 0;
  double cur = 0.5;
  auto traceback = [&](auto& self, int i) ->void {
    debug(i);
    if (i == n) {
      ans = max(cnt, ans);
      return; // 别忘了return
    }
    if (cur * (cur + l[i]) < 0) cnt ++;
    cur += l[i];
    self(self, i + 1);
    if (cur * (cur - l[i]) < 0) cnt --;
    cur -= l[i];

    if (cur * (cur - l[i]) < 0) cnt ++;
    cur -= l[i];
    self(self, i + 1);
    if (cur * (cur + l[i]) < 0) cnt --;
    cur += l[i];
  };
  traceback(traceback, 0); // 要从0开始啊
  cout << ans << endl;
}

二进制枚举写法

// 二进制枚举的血法
void solve2() {
  int n;
  cin >> n;
  vector<int> l(n);
  for (auto & x : l) cin >> x;

  int ans = 0;
  for (int st = 0; st < (1 << n); st ++){
    i64 cur = 0;
    int cnt = 0;
    for (int i = 0; i < n; i ++) {
      if (st >> i & 1) {
        if (cur < 0 && cur + l[i] >= 0) cnt ++;
        cur += l[i];
      } else {
        if (cur >= 0 && cur -l[i] < 0) cnt ++;
        cur -= l[i];
      }
    }
    ans = max(ans, cnt);
  }
  cout << ans << endl;
}

D 题

有很多条件的搜索，看着就头疼，本题的特殊点在于：

• 需要输出起点到终点的路径
• 有两个特殊的点，要求：不能和前一次方向一样、需要和之前方向一样

所以状态在记录的时候需要保存上一次的方向是什么

找到终点后一路回溯回起点

#include <bits/stdc++.h>
#ifndef DEBUG
#define debug(x)
#endif
using namespace std;
using i64 = int64_t;
#define endl '\n'

const vector<pair<int, int>> dir = {
  {1, 0}, {0, 1}, {-1, 0}, {-1, -1}
};

const string dirc = "DRUL";

void solve1() {
  int h, w;
  cin >> h >> w;
  auto maze = vector<string>(h);
  auto vis = vector(h, vector(w, 0));
  for (int i = 0; i < h; i ++) {
    cin >> maze[i];
  }
  using pii = pair<int, int>;
  pii start, end;
  set<pii> forward, free, turn, stop;
  for (int i = 0; i < h; i ++) {
    for (int j = 0; j < w; j ++) {
      if (maze[i][j] == 'S') start = {i, j};
      else if (maze[i][j] == 'G') end = {i, j};
      else if (maze[i][j] == '#') stop.emplace(i, j);
      else if (maze[i][j] == '.') free.emplace(i, j);
      else if (maze[i][j] == 'x') turn.emplace(i, j);
    }
  }

  deque<int> dq;
  int flag = 0;
  vector<int> ans;

  auto is_valid = [&](int x, int y) {
    return 0 <= x && x < w && 0 <= y && y < h;
  };


  auto dfs = [&](auto &self, int x, int y, int step, int prev_dir) {
    int fforward = 0, fturn = 0;
    if (!is_valid(x, y)) return;
    if (vis[x][y]) return;
    vis[x][y] = 1;

    if (maze[x][y] == 'G') {
      ans.resize(dq.size());
      for (int i = 0; i < dq.size(); i ++) {
        ans[i] = dq[i];
      }
      flag = 1;
    } else if (maze[x][y] == '#') {
      return;
    } else if (maze[x][y] == '.') {
      ;
    } else if (maze[x][y] == 'x') {
      fforward = 1;
    } else if (maze[x][y] == 'o') {
      fturn = 1;
    }

    // 转移
    for (int i = 0; i < 4; i ++) {
      if (fforward == 1) {
        if (i != prev_dir) continue;
      } else if (fturn == 1) {
        if (i == prev_dir) continue;
      }
      auto [dx, dy] = dir[i];
      dq.emplace_back(i);
      self(self, x + dx, y + dy, step + 1, i);
      dq.pop_back();
    }

  };
  dfs(dfs, start.first, start.second, 0, -1);

  if (flag == 0) cout << "No\n";
  else {
    cout << "Yes\n";
    for (auto i : ans) {
      cout << dirc[i];
    }
    cout << endl;
  }
}

void solve2() {
  int n, m;
  cin >> n >> m;
  vector<string> maze(n);
  for (auto &s : maze) cin >> s;
  int sx, sy, ex, ey;
  for (int i = 0; i < n; i ++) {
    for (int j = 0; j < m; j ++) {
      if (maze[i][j] == 'S') sx = i, sy = j;
    }
  }
  vector<vector<array<tuple<int, int, int>, 4>>> pre(n, vector<array<tuple<int, int, int>, 4>>(m));
  queue<tuple<int, int, int>> q;
  q.emplace(sx, sy, 0);
  q.emplace(sx, sy, 1);
  q.emplace(sx, sy, 2);
  q.emplace(sx, sy, 3);
  array<pair<int, int>, 4> dirs = {{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}};
  string dirs_str = "RLDU";
  vector<vector<array<bool, 4>>> vis(n, vector<array<bool, 4>>(m, {false, false}));
  while (!q.empty()) {
    auto [x, y, dir] = q.front();
    q.pop();
    if (maze[x][y] == 'G') {
      cout << "Yes" << '\n';
      string ans;
      while (x != sx || y != sy) {
        ans += dirs_str[dir];
        tie(x, y, dir) = pre[x][y][dir];
      }
      reverse(ans.begin(), ans.end());
      cout << ans << '\n';
      return;
    }
    for (int i = 0; i < 4; i ++) {
      if (maze[x][y] == 'o' && i != dir) continue;
      if (maze[x][y] == 'x' && i == dir) continue;
      int nx = x + dirs[i].first, ny = y + dirs[i].second;
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (maze[nx][ny] == '#') continue;
      if (vis[nx][ny][i]) continue;
      q.emplace(nx, ny, i);
      vis[nx][ny][i] = true;
      pre[nx][ny][i] = {x, y, dir};
    }
  }
  cout << "No" << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;
  // cin >> t;
  while (t --) {
    solve2();
  }
}