Codeforces Round 1086 (Div. 2)复盘

总结依旧不会看题题目很多重点信息遗漏前两个题目做的很顺就做了ABD1C题目实在找不出规律还是得要看除法的性质也是第一次遇到这种除法题目一下子看蒙了A. Bingo Candies这个题目第一眼看上去就是要统计各个数字出现的个数因为n的大小很少所以说表格中出现的数都很少所以说要设一个大小为n*n1的桶来统计个数这里我没看题设了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; vectorint 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这个题目最开始没有想到什么好的方法但是看到nm都是小于5000数据量并不大就直接模拟去做了因为只有一个地方是我求的值所以说我维护了一个p这里转化成为数组下标就是-1然后如果pk的话就减去p的位置的价值pk的话就是减去前面最小的一个就行#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--; vectorint 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; vectorstring 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; } } } } } vectorpairint, 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; } vectorint parent(n); for (int i 0; i n; i) { parent[i] i; } functionint(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; }