Codeforces Round 1086 (Div. 2)复盘
总结
依旧不会看题，题目很多重点信息遗漏，前两个题目做的很顺，就做了A，B，D1，C题目实在找不出规律，还是得要看除法的性质，也是第一次遇到这种除法题目，一下子看蒙了
A. Bingo Candies
这个题目第一眼看上去就是要统计各个数字出现的个数，因为n的大小很少，所以说表格中出现的数都很少，所以说要设一个大小为n*n+1的桶来统计个数（这里我没看题设了n*n大小的桶，错了三次无语），他要求每一行都是不同的那就每一个数字最大数量就是n*(n-1)把前n-1列全部填满，如果超出了这个范围就不可以
#include <iostream> #include <vector> using namespace std; void solve(); int main() { int T; cin >> T; while (T--)solve(); return 0; } void solve() { int n; cin >> n; vector<int> arr(n * n + 1, 0); for (int i = 0; i < n * n; i++) { int temp; cin >> temp; arr[temp]++; } int limit = n * (n - 1); bool ok = true; for (int i = 0; i <= n * n && ok; i++) { if (arr[i] > limit)ok = false; } if (ok)cout << "Yes" << endl; else cout << "NO" << endl; }B. Cyclists
这个题目最开始没有想到什么好的方法，但是看到n，m都是小于5000，数据量并不大，就直接模拟去做了，因为只有一个地方是我求的值，所以说我维护了一个p（这里转化成为数组下标就是-1），然后如果p<k的话就减去p的位置的价值，p>=k的话就是减去前面最小的一个就行
#include <iostream> #include <vector> using namespace std; void solve(); #define forn(i,n) for(int i = 0; i < (int)n; i++) int main() { int T; cin >> T; while (T--)solve(); return 0; } void solve() { int n, k, p, m; cin >> n >> k >> p >> m; p--; vector<int> arr(n); forn(i, n)cin >> arr[i]; int res = 0; while (1) { if (p < k) { if (m - arr[p] < 0)break; m -= arr[p]; arr.push_back(arr[p]); arr.erase(arr.begin() + p); res++; p = n - 1; } else { int p_min = -1; int temp = INT_MAX; forn(i, k) { if (temp > arr[i]) { temp = arr[i]; p_min = i; } } if (m - arr[p_min] < 0)break; m -= arr[p_min]; arr.push_back(arr[p_min]); arr.erase(arr.begin() + p_min); p--; } } cout << res << endl; }D1. Tree Orientation (Easy Version)
zhe
这个题目吧，还好因为数据量很少有可行性，所以就随便想了，首先正推下来，这个单项图是从树添加方向得到的，所以说，再怎么说，节点A到节点B只能有一个通路，不可逆的，并且满足自反性，传递性，和反对称。
在代码来看如果满足自反性的话，满足可逆性质的话如果
对于所有的
就有
，对于不可逆的话
。必须满足上面三个公式才可能有树的结构。
然后满足了上面三个性质之后，要构造一个满足树的结构的双向图，对于树图来说，如果A节点可以到C节点，A节点可以到B节点，虽然肯定B可以到C但是我们不认为这是一条边，找一个A到B但是无传递性的边一定是树的边，要不然没办法到达，把这些边找出来后，看这些边是否可以成为树的结构，是否可以联通所有节点，是否有环形结构
#include <iostream> #include <vector> #include <string> #include <functional> using namespace std; void solve() { int n; cin >> n; vector<string> s(n); for (int i = 0; i < n; ++i) { cin >> s[i]; } for (int i = 0; i < n; ++i) { if (s[i][i] != '1') { cout << "No\n"; return; } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (s[i][j] == '1' && s[j][i] == '1') { cout << "No\n"; return; } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (s[i][j] == '1') { for (int k = 0; k < n; ++k) { if (s[j][k] == '1' && s[i][k] != '1') { cout << "No\n"; return; } } } } } vector<pair<int, int>> edges; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) continue; if (s[i][j] == '1') { bool direct = true; for (int k = 0; k < n; ++k) { if (k == i || k == j) continue; if (s[i][k] == '1' && s[k][j] == '1') { direct = false; break; } } if (direct) { edges.push_back(make_pair(i, j)); } } } } if (edges.size() != n - 1) { cout << "No\n"; return; } vector<int> parent(n); for (int i = 0; i < n; ++i) { parent[i] = i; } function<int(int)> find = [&](int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; }; for (int i = 0; i < edges.size(); ++i) { int u = edges[i].first; int v = edges[i].second; int pu = find(u), pv = find(v); if (pu == pv) { cout << "No\n"; return; } parent[pu] = pv; } int root = find(0); for (int i = 1; i < n; ++i) { if (find(i) != root) { cout << "No\n"; return; } } cout << "Yes\n"; for (int i = 0; i < edges.size(); ++i) { cout << edges[i].first + 1 << ' ' << edges[i].second + 1 << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { solve(); } return 0; }