3.25 模拟赛 A~B

A String

设 $n$ 为 $S_1$ 长度，$m$ 为 $S_2$ 长度。

我们考虑设 $f[i]$ 表示 $S_1$ 从 $i$ 开始向后 $m$ 个字母和第二个串相同的位置个数。我们把它写出来是：

$$f[i] = \sum_{j=i}^{i+m} [S_1[j] = S_2[j - i]]$$

稍微化简一下：

$$f[i] = \sum_{p-q=i} [S_1[p]=S_2[q]]$$

这一看就很像差卷积的形式！于是我们考虑对每个字符分开做，设 $s_1[i] = 1$ 表示 $S_1[i]$ 是否为当前枚举的字符，那么这个东西可以写成：

$$f[i] = \sum_{p-q=i} s_1[p]s_2[q]$$

然后跑一遍差卷积就好了。

字符集大小只有 $10$ 复杂度 $10n\log n$ 出题人给了 5s 显然能过。

极限数据 3.8s 的code：

int n , m , k;
int A[MAXN] , B[MAXN] , b[MAXN] , F[MAXN];
char s[MAXN] , t[MAXN];
int bac[129];

int wn[2][MAXN];
int Pow( int x , int y ) {
    int res = 1;
    while (y) {
        if (y & 1) res = res * (ll) x % P;
        x = x * (ll) x % P, y >>= 1;
    }
    return res;
}
void getwn(int l) {
    for (int i = 1; i < (1 << l); i <<= 1) {
        int w0 = Pow(3, (P - 1) / (i << 1)), w1 = Pow(3, P - 1 - (P - 1) / (i << 1));
        wn[0][i] = wn[1][i] = 1;
        for (int j = 1; j < i; ++j)
            wn[0][i + j] = wn[0][i + j - 1] * (ll) w0 % P,
                    wn[1][i + j] = wn[1][i + j - 1] * (ll) w1 % P;
    }
}
int rev[MAXN];
void getr(int l) { for(int i=1;i<(1<<l);++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l-1); }
void NTT(int *A,int len,int f) {
    for (int i = 0; i < len; ++i) if (rev[i] < i) swap(A[i], A[rev[i]]);
    for (int l = 1; l < len; l <<= 1)
        for (int i = 0; i < len; i += (l << 1))
            for (int k = 0; k < l; ++k) {
                int t1 = A[i + k], t2 = A[i + l + k] * (ll) wn[f][l + k] % P;
                A[i + k] = (t1 + t2) % P;
                A[i + l + k] = (t1 - t2 + P) % P;
            }
    if (f == 1) for (int inv = Pow(len, P - 2), i = 0; i < len; ++i) A[i] = A[i] * (ll) inv % P;
}
int len , l;
void Just_DOIT( ) {
    for( int i = 0 ; i <= m ; ++ i ) b[i] = B[m - i];
    NTT( A , len , 0 ) , NTT( b , len , 0 );
    rep( i , 0 , len ) A[i] = 1ll * A[i] * b[i] % P;
    NTT( A , len , 1 );
    rep( i , m , m + n - 1 ) F[i - m] += A[i];
}

void solve() {
//    freopen("input","r",stdin);
//    freopen("ot","w",stdout);
    cin >> k;
    for( int i = 0 ; i < 9 ; ++ i ) bac["syfaknoi"[i]] = i;
    scanf("%s",s) , scanf("%s",t);
    n = strlen( s ) , m = strlen( t );
    len = 1 , l = 0;
    while( len <= n + m ) len <<= 1 , ++ l;
    getr( l ) , getwn( l );
    rep( i , 0 , n - 1 ) s[i] = bac[s[i]];
    rep( i , 0 , m - 1 ) t[i] = bac[t[i]];
    rep( i , 0 , 9 ) {
        rep( j , 0 , len ) A[j] = b[j] = B[j] = 0;
        rep( j , 0 , n - 1 ) A[j] = ( s[j] == i );
        rep( j , 0 , m - 1 ) B[j] = ( t[j] == i );
        Just_DOIT();
    }
    int re = 0;
    rep( i , 0 , n - m ) if( m - F[i] <= k ) ++ re;
    cout << re << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

B tree

通过这个题又加深了那几个树上的结论的印象。。理一下这三个结论：

for( int v : G[u] )
  for( int w : G[u] ) {
    // do sth O(1)
  }

这个东西是 $O(n^2)$ 的。考虑 这个显然有 $\sum deg[i]^2 \le (\sum deg[i])^2$

for( int v : G[u] )
  for( int w : G[u] ) {
    for( int i = 1 ; i <= siz[v] ; ++ i )
      for( int j = 1 ; j <= siz[w] ; ++ j )
        // do sth in O(1)
  }

这个东西也是 $O(n^2)$ 的！因为可以考虑，每对点其实只有在 LCA 处才有贡献。所以没对点的贡献是 1 ，总复杂度自然是 $O(n^2)$。

还有个树形背包的结论，具体建议参见 钟神的 Blog 写得很详细。

然后回到这个题。其实 dp 很显然的，设 $dp[u][i]$ 表示 $u$ 为根的子树中选择了 $i$ 个点（包括 $u$ ）作为一个联通的二叉树。然后我们的转移就是选择一个儿子作为 左儿子 / 右儿子，或者选择两个儿子分别作为左右儿子。

具体方程很好推，我也懒得写公式了。

开始踩了个坑，我认为可以不管单独选择子树作为右儿子的情况。。然后这么写交上去成功获得了 51 分的好成绩。但是看起来确实选择子树作为左儿子得到的贡献必然超过作为右儿子啊？毕竟作为右儿子不会让其他点的深度变大而且还不如只选择初始一个点的情况，但是稍微画一下特殊的情况，会发现当一个子树很深很大的时候，让它作为右儿子是比作为左儿子单独成立更好的。。（其实是个非常显然的问题只是自己开始没注意到ww）

int n , m , k;
int fa[MAXN];
vi G[MAXN];
long long dp[MAXN][MAXN] , mx[MAXN];
int siz[MAXN];
void dfs( int u ) {
    siz[u] = 1;
    long long re = 0;
    for( int v : G[u] ) {
        dfs( v );
        siz[u] += siz[v]; re += mx[v];
    }
    dp[u][1] = re + siz[u];
    for( int v : G[u] ) {
        rep( i , 1 , siz[v] ) if( dp[v][i] )
            dp[u][1 + i] = max( dp[u][1 + i] , max( ( re - mx[v] ) + ( i + 1 ) * ( siz[u] - siz[v] ) + dp[v][i] , re - mx[v] + siz[u] + dp[v][i] ) );
    }

    for( int v : G[u] )
        for( int t : G[u] ) if( t != v )
            rep( i , 1 , siz[v] ) if( dp[v][i] )
                rep( j , 1 , siz[t] ) if( dp[t][j] )
                    dp[u][i + j + 1] = max( dp[u][i + j + 1] , ( re - mx[v] - mx[t] ) + ( siz[u] - siz[v] ) * ( i + 1 ) + dp[v][i] + dp[t][j] );
    rep( i , 1 , siz[u] ) if( !mx[u] || dp[u][i] > mx[u] ) mx[u] = dp[u][i];
}
void solve() {
    cin >> n;
    rep( i , 2 , n ) scanf("%d",fa + i) , G[fa[i]].pb( i );
    dfs( 1 );
//    cout << mx[2] << endl;
    cout << mx[1] << endl;
}

signed main() {
//    freopen("big2.in","r",stdin);
//    freopen("ot","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}