题解：P9938 [USACO21OPEN] Acowdemia II B - Block

归档56

题解34 未分类7 游寄6 “你需要知道的一切”系列4 博客指南3 网络前端1 闲话1

540 字

3 分钟

题解：P9938 [USACO21OPEN] Acowdemia II B

2024-08-29

2026-10-27

题解

C艹

USACO

浏览量加载中...

前言：原来的 tj 干了一堆什么建图啊之类的，但其实不要这么复杂。

注：下文中 $n$ 是各成员名字列表。

从 $K = 1$ 开整。如果情况是 $n_i < n_{i + 1}< \cdots < n_j$ ，那么显然，咱就不知道关于成员 $n_i,\cdots,n_j$ 的相对资历的信息。也许所有这帮成员都做出了相同的贡献。

但是捏，如果存在 $i$ 使得 $n_i > n_{ + 1}$ ，则成员 $n_i$ 肯定比成员 $n_{i + 1}$ 干了更多的活儿，因此所有成员 $n_1,\cdots,n_i$ 必须比成员 $n_{i + 1} \cdots n_N$ 的贡献少。换句话说，如果 $i < j$ 但 $n_i, n_{i + 1},\cdots,n_j$ 不是按字母顺序排列的，那么咱就知道 $n_i$ 肯定比 $n_j$ 资历浅了。

要是 $K > 1$ 捏？把信息怼起来不就得了？

ACCode：

1
// Problem: P9938 [USACO21OPEN] Acowdemia II B
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P9938
4
// Memory Limit: 256 MB
5
// Time Limit: 1000 ms
6
//
7
// Powered by CP Editor (https://cpeditor.org)
8

9
/*Code by Block_Fish*/
10
#include <bits/stdc++.h>
11

12
#define log printf
13
#define EPS 1e-8
14
#define INF 0x3f3f3f3f
15
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
16
#define IOS                      \
17
  ios::sync_with_stdio(false); \
18
  cin.tie(nullptr);            \
19
  cout.tie(nullptr);
20

21
using namespace std;
22

23
typedef __int128 i128;
24
typedef long long ll;
25
typedef pair<int, int> PII;
26

27
int k, n;
28
string s;
29
map<string, int> members;
30

31
template <typename T>
32

33
inline T read() {
34
  T sum = 0, fl = 1;
35
  char ch = getchar();
36
  for (; !isdigit(ch); ch = getchar())
37
    if (ch == '-') fl = -1;
38
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
39
  return sum * fl;
40
}
41

42
template <typename T>
43

44
inline void write(T x) {
45
  if (x < 0) putchar('-'), x = -x;
46
  static T sta[35];
47
  int top = 0;
48
  do { sta[top++] = x % 10, x /= 10; } while (x);
49
  while (top) putchar(sta[--top] + 48);
50
}
51

52
int main() {
53
  IOS cin >> k >> n;
54
  FOR(i, 0, n - 1)
55
  cin >> s, members[s] = i;
56
  vector<vector<char>> ans(n, vector<char>(n, '?')); // 全给我干成一个值，为了方便就用'?'
57
  FOR(i, 0, n - 1)
58
  ans[i][i] = 'B';  // 初始化一下，后面就不用搞了
59
  FOR(i, 0, k - 1) {
60
    vector<string> pub(n);
61
    FOR(j, 0, n - 1) cin >> pub[j];
62
    FOR(j, 0, n - 1) {
63
      bool flag = true;
64
      FOR(l, j + 1, n - 1) {
65
        if (pub[l - 1].compare(pub[l]) > 0) flag = false;
66
        if (!flag) {
67
          int a = members[pub[j]], b = members[pub[l]];
68
          ans[a][b] = '0';
69
          ans[b][a] = '1';  // 上面的过程
70
        }
71
      }
72
    }
73
  }
74
  FOR(i, 0, n - 1) {
75
    FOR(j, 0, n - 1) cout << ans[i][j];
76
    cout << endl;
77
  }
78
  return 0;
79
}