CSP-J 2026 算法比赛题解

struct Seat {
  int no;
  int row;
  int col;
  int side;  // 0 在过道左侧，1 在过道右侧
  void Parse(char* c, char* s) {
    no = (c[0] - '0') * 10 + (c[1] - '0');
    row = (s[0] - '0') * 10 + (s[1] - '0');
    col = s[2] - 'A';
    if (s[2] == 'D') {
      col = 'E' - 'A';  // ABCDF -> 0 1 2 4 5，中间空一格表示过道
    }
    if (col < 3) {
      side = 0;
    } else {
      side = 1;
    }
  }
} A, B;

char c1[5], s1[5], c2[5], s2[5];
string ans;

int Dis(int a, int b) { return abs(a - b); }
void Parse() {
  A.Parse(c1, s1);
  B.Parse(c2, s2);
  ans.resize(4, '0');
  if (A.no != B.no) return;
  ans[0] = '1';
  if (A.row != B.row) return;
  ans[1] = '1';
  if (A.side != B.side) return;
  ans[2] = '1';
  if (Dis(A.col, B.col) > 1) return;
  ans[3] = '1';
}

void Solver() {  //
  scanf("%s%s%s%s", c1, s1, c2, s2);
  Parse();
  printf("%s\n", ans.c_str());
}

int n;
vector<pair<ll, char>> nums;
ll v;
char str[2];

ll SolverAns() {
  if (n == 1) return 0;
  ll ans = 0;
  int l = 0, r = n - 1;
  while (l < r) {
    auto& [ln, lc] = nums[l];
    auto& [rn, rc] = nums[r];
    ll lrMin = min(ln, rn);
    if (lc != rc) {
      // 两端字符不同，这 lrMin 对都要各改 1 个
      ans += lrMin;
    }
    ln -= lrMin;
    rn -= lrMin;
    if (ln == 0) l++;
    if (rn == 0) r--;
  }
  return ans;
}

void Solver() {  //
  scanf("%d", &n);
  nums.resize(n);
  for (int i = 0; i < n; i++) {
    scanf("%lld%s", &v, str);  // 字符串输入，避免空白问题
    nums[i] = {v, str[0]};
  }
  printf("%lld\n", SolverAns());
}

int n, m;
vector<ll> nums;
void Solver() {  //
  scanf("%d%d", &n, &m);
  nums.resize(n);
  for (int i = 0; i < n; i++) {
    scanf("%lld", &nums[i]);
  }
  sort(nums.begin(), nums.end(), greater<ll>());
  for (int b = 31; b >= 0; b--) {
    if (nums[0] & (1LL << b)) {
      // 第 b 位有 1，检查是否至少 m 个数的第 b 位也是 1
      int i = 0;
      while (i < n && (nums[i] & (1LL << b))) {
        i++;
      }
      if (i >= m) {
        // 够了，后面的数字第 b 位都是 0，选择不会更优，都删除
        while (nums.size() > i) {
          nums.pop_back();
        }
      } else {
        // 不够，这一位怎么选择都是 0，清理这一位的 1
        while (i > 0) {
          i--;
          nums[i] ^= (1LL << b);
        }
        sort(nums.begin(), nums.end(), greater<ll>());
      }
    }
    if (nums.size() == m) {
      break;  // 恰好剩余 m 个，必须都选择
    }
  }
  ll ans = nums[0];
  for (int i = 1; i < m; i++) {
    ans &= nums[i];
  }
  printf("%lld\n", ans);
}

void ForceSolver() {  // 枚举起始位置，复杂度 O(n*m)
  for (int i = 0; i < n; i++) {
    int cur = i;
    while (cur < n) {
      const int v = nums[cur];
      ans[v]++;
      cur = lastPos[v] + 1;
    }
  }
}

int n, m;
vector<int> nums;
vector<int> lastPos;  // 每种点数的最后一次出现位置

vector<int> ans;
vector<int> dp;  // dp[i]：有多少局游戏的游标落在位置 i
void SkipSolver() {
  // 利用动态规划，避免重复运算
  for (int i = 0; i < n; i++) {
    const int v = nums[i];  // 作为第一张，肯定会保留下来
    const int last = lastPos[v];
    dp[i]++;
    if (last == i) {  // v 的最后一次出现，更新答案
      ans[v] = dp[i];
      dp[last + 1] += dp[i];
    } else {  // v 还会再出现，状态合并到 last
      dp[last] += dp[i];
    }
  }
}

void Solver() {
  scanf("%d%d", &n, &m);
  nums.resize(n);
  lastPos.resize(m + 1, n);
  dp.resize(n + 1, 0);
  for (int i = 0; i < n; i++) {
    scanf("%d", &nums[i]);
    lastPos[nums[i]] = i;
  }
  ans.resize(m + 1, 0);
  SkipSolver();
  for (int i = 1; i <= m; i++) {
    printf("%d%c", ans[i], i == m ? '\n' : ' ');
  }
}