Loading... 退役选手娱乐场，做到了F结果没出C，乐。 # A. Food for Animals 水题不说了 # B. Make It Increasing ## 题意 给定一个数列，每次操作可以把某个数$a_i$变成$\lfloor \frac {a_i}{ 2}\rfloor$，问最少多少次操作可以让原数列严格增。 ## 分析 从后往前贪心就好了。如果中途有$0$就Impossible，否则计数即可。 ## 代码 ```cpp int t, n; vector<int> a; int main() { cin >> t; while (t--) { cin >> n; a.clear(); FOR(i, 1, n) { int tmp; cin >> tmp; a.pb(tmp); } ll ans = 0; bool ok = true; if (a.back() == 0) { if (a.size() == 1) cout<<0<<endl; else cout<<"-1"<<endl; continue; } for (int i = a.size()-2; i >= 0; i--) { if (a[i] == 0 && i != 0) { ok = false; break; } while (a[i] >= a[i+1]) { a[i] /= 2; ans++; } if (a[i] == 0 && i != 0) { ok = false; break; } } if (!ok) cout<<-1<<endl; else cout<<ans<<endl; } return 0; } ``` # C. Detective Task 寄。赛后终于想明白了。 ## 题意 一群人依次进入房间，然后有幅画在房间里被偷了，每个人会给出自己离开房间时房间里是否有画。可能的答案是1（有）、0（没有）或者？（不记得了）。好人一定说真话，小偷只有一个，可能任意回答。求有多少人可能是小偷。 ## 分析 如果报1：要么它自己是小偷，要么小偷一定在后面 如果报0：要么它自己是小偷，要么小偷一定在前面 所以小偷一定在最近的10中间，那么就取这一段长度就好了。 不会出现10交替出现的情况，因为好人一定说真话。 ## 代码 ```cpp int t; int main() { cin >> t; while (t--) { string str; cin >> str; if (str.front() == '0' || str.back() == '1') { cout << 1 << endl; continue; } bool ok = false; for (int i = 0; i < str.size(); i++) if (str[i] == '0') { int j; for (j = i - 1; j >= 0; j--) if (str[j] == '1' || j == 0) break; cout << i - j + 1 << endl; ok = true; break; } if (ok) continue; for (int i = str.size() - 1; i >= 0; i--) if (str[i] == '1') { cout<<str.size()-i<<endl; ok = true; break; } if (ok) continue; cout << str.size() << endl; } return 0; } ``` # D. Vertical Paths ## 题意 求树的最少链剖分数量，并输出方案。 ## 分析 每条链显然贪心dfs即可。然后同时用队列维护**不在当前链上的兄弟节点**，然后整体bfs即可。相当于bfs套dfs。 ## 代码 ```cpp int t, n; int fa[N]; vector<int> sons[N]; int rt; vector<vector<int>> ans; queue<int> q; void dfs(int p) { ans.back().push_back(p); for (int i = 1; i < sons[p].size(); i++) q.push(sons[p][i]); if (sons[p].size() > 0) dfs(sons[p].front()); } void print() { cout << ans.size() << endl; for (auto ar : ans) { cout << ar.size() << endl; for (auto v : ar) cout << v << ' '; cout << endl; } cout << endl; } void f() { ans.clear(); q.push(rt); while (!q.empty()) { int now = q.front(); q.pop(); ans.push_back(vector<int>()); dfs(now); } print(); } int main() { cin >> t; while (t--) { cin >> n; FOR(i, 1, n) sons[i].clear(); FOR(i, 1, n) { cin >> fa[i]; if (fa[i] == i) rt = i; else sons[fa[i]].pb(i); } f(); } return 0; } ``` # E. Replace With the Previous, Minimize ## 题意 给定一个字符串，$k$次操作，每次可以把字符串中的**全部特定字母**-1，问能够得到的字典序最小的结果是什么。 ## 分析 感觉做法非常显然。 因为是字典序，所以肯定要从第一位开始贪心。我们维护**已经处理过的最大字母**，这个值一开始是$a$。然后对于每个位置，当前开销就是$now-a$，如果这个值大于$k$，那么就把当前字母变为$now-k$，然后结束。否则当前字母变为$a$，然后更新标记。 每一个字母处理过后，字符串中全部相同字母可以打标记（已经变成了什么），然后等访问到的时候再处理。但这样没必要，直接暴力去做是$O(n)$的，这个界属于经典摊还分析。 ## 代码 ```cpp int t; int n, k; string str; int main() { cin >> t; while (t--) { int n, k; cin >> n >> k >> str; char up = 'a'; for (int i = 0; i < str.size() && k > 0; i++) { char v = str[i]; if (v == 'a') continue; if (k >= v - up) { k -= v - up; up = v; for (auto &x : str) if (x <= v) x = 'a'; } else { char to = v - k; k = 0; for (auto &x : str) if (x <= v && x > to) x = to; } } cout << str << endl; } return 0; } ``` # F. Vlad and Unfinished Business 赢！天梯赛领先cf一个版本！ ## 题意 给定一棵树和起点$x$，终点$y$，要求从$x$走到$y$，但中途必须要去访问某些点$\{a\}$，问最小路径长。 ## 分析 几乎是天梯赛原题。那个题答案是$2*\sum dis - \max\{dis\}$，这个题只要知道可以把$y$给标记进必经点，那么答案就是$2*\sum dis - dis_y$。这个分析是容易的。所以直接原本做法即可。统计往返路径长度可能算个难点，我用的方法是在每个点上记录子树上所有的往返必经长度，容易想到是 $$ len_{rt}= \sum_{s\in sons_{rt}} (len_s+2) $$ 其他没有什么困难的。 ## 代码 ```cpp #define N 200005 int t, n, k, x, y; vector<int> nxt[N]; int hei[N], len[N]; set<int> td; bool dfs(int p, int h = 0, int fa = -1) { hei[p] = h; bool ans = (td.find(p) != td.end()); for (auto v : nxt[p]) { if (v == fa) continue; if (dfs(v, h + 1, p)) len[p] += len[v] + 2, ans = true; } return ans; } int main() { cin >> t; while (t--) { cin >> n >> k >> x >> y; FOR(i, 1, n) { nxt[i].clear(); hei[i] = 0, len[i] = 0; } td.clear(); FOR(i, 1, k) { int tmp; cin >> tmp; td.insert(tmp); } td.insert(y); FOR(i, 1, n - 1) { int u, v; cin >> u >> v; nxt[u].push_back(v); nxt[v].push_back(u); } dfs(x); ll ans = len[x] - hei[y]; cout << ans << endl; } return 0; } ``` # G. Sorting Pancakes $n^4$的DP不知道能不能放过。大概有个$n^3$的DP做法，没有看懂，等学会了再补。 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