【CF】Day53——Codeforces Round 1023 (Div. 2) CD
C. Maximum Subarray Sum
题目：
思路：
简单题，但是我没考虑到负数
题目让我们将原来不知道的地方填充起来，然后确保最大子段和恰好为 k
我们来看看什么时候无解，显然当没填充时就存在一段最大字段和大于 k 时，那么我们无论放什么数都不可能有解
那么如何知道最大子段和呢？这里运用一个动态规划即可，我们定义 dp[i] 为前 i 个数中最长的子段和，那么就有 dp[i] = max(dp[i-1] + a[i]，a[i])，简单dp在此不做赘述
同理我们再从后往前做一次 dp，然后两次 dp 中我们时刻存储最大子段和 mx，如果 dp 完后有 mx > k，那么此时肯定是无解的，否则一定有解
为什么呢？因为题目告诉我们 a[i] 可以取 -1e18 ~ 1e18 之间的值，而原 a[i] 只能取 -1e6 ~ 1e6 的值，所以原数组的最大子段和我们可以用 -1e18 直接抵消掉，因此我们只需要找到第一个空缺的地方然后通过其左右两边的最大字段和来确定这里该放什么即可，其余地方都填 -1e18 就行
注意，由于我们的 k 是大于 0 的，因此如果这个地方左右两边有负数的话我们看成 0 即可，否则我们就取 a[i] = k - max(0LL,MXSUM[i-1]) - max(0LL,MXSUM2[i + 1])，我要同时计算左右两边的值，因为我们可以全选
代码：
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"void solve()
{int n, k;cin >> n >> k;string s;cin >> s;s = "$" + s;vector<int> a(n + 1);vector<int> MXSUM(n + 2, 0), MXSUM2(n + 2, 0);int mxsum = -1e18;for (int i = 1; i <= n; i++){cin >> a[i];if (s[i] == '0'){a[i] = -1e18;}MXSUM[i] = max(MXSUM[i - 1] + a[i], a[i]);mxsum = max({ mxsum ,MXSUM[i] });}for (int i = n; i >= 1; i--){MXSUM2[i] = max(MXSUM2[i + 1] + a[i], a[i]);mxsum = max({ mxsum ,MXSUM2[i] });}if (mxsum > k){no;return;}int flag = (mxsum == k);for (int i = 1; !flag && i <= n; i++){if (s[i] == '0'){a[i] = k - max(0LL,MXSUM[i-1]) - max(0LL,MXSUM2[i + 1]);flag = 1;break;}}if (!flag){no;return;}yes;for (int i = 1; i <= n; i++){cout << a[i] << " ";}cout << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}D. Apple Tree Traversing
题目：
思路：
代码实现不是很难，但是卡了我很久。。。
题目意思转化：我们每一次都要求得图中得最长直径，如果有相同直径的，我们就选取字典序较大的一条，然后删除，重复操作一直到图中没有一个点
那么这题其实很简单，我们只需要分三步：
①.求剩余图的直径
②.删除直径上的点
③.重复上述操作
关于第一步，求图的直径我们可以使用两次dfs，第一次顺便以一个地点找到深度最深的节点 u，然后第二次以这个节点 u 为起点再找到另一个最深的节点 v，此时 d(u，v) 就是直径
无/有向图的最长路径-图的直径 - 知乎
关于第二步删除点，由于我们已经知道了从哪个点开始能找到最长直径，那我们从这点开始遍历一遍即可，且过程中记录最深的节点 last，然后知道 last 后再做一遍 dfs 从底部开始往上走即可，记录 last 这一步我们可以放到第一步中顺带记录
关于第三步，由于我们每次删完节点后可能会将剩下的图变成多个小子图，因此我们要记录还剩下多少个节点没删除，只要还有节点，我们就要继续执行，这里使用一个 st 记录有多少个节点还活着，以及一个 used 判断这个点有没有被删除
特别的，由于可能存在不同的子图长度相同但是字典序不同的情况，比如 1 2 是一个图的，3 4 是一个图的，他们的 d(u，v) 相同，且不处于同一个图中，因此我们这时是无法根据字典序选择的，因此再所有节点都删除后我们需要 sort 一遍答案数组，防止上述情况存在
代码：
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"void solve()
{int n;cin >> n;vector<vector<int>> g(n + 1);set<int> st;st.insert(n);for (int i = 0; i < n - 1; i++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);st.insert(i + 1);}vector<bool> used(n + 1, 0);//这个点是否不在本次循环里int tot = 0;//已经用了多少个节点pair<int, pair<int, int>> tempD;vector<pair<int, pair<int, int>>> dep(n + 1);auto findlast = [&](auto& self, int now, int s, int f, int d = 1)-> void {if (used[s]){return;}int flag = 0;dep[s] = { -1,{-1,-1} };for (auto son : g[s]){if (son == f || used[son]){continue;}self(self, now, son, s, d + 1);flag = 1;if (dep[son].first + 1 > dep[s].first){dep[s].first = dep[son].first + 1;dep[s].second.second = son;dep[s].second.first = dep[son].second.first;}else if (dep[son].first + 1 == dep[s].first && dep[s].second.first < dep[son].second.first){dep[s].second.second = son;dep[s].second.first = dep[son].second.first;}}if (!flag){dep[s] = { 1,{s ,-1} };}};vector<pair<int, pair<int, int>>> res;while (tot < n){pair<int, pair<int, int>> tRes = { -1,{-1,-1 } };int i = *st.begin();findlast(findlast, i, i, i);i = dep[i].second.first;tRes = max(tRes, { dep[i].first, {max(dep[i].second.first,i),min(dep[i].second.first,i)} });findlast(findlast, i, i, i);tRes = max(tRes, { dep[i].first, {max(dep[i].second.first,i),min(dep[i].second.first,i)} });int next = tRes.second.second;findlast(findlast, next, next, next);//cout << dep[next].second.first << "??????????? " << next << endl;while (dep[next].second.second != -1){used[next] = 1;st.erase(next);//cout << next << " ";next = dep[next].second.second;}st.erase(next);used[next] = 1;//cout << next << " \n";tot += tRes.first;res.push_back(tRes);}sort(res.begin(), res.end(), greater<>());for (int i = 0; i < res.size(); i++){cout << res[i].first << " " << res[i].second.first << " " << res[i].second.second << " ";}cout << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}