EA 的练习赛题解

EternalAlexander · 2020-02-02 11:47:56 · 个人记录

EA 的练习赛简要题解

suffix

本题是签到题。

难度：普及-

前置知识：快速幂。

Subtask 1

暴力

Subtask 2

注意到，对于任意 i>1 ，S_{1...i} 是 S_{i+1...n} 的子串，则 S_{1...i-1} 必然为 S_{i...n} 的子串。因此，原限制等价于第一个字符不能在后面出现过。答案为 26\times 25^{n-1} 。如果你不会快速幂，那么你可以得到出题人慷慨送给你的这 78 分。

Subtask 3

快速幂即可。

#include <bits/stdc++.h>
#define ll long long
int n;
const int mod=998244353;
int qpow(int a,int b){
    if (b==0)return 1;
    ll d=qpow(a,b>>1);d=d*d%mod;
    if (b&1)d=d*a%mod;
    return d;
}
int main(){
    scanf("%d",&n);
    printf("%d",(ll)26*qpow(25,n-1)%mod);
    return 0;
}

p.s.

事实上，后面几乎所有题都会用到快速幂，这题算是教程。

senpai

本题是第二个签到题。

难度：普及/提高-

前置知识：乘法逆元。

Subtask 1

如果 n=2，比较强的那个容器答案为 1 ，另一个答案为 0 。n=1 则输出 0 。

这个子任务优美地考察了选手使用 if 语句的能力。

Subtask 2

爆搜。使用链表实现会较为容易。

Subtask 3

状压 dp，令 f_{S} 表示还活着的容器集合为 S 的概率。求答案的话，ans_i = \sum_{i\in S} f_S 。

Subtask 4

用前面的暴力打个表，发现答案为 \frac{n-2}{2}, \frac{n-2}{2} ... n-1 。

Subtask 5

前面的部分分和正解都没什么关系，但我也不知道能给什么部分分了。

考虑对每个容器分别计算答案，令 pre_i 表示 i 前面第一个比 i 大的位置，不存在则为 0，nxt_i 表示 i 后面第一个比 i 大的位置，不存在则为 n+1。原序列被分成了 [1,pre_i]，[pre_i+1,i]，[i,nxt_i-1]，[nxt_i,n] 四段。

一个重要的发现是，计算容器 i 的答案时，这几段里面的元素是什么是无关紧要的，我们只关心这几段的长度。特别地，对于一，四两段我们只关心它们长度之和。

考虑到，如果 i 要活下来，在任何一次决斗中，对手都不能是 pre_i 和 nxt_i ，也就是不能碰到第一段和第四段。因为第二，三两段无论怎么变化都不会出现比 i 大的元素，而如果 pre_i 或者 nxt_i 在决斗中被击倒，新的边界上的元素一定会比它们大，i 依然不能与新的边界元素进行决斗。

可以开始 dp。当计算容器 u 的答案时，令 f_{i,j,k} 表示已经进行了 i 轮，[pre_u+1,u-1] 这一段的大小为 j ，[u+1,nxt_u-1] 这一段大小为 k 的概率。为了保证容器 u 一直存活，需要让 j 和 k 恒大于等于 0 。

另外两段的总长度可以用 i-j-k-1 得到，至此转移显然。注意一下当 pre_i=0 或者 nxt_i = n+1 时会出现一点不一样的情况，因为一，四两段可能根本不存在，转移时需要特判一下。细节可以参考代码。

复杂度 \mathcal O(n^4) 。因为 n 只有 50 ，合理范围内的多项式复杂度算法应该都能通过。

