第 46 届 ICPC 亚洲区域赛（上海）补题 GI

本文主要是介绍第 46 届 ICPC 亚洲区域赛（上海）补题 GI，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客补题链接：
第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（上海）（重现赛）
参考：
【题目记录】——ICPC上海2021
2021 ICPC(上海) 试题分析

G Edge Groups

考虑将有一个共同顶点的s条边两两分组的方案数
当s为偶数时，设s = 2k
把s条边两两分组，即先在s中取2个，再在s - 2中取2个…最后除以s/2的排列
$\frac{C_{2k}^2C_{2k-2}^2...C_2^2}{A_k^k}$
$\frac{k(2k-1)·(k-1)(2k-3) · ... ·1}{k(k-1)...1}$
$= (2 k - 1) (2 k - 3) ...1$
$= (2 k - 1)!! = (s - 1)!!$
同理可得，s为奇数时的方案数是 $s!!$

考虑树上一个顶点x，它的子树大小为size(x)
当size(x)为奇时（即子树上边数为偶），那么可以子树中两两分组，记这样的方案数为dp[x]；
当size(x)为偶时（即子树上边数为奇），就需要留一条边（与{x, fa[x]}或者其他留下的边成一组），其他边分组，记这样的方案数为dp[x]
那么计算dp[x]时，不仅要x的所有儿子的方案相乘，还要将留下的边分组
记x的儿子为y，有k个y满足size(y)为偶

$=\begin{cases} (k-1)!!\prod dp[y], & \text{if k is even} \\k!!\prod dp[y], & \text{if k is odd}\end{cases}$

好了，开写

#include <iostream>
#include <cstdio>
using namespace std;#define N 100005
#define M 200005
const int P = 998244353;
typedef long long ll;int head[N], fa[N], siz[N];
int nxt[M], to[M];
ll dp[N], fac[N];int tot = 0;
void add(int x, int y)
{tot++;nxt[tot] = head[x];head[x] = tot;to[tot] = y;
}void dfs(int x)
{siz[x] = 1;int k = 0;dp[x] = 1;for (int i = head[x]; i; i = nxt[i]){int y = to[i];if (y == fa[x]) continue;fa[y] = x;dfs(y);if (siz[y] & 1) k++;siz[x] += siz[y];dp[x] = dp[x] * dp[y] % P;}if (k & 1) dp[x] = dp[x] * fac[k] % P;else if (k > 0) dp[x] = dp[x] * fac[k - 1] % P;//cout << x << ' ' << siz[x] << ' ' << dp[x] << endl;
}int main()
{int n;cin >> n;for (int i = 1 ; i < n; i++){int x, y;cin >> x >> y;add(x, y), add(y, x);}fac[0] = fac[1] = 1;for (int i = 2; i <= n; i++){fac[i] = fac[i - 2] * i % P;}dfs(1);cout << dp[1];return 0;
}

I Steadily Growing Steam

dp
f[i][j][k]表示从1-i中选，用了j次加倍，S和T的t值之和的差+2600为k时，能获得的v值之和最大值

#include <iostream>
#include <cstdio>using namespace std;#define N 105
#define INF 1e9
int v[N], t[N];
long long f[N][N][5205];int main()
{int n, k;cin >> n >> k;for (int i = 1; i <= n; i++)cin >> v[i] >> t[i];for (int j = 0; j <= k; j++)for (int o = 0; o <= 5200; o++)f[0][j][o] = (o == 2600 ? 0 : -INF);for (int i = 1; i <= n; i++){for (int j = 0; j <= k; j++){for (int o = 0; o <= 5200; o++){f[i][j][o] = f[i - 1][j][o];if (j)//加倍{//sif (o + 2*t[i] <= 5200) f[i][j][o] = max(f[i][j][o], f[i - 1][j - 1][o + 2*t[i]] + v[i]);//tif (o >= 2*t[i]) f[i][j][o] = max(f[i][j][o], f[i - 1][j - 1][o - 2*t[i]] + v[i]);}//sif (o + t[i] <= 5200) f[i][j][o] = max(f[i][j][o], f[i - 1][j][o + t[i]] + v[i]);//tif (o >= t[i]) f[i][j][o] = max(f[i][j][o], f[i - 1][j][o - t[i]] + v[i]);}}}long long ans = -INF;for (int j = 0; j <= k; j++)ans = max(ans, f[n][j][2600]);cout << ans;return 0;
}