T1 染色
我们按照深度分别进行考虑，设当前考虑的深度为 \(x\) ，考虑一种暴力的做法是设 \(f_u\) 表示将 \(u\) 节点内所有深度为 \(x\) 的点全部涂黑的最小代价，显然有转移 \(f_u=\min(\sum f_v,a_{x-deep_u})\) ，正解考虑将深度为 \(x\) 的点取出来建立虚树，容易发现一个点代表原树一条链，因此这个点可以选择的方案对应 \(a\) 数组上一段连续的区间，用 ST 表维护区间最小值即可。
code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int max1 = 1e5;
int n, a[max1 + 5];
vector <int> edge[max1 + 5];
int father[max1 + 5], deep[max1 + 5], siz[max1 + 5], son[max1 + 5];
int top[max1 + 5], dfn[max1 + 5], rk[max1 + 5], dfs_clock;
vector <int> point[max1 + 5];
int tmp[max1 * 2 + 5], len;
int s[max1 + 5], stop;
vector <int> new_edge[max1 + 5];
long long f[max1 + 5], ans;
void Find_Heavy_Edge ( int now, int fa, int depth )
{
father[now] = fa, deep[now] = depth, siz[now] = 1, son[now] = 0;
int max_siz = 0;
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
Find_Heavy_Edge(v, now, depth + 1);
if ( max_siz < siz[v] )
max_siz = siz[v], son[now] = v;
siz[now] += siz[v];
}
return;
}
void Connect_Heavy_Edge ( int now, int ancestor )
{
top[now] = ancestor;
dfn[now] = ++dfs_clock;
rk[dfs_clock] = now;
if ( son[now] )
Connect_Heavy_Edge(son[now], ancestor);
for ( auto v : edge[now] )
{
if ( v == father[now] || v == son[now] )
continue;
Connect_Heavy_Edge(v, v);
}
return;
}
int Get_Lca ( int u, int v )
{
while ( top[u] != top[v] )
{
if ( deep[top[u]] < deep[top[v]] )
swap(u, v);
u = father[top[u]];
}
if ( deep[u] > deep[v] )
swap(u, v);
return u;
}
struct ST_List
{
int list[max1 + 5][18];
void Build ()
{
for ( int i = 1; i <= n; i ++ )
list[i][0] = a[i];
for ( int k = 1; ( 1 << k ) <= n; k ++ )
for ( int i = 1; i + ( 1 << k ) - 1 <= n; i ++ )
list[i][k] = min(list[i][k - 1], list[i + ( 1 << k - 1 )][k - 1]);
return;
}
int Query ( int L, int R )
{
return min(list[L][__lg(R - L + 1)], list[R - ( 1 << __lg(R - L + 1) ) + 1][__lg(R - L + 1)]);
}
}ST;
bool Cmp ( const int &x, const int &y )
{
return dfn[x] < dfn[y];
}
void DP ( int now, int pre, int target )
{
f[now] = ST.Query(target - deep[now] + 1, target - pre);
if ( !new_edge[now].empty() )
{
long long sum = 0;
for ( auto v : new_edge[now] )
{
DP(v, deep[now], target);
sum += f[v];
}
f[now] = min(f[now], sum);
}
return;
}
int main ()
{
freopen("color.in", "r", stdin);
freopen("color.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
for ( int i = 2, u, v; i <= n; i ++ )
{
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs_clock = 0;
Find_Heavy_Edge(1, 0, 0);
Connect_Heavy_Edge(1, 1);
for ( int i = 1; i <= n; i ++ )
point[deep[i]].push_back(i);
ST.Build();
ans = 0;
for ( int i = 0; i <= n - 1; i ++ )
{
if ( point[i].empty() )
continue;
sort(point[i].begin(), point[i].end(), Cmp);
len = 0;
int cnt = point[i].size() - 1;
for ( int k = 0; k <= cnt; k ++ )
tmp[++len] = dfn[point[i][k]];
for ( int k = 0; k <= cnt - 1; k ++ )
tmp[++len] = dfn[Get_Lca(point[i][k], point[i][k + 1])];
tmp[++len] = 1;
sort(tmp + 1, tmp + 1 + len);
len = unique(tmp + 1, tmp + 1 + len) - ( tmp + 1 );
for ( int k = 1; k <= len; k ++ )
{
tmp[k] = rk[tmp[k]];
new_edge[tmp[k]].clear();
}
stop = 0;
for ( int k = 1; k <= len; k ++ )
{
while ( stop && Get_Lca(s[stop], tmp[k]) != s[stop] )
--stop;
if ( stop )
new_edge[s[stop]].push_back(tmp[k]);
s[++stop] = tmp[k];
}
DP(1, -1, i);
ans += f[1];
}
printf("%lld\n", ans);
return 0;
}
T2 技能
2023冲刺清北营10 T3 。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1000, lim = 200;
const int inf = 0x3f3f3f3f;
int n, a[max1 + 5][3];
int now, f[2][max1 + 5][max1 + 5][3];
int main ()
{
freopen("skill.in", "r", stdin);
freopen("skill.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
for ( int k = 0; k < 3; k ++ )
scanf("%d", &a[i][k]);
now = 0;
for ( int i = 0; i <= n; i ++ )
for ( int j = 0; j <= n; j ++ )
for ( int k = 0; k < 3; k ++ )
f[now][i][j][k] = -inf;
f[now][1][1][0] = f[now][1][1][1] = f[now][1][1][2] = 0;
for ( int i = 1; i <= n; i ++ )
{
now ^= 1;
for ( int j = max(1, i - lim); j <= i + 1; j ++ )
for ( int k = max(1, i - lim); k <= i + 1; k ++ )
for ( int w = 0; w < 3; w ++ )
f[now][j][k][w] = -inf;
for ( int j = max(1, i - lim - 1); j <= i; j ++ )
{
for ( int k = max(1, i - lim - 1); k <= i; k ++ )
{
int x, y, z;
if ( f[now ^ 1][j][k][0] != -inf )
{
x = 1;
y = i - j;
z = i - k;
f[now][j + ( j == i )][k + ( k == i )][0] = max(f[now][j + ( j == i )][k + ( k == i )][0], f[now ^ 1][j][k][0] + a[i][0] - y - z);
f[now][i - 1][k + ( k == i )][1] = max(f[now][i - 1][k + ( k == i )][1], f[now ^ 1][j][k][0] + a[i][1] - x - z);
f[now][i - 1][j + ( j == i )][2] = max(f[now][i - 1][j + ( j == i )][2], f[now ^ 1][j][k][0] + a[i][2] - x - y);
}
if ( f[now ^ 1][j][k][1] != -inf )
{
x = i - j;
y = 1;
z = i - k;
f[now][i - 1][k + ( k == i )][0] = max(f[now][i - 1][k + ( k == i )][0], f[now ^ 1][j][k][1] + a[i][0] - y - z);
f[now][j + ( j == i )][k + ( k == i )][1] = max(f[now][j + ( j == i )][k + ( k == i )][1], f[now ^ 1][j][k][1] + a[i][1] - x - z);
f[now][j + ( j == i )][i - 1][2] = max(f[now][j + ( j == i )][i - 1][2], f[now ^ 1][j][k][1] + a[i][2] - x - y);
}
if ( f[now ^ 1][j][k][2] != -inf )
{
x = i - j;
y = i - k;
z = 1;
f[now][k + ( k == i )][i - 1][0] = max(f[now][k + ( k == i )][i - 1][0], f[now ^ 1][j][k][2] + a[i][0] - y - z);
f[now][j + ( j == i )][i - 1][1] = max(f[now][j + ( j == i )][i - 1][1], f[now ^ 1][j][k][2] + a[i][1] - x - z);
f[now][j + ( j == i )][k + ( k == i )][2] = max(f[now][j + ( j == i )][k + ( k == i )][2], f[now ^ 1][j][k][2] + a[i][2] - x - y);
}
}
}
}
int ans = -inf;
for ( int i = max(1, n - lim); i <= n + 1; i ++ )
for ( int j = max(1, n - lim); j <= n + 1; j ++ )
for ( int w = 0; w < 3; w ++ )
ans = max(ans, f[now][i][j][w]);
printf("%d\n", ans);
return 0;
}
T3 重排
设球的总数为 \(n\) ，操作次数为 \(k\) ，求解的位置为 \(pos\) 。
可以得到一个结论：如果存在一次操作选择了前 \(i\) 个球，那么这 \(i\) 个球对应的概率完全相同。
设 \(M=\max(l_i)\) ，其中 \(l_i\) 为第 \(i\) 次选择的前缀长度，我们大致分两种情况考虑：
如果 \(M<pos\) ，显然这个球位置不变，贡献为 \(P(M)\times pos\) ；
如果 \(M\ge pos\) ，那么第 \(pos\) 个球的活动范围为 \([1,M]\) ，并且前 \(M\) 个球的概率相同，贡献为 \(P(M)\times\tfrac{M+1}{2}\) 。
枚举 \(M\) 计算即可。
code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, pos, k;
double ans;
double Quick_Power ( double base, int p )
{
double res = 1.0;
while ( p )
{
if ( p & 1 )
res = res * base;
p >>= 1;
base = base * base;
}
return res;
}
double P ( int x )
{
return Quick_Power(1.0 * ( x - 1 ) / n, k);
}
int main ()
{
freopen("arrange.in", "r", stdin);
freopen("arrange.out", "w", stdout);
scanf("%d%d%d", &n, &pos, &k);
ans = P(pos) * pos;
for ( int i = pos; i <= n; i ++ )
ans += ( P(i + 1) - P(i) ) * ( i + 1 ) * 0.5;
printf("%.15lf\n", ans);
return 0;
}