#include <bits/stdc++.h>
#define ll long long
const int mod=998244353;
int n,p[55],nxt[55],pre[55],f[55][55][55],fac[55];
int qpow(int a,int b){
    if (b==0)return 1;
    ll d=qpow(a,b>>1);d=(ll)d*d%mod;
    if (b&1)d=d*a%mod;
    return d;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&p[i]);
    for(int i=1;i<=n;++i){
        pre[i]=0;nxt[i]=n+1;
        for(int j=1;j<i;++j)if(p[j]>p[i])pre[i]=j;
        for(int j=n;j>i;j--)if(p[j]>p[i])nxt[i]=j;
    }
    for(int i=1;i<=n;++i){
        std::memset(f,0,sizeof(f));
        f[0][i-pre[i]-1][nxt[i]-i-1]=1;
        int ans=0,sum=1;
        for(int j=1;j<n;++j){
            sum=(ll)sum*(n-j)%mod;
            int inv=qpow(sum,mod-2);
            for(int k=0;k<=n;++k)
            for(int l=0;1+k+l<=n-j;++l){
                f[j][k][l]=(ll)f[j-1][k][l+1]*(l+1+(nxt[i]!=n+1))%mod;
                f[j][k][l]=(f[j][k][l]+(ll)f[j-1][k+1][l]*(k+1+(pre[i]!=0))%mod)%mod;
                f[j][k][l]=
                (f[j][k][l]+(ll)f[j-1][k][l]*
                (n-1-k-l-j-(pre[i]!=0&&nxt[i]!=n+1))%mod)%mod;
                ans=(ans+(ll)f[j][k][l]*inv%mod)%mod;
            }
        }printf("%d ",(ll)ans);
    }
    return 0;
}

p.s

其他四个都是很久以前出的，这个题是为了降低一点难度差距这次临时造的。

upd.据某人说是原题？可能是我做题少了，没见过。

silksong

本题是简单题。

难度：普及+/提高

前置知识：斜率优化。

Subtask 1

爆搜，注意搜是有技巧的，太暴力可能不是很跑得过去。

Subtask 2

考虑唯一的这条弦 (u,v) ，割掉它的代价是 a 在 u 之前的最小值乘以 b 在 v 之后的最大值。

Subtask 3

显然切割 (1,n) 可以割掉所有弦，输出 1 即可。

Subtask 4

合理范围内的多项式复杂度算法应该都可以通过。

Subtask 5

首先观察到，对于两条弦 i 和 j ，如果 u_i\leq u_j 且 v_i\geq v_j 那么 j 是没有用的，因为只要 i 被割掉 j 一定也会被割掉。我们先把所有没有用的弦删去，剩下的弦按照 u 排序，显然不会再有任意两条弦相交。

上面两步的目的是使每一次切割割掉的弦的编号连续，然后就可以考虑按照弦 dp 了。f_i 表示割掉 i 之前的弦的最小代价，枚举上一次切割中最后一个被割掉的弦转移即可。预处理一个前后缀最小值即可做到 \mathcal O(1) 转移。具体而言，令 c_i = \min_{j=1}^i a_j ，d_i=\min_{j=i}^n b_j，转移式可写成 f_i = \min_{j=0}^{i-1} f_j + c_{u_{j-1}-1}\times d_{v_i+1}。注意一下边界情况。

Subtask 6

对上式斜率优化。注意斜率优化细节，有可能 x 值相同导致斜率不存在，需要特殊处理。

#include <bits/stdc++.h>
#define maxn 500108
#define ll long long
struct node {
    int u,v;
}L[maxn],T[maxn];
int cmp(node a,node b){return a.u==b.u?a.v>b.v:a.u<b.u;}
int n,m,a[maxn],b[maxn],tl,fr,re;
ll x[maxn],y[maxn],f[maxn];

void push(ll x1,ll y1){
    if (x1==x[fr]){y1=std::min(y[fr],y1);fr++;}
    while (re>fr&&(y[fr]-y1)*(x[fr+1]-x[fr])>(y[fr+1]-y[fr])*(x[fr]-x1))fr++;
    x[--fr]=x1;y[fr]=y1;
}

