526互联

暑假集训 Day17 模拟赛题解

发布时间 2023-09-08 10:44:12作者: NBest

2023-08-03 18:18:03

前言

好家伙，很少完整订正一场比赛，可能是因为这个比赛相对来说确实不难吧（至少正解不难）。

总结与反思

这场比赛其实没有我想象的那么难，只是觉得题目可能不简单，就没有往简单的思路想，反而是被之前讲过的题疑惑，以为要用到一些很奇特的算法，结果打完以后看了题解再结合自己的思考，发现都是一些非常简单的题。然鹅第一题虽然想到正解了，却忘记了数据范围，和没想到正解的一样的分数，需要注意。

不过进步的点也是有的，发现自己可以更快更好地打部分分了（虽然有时候会产生畏难心理不敢去打），基本上赛后发现自己其实部分分可以拿 \(90\) 分甚至更多，下次争取继续优化暴力！

进入正题吧~

A题

简化题意：记一个数 \(x\) 的每一位数字的平方和为 \(s(x)\)，让你算 \([L,R]\) 内有多少数字满足 \(s(x)\times K=x\)。

\(1\le K,L,R \le 10^{18}\)。

一开始觉得是个裸的数位 dp，然后就在考场上大惊小怪，不知道是不是被我影响还是他们也看见了这个数据范围，然后赛后纷纷都说数位 dp 怎么打（郑宇轩打了一个跑了 \([0,L-1]\)，\([0,R]\) 的"数位 dp"）。

结果发现状态要么跟 \(K\) 有关，要么跟 \(x\) 有关，而这俩都是贼大，不可能枚举。

这使得我考虑到分类讨论，当 \(K\) 很小的时候就用数位 dp，具体：

  • 考虑到 \(s(x)\) 最大不超过 \(9^2 \times 18=1458\)，枚举 \(s(x)\)。
  • 存两个值，一个是 \(x/s(x)\) 的结果（下取整），和除后的余数，每加一位两边都乘 \(10\) 即可。
  • 最后判余数是否为 \(0\)，并且除后结果是否等于 \(k\)。

当 \(K\) 很大的时候，那也没几种可能，枚举即可。

等一下，没几种可能？

\(s(x)\times K=x\)

我们重新看一下，发现 \(s(x)\) 只有最大 \(1458\)，那么最多只有 \(1458\) 个 \(x\)，枚举即可。

想太多了啊啊啊，这么简单的题居然想到数位 dp 去了。

$\color {red} { 一定要注意数据范围，开__int128!!!} $

\(Code\)

typedef long long ll;
typedef __int128 inp;
int T;
inp K,L,R;
bool check(inp x,ll p){
    ll res=0;
    while(x){
        res+=(x%10)*(x%10);
        x/=10;
    }
    if(p==res)return 1;
    return 0;
}
int main(){
    cin>>T;
    while(T--){
        ll ans=0;
        K=read(),L=read(),R=read();
        for(ll i=1;i<=1620;i++){
            inp o=K*i;
            if(o<L||o>R)continue;
            if(check(o,i))ans++;
        }
        printf("%lld\n",ans);
    }
}

B

题意：

有一个 \(n\) 个点的树，每条边有边权。

现在给定点集 \(X,Y\)，要求你删若条边，使得 \(X\) 中任何一个点都和 \(Y\) 中的点不连通。同时要求你最小化删掉的边的边权之和。

\(1\le w\le 10^9,1\le |X|,|Y|\le n\le 10^5\)，\(X,Y\) 无交。

部分分

\(30\%:1 \le n\le 15\)，可以直接状压处理每一条边。

\(20\%:1\le |X|,|Y| \le 3\)，可以建只有 \(X,Y\) 的虚树（我不会，反正就是缩边吧），然后也没几条边，可以继续状压。

\(20\%:|X|=1\)，树形 dp，\(f[x]\) 表示 \(x\) 子树没有 \(Y\) 的方案数，然后转移即可。

