T1 图案
首先是题解做法：考虑对于每个 \(r\) ，判断 \(s[1,r]\) 是否为一个图案，设 \(r=ik+j\) ，其中 \(0\le j\le i\) ，如果存在一组这样的 \((i,j)\) 满足 \(s[1,r-i]=s[i+1,r]\) ，那么 \(s[1,r]\) 是一个图案，考虑这样做的正确性，如果 \(s[1,r-i]=s[i+1,r]\) ，那么一定有 \(s[i+1,r-2i]=s[2i+1,r-i]\) ，这样操作 \(k\) 次，剩余串的长度一定为 \(j\) ，容易判断这个串是一个图案。
因此我们枚举 \(i\) ，发现合法的 \(r\) 的区间为 \([ki,(k+1)i]\cap[1,\operatorname{lcp}(s[1,n],s[i+1,n])]\) ，求解过程可以用二分哈希，用 Z 函数可以做到 \(O(n)\) 。
简单叙述一下自己的想法，仍然考虑枚举 \(BA\) 的长度 \(len\) ，此时需要判断前缀由 \(k\) 个长度为 \(len\) 的相同的字符串拼接而成，发现暴力枚举判断的复杂度为 \(o(n)\) ，因此直接暴力即可，之后找到 \(s[klen+1,n]\) 和 \(s[1,n]\) 的 \(\operatorname{lcp}\) 做区间覆盖即可。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1e6;
const int base = 29, mod1 = 998244353, mod2 = 20051107;
int n, k;
char s[max1 + 5];
int f[max1 + 5];
struct Data
{
int h1, h2;
Data () {}
Data ( int __h1, int __h2 )
{ h1 = __h1, h2 = __h2; }
Data operator + ( const Data &A ) const
{ return Data(( h1 + A.h1 ) % mod1, ( h2 + A.h2 ) % mod2); }
Data operator - ( const Data &A ) const
{ return Data(( h1 - A.h1 + mod1 ) % mod1, ( h2 - A.h2 + mod2 ) % mod2); }
Data operator * ( const Data &A ) const
{ return Data(1LL * h1 * A.h1 % mod1, 1LL * h2 * A.h2 % mod2); }
bool operator == ( const Data &A ) const
{ return h1 == A.h1 && h2 == A.h2; }
bool operator != ( const Data &A ) const
{ return h1 != A.h1 || h2 != A.h2; }
};
struct Hash
{
Data power[max1 + 5], h[max1 + 5];
void Build ( const char *s, const int &len )
{
power[0] = Data(1, 1);
for ( int i = 1; i <= len; i ++ )
power[i] = power[i - 1] * Data(base, base);
h[0] = Data(0, 0);
for ( int i = 1; i <= len; i ++ )
h[i] = h[i - 1] * Data(base, base) + Data(s[i] - 'a' + 1, s[i] - 'a' + 1);
return;
}
Data Query ( int L, int R )
{ return h[R] - h[L - 1] * power[R - L + 1]; }
}H;
int main ()
{
freopen("pattern.in", "r", stdin);
freopen("pattern.out", "w", stdout);
scanf("%d%d%s", &n, &k, s + 1);
H.Build(s, n);
for ( int len = 1; len <= n; len ++ )
{
if ( k * len > n )
break;
bool flag = true;
Data d = H.Query(1, len);
for ( int i = 2; i <= k; i ++ )
if ( H.Query(i * len - len + 1, i * len) != d )
{ flag = false; break; }
if ( flag )
{
int L = 0, R = min(n - k * len, len), pos = 0;
while ( L <= R )
{
int mid = L + R >> 1;
if ( H.Query(1, mid) == H.Query(k * len + 1, k * len + mid) )
pos = mid, L = mid + 1;
else
R = mid - 1;
}
++f[k * len];
--f[k * len + R + 1];
}
}
for ( int i = 1; i <= n; i ++ )
{
f[i] += f[i - 1];
if ( f[i] )
putchar('1');
else
putchar('0');
}
putchar('\n');
return 0;
}
T2 树点购买
首先有一个显然的结论：任意一颗子树内最多有一个密码未知的叶子。考虑利用这个性质进行 dp ，设 \(f_{u,0/1}\) 表示当前考虑以 \(u\) 为根的子树，子树内存在 \(0/1\) 个密码未知的叶子，比较显然转移有：
\[\begin{aligned} f_{u,0}&=\min(\sum_{v}f_{v,0},\sum_{v}f_{v,0}-\max_{v}(f_{v,0}-f_{v,1})+c_{u})\\ f_{u,1}&=\sum_{v}f_{v,0}-\max_{v}(f_{v,0}-f_{v,1}) \end{aligned} \]通过 \(f\) 的值由哪些状态转移过来，解决剩余两个问题。
首先证明一个结论： \(f_{u,0}\) 对应的所有方案中被选择节点构成的集合一定是 \(f_{v,1}\) 对应的所有方案中被选择节点构成集合的超集。
考虑归纳证明：
当 \(u\) 为叶节点时， \(f_{u,0}\) 对应 \(\{u\}\) ， \(f_{u,1}\) 对应 \(\emptyset\) ，显然成立。
当 \(u\) 不为叶节点时，如果 \(\max(f_{v,0}-f_{v,1})\) 在一个儿子 \(w\) 中取到，那么 \(f_{u,0}\) 对应的集合为 \(f_{v,0}\) 对应集合的并集或者 \(\{u\}\) 与 \(f_{v,0},(v\ne w)\) 对应集合与 \(f_{w,1}\) 对应集合的并集， \(f_{v,1}\) 对应集合为 \(f_{v,0},(v\ne w)\) 对应集合与 \(f_{w,1}\) 对应集合的并集；如果 \(\max(f_{v,0}-f_{v,1})\) 在多个儿子中被取到，那么 \(f_{u,0}\) 对应集合为 \(f_{v,0}\) 对应集合的并集或 \(\{u\}\) 与 \(f_{v,0}\) 对应集合的并集， \(f_{u,1}\) 对应集合为 \(f_{v,0}\) 对应集合的并集。显然上述两种情况均满足 \(f_{u,0}\) 对应集合为 \(f_{u,1}\) 对应集合的超集。
因此考虑再次 Dfs ，定义函数 \(\operatorname{Redfs}(u,type)\) 可以找到 \(f_{u,type}\) 对应的集合，根据上述结论，如果存在两个方案满足一个包含 \(f_{v,0}\) ，一个包含 \(f_{v,1}\) ，只需要调用 \(\operatorname{Redfs}(v,1)\) 即可，可以保证复杂度。
考虑解决第三个问题，定义 \(g_{u,0/1}\) 为 \(f_{u,0/1}\) 对应的方案数，按照转移到 \(f_{u,0/1}\) 的状态计算 \(g_{u,0/1}\) 即可，比较简单，在此不再赘述。
code
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int mod = 998244353;
const int max1 = 1e6;
const long long inf = 0x3f3f3f3f3f3f3f3f;
int n, k, c[max1 + 5];
vector <int> edge[max1 + 5];
int son[max1 + 5];
long long f[max1 + 5][2], sum[max1 + 5], Max[max1 + 5];
int cnt[max1 + 5], pi[max1 + 5], g[max1 + 5][2];
bool choose[max1 + 5];
void Dfs ( int now, int fa )
{
son[now] = 0;
sum[now] = 0;
Max[now] = -inf, cnt[now] = 0;
pi[now] = 1;
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
++son[now];
Dfs(v, now);
sum[now] += f[v][0];
if ( Max[now] < f[v][0] - f[v][1] )
{
Max[now] = f[v][0] - f[v][1];
cnt[now] = 0;
}
if ( Max[now] == f[v][0] - f[v][1] )
++cnt[now];
pi[now] = 1LL * pi[now] * g[v][0] % mod;
}
if ( !son[now] )
{
f[now][0] = c[now];
f[now][1] = 0;
g[now][0] = g[now][1] = 1;
}
else
{
int p = 0, q = 1;
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
p = 1LL * p * g[v][0] % mod;
if ( f[v][0] - f[v][1] == Max[now] )
p = ( p + 1LL * q * g[v][1] ) % mod;
q = 1LL * q * g[v][0] % mod;
}
f[now][0] = min(sum[now], sum[now] - Max[now] + c[now]);
g[now][0] = 0;
if ( sum[now] <= sum[now] - Max[now] + c[now] )
g[now][0] = ( g[now][0] + pi[now] ) % mod;
if ( sum[now] >= sum[now] - Max[now] + c[now] )
g[now][0] = ( g[now][0] + p ) % mod;
f[now][1] = sum[now] - Max[now];
g[now][1] = p;
}
return;
}
void Redfs ( int now, int fa, int type )
{
if ( !type )
{
if ( !son[now] )
choose[now] = true;
else
{
if ( sum[now] < sum[now] - Max[now] + c[now] )
{
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
Redfs(v, now, 0);
}
}
else if ( sum[now] > sum[now] - Max[now] + c[now] )
{
choose[now] = true;
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
if ( f[v][0] - f[v][1] == Max[now] )
Redfs(v, now, cnt[now] == 1);
else
Redfs(v, now, 0);
}
}
else
{
choose[now] = true;
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
Redfs(v, now, 0);
}
}
}
}
else
{
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
if ( f[v][0] - f[v][1] == Max[now] )
Redfs(v, now, cnt[now] == 1);
else
Redfs(v, now, 0);
}
}
}
int main ()
{
freopen("purtree.in", "r", stdin);
freopen("purtree.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &c[i]);
for ( int i = 1, u, v; i <= n - 1; i ++ )
scanf("%d%d", &u, &v), edge[u].push_back(v), edge[v].push_back(u);
scanf("%d", &k);
Dfs(1, 0);
Redfs(1, 0, 0);
printf("%lld\n", f[1][0]);
if ( k > 1 )
{
for ( int i = 1; i <= n; i ++ )
if ( choose[i] )
printf("%d ", i);
printf("\n");
}
if ( k > 2 )
printf("%d\n", g[1][0]);
return 0;
}
T3 舰队游戏
由于原图构成 DAG ，因此设 \(f_{u,i}\) 表示当前位于第 \(u\) 个节点，剩余生命值为 \(i\) 时的期望步数，显然有转移：
\[f_{u,i}=min(1+\tfrac{1}{deg}\sum_{v}f_{v,i-d_v},f_{1,H}+H-i) \]发现转移存在后效性，但是这只涉及了 \(f_{1,H}\) ，因此考虑确定 \(f_{1,H}\) 的值进行转移，具体的，我们二分 \(f_{1,H}\) 的值为 \(x\) 进行 dp ，如果 dp 得到的 \(f_{1,H}\) 等于二分的值，那么 \(L=mid\) ，否则 \(R=mid\) 。
考虑这样做的正确性，将 \(f_{u,i}\) 看做关于 \(x\) 的函数，用归纳法很容易证明 \(f_{u,i}(x)\) 的导数 \(\le 1\) ，那么 \((x-f_{u,i})'\ge 0\) ，因此函数具有单调性，可以二分求解。
code
#include <cstdio>
#include <vector>
#include <cmath>
#include <cassert>
using namespace std;
const int max1 = 100;
const double inf = 0x3f3f3f3f3f3f3f3f, eps = 1e-8;
int n, m, H, d[max1 + 5];
vector <int> edge[max1 + 5];
double f[max1 + 5][max1 + 5];
double F ( int u, int i )
{
if ( i <= 0 )
return inf;
return f[u][i];
}
bool Check ( double x )
{
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= H; j ++ )
f[i][j] = inf;
for ( int i = 1; i <= H; i ++ )
f[n][i] = 0;
for ( int i = 1; i <= H; i ++ )
{
for ( int u = n - 1; u >= 1; u -- )
{
int deg = edge[u].size();
if ( deg )
{
f[u][i] = 0;
for ( auto v : edge[u] )
f[u][i] += F(v, i - d[v]);
f[u][i] = f[u][i] / deg + 1;
}
f[u][i] = min(f[u][i], x + H - i);
}
}
return abs(f[1][H] - x) > eps;
}
int main ()
{
freopen("kancolle.in", "r", stdin);
freopen("kancolle.out", "w", stdout);
scanf("%d%d%d", &n, &m, &H);
for ( int i = 1, u, v; i <= m; i ++ )
{
scanf("%d%d", &u, &v);
edge[u].push_back(v);
}
for ( int i = 1; i <= n; i ++ )
scanf("%d", &d[i]);
double l = 0, r = 1e6 + 5, ans = -1;
while ( r - l > eps )
{
double mid = 0.5 * ( l + r );
if ( Check(mid) )
ans = mid, r = mid;
else
l = mid;
}
if ( ans < 0 )
printf("-1\n");
else
printf("%.8lf\n", ans);
return 0;
}