void update(ll k){
    while (re>fr&&(y[re-1]-y[re])<k*(x[re-1]-x[re]))re--;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)scanf("%d",&b[i]);
    for(int i=2;i<=n;++i)a[i]=std::min(a[i],a[i-1]);
    for(int i=n-1;i>=1;i--)b[i]=std::min(b[i],b[i+1]);
    for(int i=1;i<=m;++i)scanf("%d%d",&L[i].u,&L[i].v);
    std::sort(L+1,L+m+1,cmp);
    for(int i=1,r=0;i<=m;++i){
        if (L[i].v<=r)continue;
        r=L[i].v;T[++tl]=L[i];
    }fr=re=500003;x[fr]=a[T[1].u-1];y[fr]=0;
    for(int i=1;i<=tl;++i){
        update(-b[T[i].v+1]);
        f[i]=b[T[i].v+1]*x[re]+y[re];
        for(int j=fr;j<=re;++j)
            f[i]=std::min(f[i],b[T[i].v+1]*x[j]+y[j]);
        push(a[T[i+1].u-1],f[i]);
    }printf("%lld",f[tl]);
    return 0;
}

p.s.

这是本场唯一一个最优化问题。

search

本题是第二个简单题。

难度：提高+/省选-

前置知识：长链剖分，线段树。

upd：可以只使用树状数组实现，下面这个解法写麻烦了。

Subtask 1

考虑计算出所有方案中访问到的节点数总和再除掉总方案数。枚举所有可能情况，按照题意模拟。

Subtask 4

一条链显然那个最优性剪枝没有用，输出 n 。

Subtask 5

可以 dp，f_{i,j} 表示程序跑到节点 i ，当前深度限制是 j 时子树中访问节点数的期望。

Subtask 2

合理的多项式复杂度算法都可以通过。

Subtask 3

令 h_i 为 i 号节点子树中深度最小的叶子的深度，d_i 表示 i 号节点的深度，c_i 表示 i 号节点的子节点数量。

还是计算所有方案中访问到的节点数总和再除掉总方案数，我们可以对每个节点分别统计它会被计算多少次。考虑一个节点 x 被访问到的条件，不是它祖先的节点的访问顺序是任意的，对于每个它的祖先节点 u ,令 v 为 u 到 x 路径上的第一个点，发现 u 不能在访问 v 之前访问任何 h 值小于 d_x 的子节点，假设这样的子节点有 l 个，u 号节点有 m 个子节点，可以发现方案数为 \binom {m}{l+1}\times (n-l-1)! \times l! 。对每个节点一直往上爬统计贡献，然后乘上其它无关节点的子结点个数的阶乘即可。

这个做法可以同时通过 \text{Subtask 2, 3, 5} 。

Subtask 6

沿用 \text{Subtask 3} 的做法，考虑换一种方向计算。首先将所有节点的答案初始化为 \prod c_i! ，然后对每个节点 u 计算它对子树中节点的贡献，即除掉 c_u! 再乘上真实的贡献。考虑长链剖分，对于短儿子中的节点暴力遍历，然后算真实贡献时，限制必须先访问的节点数可以二分出来。对于长儿子我们需要对深度保存一棵线段树，将短儿子根据 h 排序，然后贡献到线段树上是一个区间乘法的形式，这个线段树需要线段树合并。注意这棵线段树的推标记的方式有些特别，细节可以参考代码。

尽管线段树合并，暴力遍历短儿子线段树，二分出节点数，算逆元等等有很多 log ，但这些 log 都不在一起，总复杂度依然是 \mathcal O(nlogn) 。常数合理的 \mathcal O(nlog^2n) 应该也可以通过。

#include <bits/stdc++.h>
#define maxn 300005
#define ll long long

const int mod=998244353;
int n,fa[maxn],h[maxn],root[maxn],tag[maxn<<5],tl,ans,fac[maxn],sum=1,depth[maxn],H[maxn],
son[maxn],vis[maxn],ifac[maxn];
std::vector<int>ch[maxn],rk[maxn];

