关于闲话
如果写学术性闲话确实没有必要。（毕竟几乎每天都在写题解）
但如果写别的内容可能大家也不会有太大的兴趣，因为可以用于聊的兴趣就是二次元了，但是现在机房里真正以二次元为爱好的人并不多。（如果真正写闲话可能会变成补番指南）
T1 九转大肠
考虑进行 dp ，设 \(f_{i,j,k}\) 表示当前以 \(i\) 为根， \(j\) 号节点的 \(dfn\) 序为 \(k\) 的方案数。考虑边 \(u\to v\) 的转移，设 \(g_{u,i,j}\) 表示在 \(u\) 的儿子中（不包含 \(v\) ）选择 \(i\) 个子树，子树总大小为 \(j\) 的总方案数，此时有转移：
\[f_{v,i,j}\times g_{u,k,t}\to f_{u,i,j+t+1} \]发现上述转移与 \(t\) 无关，因此可以预处理 \(\sum_t g_{u,k,t}\) ，转移需要枚举 \(i,j,t\) ，容易发现枚举次数为 \(\sum_{(u,v)}siz_v^2(siz_u-siz_v)\) ，将 \(siz_v\) 视为 \(O(n)\) ，上述式子为 \(n\sum_{(u,v)}siz_v(siz_u-siz_v)\) ，后半部分可以理解为树上 \(2\) 点只在 lca 处贡献复杂度，容易发现复杂度为 \(O(n^3)\) 。
然而每次暴力求解 \(g\) 显然会 TLE ，但容易发现这是一个可撤销背包，因此在全部子树贡献的基础上撤销 \(v\) 子树的贡献即可。
code
#include <cstdio>
#include <vector>
using namespace std;
const int max1 = 500;
const int mod = 998244353;
int n, fac[max1 + 5], in[max1 + 5], out[max1 + 5], dfs_clock;
vector <int> edge[max1 + 5];
int f[max1 + 5][max1 + 5], g[max1 + 5][max1 + 5], h[max1 + 5][max1 + 5], tmp[max1 + 5], sum[max1 + 5];
void Add ( int &x, int y )
{
x = x + y;
if ( x >= mod )
x = x - mod;
return;
}
void Dfs ( int now )
{
sum[now] = fac[edge[now].size()];
in[now] = ++dfs_clock;
for ( auto v : edge[now] )
{
Dfs(v);
sum[now] = 1LL * sum[now] * sum[v] % mod;
}
out[now] = dfs_clock;
int len = edge[now].size(), lim = out[now] - in[now];
for ( int i = 0; i <= len; i ++ )
for ( int k = 0; k <= lim; k ++ )
h[i][k] = 0;
h[0][0] = 1;
for ( auto v : edge[now] )
for ( int i = len; i >= 0; i -- )
for ( int k = 0; k <= in[v] - in[now] - 1; k ++ )
if ( h[i][k] )
Add(h[i + 1][k + out[v] - in[v] + 1], h[i][k]);
for ( auto v : edge[now] )
{
lim -= out[v] - in[v] + 1;
for ( int i = 0; i <= len; i ++ )
for ( int k = 0; k <= lim; k ++ )
if ( h[i][k] )
Add(h[i + 1][k + out[v] - in[v] + 1], mod - h[i][k]);
for ( int k = 0; k <= lim; k ++ )
{
tmp[k] = 0;
for ( int i = 0; i <= len - 1; i ++ )
tmp[k] = ( tmp[k] + 1LL * h[i][k] * fac[i] % mod * fac[len - 1 - i] ) % mod;
}
int x = 1;
for ( auto p : edge[now] )
if ( p != v )
x = 1LL * x * sum[p] % mod;
for ( int i = in[v]; i <= out[v]; i ++ )
for ( int k = 1; k <= out[v] - in[v] + 1; k ++ )
g[i][k] = 0;
for ( int w = 0; w <= lim; w ++ )
{
if ( !tmp[w] )
continue;
for ( int i = in[v]; i <= out[v]; i ++ )
{
for ( int k = 1; k <= out[v] - in[v] + 1; k ++ )
{
if ( !f[i][k] )
continue;
g[i][k + w + 1] = ( g[i][k + w + 1] + 1LL * f[i][k] * tmp[w] % mod * x ) % mod;
}
}
}
for ( int i = in[v]; i <= out[v]; i ++ )
for ( int k = 1; k <= out[now] - in[now] + 1; k ++ )
f[i][k] = g[i][k];
for ( int i = len; i >= 0; i -- )
for ( int k = 0; k <= lim; k ++ )
if ( h[i][k] )
Add(h[i + 1][k + out[v] - in[v] + 1], h[i][k]);
lim += out[v] - in[v] + 1;
}
f[in[now]][1] = sum[now];
return;
}
int main ()
{
freopen("intestine.in", "r", stdin);
freopen("intestine.out", "w", stdout);
scanf("%d", &n);
for ( int i = 2, u; i <= n; i ++ )
{ scanf("%d", &u); edge[u].push_back(i); }
fac[0] = 1;
for ( int i = 1; i <= n; i ++ )
fac[i] = 1LL * fac[i - 1] * i % mod;
Dfs(1);
for ( int i = 1; i <= n; i ++, putchar('\n') )
for ( int k = 1; k <= n; k ++ )
printf("%d ", f[in[i]][k]);
return 0;
}
T2 原本味道
设左端点为 \(A\) ，右端点为 \(B\) ，发现 \(B\) 在 \(q\) 步后到达的位置很容易求解，因此考虑通过求解 \(AB\) 线段最终的距离来得到 \(A\) 端点的移动次数，考虑构造序列 \(t\) ，初始时序列中所有元素为 \(0\) ，不考虑 \(B\) 对 \(A\) 的限制，如果第 \(i\) 秒 \(B\) 向右移动则 \(t_i+1\to t_i\) ，如果 \(A\) 向右移动则 \(t_i-1\to t_i\) ，此时我们初始化 \(AB\) 距离为 \(d\) ，按照时间依次处理每个 \(t_i\) ，容易发现每次的操作为 \(d=\max(1,d+t_i)\) 。
考虑找到最后一个 \(d=1\) 的位置 \(pos\) ，可以发现 \(\sum_{i=pos+1}^{n}t_i\) 就是 \(AB\) 的距离，可以发现 \(\sum_{i=pos+1}^{n}t_i\) 为 \(t\) 序列的最大后缀和，证明考虑如果最大后缀和满足 \(d>1\) ，但是由于开头满足 \(d=1\) ，因此这个位置一定不是最大后缀和。
容易发现 \(t\) 序列以 \(\operatorname{lcm}(a_1+b_1,a_2+b_2)\) 为周期循环，因此考虑将时间轴按照循环周期分段，设当前询问为 \(x\) ，找到 \(x\) 所对应的周期，容易发现 \(t\) 序列的后缀 \(\max\) 只有简单的三种情况：后缀 \(\max\) 全部位于 \(x\) 所对应的周期，一部分位于 \(x\) 所对应的周期，一部分包含倒数第 \(2\) 个周期的一段后缀，包含 \(x\) 所对应的周期到 \(1\) 所对应的周期的一个后缀的全部部分。可以维护一个周期的前缀和以及一个周期的每个位置的后缀 \(\max\) 快速查询。
然而周期的长度很大，因此考虑合并一段 \(t\) 值完全相同的区间，不难发现有用的状态被压缩为 \(O(a+b)\) 级别，可以通过。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1e6;
const long long inf = 0x3f3f3f3f3f3f3f3f;
int a1, b1, a2, b2, len1, len2, len, q;
long long lcm;
struct Point
{
long long R; int x;
Point () {}
Point ( long long __R, int __x )
{ R = __R, x = __x; }
bool operator < ( const Point &A ) const
{ return R < A.R; }
}val[max1 * 8 + 5];
long long max_suffix[max1 * 8 + 5], prev_sum[max1 * 8 + 5], sum, maxs;
void Build ()
{
val[0] = Point(0LL, 0); len = 0;
int i = 1, j = 1; long long pre = 0;
while ( i <= len1 + len1 && j <= len2 + len2 )
{
long long now1, now2;
if ( i & 1 )
now1 = 1LL * ( i >> 1 ) * ( a1 + b1 ) + a1;
else
now1 = 1LL * ( i >> 1 ) * ( a1 + b1 );
if ( j & 1 )
now2 = 1LL * ( j >> 1 ) * ( a2 + b2 ) + a2;
else
now2 = 1LL * ( j >> 1 ) * ( a2 + b2 );
int p = ( i & 1 ) - ( j & 1 );
if ( now1 < now2 )
{
val[++len] = Point(now1, p);
pre = now1;
++i;
}
else if ( now1 > now2 )
{
val[++len] = Point(now2, p);
pre = now2;
++j;
}
else
{
val[++len] = Point(now1, p);
pre = now1;
++i, ++j;
}
}
max_suffix[0] = prev_sum[0] = 0LL;
for ( int i = 1; i <= len; i ++ )
{
max_suffix[i] = max_suffix[i - 1] + ( val[i].R - val[i - 1].R ) * val[i].x;
max_suffix[i] = max(max_suffix[i], 0LL);
prev_sum[i] = prev_sum[i - 1] + ( val[i].R - val[i - 1].R ) * val[i].x;
}
sum = maxs = 0LL;
for ( int i = len; i >= 1; i -- )
{
sum += ( val[i].R - val[i - 1].R ) * val[i].x;
maxs = max(maxs, sum);
}
return;
}
void Solve ()
{
long long x, belong, ans;
scanf("%lld", &x);
belong = ( x - 1 ) / lcm; x = ( x - 1 ) % lcm + 1;
int pos = upper_bound(val + 1, val + 1 + len, Point(x, 0)) - val - 1;
ans = ( x - val[pos].R ) * val[pos + 1].x + max_suffix[pos];
ans = max(ans, 0LL);
if ( belong )
{
ans = max(ans, prev_sum[pos] + ( x - val[pos].R ) * val[pos + 1].x + maxs);
ans = max(ans, prev_sum[pos] + ( x - val[pos].R ) * val[pos + 1].x + ( belong - 1 ) * sum + maxs);
}
long long count = ( belong * lcm + x - 1 ) / ( a1 + b1 ) * a1;
if ( ( belong * lcm + x - 1 ) % ( a1 + b1 ) + 1 <= a1 )
count += ( belong * lcm + x - 1 ) % ( a1 + b1 ) + 1;
else
count += a1;
ans = count - ans;
printf("%lld\n", ans);
return;
}
int main ()
{
freopen("snow.in", "r", stdin);
freopen("snow.out", "w", stdout);
scanf("%d%d%d%d%d", &a1, &b1, &a2, &b2, &q);
lcm = 1LL * ( a1 + b1 ) * ( a2 + b2 ) / __gcd(a1 + b1, a2 + b2);
len1 = lcm / ( a1 + b1 ); len2 = lcm / ( a2 + b2 );
Build();
while ( q -- )
Solve();
return 0;
}
T3 顶级厨师
首先有一个很显然的结论：如果某项技能在某个时刻变为 \(0\) ，那么这个时刻前一定不会提升该项技能。根据这个结论，我们可以不考虑一项技能变为 \(0\) 所造成的影响。此时有一种显然的 dp ，设 \(f_{i,j,0/1/2}\) 表示上次选择的技能为 \(0/1/2\) ，剩余两次技能最后依次提升在第 \(i,j\) 天，大力分类讨论进行转移即可。
考虑利用 \(w\) 值域很小的限制，此时存在结论：任意两个相邻的相同的技能间隔的天数不超过 \(O(\sqrt{w})\) ，证明考虑如果存在一种技能间隔的天数超过 \(\sqrt{w}\) ，设这分别为第 \(i, j\) 天，考虑将第 \(\tfrac{i+j}{2}\) 天的颜色替换为当前颜色，容易发现这个点产生的最大代价为 \(w\) ，假设其他颜色满足相邻的相同技能间隔天数不超过 \(O(\sqrt{w})\) ，那么删除原有颜色最多产生 \(w\) 的代价，而此时替换产生的贡献约为 \(\tfrac{(j-i)^2}{2}-\tfrac{(\tfrac{j-i}{2})^2}{2}\times 2\) ，也就是 \(\tfrac{(j-i)^2}{4}\) ，容易发现当 \(j-i\ge O(\sqrt{w})\) 时，贡献大于代价。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1000, B = 200;
const int inf = 0x3f3f3f3f;
int T, n, a[max1 + 5][3];
int now, f[2][max1 + 5][max1 + 5][3];
void Work ()
{
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
for ( int k = 0; k < 3; k ++ )
scanf("%d", &a[i][k]);
now = 0;
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 - B); j <= i + 1; j ++ )
for ( int k = max(1, i - B); k <= i + 1; k ++ )
f[now][j][k][0] = f[now][j][k][1] = f[now][j][k][2] = -inf;
for ( int j = max(1, i - 1 - B); j <= i; j ++ )
{
for ( int k = max(1, i - 1 - B); k <= i; k ++ )
{
int x, y, z, valx, valy, valz;
x = i - 1, y = j, z = k;
if ( x == i )
++x;
if ( y == i )
++y;
if ( z == i )
++z;
valx = valy = valz = 0;
if ( x < i )
valx = i - x;
if ( y < i )
valy = i - y;
if ( z < i )
valz = i - z;
f[now][y][z][0] = max(f[now][y][z][0], f[now ^ 1][j][k][0] + a[i][0] - valy - valz);
f[now][x][z][1] = max(f[now][x][z][1], f[now ^ 1][j][k][0] - valx + a[i][1] - valz);
f[now][x][y][2] = max(f[now][x][y][2], f[now ^ 1][j][k][0] - valx - valy + a[i][2]);
x = j, y = i - 1, z = k;
if ( x == i )
++x;
if ( y == i )
++y;
if ( z == i )
++z;
valx = valy = valz = 0;
if ( x < i )
valx = i - x;
if ( y < i )
valy = i - y;
if ( z < i )
valz = i - z;
f[now][y][z][0] = max(f[now][y][z][0], f[now ^ 1][j][k][1] + a[i][0] - valy - valz);
f[now][x][z][1] = max(f[now][x][z][1], f[now ^ 1][j][k][1] - valx + a[i][1] - valz);
f[now][x][y][2] = max(f[now][x][y][2], f[now ^ 1][j][k][1] - valx - valy + a[i][2]);
x = j, y = k, z = i - 1;
if ( x == i )
++x;
if ( y == i )
++y;
if ( z == i )
++z;
valx = valy = valz = 0;
if ( x < i )
valx = i - x;
if ( y < i )
valy = i - y;
if ( z < i )
valz = i - z;
f[now][y][z][0] = max(f[now][y][z][0], f[now ^ 1][j][k][2] + a[i][0] - valy - valz);
f[now][x][z][1] = max(f[now][x][z][1], f[now ^ 1][j][k][2] - valx + a[i][1] - valz);
f[now][x][y][2] = max(f[now][x][y][2], f[now ^ 1][j][k][2] - valx - valy + a[i][2]);
}
}
}
int ans = -inf;
for ( int i = max(1, n - B); i <= n + 1; i ++ )
for ( int j = max(1, n - B); j <= n + 1; j ++ )
for ( int k = 0; k < 3; k ++ )
ans = max(ans, f[now][i][j][k]);
printf("%d\n", ans);
return;
}
int main ()
{
freopen("codechef.in", "r", stdin);
freopen("codechef.out", "w", stdout);
scanf("%d", &T);
while ( T -- )
Work();
return 0;
}