CSP 联测 34

Ishar-zdl的博客 / 2024-09-27 / 原文

A 几何

显然有一个 $\mathcal{O}(nx^2)$ 的 DP，算一下是 1e9 左右，~~注意到数据水所以可以直接过，~~ 注意到我们只关心可达性，上 bitset 设 $f_{i,j}$ 表示匹配到 $i$ 位置，$x$ 匹配到 $j$ 位置是 $y$ 各位置的匹配状态，然后直接记一下 $x$ 字母的出现位置，和 $y$ 的各个字符匹配状态就做完了，时间 $\mathcal{O}(\frac{nx^2}{w})$，~~加了剪枝后的暴力吊打这个，根本卡不掉~~

B 分析

我不会图论和树形 DP。
题目想干的就是在这棵树上完成一个一笔画问题，从这个方向入手，A 操作相当于加一条重边，对于一个有 $x$ 个奇点的图来说，需要 $\left\lfloor\frac{x}{2}\right\rfloor-1$ 次 B 操作才成完成一笔画（0 个奇点特殊），然后就只用考虑对于加完边后的图计算答案即可。
设 $f_{i,0/1/2}$ 表示在 $i$ 子树内，没有奇点/ $i$ 是奇点/ $i$ 不是奇点但子树内有奇点的最小代价。有一个显然的性质，奇点总是有偶数个，这样使转移更加明确。
对于转移，加边不改变奇偶，不加边改变，建议画一个九宫格看看，注意两个有奇点的子树合并时，代价要在加上一个 $B$，因为直接加是 $\frac{k_1+k_2}{2}-2$。

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e5+10,inf=1e15;
int n,A,B,f[N][3];
std::vector<int> e[N];
inline void dfs(int u,int fa){
    f[u][0]=0;f[u][1]=f[u][2]=inf;
    for(int v:e[u]){
        if(v==fa)continue;
        dfs(v,u);
        int _0=f[u][0],_1=f[u][1],_2=f[u][2];
        int zc=_0+f[v][0]+A;
        f[u][0]=zc;
        zc=_0+f[v][0];zc=std::min(zc,_0+f[v][1]);zc=std::min(zc,_0+f[v][2]+B);zc=std::min(zc,_2+f[v][0]+B);zc=std::min(zc,_2+f[v][1]+B);zc=std::min(zc,_2+f[v][2]+B*2);zc=std::min(zc,_1+f[v][0]+A);zc=std::min(zc,_1+f[v][1]+A+B);zc=std::min(zc,_1+f[v][2]+A+B);
        f[u][1]=zc;
        zc=_1+f[v][0];zc=std::min(zc,_1+f[v][1]);zc=std::min(zc,_1+f[v][2]+B);zc=std::min(zc,_0+f[v][1]+A);zc=std::min(zc,_0+f[v][2]+A);zc=std::min(zc,_2+f[v][0]+A);zc=std::min(zc,_2+f[v][1]+A+B);zc=std::min(zc,_2+f[v][2]+A+B);
        f[u][2]=zc;
    }
}
signed main(){
    freopen("analyse.in","r",stdin);freopen("analyse.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read(),A=read(),B=read();A=std::min(A,B);
    for(int i=1;i<n;++i){
        int u=read(),v=read();e[u].emplace_back(v);e[v].emplace_back(u);
    }
    dfs(1,0);
    std::cout<<std::min(f[1][0],std::min(f[1][1],f[1][2]))<<'\n';
}

代数

神仙计数，赛时以为是二项式定理题。
考虑 $x^k$ 的组合意义，发现就是从一个大小为 $x$ 的几何随机选 $k$ 次，组成一个序列的方案数。期望具有线性性，所以 $E(x^k)=\sum_{j=1}^k\sum_{i_j=1}^{n}(这种选择方案合法的概率P)$，这样就把答案转化为了随机选 $k$ 个点（可重），都在 $u$ 子树内的概率和。
显然很难统计这个，然后就到了本题最为人类智慧的地方，考虑在后面虚空加入 $k$ 个点，他们的父亲只能是 $[1,n]$，然后问题就转化这 $k$ 个虚点都在一个子树内的概率和（应该是为了确保都有 $k$ 个点可选），然后设 $f_{i,j}$ 表示以 $[i,n]$ 这些点做父亲，虚点构成了 $j$ 个连通块的概率，注意，这里 DP 表示的是概率，并不是概率和，所以 DP 的是 $\frac{\sum p}{n^k}$，最后答案要乘上 $n^k$。$f_{u,1}$ 就是 $u$ 的概率，这时所有虚点都是 $u$ 的子节点。有状态转移方程：

\[f_{i,j-l+1}\gets f_{i,j-l+1}+f_{i+1,j}\times{j\choose l}(i-1)^{j-l}/i^j \]

表示从 $j$ 个块中选择 $l$ 个连到 $i$ 上，剩下的连到 $[1,i-1]$ 上，后面依托是概率。
每次 DP 完一个 $i$ 后，先计算答案，因为实际上存在分 0 个块给 $i$ 节点，对于答案，这是不合法的，但是在转移中是必要的情况，考虑单独转移这个，直接 $f_{i,j}=f_{i,j}+f_{i,j}\times(i-1)^{j}/i^j$，时间复杂度 $\mathcal{O}(nk^2)$ 需要预处理逆元和次幂，存在 $\mathcal{O}(nk)$ 的第二类斯特林数解法。$n^2$ 做法不会，求来个大神教教。
最后计算出来的 $ans=ans\times n^k$，表示概率和。为什么是 $n^k$，因为是钦定意义是从 $n$ 个数中选择，尽管有一些点不合法，但是在计算的过程中他们合法的概率也是 0，不会对答案造成影响，如果不这样做，DP 的限制就更多了。

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10,mod=1e9+7;
int n,k,a[N],f[N][25],C[25][25],qp[25][N],ans,inv[25][N];
inline int mo(int x){return x<mod?x:x%mod;}
signed main(){
    freopen("algebra.in","r",stdin);freopen("algebra.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read();k=read();for(int i=1;i<=n;++i)a[i]=read();
    C[0][0]=1;
    for(int i=1;i<=k;++i){C[i][0]=1;for(int j=1;j<=i;++j)C[i][j]=mo(C[i-1][j]+C[i-1][j-1]);}
    f[n+1][k]=1;
    qp[0][0]=1;
    inv[1][1]=1;
    for(int i=2;i<=n;++i)inv[1][i]=(mod-mod/i)*inv[1][mod%i]%mod;
    for(int i=1;i<=n;++i){
        qp[0][i]=1;inv[0][i]=1;
        for(int j=1;j<=k;++j)qp[j][i]=mo(qp[j-1][i]*i),inv[j][i]=mo(inv[j-1][i]*inv[1][i]);
    }
    for(int i=n;i;--i){
        for(int j=1;j<=k;++j){
            for(int l=1;l<=j;++l){
                f[i][j-l+1]=mo(f[i][j-l+1]+f[i+1][j]*C[j][l]%mod*qp[j-l][i-1]%mod*inv[j][i]%mod);
            }
        }
        ans=mo(ans+a[i]*f[i][1]%mod);
        for(int j=1;j<=k;++j)
            f[i][j]=mo(f[i][j]+f[i+1][j]*qp[j][i-1]%mod*inv[j][i]%mod);
    }
    std::cout<<ans*qp[k][n]%mod<<'\n';
}

D 组合

幽默 ZROI，原题是 CEOI2023，APIO 的讲评题，但是参加的人都睡觉了，所以没一个人会。
考虑看这 $m$ 个数的第 $i$ 列，表示的是对第 $i$ 个位置的询问方案，对于第 $i$ 列的数和第 $j$ 列的数或出来的值，表示答案为 $(i,j)$ 时，询问得到的答案，如果有两个不同点对对应的列或出来的值一样，则这些询问一定无法确定出所有答案。所以题目转化为了找到 $N$ 个数，使得这些数两两或值不同。这题到这已经结束了，~~你完全可以，也应该去贺 std 了~~
构造比较困难，CEOI 表示模拟退火，std 表示玄学构造，建议直接用 std 跑两分钟出答案后直接交。