int qpow(int a,int b){
    int ans=1;
    for(ll d=a;b;b>>=1,d=d*d%mod)
        if (b&1)ans=d*ans%mod;
    return ans;
}
int inv(int x){return qpow(x,mod-2);}
int dgr(int u){return ch[u].size();}
int cmp(int a,int b){return vis[a]||vis[b]?vis[a]<vis[b]:h[a]<h[b];}
int binom(int n,int m){return (ll)fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int calc(int n,int l){return (ll)binom(n,l+1)*fac[n-l-1]%mod*fac[l]%mod;}

int find(int u,int lim){
    int l=1,r=dgr(u)-1,ans=0;
    while (l<=r){
        int mid=(l+r)>>1;
        if (h[ch[u][mid-1]]<lim){ans=mid;l=mid+1;}
        else r=mid-1;
    }
    return ans;
}

namespace ds {
    int ch[maxn<<5][2];
    void pushdown(int rt){
        if (!ch[rt][0]&&!ch[rt][1])return;
        if (ch[rt][0])tag[ch[rt][0]]=(ll)tag[ch[rt][0]]*tag[rt]%mod;
        if (ch[rt][1])tag[ch[rt][1]]=(ll)tag[ch[rt][1]]*tag[rt]%mod;
        tag[rt]=1;
    }
    int insert(int l,int r,int p,int rt){
        if (!rt){rt=++tl;tag[rt]=(l!=r);}
        if (l==r){
            tag[rt]=(tag[rt]+sum)%mod;
            return rt;
        }int mid=(l+r)>>1;
        pushdown(rt);
        if (p<=mid)ch[rt][0]=insert(l,mid,p,ch[rt][0]);
        else ch[rt][1]=insert(mid+1,r,p,ch[rt][1]);
        return rt;
    } 
    int merge(int u,int v){
        if (!u||!v)return u+v;
        pushdown(u);pushdown(v);
        ch[u][0]=merge(ch[u][0],ch[v][0]);
        ch[u][1]=merge(ch[u][1],ch[v][1]);
        if (!ch[u][0]&&!ch[u][1])tag[u]=(tag[u]+tag[v])%mod;
        return u;
    }
    void multiply(int l,int r,int L,int R,int v,int rt){
        if (l>R||r<L||!rt||l>r)return;
        if (l<=L&&R<=r){tag[rt]=(ll)tag[rt]*v%mod;return;}
        pushdown(rt);
        multiply(l,r,L,(L+R)>>1,v,ch[rt][0]);
        multiply(l,r,((L+R)>>1)+1,R,v,ch[rt][1]);
    }
    void dfs1(int rt,int u,int v,int l,int r){
        if (!rt)return;
        if (l==r){
            int L=l-depth[u];
            tag[rt]=(ll)tag[rt]*calc(dgr(u),find(u,L)-(h[v]<L)+(h[son[u]]<L))%mod;
            return;
        }dfs1(ch[rt][0],u,v,l,(l+r)>>1);
        dfs1(ch[rt][1],u,v,((l+r)>>1)+1,r);
    }void sum(int l,int r,int rt){
        if (!rt)return;
        if (l==r)
            ans=(ans+tag[rt])%mod;
        pushdown(rt);
        sum(l,(l+r)>>1,ch[rt][0]);sum(((l+r)>>1)+1,r,ch[rt][1]);
    }
}

void prework(int u){
    h[u]=1e9;H[u]=1;
    for(int i=0;i<dgr(u);++i) {
        int v=ch[u][i];
        prework(v);
        h[u]=std::min(h[u],h[v]+1);
        H[u]=std::max(H[u],H[v]+1);
        if (H[v]>H[son[u]])son[u]=v;
    }if (h[u]>n)h[u]=1;
    vis[son[u]]=1;
}

void dfs(int u){
    depth[u]=depth[fa[u]]+1;
    for(int i=0;i<dgr(u);++i)dfs(ch[u][i]);
    int len=dgr(u);
    if (len){
        ds::multiply(1,len==1?n:h[ch[u][0]]+depth[u],1,n,fac[len],root[son[u]]);
        for(int i=0;i<len-1;++i){
            ds::multiply(h[ch[u][i]]+depth[u]+1,
            i==len-2?n:h[ch[u][i+1]]+depth[u],1,n,calc(len,i+1),root[son[u]]);
            ds::dfs1(root[ch[u][i]],u,ch[u][i],1,n);
        } 
        for(int i=0;i<dgr(u);++i)
            root[u]=ds::merge(root[u],root[ch[u][i]]);
        tag[root[u]]=(ll)tag[root[u]]*inv(fac[len])%mod;
    }
    root[u]=ds::insert(1,n,depth[u],root[u]);
}

int main(){
    scanf("%d",&n);
    fac[0]=ifac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=(ll)i*fac[i-1]%mod;
        ifac[i]=(ll)inv(i)*ifac[i-1]%mod;
    }
    for(int i=2;i<=n;++i){
        scanf("%d",&fa[i]);
        ch[fa[i]].push_back(i);
    }prework(1);
    for(int i=1;i<=n;++i){
        std::sort(ch[i].begin(),ch[i].end(),cmp);
        if (son[i])assert(ch[i][dgr(i)-1]==son[i]);
        sum=(ll)sum*fac[dgr(i)]%mod;
    }
    dfs(1);
    ds::sum(1,n,root[1]);
    printf("%d",(ll)ans*inv(sum)%mod);
    return 0;
}

