SDUT 2021 Winter Individual Contest - M

博主： spirit
发布时间：2021 年 02 月 22 日
1660 次浏览
暂无评论
2196字数
分类： VJ训练赛

# [Benelux Algorithm Programming Contest (BAPC) preliminaries 2016](https://open.kattis.com/problem-sources/Benelux%20Algorithm%20Programming%20Contest%20(BAPC)%20preliminaries%202016)

## [A - Block Game](https://open.kattis.com/problems/blockgame2)

- 题意：有 $a \ b$ 两个数字，两人轮流操作，每次操作可以从较大值中减去较小值的若干倍，若大小相同则由玩家任意选择。给出这两个数字，问先手是否必赢。
- 思路：如果 $a \mod b = 0$ ，则先手必赢；如果 $a > b$ ，则先手只能操作为 $(a - b, b)$ ；如果 $a > 2b$ ，则先手必赢，假如 $(b, a \mod b)$ 为必赢态，那么先手可以操作为 $(b, a \mod b + b)$ ，将必赢态留给自己，否则先手操作为 $(b, a \mod b)$ ，后手必输。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  
  int main(int argc, char const *argv[]) {
      LL n, m;
      cin >> n >> m;
      if (n > m) swap(n, m);
      bool flag = true;
      while (true) {
          if (m % n == 0) break;
          if (m > 2 * n) break;
          m -= n;
          if (m <= n) swap(n, m);
          flag = !flag;
      }
      if (flag)
          puts("win");
      else
          puts("lose");
      return 0;
  }
  ```

## [B - Chess Tournament](https://open.kattis.com/problems/chesstournament)

- 题意：共有 $n$ 个选手，给出 $m$ 组关系，$a > b$ 表示 $a$ 选手的实力比 $b$ 选手实力高，$a = b$ 表示两人实力相当，问是否存在矛盾。
- 思路：先用并查集把实力相当的选手缩为一个点，然后将所有大于关系建边，通过拓扑排序判断是否存在矛盾。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 5e4 + 10;
  vector<pair<int, int>> v;
  vector<int> g[N];
  int s[N], d[N];
  
  void init(int n) {
      for (int i = 0; i <= n; i++) s[i] = i;
  }
  
  int Find(int u) {
      if (s[u] == u) return u;
      return s[u] = Find(s[u]);
  }
  
  void Union(int x, int y) {
      x = Find(x);
      y = Find(y);
      if (s[x] != y) s[x] = y;
  }
  
  bool check(int n) {
      for (auto it : v) {
          int x = Find(it.first);
          int y = Find(it.second);
          if (x == y) return false;
          g[x].push_back(y);
          d[y]++;
      }
      queue<int> q;
      int cnt = 0;
      for (int i = 0; i < n; i++)
          if (!d[i]) q.push(i);
      while (!q.empty()) {
          int u = q.front();
          q.pop();
          cnt++;
          for (auto it : g[u]) {
              d[it]--;
              if (!d[it]) q.push(it);
          }
      }
      return cnt == n;
  }
  
  int main(int argc, char const *argv[]) {
      int n, m, x, y;
      char op[2];
      cin >> n >> m;
      init(n);
      for (int i = 1; i <= m; i++) {
          scanf("%d %s %d", &x, op, &y);
          if (*op == '=') {
              Union(x, y);
          } else {
              v.push_back({x, y});
          }
      }
      if (check(n))
          puts("consistent");
      else
          puts("inconsistent");
      return 0;
  }
  ```

## [C - Completing the Square](https://open.kattis.com/problems/completingthesquare)