\(60pts\ Code\)

typedef pair<int,ll> PII;
int n,X[100005],nx,ny,Y[100005],fa[100005];
pair<PII,ll> edge[100005];
ll lsum;
vector<PII>f[100005];
inline int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
bool work1(){
    ll res=0;
    for(int s=0;s<(1<<n-1);s++){
        for(int i=1;i<=n;i++)fa[i]=i;
        ll o=0;
        for(int i=1;i<n;i++){
            if(s&(1<<i-1)){
                int x=edge[i].first.first,y=edge[i].first.second;
                o+=edge[i].second;
                fa[find(x)]=find(y);
            }
        }
        bool flag=1;
        for(int i=1;i<=nx&&flag;i++){
            for(int j=1;j<=ny&&flag;j++){
                if(find(X[i])==find(Y[j]))flag=0;
            }
        }
        if(flag)res=max(res,o);
    }
    printf("%lld",lsum-res);
    return 0;
}
ll dp[100005];
bool M[100005];
void dfs1(int x,int Fa){//拿|X|=1的分
    for(PII PI:f[x]){
        int y=PI.first;
        if(y==Fa)continue;
        dfs1(y,x);
        if(M[y]){
            dp[x]+=PI.second;
        }else{
            dp[x]+=min(dp[y],PI.second);
        }
    }
}
int main(){
    n=read();
    nx=read();
    for(int i=1;i<=nx;i++)X[i]=read();
    ny=read();
    for(int i=1;i<=ny;i++)Y[i]=read(),M[Y[i]]=1;;
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        lsum+=w;
        edge[i]={{u,v},w};
        f[u].push_back({v,w});
        f[v].push_back({u,w});
    }
    if(n<=15)return work1()&0;
    dfs1(X[1],0);
    cout<<dp[X[1]]<<endl;
}

正解

居然都想到树形 dp 了，却以为这道应该是什么虚树或者奇奇怪怪的东西，然后发现就是树形 dp。

题解给的状态设计就是，用 f[0/1/2][x] 表示以 \(x\) 为根的子树，只与 普通节点/\(X\)/\(Y\) 联通的最小代价（保证子树内部 \(X,Y\) 也不联通）。

式子一出，直接秒了。

我看到提交记录里有人只记录了两维，因为只连接普通节点是不是也包含在了特殊情况内（可以看成连接数量为 \(0\)），然后就可以更简洁一点。

\(Code\)

typedef pair<int,ll> PII;
int n,nx,ny;
ll f[2][100005];// 0=only x 1=only y
bool is_x[100005],is_y[100005];
vector<PII>F[100005];
void dfs(int x,int fa){
    if(is_x[x])f[1][x]=1e14;
    if(is_y[x])f[0][x]=1e14;
    for(PII PI:F[x]){
        int y=PI.first;
        if(y==fa)continue;
        dfs(y,x);
        ll w=PI.second;
        if(!is_y[x])f[0][x]+=min(f[0][y],f[1][y]+w);
        if(!is_x[x])f[1][x]+=min(f[0][y]+w,f[1][y]);
    }
    return;
}
int main(){
    n=read();
    nx=read();
    for(int i=1;i<=nx;i++)is_x[read()]=1;
    ny=read();
    for(int i=1;i<=ny;i++)is_y[read()]=1;
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        F[u].push_back({v,w});
        F[v].push_back({u,w});
    }
    dfs(1,0);
    printf("%lld",min(f[0][1],f[1][1]));
    return 0;
}

哎呀呀，还是不要想得太复杂为妙，真就正解码量小于暴力。

C

题意

给定 \(n,k\)，求有多少长度为 \(n\) 的 \([1..n]\) 的排列 \(P\)，满足对于所有 \(i\in [1,n]\) 都有 \(|Pi−i|\le k\)。

\(0\le k\le 9,1\le n\le 10^{10-k}\)。