p.s.

尽管多一个 log ，重链剖分也是可以通过的。

sacrificial

本题是第三个简单题。

难度：提高+/省选-

前置知识：prufer 序列。

upd：似乎可以插值。

Subtask 1

手动把所有可能的情况画出来，发现答案是 102 。

写个爆搜也行。

Subtask 2

众所周知 n 个节点的无根树有 n^{n-2} 种，有根树就是 n^{n-1} 种，输出 n^{n-1} 即可。

Subtask 4

枚举树的形态然后计算。

可以同时通过 \text{Subtask 3}。

Subtask 3

考虑一下假如我们知道了每个点的权值是什么，应该如何计算合法的树的形态数。

从小到大考虑每一种权值并将其加入树中，答案是每种权值的合法方案数的乘积。

令 A_i 为权值为 i 的节点个数，f(i)=\sum_{j=0}^i A_i ，G_{i,j} 为当前权值的节点有i个，之前有j个节点，将当前节点加入原树的方案数，只需要快速计算 G_{i,j} 即可。

求解 G_{i,j} 时，把已经加入原树的所有 j 个点看作一个大点，直接考虑这个大点和所有新点的生成树的 prufer 序列。如果这个大点在 prufer 序列中出现的次数为 d，则其度数为 d+1。因为这个大点其实是 j 个点，我们需要把答案乘上 j^{d+1}。

简单推导一下，

G_{i,j}=\sum_{p_1,p_2...p_{i+1-2}\ p_k \in [1,i+1]} j^{d+1}

$j\times \sum_{p_1,p_2...p_{i-1}\ p_k \in [1,i+1]} \ \prod_{k=1}^{i-1} \begin{cases}j\,(p_k=1)\\1\end{cases}

j\times \prod_{k=1}^{i-1}\sum_{p_k=1}^{i+1}\begin{cases}j\,(p_k=1)\\1\end{cases}

= j\times(i+j)^{i-1}

(求助，怎么在 luogu 打多行公式啊...)

枚举权值序列，直接计算即可。

另一种计算 G_{i,j} 的方法是枚举大点出现次数，复杂度略高。

在这个数据范围下，通过矩阵树定理等方式计算 G_{i,j} 也是可行的。

Subtask 5

如果你的复杂度稍高或者不知道如何处理巨大的值域可以的得到这一档分。

Subtask 6

