首页 > 其他分享 >暑假集训 Day17 模拟赛题解

暑假集训 Day17 模拟赛题解

时间：2023-09-08 10:47:07浏览次数：58  
标签：10 le int 题解 ll 100005 Day17 ans 集训

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]);
    }
}

标签：10,le,int,题解,ll,100005,Day17,ans,集训
From： https://www.cnblogs.com/NBest/p/17686905.html

相关文章

  • UVA10368 题解
    2023-08-0615:18:08solution双倍经验这种有限轮游戏的博弈通常都是有两种状态，必胜态和必败态。对于必胜态，指的是从它可以转移到必败态。对于必败态，指的是从它不论如何只能转移到必胜态。对于每个玩家都采取最优策略的有限游戏，我们通常只需要关注必胜态与必败态之间的转移即......
  • 【题解】AtCoder Regular Contest 162
    A.EkidenRace题目描述：有\(n\)个人参加了往返赛跑，每个人有一个编号\(1\)到\(n\)。已知以下信息：如果按照往路的成绩排序，那么任何两个人的成绩都不相同。同时第\(i\)个人在往路中排名第\(i\)。如果按照往返的成绩排序，那么任何两个人的成绩都不相同。同时第\(i\)个人......
  • P9189 [USACO23OPEN] Custodial Cleanup G 题解
    Description奶牛旅馆可以被看作一个\(N\)个节点\(M\)条边的无向简单图，其中每个房间有一个颜色\(C_i\)，以及一个钥匙，颜色为\(S_i\)，FJ最初在\(1\)号节点，手上一把钥匙都没有。FJ可以进行无数次以下操作：捡起当前房间的钥匙。（FJ可以同时手持多个钥匙）将部分或全部手......
  • All Pairs Maximum Flow题解
    前置知识：1.P3376【模板】网络最大流2.P4897【模板】最小割树（Gomory-HuTree）Ebola有一句很著名的话如果你乱搞过了我请你抽烟那么这道题肯定不能普通的dinic直接水过去，不然就不是紫题了，那么直接祭出最小割树，复杂度\(O(Tn^3m)\)，但是因为dinic跑不满，所以是可以过的。......
  • [题解] AtCoder Beginner Contest 308 A~G
    AtCoderBeginnerContest308A~GA.NewSchemevoidMain(){vector<i64>a(8);for(auto&x:a)cin>>x;if(!is_sorted(a.begin(),a.end())&&!all_of(a.begin(),a.end(),[](auto&x){returnx%25!=0||!(100......
  • CF1374E2 Reading Books(hard version) 题解
    CF1374E2ReadingBooks(hardversion)这道题是在CF1374E1ReadingBooks(easyversion)的基础上出的，而且仅仅增加了一个\(m\)的限制，下面的做法也是基于简单版的思路而想到的。建议先尝试简单版，然后尝试此题。题意简述：有\(n\)本书，每本书有一个阅读时间\(t_i\)，和属性\(......
  • Eclipse里做JBPM工作流gpd.xml中文乱码问题解决
         刚开始接到是做一个简单的文档借阅流程，对于流程定义是采用eclipse中的jbpm插件，但存在一个问题是节点中文命名的在gpd.xml中全部为乱码或根本看不到任何东西。     但是网上有人说没关系，这只是eclipse本身存在的一个bug，在项目所在硬盘目录下打开该文件还是显示正常......
  • 题解 [NOIP2018 提高组] 赛道修建
    题目链接挺综合的一道题目。询问最小值最大，考虑二分最小值，二分上下界是\([最小边权,树的直径]\)，但是为了方便我们直接设为\([1,5\times10^8]\)即可。考虑如何\(check\)，可以采用类似树形\(dp\)的方式进行贪心。对于节点\(u\)的子树，\(u\)内部的点显然可以构成几条链，同......
  • 【PCL】使用kdtree时pop_t报错问题解决
    问题描述在使用kdtree时，遇到的报错，具体报错信息如下：提示找不到pop_t，点击错误信息会进入到dist.h文件中问题解决解决办法很简单，在这里简单总结一下进入dist.h文件中，将下面这行代码，应该是在源文件的503行：typedefunsignedlonglongpop_t;具体位置如下图所示：将这行代码......
  • FTP权限问题解析,553 Can't open that file: Permission denied
    FTP权限问题解析,553Can'topenthatfile:Permissiondenied FTP上传文件,提示553Can'topenthatfile:Permissiondenied原因:目录的所属组,所属用户属于root,导致FTP无法上传,修改组和所属用户为www即可chown-fRwww./*chgrp-fRwww./* ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99