暴力做法

直接深搜可拿 \(20pts\)，然后把 \(k=1\) 的情况打表发现是一个广义斐波那契数列，然后可以用矩阵快速幂做（但是数据中 \(k=1\) 的情况好像不大，直接递推也行）。

赛时 \(Code\) \(30pts\)

const ll mod=1e9+7;
ll k,n;
bool work1(){
    int o[15];
    for(int i=1;i<=n;i++)o[i]=i;
    int rrr=0;
    do{
        bool flag=1;
        for(int i=1;i<=n;i++){
            if(abs(o[i]-i)>k){
                flag=0;break;
            }
        }
        if(flag)rrr++;
    }while(next_permutation(o+1,o+1+n));
    cout<<rrr<<endl;
    return 0;
}
bool vis[100005];
ll work2(int x,int v){
    if(x==n){
        return 1;
    }
    vis[v]=1;
    ll res=0;
    for(int i=max(1ll,x+1-k);i<=min(n,x+1+k);i++){
        if(!vis[i])res+=work2(x+1,i);
    }
    vis[v]=0;
    return res;
}
struct Matrix{
    ll a[2][2];
    Matrix(){memset(a,0,sizeof(a));}
    inline Matrix operator *(const Matrix &w)const{
        Matrix ans;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    ans.a[i][j]=(ans.a[i][j]+a[i][k]*w.a[k][j]%mod)%mod;
        return ans;
    }
};
bool work3(){
    Matrix a,ans,o;
    a.a[0][0]=2,a.a[1][0]=1;
    o.a[0][0]=o.a[0][1]=o.a[1][0]=1;
    ans=o;
    for(ll p=n-3;p;p>>=1,o=o*o)if(p&1)ans=ans*o;
    ans=ans*a;
    printf("%lld\n",ans.a[0][0]);
    return 0;
}
int main(){
    scanf("%lld%lld",&n,&k);
    if(n<=10)return work1(),0;
    else if(n<=17)return printf("%lld",work2(0,0))&0;
    else if(k==1)return work3(),0;
    else if(k==0)return puts("1"),0;
    //for(n=3,k=1;n<=20;n++)
    printf("%lld\n",work2(0,0));
}

正解

考虑当 \(i>k+1\) 时，第 \(i\) 位能放的范围只有 \([i-k,i+k]\)，所以我们只需要存 \([i-k,i+k]\) 的数是否被取即可。

这里我们有一个结论，当遍历到第 \(i\) 个时，遍历结束之后在 \([i-k,i+k]\) 中必然有 \(k+1\) 个数被取。

我一开始很疑惑，难道 \(i-k\) 之前的部分不会填到这里面来吗？答案是会，但是因为这里往里面填了，如果我 \([i-k,i]\) 中的数不填回去而是也填在 \([i-k,i+k]\) 中，必然会导致最终前面的数没有被填完，而后面数过多的情况。

那这个结论有什么用呢？注意我们直接枚举所有状态的复杂度是 \(O(n2^{2k+1}k)\) 的，而且还容易多算不合法的情况，所以我们选状态只需要取了 \(k+1\) 个数的情况，这样相当于状态数变成了 \(\binom{2k+1}{k+1}\) 个状态，这优化了我们接下来要说的矩阵加速和线性递推。

先思考如何用状压 dp 转移，我们用 \(f[i][S]\) 表示遍历到 \(i\),状态为 \(S\) 的方案数，然后枚举转移前的状态，因为两个状态中表示的数是不相同的（即 \([i-k,i+k]\) 是相对的），所以之前的状态要通过平移（二进制下右移）才能转移到当前状态，然后枚举在这一次放在哪一个数即可，复杂度 \(O(n\binom{2k+1}{k+1}k)\)。

因为转移只与状态有关与 \(i\) 无关，所以考虑矩阵加速，构造矩阵，然后正常的转移即可，复杂度 \(O(\binom{2k+1}{k+1}^3\log n)\)。

