C. Have Your Cake and Eat It Too
题目：
思路：
暴力，太暴力了
简化一下题意，就是让我们在a,b,c三个数组中选3段无重复的连续区间，使得每段区间和都是sum/3，其中sum是每个数组的和，并且保证每个数组和相同
既然要选区间，那么最后肯定是如下图所示的选法
即一段左边，一段中间，一段右边
但是谁中间谁左边谁右边呢？
无所谓，暴力枚举会拯救一切，我们直接排列组合一下即可，发现最多就6种情况，所以我们可以枚举
那么如何选区间呢？我们可以用两个指针，左指针从左边开始累加，如果总和大于sum/3那就停止，右指针同理，最后 l~r 就是中间的和了，然后判断一下是否可行即可，如果可以就输出，否则看下一种情况 ，如果都不行就输出-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"
int n;
void Print(const vector<pair<int, int>>& ans)
{cout << ans[0].first << " " << ans[0].second << " ";cout << ans[1].first << " " << ans[1].second << " ";cout << ans[2].first << " " << ans[2].second << endl;
}
bool check(const int& sum,const vector<int>& a, const vector<int>& b, const vector<int>& c,const int& o, const int& t, const int& s)
{vector<pair<int, int>> ans(3, { 0,0 });int l = 1, r = n;int sa = 0, sb = 0, sc = 0;while (sa < sum){sa += a[l++];}while (sc < sum){sc += c[r--];}for (int i = l; i <= r; i++){sb += b[i];}if (sa >= sum && sb >= sum && sc >= sum){ans[o-1] = { 1,l-1};ans[t-1] = { l,r };ans[s-1] = { r+1,n};Print(ans);return true;}return false;
}void solve()
{cin >> n;vector<int> a(n+1), b(n+1), c(n+1);int sum = 0;for (int i = 1; i <= n; i++){cin >> a[i];sum += a[i];}for (int i = 1; i <= n; i++){cin >> b[i];}for (int i = 1; i <= n; i++){cin >> c[i];}sum = (sum + 2) / 3;if (check(sum, a, b, c, 1, 2, 3))return;if (check(sum, a, c, b, 1, 3, 2))return;if (check(sum, b, a, c, 2, 1, 3))return;if (check(sum, b, c, a, 2, 3, 1))return;if (check(sum, c, b, a, 3, 2, 1))return;if (check(sum, c, a, b, 3, 1, 2))return;cout << -1 << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}拓扑排序
题目：
思路：
题目让我们将无向边变为有向边，使得最后的图无环，那么一个显然的做法就是先看一开始是否有环，如果无的话那么一定可以，否则不行
那么我们分步来写，我们首先要判断是否是一个 有向无环图，这里我们可以使用拓扑排序
拓扑排序的步骤：找到入度为0的点，将其假如队列，然后从队列中取出点，并将其子节点的入读-1，如果其子节点减完后入读也是0，那么就将其加入队列，如此往复，如果最后能把所有点都找过一遍，说明无环，否则有环
那么判断完后我们就得到拓扑排序了，这时我们就可以将无向边按照拓扑排序的优先级直接判断了，具体操作是，对于 u v 两点，如果拓扑排序中 u 在 v 前面，那就使 u -> v，否则就是 v -> u，这样我们按照拓扑排序的顺序操作到最后一定不会有环
代码：
#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, m1, m2;cin >> n >> m1 >> m2;vector<pair<int,int>> gnone;vector<vector<int>> ghas(n+1);vector<int> d(n + 1,0);vector<int> list(n + 1, 0);for (int i = 0; i < m1; i++){int u, v;cin >> u >> v;gnone.push_back({ u,v });}for (int i = 0; i < m2; i++){int u, v;cin >> u >> v;ghas[u].push_back(v);d[v]++;}int index = -1;int cnt = 0;queue<int> q;for (int i = 1; i <= n; i++){if (!d[i])q.push(i);}while (!q.empty()){int t = q.front();list[t] = n - cnt;q.pop();cnt++;for (auto son : ghas[t]){d[son]--;if (!d[son])q.push(son);}}if (cnt < n){cout << "-1\n";return;}for (int i = 0;i < m1;i++){if (list[gnone[i].first] < list[gnone[i].second])swap(gnone[i].first, gnone[i].second);cout << gnone[i].first << " " << gnone[i].second << endl;}
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;while (t--){solve();}return 0;
}树上贪心二分
题目：
思路：
一个很显然的二分，最大值的最小值
那我们如何check呢？我们可以考虑从叶子节点往上累加，当一个点有两颗或以上的子树时，我们就要考虑贪心了，因为我们要考虑最小值，那么对于这个节点，我们就要选其所有子树中最小的那条线段，为什么？
如果我们不选最小的，假设这个节点的父亲就是根，那么线段长就是 len + 1，而选了最短的 mi + 1，其中 len > mi，显然肯定是选短的好，因此贪心成立
注意细节方面，在dfs中我们返回的是最小值，但是我们还要时刻记录最大值，比如一个节点的子树的线段分别是 4 2，而我们的 mid 是 3，那么遇到 4 的时候就要提前结束了
具体实现看代码
代码：
#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"
const int INF = 1e9;
void solve()
{int n;cin >> n;vector<vector<int>> g(n + 1);for (int i = 2; i <= n; i++){int father;cin >> father;g[father].push_back(i);}auto dfs = [&](auto dfs,int fa,int mid)->int{if (!g[fa].size()) return 0;int mx = -INF;int mi = INF;for (auto x : g[fa]){int t = dfs(dfs, x, mid);if (t == INF)return INF;mx = max(mx, t+1);if (mx > mid)return INF;mi = min(mi, t + 1);}return mi;};auto check = [&](int mid) {return dfs(dfs,1,mid) != INF;};int l = 0, r = n - 1;while (l + 1 < r){int mid = l + r >> 1;if (check(mid)){r = mid;}else{l = mid;}}cout << l+1 << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}