考虑计算恰好有 k 种权值的方案数，乘上一个 \binom{m}{k} 即可。下面我们计算时，规定假如一共恰好有 k 种权值，则所有点的权值都是 [1,k] 中的整数。

令 F 为树中所有节点的权值排序后的数列。对于特定的 F 序列，我们可以根据 \text{Subtask 4} 的做法算出树的形态数。然后我们还要考虑有多少种权值序列排序后会得到这个 F 。

为了建立一个一一映射的关系，我们加入一个排序第二关键字为节点编号。令 c_i 表示 F 中元素 i 的个数，s_i=\sum_{j< i} c_j ，则排序后恰好得到 F 的权值序列数量为 \prod \binom{n-s_i}{c_i}。

对于特定的 F 序列，我们记它的答案为根据 F 算出的树的形态数乘以排序后得到 F 的权值序列数量。最后的答案是所有 F 序列的答案之和。我们可以考虑 dp，f_{i,j} 表示长度为 i ，最后一个元素为 j 的所有 F 序列的答案之和，枚举最后一种元素的数量转移即可。然后恰好有 k 种权值且每种权值都在 [1,k] 的范围内的树的形态数之和就是 f_{n,k} ，最终的答案是 \sum_{k=1}^n \binom{m}{k} \times f_{n,k} 。注意因为 m 很大，计算组合数需要一点技巧。

#include <bits/stdc++.h>
#define maxn 1505
#define ll long long
const int mod=998244353;
int n,m,C[maxn][maxn],pw[maxn*2][maxn],g[maxn][maxn],f[maxn][maxn],ans,fac[maxn];
int qpow(int a,int b){
    if (b==0)return 1;
    ll d=qpow(a,b>>1);d=(ll)d*d%mod;
    if (b&1)d=d*a%mod;
    return d;
}
int binom(int n,int m){
    int ans=qpow(fac[m],mod-2);
    for(int j=n-m+1;j<=n;j++)ans=1ll*ans*j%mod;
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    fac[0]=1;for(int i=1;i<=n;++i)fac[i]=(ll)fac[i-1]*i%mod;
    C[0][0]=1;
    for(int i=1;i<=n;++i){
        C[i][0]=1;
        for(int j=1;j<=n;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    for(int i=1;i<=n*2;++i){
        pw[i][0]=1;
        for(int j=1;j<=n;++j)pw[i][j]=(ll)pw[i][j-1]*i%mod;
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            g[i][j]=(ll)j*pw[i+j][i-1]%mod;
    for(int i=1;i<=n;++i)g[i][0]=pw[i][i-1];
    f[0][0]=1;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    for(int k=0+i-1;k<j;++k)
        f[i][j]=(f[i][j]+(ll)f[i-1][k]*g[j-k][k]%mod*C[n-k][j-k]%mod)%mod;
    for(int i=1;i<=n&&i<=m;++i)ans=(ans+(ll)binom(m,i)*f[i][n]%mod)%mod;
    printf("%d",ans);
}

总结

本着不卡时间不卡空间的原则，出题人把每题的时限都开到了 std 的十倍以上，空间都开到了 luogu 规定的上限。

本次比赛难度较低，题意清晰，解法套路，给出题人点赞！

EA 的练习赛 题解

EA 的练习赛 简要题解

suffix

Subtask 1

Subtask 2

Subtask 3

p.s.

senpai

Subtask 1

Subtask 2

Subtask 3

Subtask 4

Subtask 5

p.s

silksong

Subtask 1

Subtask 2

Subtask 3

Subtask 4

Subtask 5

Subtask 6

p.s.

search

Subtask 1

Subtask 4

Subtask 5

Subtask 2

Subtask 3

Subtask 6

p.s.

sacrificial

Subtask 1

Subtask 2

Subtask 4

Subtask 3

Subtask 5

Subtask 6

总结

EA 的练习赛题解

EA 的练习赛简要题解