观察到数据范围：\(0\le k\le 9,1\le n\le 10^{10-k}\)。

这个 \(n\) 与 \(k\) 有关，\(k\) 很大时 \(n\) 很小。而 \(k\) 大的时候我们矩阵快速幂的复杂度就巨大，\(k\) 小的时候 \(n\) 很大导致线性递推的复杂度巨大，所以根据这个性质分类讨论即可。发现在 \(k\le 4\) 的时候矩阵加速基本可以实现，而此时线性递推虽然有些卡常但是还是可以通过。

细节：

  • 线性递推要滚动数组（与 \(i\) 无关，所以直接滚成二维即可）。
  • 各种数组都要开大（\(RE\) 了好多发）。
  • 要注意自己矩阵的开始位置（乘法从 \(1\) 开始，答案却输出 \(0\) 的位置，卡了挺久）。
  • 要预处理 \(i\le k+1\) 的情况，因为此时还没有放下 \(k+1\) 个数，不能用优化后的转移。
  • 答案是 \([n-k,n]\) 全填了的状态，因为后面都填不了。
  • 滚动数组清空。
  • 矩阵乘法横着放和竖着放要注意乘法顺序（矩阵乘法不满足交换律）。
  • 要预处理该状态可以到哪些状态，因为复杂度确实有些卡，不开就一直 \(T\) 最后一个点。

\(AC\ Code\)

typedef long long ll;
const int mod=1e9+7;
ll n,K,f[2][1<<19];
int m,s[1<<19],pm[1<<19];
struct Matrix{
    ll a[127][127];
    Matrix(){memset(a,0,sizeof(a));}
    void init(){
        for(int p=1;p<=m;p++){
            for(int i=0;i<=2*K;i++){
                if(!((s[p]>>1)&(1<<i)))
                    a[pm[(s[p]>>1)^(1<<i)]][p]=1;
            }
        }
    }
    inline Matrix operator *(const Matrix &w)const{
        Matrix ans;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=m;j++)
                for(int k=1;k<=m;k++)
                    ans.a[i][j]=(ans.a[i][j]+a[i][k]*w.a[k][j]%mod)%mod;
        return ans;
    }
}ans,a;
vector<int>F[1<<19];
int main(){
    scanf("%lld%lld",&n,&K);
    for(int S=0;S<(1<<(2*K+1));S++){
        if(__builtin_popcount(S)==K+1){
            s[++m]=S;
            pm[S]=m;
        }
    }
    f[0][0]=1;
    int o=1;
    for(int w=1;w<=K+1;w++,o^=1){
        for(int S=0;S<(1<<(2*K+1));S++)f[o][S]=0;
        for(int S=0;S<(1<<(2*K+1));S++){
            for(int i=0;i<=2*K;i++){
                if(!((S>>1)&(1<<i)))(f[o][(S>>1)^(1<<i)]+=f[o^1][S])%=mod;
            }
        }
    }
    if(K<=4){
        o^=1;
        for(int i=1;i<=m;i++){
            ans.a[i][1]=f[o][s[i]];
        }
        a.init();
        n-=K+1;
        for(;n;n>>=1,a=a*a)if(n&1)ans=a*ans;
        printf("%lld",ans.a[1][1]);
    }else{
        for(int p=1;p<=m;p++){
            for(int i=0;i<=2*K;i++){
                if(!((s[p]>>1)&(1<<i)))
                    F[(s[p]>>1)|(1<<i)].push_back(s[p]);
            }
        }
        for(int w=K+2;w<=n;w++,o^=1){
            for(int p=1;p<=m;p++)f[o][s[p]]=0;
            for(int p=1;p<=m;p++){
                for(int S:F[s[p]]){
                    (f[o][s[p]]+=f[o^1][S])%=mod;
                }
            }
        }
        printf("%lld",f[o^1][(1<<K+1)-1]);
    }
}