竞赛讨论区 > 牛客练习赛 98 题解

牛客练习赛 98 题解

头像
可爱小萌妹
编辑于 2022-05-18 12:35:49 APP内打开
赞 12 | 收藏 0 | 回复14 | 浏览2115

牛客练习赛 98 题解

A.魔圆寄录 by lgswdn

如果 ,那么我们每轮选择五次 Normal 攻击。

否则我们每轮选择五次 Blast 攻击。

得到的答案为

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

signed main(void){

    int h=read(),a=read(),b=read();
    cout<<(h-1)/(5*max(a,3*b))+1<<endl;

    return 0;

}

B.Mentai Cosmic by 云浅

显然,选出数中至多有一个数小于 。否则若 均小于 ,则 ,与题意矛盾。

那么如果 我们肯定就把它选上,接下来再看看剩下的数中最大的那个数是否符合要求即可。

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int MN=1e6+5;
const int INF=1e9;
int n,m,a[MN];

void solve(){
    n=read(),m=read();int x=0,mn=INF,mx=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(a[i]*2>=m)x++,mn=min(mn,a[i]);
        else mx=max(mx,a[i]);
    }
    cout<<max(1ll,x+(mx+mn>=m))<<endl;
}

signed main(void){

    int tt=read();
    while(tt--)solve();

    return 0;
}

时间复杂度

C.AIR Triplet by lgswdn

先考虑单独处理一个查询。首先异或的条件可以转化成 。考虑如何求解:求得一个计数器 表示 在当前序列中出现的个数。考虑枚举 是多少,则答案应为

考虑修改一个数对于全局的影响。这个数的位置是无所谓的,我们只关心值。把 修改成 相当于删掉一个 再添加一个 。删掉一个 相当于将 减一,即答案 。添加一个 同理。

所以一次操作(把一个 换成一个 )的步骤应为:

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int MN=1e6+5;
int n,a[MN],cnt[MN],q;

int calc(int x){
    return x*(x-1)/2*(x-2)/3;
}

signed main(void){

    n=read(),q=read();int N=1e6,ans=0;
    for(int i=1;i<=n;i++)cnt[a[i]=read()]++;
    for(int i=1;i<=N;i++)ans+=calc(cnt[i]);
    while(q--){
        int x=read(),y=read();
        ans-=calc(cnt[a[x]]--),ans+=calc(cnt[a[x]]),a[x]=y;
        ans-=calc(cnt[a[x]]++),ans+=calc(cnt[a[x]]);
        cout<<ans<<endl;
    }

    return 0;
}

D.Sonstring by lgsdwn

首先我们把所有数位都变成其模 的余数(奇数是 偶数是 ),然后我们发现这个对 求和相当于不限制划分的子串数量。于是我们转化成了如下问题:

给定一个 字符串,问有多少种划分,使得每一个划分出来的子串的 的个数,组成的序列,是回文的。

这个数据范围比较小,而且这个 的个数组成的序列是回文的条件比较难处理,所以可以考虑硬上区间 DP。由于切的顺序无关,我们可以钦定一种方便我们 DP 的切的顺序:对于一个区间,必须先切外再切里(不断缩小区间)。

转移即枚举如何切 子串(的第一步)。它可以不切,或者切(然后枚举它的回文中心)。

区间的划分方案数。设 表示区间 的个数,则有

可以发现对于一个确定的 ,满足 的取值是一段区间。并且随着 的增大,区间的左右端点的移动都是单调的。

因此可以维护两个指针表示 的取值区间,同时记录 的前缀和即可做到

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int MN=505,mod=998244353;
int n,f[MN][MN],g[MN][MN];
char s[MN];
int sum[MN];

signed main(void){

    cin>>(s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++)f[i][i-1]=1,g[i][i-1]=1;
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(((int)(s[i]-'0'))&1);

    for(int len=1;len<=n;len++){
        for(int i=1,j=len;j<=n;i++,j++){
            f[i][j]=1;int p=j,q=j;
            for(int l=i;l<=j-1;l++){
                while(p>=l&&sum[j]-sum[p-1]<=sum[l]-sum[i-1])p--;
                while(sum[j]-sum[q-1]<sum[l]-sum[i-1])q--;
                if(q<=l)break;
                f[i][j]+=(g[l+1][q-1]-g[l+1][p-1]+mod)%mod,f[i][j]%=mod;
            }
            g[i][j]=g[i][j-1]+f[i][j],g[i][j]%=mod;
        }
    }

    cout<<f[1][n]%mod<<endl;

    return 0;
}

E.Robotic Girl by 云浅

当然很好做。考虑 时怎么做。

考虑对每一组逆序对算贡献。对于一组逆序对 ,不难发现其被计算的次数就是

或者,形式化地:

维护一个树状数组。从前往后处理,处理到 时求一下 的区间和,乘上 并累加;然后在树状数组 的位置处 。注意 最大可以到 ,需要离散化。

