A - Cake（树上dp）

• 首先两个人依次从一棵树的根走向叶子结点，对于每个结点，它的前缀结点都是确定的，所以先计算出走到每个结点时的 $0$ 在所有前缀字符串中的占比 $p$（取最大，因为最后切蛋糕的人想让 $0$ 最多）
• 第一个人想尽可能让 $1$ 更多，也就是让 $p$ 更小，第二个人想让 $p$ 更大，那第一个人操作的时候尽可能让 $p$ 小，第二个人尽可能让 $p$ 更大就可以了

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin >> n;vector<vector<PII>> g(n + 1);for (int i = 1; i < n; i ++ ){int u, v, c;cin >> u >> v >> c;g[u].push_back({v, c});g[v].push_back({u, c});}vector<int> dep(n + 1);vector<double> f(n + 1);vector<vector<int>> cnt(n + 1, vector<int>(2));function<void(int, int)> dfs = [&](int u, int fa){if (u != 1) f[u] = max(f[u], (double)(1.0 * cnt[u][0] / (cnt[u][0] + cnt[u][1])));for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i].first, c = g[u][i].second;if (j == fa) continue;dep[j] = dep[u] + 1;cnt[j][0] = cnt[u][0], cnt[j][1] = cnt[u][1];cnt[j][c] ++ ;f[j] = f[u];dfs(j, u);}};dep[1] = 1;dfs(1, -1);vector<double> ans(n + 1);function<void(int, int)> dp = [&](int u, int fa){int sz = 0;if (dep[u] & 1) ans[u] = 1;for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i].first, c = g[u][i].second;if (j == fa) continue;dp(j, u);sz ++ ;if (dep[u] & 1) ans[u] = min(ans[u], ans[j]);else ans[u] = max(ans[u], ans[j]);}if (sz == 0) ans[u] = f[u];};dp(1, -1);printf("%.12Lf\n", 1 - ans[1]);
}signed main()
{// ios::sync_with_stdio(false);// cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

B - Cake 2（暴力）

• 枚举每个点作为开头，把结尾点存进队列，一旦开头超过队头就把队头弹出

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, k;cin >> n >> k;if (n == k * 2){cout << n << '\n';return;}k = min(k, n - k);queue<int> q;q.push(k % n);int cnt = 1;int ans = 2;for (int i = 1; i < n; i ++ ){int tmp = (i + k) % n;q.push(tmp);int top = -1;if (q.size()) top = q.front();if (top == i){q.pop();cnt -- ;}if (tmp < i) ans += (cnt + tmp) + 1;else ans += cnt + 1;cnt ++ ;}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}

D - Puzzle: Wagiri（tarjan）

• 首先只看轮边，跑边的双连通分量找桥，所有的桥都不在环上，所以轮边不包括桥，然后将所有不是桥的轮边加到答案里并更新并查集
• 遍历所有切边，在同一个并查集的两个点之间必不连切边

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;vector<vector<int>> g(n + 1);vector<PII> qb, lb, ans;for (int i = 0; i < m; i ++ ){int u, v; cin >> u >> v;string s; cin >> s;if (s[0] == 'L'){g[u].push_back(v);g[v].push_back(u);lb.push_back({u, v});}else qb.push_back({u, v});}int timestamp = 0;vector<int> fa(n + 1), dfn(n + 1), low(n + 1);set<PII> bridge;function<void(int, int)> tarjan = [&](int u, int father){fa[u] = father;dfn[u] = low[u] = ++ timestamp;for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i];if (!dfn[j]){tarjan(j, u);low[u] = min(low[u], low[j]);if (dfn[u] < low[j]){bridge.insert({j, fa[j]});bridge.insert({fa[j], j});}}else if (dfn[j] < dfn[u] && j != father)low[u] = min(low[u], dfn[j]);}};for (int i = 1; i <= n; i ++ )if (!dfn[i]) tarjan(i, -1);vector<int> p(n + 1);for (int i = 1; i <= n; i ++ ) p[i] = i;function<int(int)> find = [&](int u){if (u != p[u]) p[u] = find(p[u]);return p[u];};for (auto t : lb){int u = t.first, v = t.second;if (bridge.count(t)) continue;int pu = find(u), pv = find(v);if (pu != pv) p[pu] = pv;ans.push_back(t);}for (int i = 1; i <= n; i ++ ) find(i);for (auto t : qb){int u = t.first, v = t.second;int pu = find(u), pv = find(v);if (pu != pv){ans.push_back({u, v});p[pu] = pv;}}int p1 = find(1);for (int i = 2; i <= n; i ++ ){if (find(i) != p1){cout << "NO\n";return;}}cout << "YES\n";cout << (int)(ans.size()) << '\n';for (auto t : ans) cout << t.first << ' ' << t.second << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}

F - Challenge NPC 2（构造）

队友的代码

