选择题一堆不会，开摆。算法ak。

第一题

给一个井字棋的局面，问a和b谁赢了，亦或是平局

#include <bits/stdc++.h>
using namespace std;
void solve() {
  string s[3];
  for (auto &x : s) cin >> x;
  auto valid = [&](int x, int y) { return x >= 0 && x < 3 && y >= 0 && y < 3; };
  int ans = 0;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (s[i][j] == 'o') {
        if (valid(i - 1, j) && valid(i + 1, j) && s[i - 1][j] == '*' &&
            s[i + 1][j] == '*')
          ans |= 1;
        if (valid(i, j - 1) && valid(i, j + 1) && s[i][j - 1] == '*' &&
            s[i][j + 1] == '*')
          ans |= 1;
      } else if (s[i][j] == '*') {
        if (valid(i - 1, j) && valid(i + 1, j) && s[i - 1][j] == 'o' &&
            s[i + 1][j] == 'o')
          ans |= 2;
        if (valid(i, j - 1) && valid(i, j + 1) && s[i][j - 1] == 'o' &&
            s[i][j + 1] == 'o')
          ans |= 2;
      }
    }
  }
  if(ans==2) puts("yukari");
  else if(ans==1)puts("kou");
  else puts("draw");
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

第二题

某人有不超过20个状态，然后有m种药，每个药能去掉某些状态，同时增加某些状态。现在按照某个顺序喝药，问喝了每种药之后有多少个状态。

#include <bits/stdc++.h>
using namespace std;
int cal(string s) {
  int ret = 0;
  for (auto x : s) {
    ret <<= 1;
    if (x == '1') ret++;
  }
  return ret;
}
void solve() {
  int n;
  cin >> n;
  int now = 0;
  string s;
  cin >> s;
  now = cal(s);
  int m;
  cin >> m;
  vector<array<int, 2>> v(m);
  for (auto &x : v) {
    for (auto &t : x) {
      cin >> s;
      t = cal(s);
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int x;
    cin >> x;
    x--;
    now &= ~v[x][0];
    now |= v[x][1];
    cout << __builtin_popcount(now) << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

第三题

n*m的图，初始在左上角，每次操作可以往右或往下或往右下行动若干格，问要多少次操作才能到右下角。

一开始看错题了，以为可以往左上走，然后写了个用set优化的bfs，然后发现只能往右下走，就纯bfs了。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
void solve() {
  int n, m;
  cin >> n >> m;
  vector<string> v(n);
  for (auto &x : v) cin >> x;
  vector<vector<int>> dp(n, vector<int>(m, INF));
  dp[0][0] = 0;
  queue<array<int, 2>> q;
  q.push({0, 0});
  while (q.size()) {
    auto [i, j] = q.front();
    q.pop();
    for (int k = i + 1; k < n && v[k][j] != '*'; k++) {
      if (dp[k][j] <= dp[i][j]) break;
      dp[k][j] = dp[i][j] + 1;
      q.push({k, j});
    }
    for (int k = j + 1; k < m && v[i][k] != '*'; k++) {
      if (dp[i][k] <= dp[i][j]) break;
      dp[i][k] = dp[i][j] + 1;
      q.push({i, k});
    }
    for (int k = 1; i + k < n && j + k < m && v[i + k][j + k] != '*'; k++) {
      if (dp[i + k][j + k] <= dp[i][j]) break;
      dp[i + k][j + k] = dp[i][j] + 1;
      q.push({i + k, j + k});
    }
    if (dp.back().back() != INF) break;
  }
  int ans = dp.back().back();
  if (ans == INF) ans = -1;
  cout << ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}