时间复杂度

现在我们来考虑 较大的情形:仍然考虑一组逆序对 的贡献。

此时相当于要从 中分别选出来 个点,但是不记顺序。

形式化地,我们选出的左端点需要满足 ,求满足这个条件的序列 的个数。这是经典排列组合问题,可以发现答案就是

略证:上式等价于

因此就相当于从 中不重复地选出 个数,那么答案就是你所熟悉的组合数,

因此只需要 预处理组合数,然后 计算答案即可。复杂度

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int MN=1e6+5;
const int mod=998244353;
int n,k;
int a[MN],b[MN],fac[MN],ifac[MN];

int ksm(int y,int z,int p=mod){
    y%=p;int ans=1;
    for(int i=z;i;i>>=1,y=y*y%p)if(i&1)ans=ans*y%p;
    return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
int C(int n,int m){
    if(n<m)return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

struct BIT{
    int c[MN<<1];
    void clear(){memset(c,0,sizeof(c));}
    int lowbit(int x){return x&(-x);}
    void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i))c[i]+=k,c[i]%=mod;}
    int sum(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i],res%=mod;return res;}
}tree;

void solve(){
    n=read(),k=read();int ans=0;tree.clear();
    for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i];
    sort(b+1,b+n+1);int len=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    for(int i=1;i<=n;i++)ans+=(tree.sum(n)-tree.sum(a[i])+mod)%mod*C(n-i+k,k)%mod,ans%=mod,tree.add(a[i],C(i+k-1,k));
    cout<<ans%mod<<endl;
}

const int N=1e6;

signed main(void){

    fac[0]=1;for(int i=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;
    ifac[N]=inv(fac[N])%mod;for(int i=N-1;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod;

    int tt=read();
    while(tt--)solve();

    return 0;
}

F.Ginga Tetsudou no Penguin by 云浅

考虑一个朴素的 dp:设 表示前 只企鹅选 个,且必须选第 只的最小代价,那么

直接转移复杂度是 的。这显然不行。

我们考虑优化:注意到随着 的增加, 都在单调递增。

因此可以使用单调队列优化:用单调队列来记录区间 内的最小值,单次转移就是 了。

这样就做到了 的时间复杂度,但仍然无法面对 的数据范围。

看上去状态数已经是 ,似乎已经达到了极限。

实际上并不然。设 表示选 个时的最小代价,可以证明 是一个凸函数,也就是其相邻两点连线斜率单调。

因此可以二分这个斜率 ,计算 的最小值点(由于没有了 的限制,这就相当于将每个物品的价值减去 ,从而可以在 的时间内计算完毕),根据此时算出的点 来确定斜率的大小。

这样做的时间复杂度为 ,其中 为值域。

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int MN=2e5+5;
int f[MN],g[MN],n,m,k,a[MN];
deque<int>dmin;

const int INF=2e14;

#define fi first
#define se second
#define mk make_pair

pair<int,int> calc(int x){
    memset(f,63,sizeof(f)),memset(g,0,sizeof(g));
    while(dmin.size())dmin.pop_back();f[0]=0,dmin.push_back(0);
    for(int i=1;i<=n;i++){
        while(dmin.size()&&dmin.front()<i-m)dmin.pop_front();
        f[i]=a[i]-x,g[i]=1;
        if(dmin.size())f[i]+=f[dmin.front()],g[i]+=g[dmin.front()];
        while(dmin.size()&&f[i]<=f[dmin.back()])dmin.pop_back();dmin.push_back(i);
    }
    while(dmin.size()&&dmin.front()<n-m+1)dmin.pop_front();
    return mk(f[dmin.front()],g[dmin.front()]);
}

void solve(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)a[i]=read();
    int L=-INF,R=INF,ans=L;
    while(L<=R){
        int mid=(L+R)>>1;
        auto x=calc(mid);
        if(x.se<k)L=mid+1;
        else ans=mid,R=mid-1;
    }
    cout<<calc(ans).fi+ans*k<<endl;
}

signed main(void){

    int tt=read();while(tt--)solve();

    return 0;
}

G.Romantic Misletoe by lgswdn

首先抛开 条件不看,我们可以得到一个 表示考虑 子树且 的方案数。。考虑 的前缀和 ,则有 。考虑优化。

看到只有连乘,可以猜想一下 是一个关于 的多项式 。可以归纳证明。叶节点一定是。如果子节点是,那么子节点的前缀和(多项式相加)也必然是,所以多项式相乘也必然是。

所以,我们发现 必然是一个次数不大于 的多项式。因为转移为乘积,多项式的乘积仍然为多项式,并且次数为多项式的次数之和。也就是意味着我们可以得到 然后拉格朗日插值插出 。这部分可以 解决。

然后,我们加入 的条件。套路地,我们使用数论容斥(或者也可以理解为莫比乌斯反演,不过不知道这个也没有关系),对于每个 计算出钦定大家都是 的倍数的条件,容斥系数容易推得为莫比乌斯函数,则有

的取值很少,暴力做即可。

运用拉格朗日插值插出多项式系数后,多项式求值只需要 复杂度。所以总复杂度为

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

#define OK puts("OK")

const int mod=1e9+7;
const int MN=2005;
const int MC=3e7+5;
int n,m;
vector<int>G[MN];
int f[MN][MN],g[MN][MN];

void dp(int u,int fa){
    for(int i=1;i<=n+1;i++)f[u][i]=1;
    for(int v:G[u]){
        if(v==fa)continue;
        dp(v,u);
        for(int i=1;i<=n+1;i++)f[u][i]=f[u][i]*g[v][i]%mod;
    }
    for(int i=1;i<=n+1;i++)g[u][i]=(g[u][i-1]+f[u][i])%mod;
}

int a[MN],invx[MN],p[MN],q[MN],r[MN],tmp[MN];

int ksm(int x,int y,int p=mod){
    int res=1;
    for(int i=y;i;i>>=1,x=x*x%p)if(i&1)res=res*x%p;
    return res;
}

int inv(int x,int p=mod){
    return ksm(x,p-2,p);
}

void Lagrange(){
    for(int i=1;i<=n+1;i++)invx[i]=inv(i);
    p[0]=1;
    for(int i=1;i<=n+1;i++){
        q[0]=mod-i,q[1]=1;
        for(int j=0;j<i;j++)
            for(int k=0;k<=1;k++)r[j+k]=(r[j+k]+p[j]*q[k]%mod+mod)%mod;
        for(int j=0;j<=i;j++)p[j]=r[j],r[j]=0;
    }
    for(int i=1;i<=n+1;i++){
        int fm=inv(g[1][i])%mod;
        for(int j=1;j<=n+1;j++)if(j!=i)fm=fm*(i-j+mod)%mod;
        r[0]=(mod-p[0]*invx[i]%mod+mod)%mod,fm=inv(fm);
        for(int j=1;j<=n;j++)r[j]=(mod-(p[j]-r[j-1]+mod)%mod*invx[i]%mod+mod)%mod;
        for(int j=0;j<=n;j++)a[j]=(a[j]+r[j]*fm%mod+mod)%mod;
    }
}

int calc(int k){
    int res=0;
    for(int i=n;i>=0;i--)res=(res*k%mod+a[i])%mod;
    return res;
}

int mu[MC],pri[1857860];
bool isp[MC];

void pre(){
    int N=30000000,cnt=0;mu[1]=1;
    memset(isp,1,sizeof(isp));
    for(int i=2;i<=N;i++){
        if(isp[i])pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt;j++){
            if(i*pri[j]>N)break;
            int x=i*pri[j];isp[x]=0;
            if(i%pri[j]==0){mu[x]=0;break;}
            mu[x]=-mu[i];
        }
    }
    for(int i=1;i<=N;i++)mu[i]+=mu[i-1];
}

