ZROI 2022 没打的场

· · 个人记录

CSP7连 附加赛 Day1

A

一道好题，启示我们要从多个角度思考。并且思考这道题不可做的原因是什么，然后解决它/换思路。

首先我们发现字符串中的关系十分的混乱，有很多位置需要相等，容易想到维护这些相等的位置，可以用并查集，假设最后维护出了 cnt 个连通块，则 ans=m^{cnt} 。时间复杂度 O(kn\log n) 。

const int N=2010,p=1e9+7;
int fa[N],cnt,n,m,k;
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
void merge(int x,int y){fa[get(x)]=get(y);}
int power(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*c*a%p;
        a=1ll*a*a%p;
    }
    return c;
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n-k+1;i++)for(int j=i;j<=(i*2+k)>>1;j++)merge(j,i*2+k-j-1);
    for(int i=1;i<=n;i++)if(fa[i]==i)cnt++;
    cout<<power(m,cnt);
    return 0;
}

B

容易想到假设没有行列之间的影响的话，就用堆维护最大值即可。

发现假设行列选择方案数固定后，对答案的贡献值是一定的。即为 i\times (k-i)\times p 。

于是我们可以枚举行的方案数，更新最大值即可。

const int N=1010;
int a[N][N],s[N],t[N],n,m,k,p,ans=-1e18,res=0;
priority_queue<int>q1,q2;
signed main()
{
    n=read(),m=read(),k=read(),p=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
            s[i]+=a[i][j];
            t[j]+=a[i][j];
        }
    }
    for(int i=1;i<=n;i++)q1.push(s[i]);
    for(int i=1;i<=m;i++)q2.push(t[i]);
    for(int i=1;i<=k;i++){
        s[i]=s[i-1]+q1.top();
        q1.push(q1.top()-p*m);
        q1.pop();
    }
    for(int i=0;i<=k;i++){
        ans=max(ans,res+s[k-i]-i*(k-i)*p);
        res+=q2.top();q2.push(q2.top()-p*n);q2.pop();
    }
    cout<<ans;
    return 0;
}

但受 一开始假设行列不影响的贪心思想 的影响，很容易写出一下的错误贪心：

const int N=1010;
int a[N][N],s[N],t[N],n,m,k,p,cnt_s,cnt_t,ans;
priority_queue<int>q1,q2;
int main()
{
    n=read(),m=read(),k=read(),p=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
            s[i]+=a[i][j];
            t[j]+=a[i][j];
        }
    }
    for(int i=1;i<=n;i++)q1.push(s[i]);
    for(int i=1;i<=m;i++)q2.push(t[i]);
    while(k--){
        int A=q1.top(),B=q2.top();
        if(A-cnt_t*p>B-cnt_s*p){
            cnt_s++;
            ans+=A-cnt_t*p;
            q1.pop();
            q1.push(A-m*p);
        }
        else {
            cnt_t++;
            ans+=B-cnt_s*p;
            q2.pop();
            q2.push(B-n*p);
        }
    }
    cout<<ans;
    return 0;
}

这样为什么是错的呢？

很容易构造出AB相等的情况，发现无法在规定的数据范围内决策选A还是B。

CSP7连 附加赛 Day2

A

观察题面中求 LCA 的代码容易发现，答案正确的充要条件是 dep_x-dep_y=d_x-d_y 。（d 是真实的深度）

考虑如何统计，设 z=LCA(x,y) ，显然只需要统计 (x,z),(y,z) 路径上 1 的个数即可。

对于 70 \% 的数据，枚举 1 的个数，即为 \sum \binom{d_x-d_z}{i}\binom{d_y-d_z}{d_x-d_y-i} 。

然后这就是个范德蒙德卷积，有 \sum \binom{d_x-d_z}{i}\binom{d_y-d_z}{d_x-d_y-i}=\binom{d_x+d_y-2d_z}{d_x-d_z} \ (d_x\leq d_y) 。于是就可以直接做了，时间复杂度 O(n\log n) 。

const int N=2e5+10,p=998244353;
vector<int>e[N];
int n,m,d[N],f[N][20],fac[N],inv[N];
int power(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=c*a%p;
        a=a*a%p;
    }
    return c;
}
void dfs(int x){
    for(int i=1;i<=17;i++)f[x][i]=f[f[x][i-1]][i-1];
    for(int y:e[x]){
        if(y!=f[x][0]){
            f[y][0]=x,d[y]=d[x]+1;
            dfs(y);
        }
    }
}
int LCA(int x,int y){
    if(d[x]<d[y])swap(x,y);
    for(int i=17;i>=0;i--)if(d[f[x][i]]>=d[y])x=f[x][i];
    if(x==y)return x;
    for(int i=17;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
void init(){
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
    inv[n]=power(fac[n],p-2);
    for(int i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%p;
}
int C(int x,int y){
    return fac[x]*inv[y]%p*inv[x-y]%p;
}
signed main()
{
    n=read();
    init();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        e[x].pb(y),e[y].pb(x);
    }
    d[1]=1;
    dfs(1);
    m=read();
    while(m--){
        int x=read(),y=read(),z;
        z=LCA(x,y);
        if(d[x]>d[y])swap(x,y);
        printf("%lld\n",C(d[x]+d[y]-2*d[z],d[x]-d[z])*power(power(2,d[x]+d[y]-2*d[z]),p-2)%p);
    }
    return 0;
}

CSP7连 附加赛 Day5

C

树形dp，设 f_x/g_x/cnt_x 分别表示以 x 为根的连通块的平方和/和/数量。于是有：

f_x\leftarrow f_x\times cnt_y+f_y\times cnt_x +2\times g_x\times g_y g_x\leftarrow g_x\times cnt_x+g_y\times cnt_y cnt_x\leftarrow cnt_x\times cnt_y

记得初始化。

const int N=1e5+10,p=998244353;
vector<int>e[N];
int n,ans,f[N],g[N],w[N],cnt[N];
void dfs(int x,int fa){
    cnt[x]=1;
    g[x]=w[x];
    f[x]=w[x]*w[x]%p;
    for(int y:e[x]){
        if(y!=fa){
            dfs(y,x);
            f[x]=(f[x]+f[x]*cnt[y]+2*g[x]*g[y]+cnt[x]*f[y])%p;
            g[x]=(g[x]+g[x]*cnt[y]+g[y]*cnt[x])%p;
            cnt[x]=(cnt[x]+cnt[x]*cnt[y])%p;
        }
    }
    ans=(ans+f[x])%p;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)w[i]=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}