- 题意：给出矩形的三个点，求第四个点坐标。
- 思路：先用勾股定理判断点的相对位置，然后通过向量求解即可。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  
  int get_dist(int x1, int y1, int x2, int y2) {
      int dx = x1 - x2;
      int dy = y1 - y2;
      return dx * dx + dy * dy;
  }
  
  int main(int argc, char const *argv[]) {
      int x[5], y[5], len[5];
      for (int i = 1; i <= 3; i++) scanf("%d %d", &x[i], &y[i]);
      len[1] = get_dist(x[1], y[1], x[2], y[2]);
      len[2] = get_dist(x[2], y[2], x[3], y[3]);
      len[3] = get_dist(x[1], y[1], x[3], y[3]);
      if (len[1] + len[2] == len[3]) swap(x[1], x[2]), swap(y[1], y[2]);
      if (len[2] + len[3] == len[1]) swap(x[1], x[3]), swap(y[1], y[3]);
      x[4] = x[2] - x[1] + x[3];
      y[4] = y[2] - y[1] + y[3];
      cout << x[4] << ' ' << y[4] << '\n';
      return 0;
  }
  ```

## [F - Memory Match](https://open.kattis.com/problems/memorymatch)

- 题意：类似于连连看的游戏，最初所有的牌均反面向上，每张牌上有一个图案，每个图案出现两次。两人轮流操作，每次依次翻开两张牌，若图案相同则积一分，且牌面保持向上，获得额外一回合；否则牌面翻回反面向上，下一个玩家操作。给出前 $k$ 次的操作记录，接下来到你操作，问你有把握得到的分数是多少。
- 思路：首先已知的相同牌可以直接翻开。如果剩下的已知牌和未知牌数量相同，可以翻一张未知牌，再去已知牌中找相同图案，这样可以得到剩下的所有分数。如果只剩两张未知牌，也可以直接翻开，积一分。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 1005;
  map<string, int> mp;
  vector<int> num[N];
  int book[N], idx;
  
  int ID(string &s) {
      int id = mp[s];
      if (!id) {
          mp[s] = ++idx;
          id = idx;
      }
      return id;
  }
  
  int main(int argc, char const *argv[]) {
      ios::sync_with_stdio(false);
      int n, k, a, b, cnt = 0, res = 0;
      string s1, s2;
      cin >> n >> k;
      for (int i = 0; i < k; i++) {
          cin >> a >> b >> s1 >> s2;
          int id1 = ID(s1), id2 = ID(s2);
          if (id1 == id2) {
              cnt += 2;
              book[a] = book[b] = -1;
              num[id1].clear();
          } else {
              if (!book[a]) {
                  book[a] = id1;
                  num[id1].push_back(a);
              }
              if (!book[b]) {
                  book[b] = id2;
                  num[id2].push_back(b);
              }
          }
      }
      for (int i = 1; i <= idx; i++) {
          if ((int)num[i].size() == 2) {
              res++;
              book[num[i][0]] = book[num[i][1]] = -1;
              num[i].clear();
          }
      }
      int num1 = 0, num2 = 0;
      for (int i = 1; i <= n; i++) {
          if (book[i] == 0)
              num2++;
          else if (book[i] > 0)
              num1++;
      }
      if (num1 == num2) res += num1;
      if (!num1 && num2 == 2) res++;
      printf("%d\n", res);
      return 0;
  }
  ```

## [G - Millionaire Madness](https://open.kattis.com/problems/millionairemadness)

- 题意：给出一个 $n \times m$ 的矩阵，左上角为入口，右下角为出口，每个位置都有一个高度，由高处向低处可以直接自由落体，由低处到高处需要有大于等于高度差的梯子。在每个位置你都可以在不超过地图边界的情况下向上下左右四个方向移动，问最少需要多长的梯子。
- 思路：如果将到 $p$ 点的路径长度定义为走到 $p$ 点需要的梯子长度，可以发现任意一条路径上，路径长度都是非递减的，这恰好符合 $Dijkstra$ 算法，因此直接运行一遍该算法即可。（队友的思路是二分答案，$bfs$ 时把路径长度大于 $len$ 的边视为不通即可）。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 1e3 + 10;
  int a[N][N], dp[N][N];
  int main(int argc, char const *argv[]) {
      int n, m;
      cin >> n >> m;
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
      memset(dp, 0x3f, sizeof dp);
      dp[1][1] = 0;
      set<pair<int, pair<int, int>>> se;
      se.insert({0, {1, 1}});
      int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
      while (!se.empty()) {
          auto p = *se.begin();
          se.erase(se.begin());
          int x = p.second.first, y = p.second.second;
          for (int i = 0; i < 4; i++) {
              int u = x + dx[i], v = y + dy[i];
              if (u < 1 || u > n || v < 1 || v > m) continue;
              int val = max(dp[x][y], a[u][v] - a[x][y]);
              if (val < dp[u][v]) {
                  se.erase({dp[u][v], {u, v}});
                  dp[u][v] = val;
                  se.insert({dp[u][v], {u, v}});
              }
          }
      }
      cout << dp[n][m] << '\n';
      return 0;
  }
  ```

## [I - Rock Band](https://open.kattis.com/problems/rockband)

- 题意：乐队有 $m$ 个成员，一次演出候选的演出歌曲有 $s$ 首，每个成员对于不同歌曲的喜爱程度不同，对于任意一位成员，在要求他演奏歌曲 $x$ 时，必须满足所有他喜爱值高于歌曲 $x$ 的歌曲都在演奏名单上。同时演奏名单中歌曲的数量越少越好，求最少需要演奏多少歌曲，并给出相应的名单。
- 思路：假如要演奏 $n$ 首歌曲，必须满足 $n$ 首歌曲恰好是每一位成员最喜欢的 $n$ 首歌。由于每首歌的编号都是不同的，找到第一个前缀和的值相同的位置即可。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 1e6 + 10;
  vector<int> a[N];
  int ans[N];
  LL sum[N];
  
  int main(int argc, char const *argv[]) {
      int n, m, res, x;
      cin >> n >> m;
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= m; j++) {
              scanf("%d", &x);
              a[i].push_back(x);
          }
      for (int i = 0; i < m; i++) {
          set<int> se;
          for (int j = 1; j <= n; j++) {
              sum[j] += a[j][i];
              se.insert(sum[j]);
          }
          if (se.size() == 1) {
              res = i + 1;
              break;
          }
      }
      for (int i = 1; i <= res; i++) ans[i] = a[1][i - 1];
      sort(ans + 1, ans + res + 1);
      cout << res << '\n';
      for (int i = 1; i <= res; i++)
          printf("%d%c", ans[i], i == res ? '\n' : ' ');
      return 0;
  }
  ```