signed main(void){

#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
#endif

    n=read(),m=read();
    for(int i=1;i<=n-1;i++){
        int u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
    }
    dp(1,0);pre(),Lagrange();
    int ans=0;
    for(int l=1,r=0;l<=m;l=r+1){
        r=m/(m/l);
        ans=(ans+(mu[r]-mu[l-1]+mod)%mod*calc(m/l)%mod+mod)%mod;
    }
    cout<<ans<<endl;


    return 0;
}

update on 5.17

  1. D 的 做法

抱歉咕了这么久=_=

考虑先找出来原字符串中奇数的位置,设为

如果我们选出的 个点分别是 ,由于对每个 ,满足 的数量是回文的,因此,对每个 ,满足 的数量同样应该是回文的。

可以这么理解:由于每相邻两个划分点之间的奇数个数对称,那么按照奇数的位置划分之后,每一段中的划分点的个数必然是对称的;否则,在不对称的那个位置就会出现「错位」,导致划分出来的奇数个数不对称。

因此,我们可以依次枚举每相邻两个奇数段 ,记 ,那么在这两边选出来的个数需要一样。枚举选出来了多少个,可以发现贡献为

其实直接枚举已经能做到 了。需要特判一下最中间的那一段,若其长度为 ,则其贡献为

注意到上式其实就是 ,因此我们还能做到更快,并且支持一些动态修改。在本题中没有必要。

ps:之前能过的一份 被我卡了

  1. 为什么 F 中的函数是凸的呢

因为和 O(nk) 的暴力 dp 拍了几千组都过了

有一个感性的证明:考虑从 的时候,就相当于多选了一个。

由于前面我们已经选过一些数了,因此选出来的这些数对「每 个就需要选一个」这一要求已经做出了一些贡献。这样一来,选择数的限制更松了,那么自然就有

6条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