D
题意：
有n天，访客逗留d 天。
有 k 项 工作，有这项 工作开始的 时间和结束的时间
问 哪一天 不同的工作数最多，那一天最多。

长度为 d 的 滑动窗口，我们记录 每一个时间点 开始的工作数量，和结束的工作数量。 加上新 加入 的点 所开始的工作，减去 离开区间的点 结束的数量。

void solve()
{int n, d, k;cin >> n >> d >> k;vector<int> a(n + 3);vector<int> b(n + 3);int x, y;while (k--){cin >> x >> y;a[x]++;b[y]++;}int mx, mn = 0;for (int i = 1; i <= d; i++){mx += a[i];}mn = mx;int ans1, ans2;ans1 = 1;ans2 = 1;int t = mx;for (int i = 2; i <= n - d + 1; i++){t -= b[i - 1];t += a[i + d - 1];if (t > mx){mx = t;ans2 = i;}if (t < mn){mn = t;ans1 = i;}}cout << ans2 << " " << ans1 << "\n";
}

E
前半边那个 在一个点汇合的有点像 百度23年的一道题
添加链接描述
两个人a b 在两个点出发，到N。a走一步体力消耗为TE,b走一步体力消耗为TF ，如果两个人汇合，那么两个人走一步的体力消耗和为TE+TF-s.问两个人到N点的最小体力消耗。
思路就是枚举汇合的地点。我们需要处理三个最短路（因为边权是固定的，所以可以用bfs）一个是a 到每个点的最短路，b 到每个店的最短路,每个点到N的最短路（其实就是N到每个点的最短路）

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}
const int N = 4e4 + 5;
vector<int> e[N];
int a[N], b[N], c[N];
void solve()
{int te, tf, s;cin >> te >> tf >> s;int t, f, n, m;cin >> t >> f >> n >> m;int u, v;while (m--){cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}auto bfs = [&](int s,  int *a) -> void{for (int i=1;i<=n;i++)a[i]=2e9;queue<int> q;q.push(s);a[s]=0;while (!q.empty()){int u = q.front();q.pop();for (auto v : e[u]){// 已经遍历 这个点了if (a[v]!=2e9)continue;a[v] = a[u] + 1;q.push(v);}}};bfs(t,a);bfs(f,b);bfs(n,c);int mn=2e9;// 枚举汇合的点for (int i=1;i<=n;i++){mn=min(mn,a[i]*te+b[i]*tf+c[i]*(te+tf-s));}if (mn==2e9)cout<<-1<<"\n";else cout<<mn<<"\n";}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;t = 1;// cin>>t;while (t--){solve();}return 0;
}

这道题 主题 的思路 和这个一样。只不过在上一道题的基础上 多了分层。
我们 可以将 所以节点 没有马的情况 看做一层图，将所有 节点 有马的情况看做一层图。
然后 对于 有马的节点
考虑拆点。我们将点 拆成点 i 和点 n+i，其中点 i 表示到i 点时没有骑马，点 i+n表示到 点时骑上了马。那么对于一个有马的点 连边 （i ,i+n ,0），对于一条边 (u , v ,w) 连边 以及 (u+n ,v+n , w/2)。然后分别 跑 Dijkstra 求单源最短路。最后枚举两人到哪个点集合，并分别枚举两人到达时是否骑马即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4e5 + 100;
vector<pair<int, int>> e[N];
struct node
{int x;int y;bool operator<(const node &a) const{return a.y < y;}
};
void solve()
{int n, m, h;cin >> n >> m >> h;for (int i = 0; i <= 2 * n; i++){e[i].clear();}for (int i = 0, u; i < h; i++){cin >> u; e[u].push_back({n+u,0});}for (int i = 0, u, v, w; i < m; i++){cin >> u >> v >> w;e[u].push_back({v, w});e[v].push_back({u, w});e[u + n].push_back({v + n, w / 2});e[v + n].push_back({u + n, w / 2});}auto dij = [&](int s, vector<int> &dis) -> void{vector<bool> vis(2 * (n + 1), false);dis[s] = 0;priority_queue<node> q;q.push({s, 0});while (!q.empty()){node t = q.top();q.pop();int u = t.x;if (vis[u])continue;vis[u] = 1;for (auto [v, w] : e[u]){if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({v, dis[v]});}}}};vector<int> dis1(2 * (n + 1), 1e18);vector<int> dis2(2 * (n + 1), 1e18);dij(1, dis1);dij(n, dis2);int ans = 1e18;for (int i = 1; i <= n; i++){ans = min(ans, max(dis1[i], dis2[i]));ans = min(ans, max(dis1[i + n], dis2[i]));ans = min(ans, max(dis1[i], dis2[i + n]));ans = min(ans, max(dis1[i + n], dis2[i + n]));}if (ans == 1e18)cout << -1 << "\n";elsecout << ans << "\n";}
signed main()
{int t=1;cin>>t;while(t--){solve();}
}

F
题意：
一棵树，每次可以使 这个节点 的相邻节点都减c 使``得 将这个节点的价值 统计进答案。
求整棵树的最大价值和

显然的是可以转移的东西。通常树上的dp【i】代表 以i 为根节点 的子树 的状态。

// dp[i][1]代表 以i 为根的子树 ，根节点不取的情况下 的价值的最大值
// dp[i][0]代表 以i 为根的子树 ，根节点取的情况下 的价值的最大值

考虑一下转移
我们只需要 关注 那些选的节点的权值
dp[i] 的状态 是由 他的子节点 转移 过来的。
如果这个点统计进答案，那么和这个点相邻的点都要减去c
因为是相邻的节点 所以 转移的时候 要考虑 根节点对子节点的影响 子节点对根节点的影响
如果根节点不选的话，根节点不会对子节点造成减c的影响，子节点（不论子节点选不选） 无法 对根节点造成减c 的影响（因为 根节点的 价值不计入答案）
如果根节点选的话 ，从不选的子节点转移过来的时候，不造成影响（因为我们只关注选的节点），从选的子节点转移时，子节点对根节点 有 -c,根节点对子节点有-c ，所以要减去两个c

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}const int N=2e5+5;
int dp[N][2];
// dp[i][1]代表 以i 为根的子树 ，根节点不取的情况下 的价值的最大值
// dp[i][0]代表  以i 为根的子树 ，根节点取的情况下 的价值的最大值
vector<vector<int>>e(N);void solve()
{memset(dp,sizeof(dp),0);int n,c;cin>>n>>c;vector<int>a(n+1);for (int i=1;i<=n;i++){cin>>a[i];e[i].clear();}int u,v;for (int i=1;i<=n-1;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}auto  dfs=[&](auto && self,int u,int fa)->void{dp[u][0]=0;dp[u][1]=a[u];// if (e[u].size()==0)// return ;for(auto v:e[u]){if(v==fa)continue;self(self,v,u);dp[u][0]+=max(dp[v][0],dp[v][1]);dp[u][1]+=max(dp[v][0],dp[v][1]-2*c);}   };dfs(dfs,1,-1);cout<<max(dp[1][0],dp[1][1])<<"\n";}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;cin>>t;while (t--){solve();}return 0;
}

H
容易发现 后手 最多是平局。这就需要 这个区间内的 不同的数字 的个数 是偶数。
使用异或哈希来做。（按照我的理解 ，异或哈希 是 随机化算法和 异或和 的组合）
当然可以 直接 将 这个值域内的数 都随机化出来，构建出来hash 表。我下面的代码是 用了map 来记录是否 出现过这个数字。都可以

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{mt19937 mt(time(0));int n, q;cin >> n >> q;vector<int> a(n + 1);int t;map<int, int> mp;for (int i = 1; i <= n; i++){cin >> t;if (mp.find(t) == mp.end())mp[t] = mt();a[i] = mp[t];}for (int i = 1; i <= n; i++){a[i] = a[i] ^ a[i - 1];}int l, r;while (q--){cin >> l >> r;if ((a[r] ^ a[l - 1]) == 0){cout << "YES\n";}elsecout << "NO\n";}
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;cin >> t;while (t--){solve();}return 0;
}