## [K- Translators' Dinner](https://open.kattis.com/problems/translatorsdinner)

- 题意：有 $n$ 中语言和 $m$ 个翻译，每个翻译会两种语言，题目保证每两种语言之间都可以互相翻译，没有两个翻译会的语言是完全一样的。现在聚餐时只有两人桌，要求坐在一桌的两位翻译必须有一门共同的语言。问能否成功匹配？如果可以给出一个可行的匹配。
- 思路：将语言视为节点，翻译视为边建图，由于语言之间可以互相翻译，所以得到的一定是连通图。对于该图求一个生成树，每次对于该树的叶子结点 $p$ 操作，假如与 $p$ 相连的非树上的边有偶数个，则让这些边两两一对即可，然后在树上把 $p$ 点删除；如果是奇数条边，对于剩下的一条边，让它和生成树与 $p$ 相连的那条边匹配即可，将 $p$ 点从树中删除，并且将匹配的边从图中删除。由于图是连通的，且树删除叶子结点后还是树，所以只要边的数量是偶数就一定可以匹配成功，反之不成功。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 105, M = 205;
  vector<pair<int, int>> g[N], ans;
  int book[M], s[N], d[N];
  
  void init(int n) {
      for (int i = 0; i <= n; i++) s[i] = i;
  }
  
  int Find(int u) {
      if (s[u] == u) return u;
      return s[u] = Find(s[u]);
  }
  
  int main(int argc, char const *argv[]) {
      int n, m;
      cin >> n >> m;
      init(n);
      for (int i = 0; i < m; i++) {
          int x, y;
          scanf("%d %d", &x, &y);
          int u = Find(x), v = Find(y);
          if (u != v) {
              s[u] = v;
              book[i] = -1;
              d[x]++, d[y]++;
          }
          g[x].push_back({y, i});
          g[y].push_back({x, i});
      }
      if (m & 1) {
          puts("impossible");
      } else {
          queue<int> q;
          for (int i = 0; i < n; i++)
              if (d[i] == 1) q.push(i);
          while (!q.empty()) {
              int u = q.front();
              q.pop();
              int last = -1, id, v;
              for (auto it : g[u]) {
                  if (book[it.second] == 0) {
                      if (last == -1) {
                          last = it.second;
                      } else {
                          ans.push_back({last, it.second});
                          book[last] = book[it.second] = 1;
                          last = -1;
                      }
                  } else if (book[it.second] == -1) {
                      id = it.second;
                      v = it.first;
                  }
              }
              book[id] = 0;
              d[v]--;
              if (d[v] == 1) q.push(v);
              if (last != -1) {
                  ans.push_back({last, id});
                  book[id] = book[last] = 1;
              }
          }
          for (auto it : ans) printf("%d %d\n", it.first, it.second);
      }
      return 0;
  }
  ```

最后修改：2021 年 02 月 22 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

SDUT 2021 Winter Individual Contest - M

spirit • 2021 年 02 月 22 日