#include<cstdio>
#include<vector>
struct node{int n;node *nxt;
}*mp[1000005],use[2000005],*nw;
void add(int u,int v)
{node *p=nw++;p->n=v;p->nxt=mp[u];mp[u]=p;
}
int du[1000005];
int base;
std::vector<int> dp[1000005];
int dfs(int now,int fa=-1,int dep=1)
{du[now]=1000000000;dp[dep+base].push_back(now);int ret=dep;node *p=mp[now];while(p){if(p->n!=fa){int r=dfs(p->n,now,dep+1);if(r>ret) ret=r;}p=p->nxt;}return ret;
}
int ans[1000005],ansl;
bool fl[1000005];
int main()
{int T;scanf("%d",&T);while(T--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)mp[i]=0,du[i]=0,fl[i]=0;fl[1]=fl[2]=fl[3]=0;nw=use;ansl=0;base=0;for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);du[u]++;du[v]++;}for(int i=1;i<=n;i++)if(du[i]<=1){if(du[i]==0){base++;dp[base].push_back(i);fl[base]=1;}else base+=dfs(i);}if(base<=3){if(fl[1]||fl[2]||fl[3]){if(fl[1]){for(int i=0;i<dp[2].size();i++)ans[ansl++]=dp[2][i];for(int i=0;i<dp[1].size();i++)ans[ansl++]=dp[1][i];for(int i=0;i<dp[3].size();i++)ans[ansl++]=dp[3][i];					}else{for(int i=0;i<dp[2].size();i++)ans[ansl++]=dp[2][i];for(int i=0;i<dp[1].size();i++)ans[ansl++]=dp[3][i];for(int i=0;i<dp[3].size();i++)ans[ansl++]=dp[1][i];	}for(int i=0;i<ansl;i++)printf("%d ",ans[i]);goto label;				}printf("-1");goto label;}for(int i=2;i<=base;i+=2)for(int j=0;j<dp[i].size();j++)ans[ansl++]=dp[i][j];for(int i=1;i<=base;i+=2)for(int j=0;j<dp[i].size();j++)ans[ansl++]=dp[i][j];for(int i=0;i<ansl;i++)printf("%d ",ans[i]);label:putchar('\n');for(int i=1;i<=base;i++)dp[i].clear();}return 0;
}

H - Genshin Impact’s Fault（签到）

#include<cstdio>
#include<cstring>
char s[1000005];
int main()
{int T;scanf("%d",&T);while(T--){scanf("%s",s);int len=strlen(s);int lst=1;for(int i=0;i<=len-10;i++){int cnt=0;for(int j=i;j<i+10;j++)if(s[j]=='3') cnt++;if(cnt==10){printf("invalid\n");goto label;}}for(int i=0;i<=len-90;i++){int cnt=0;for(int j=i;j<i+90;j++)if(s[j]=='3'||s[j]=='4') cnt++;if(cnt==90){printf("invalid\n");goto label;}}for(int i=0;i<len;i++){if(s[i]=='U') lst=1;if(s[i]=='5'){if(lst==0){printf("invalid\n");goto label;}lst=0;}}printf("valid\n");label:;}return 0;
}

I - Intersecting Intervals（dp）

• $f[i][j]$ 表示第 $i$ 行，第 $j$ 个必选的最优答案
• 上下两行相交只会是这两种情况：
  
• 当 $k<j$ 时，首先肯定加上 $f[i-1][k]$，然后因为 $[k,j]$ 必选，所以还要加上 $su{m}_{k,j}$，$k$ 的左边随便选多少，记作 $pre[k]$，$j$ 的右边随便选多少，记作 $suf[j]$
• 当 $k>j$ 时，首先肯定加上 $f[i-1][k]$，然后因为 $[j,k]$ 必选，所以还要加上 $su{m}_{j,k}$，$j$ 的左边随便选多少，记作 $pre[j]$，$k$ 的右边随便选多少，记作 $suf[k]$
• 直接枚举 $k$ 的话会超时，我们可以利用前缀和后缀记录最优的 $k$

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;vector<vector<int>> a(n + 1, vector<int>(m + 1));vector<int> f(m + 2), l0(m + 2), l1(m + 2), r0(m + 2), r1(m + 2);for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= m; j ++ ){cin >> a[i][j];l0[j] = max(0ll, l0[j - 1]) + a[i][j];if (j == 1) l1[j] = f[j] + l0[j];else l1[j] = max(l0[j] + f[j], l1[j - 1] + a[i][j]);}for (int j = m; j >= 1; j -- ){r0[j] = max(0ll, r0[j + 1]) + a[i][j];if (j == m) r1[j] = f[j] + r0[j];else r1[j] = max(r0[j] + f[j], r1[j + 1] + a[i][j]);}for (int j = m; j >= 1; j -- ){f[j] = max(l0[j] - a[i][j] + r1[j], r0[j] - a[i][j] + l1[j]);}}int ans = -INF;for (int i = 1; i <= m; i ++ ) ans = max(ans, f[i]);cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}