可爱小萌妹

编辑于 2022-05-18 12:35

+ 关注

牛客练习赛 98 题解精

牛客练习赛 98 题解

A.魔圆寄录 by lgswdn

如果 $a>3b$ ，那么我们每轮选择五次 Normal 攻击。

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

得到的答案为 $\lceil\frac{h}{5\max(a,3b)}\rceil$ 。

#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 云浅

显然，选出数中至多有一个数小于 $\dfrac{m}{2}$ 。否则若 $x_i,x_j$ 均小于 $\dfrac{m}{2}$ ，则 $x_i+x_j<m$ ，与题意矛盾。

那么如果 $a_i\ge \dfrac{m}{2}$ 我们肯定就把它选上，接下来再看看剩下的数中最大的那个数是否符合要求即可。

#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;
}

时间复杂度 $O(n)$ 。

C.AIR Triplet by lgswdn

先考虑单独处理一个查询。首先异或的条件可以转化成 $a_i=a_j=a_k$ 。考虑如何求解：求得一个计数器 $c_i$ 表示 $i$ 在当前序列中出现的个数。考虑枚举 $a_i$ 是多少，则答案应为 $\sum C_{n}^{3}$ 。

考虑修改一个数对于全局的影响。这个数的位置是无所谓的，我们只关心值。把 $x$ 修改成 $y$ 相当于删掉一个 $x$ 再添加一个 $y$ 。删掉一个 $x$ 相当于将 $c_x$ 减一，即答案 $-C_{c_x}^3+C_{c_x-1}^3$ 。添加一个 $y$ 同理。

所以一次操作（把一个 $x$ 换成一个 $y$ ）的步骤应为：

$ans:=ans-C_{c_x}^3+C_{c_x-1}^3$
$c_x:=c_x-1$
$ans:=ans-C_{c_y}^{3}+C_{c_y+1}^{3}$
$c_y:=c_y+1$

#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

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

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

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

转移即枚举如何切 $[l,r]$ 子串（的第一步）。它可以不切，或者切（然后枚举它的回文中心）。

设 $f(l,r)$ 为 $[l,r]$ 区间的划分方案数。设 $p(l,r)$ 表示区间 $1$ 的个数，则有

$f(l,r)=1+\sum_{l\le x< y\le r} [p(l,x)=p(y,r)]f(x+1,y-1)\\$

可以发现对于一个确定的 $x$ ，满足 $p(l,x)=p(y,r)$ 的 $y$ 的取值是一段区间。并且随着 $x$ 的增大，区间的左右端点的移动都是单调的。

因此可以维护两个指针表示 $y$ 的取值区间，同时记录 $f(i,\cdot)$ 的前缀和即可做到 $O(n^3)$ 。

#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 云浅

$k=0$ 当然很好做。考虑 $k=1$ 时怎么做。

考虑对每一组逆序对算贡献。对于一组逆序对 $(i,j)$ ，不难发现其被计算的次数就是 $i\cdot (n-j+1)$ 。

或者，形式化地： $\begin{aligned}\sum_{l=1}^n\sum_{r=l}^nF_1(l,r)&=\sum_{l=1}^n\sum_{r=l}^n\sum_{i=l}^{r-1}\sum_{j=i+1}^r[a_i>a_j]\\&=\sum_{i=1}^{n-1}\sum_{j=i+1}^n[a_i>a_j]\sum_{l=1}^i\sum_{r=j}^n1=\sum_{i=1}^{n-1}\sum_{j=i+1}^n[a_i>a_j]\cdot i(n-j+1)\end{aligned}\\$

维护一个树状数组。从前往后处理，处理到 $a_i$ 时求一下 $[a_i+1,10^9]$ 的区间和，乘上 $(n-i+1)$ 并累加；然后在树状数组 $a_i$ 的位置处 $+i$ 。注意 $a_i$ 最大可以到 $10^9$ ，需要离散化。

时间复杂度 $O(n\log n)$ 。

现在我们来考虑 $k$ 较大的情形：仍然考虑一组逆序对 $(i,j)$ 的贡献。

此时相当于要从 $[1,i]$ 与 $[j,n]$ 中分别选出来 $k$ 个点，但是不记顺序。

形式化地，我们选出的左端点需要满足 $1\le L_1\le L_2\le \cdots\le L_k\le i$ ，求满足这个条件的序列 $L$ 的个数。这是经典排列组合问题，可以发现答案就是

$\binom{i+k-1}{k}\\$

略证：上式等价于 $1\le L_1<L_2+1<L_3+2<\cdots<L_k+k-1\le i+k-1$ 。

因此就相当于从 $1,2,\cdots,i+k-1$ 中不重复地选出 $k$ 个数，那么答案就是你所熟悉的组合数， $C_{i+k-1}^k$ 。

因此只需要 $O(n+k)$ 预处理组合数，然后 $O(n\log n)$ 计算答案即可。复杂度 $O(k+Tn\log n)$ 。

#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：设 $F(i,j)$ 表示前 $i$ 只企鹅选 $j$ 个，且必须选第 $i$ 只的最小代价，那么

$F(i,j)=\min_{i-m\le x<i}F(x,j-1)+a_i\\$

直接转移复杂度是 $O(n\cdot m\cdot k)$ 的。这显然不行。

我们考虑优化：注意到随着 $i$ 的增加， $i-m$ 和 $i$ 都在单调递增。

因此可以使用单调队列优化：用单调队列来记录区间 $[i-m,i)$ 内的最小值，单次转移就是 $O(1)$ 了。

这样就做到了 $O(nk)$ 的时间复杂度，但仍然无法面对 $n,k\le 2\times 10^5$ 的数据范围。

看上去状态数已经是 $O(nk)$ ，似乎已经达到了极限。

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

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

这样做的时间复杂度为 $O(n\log V)$ ，其中 $V$ 为值域。

#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

首先抛开 $\gcd$ 条件不看，我们可以得到一个 $dp$ 。 $f_{u,i}$ 表示考虑 $u$ 子树且 $d_u=i$ 的方案数。 $f_{u,i}=\prod_v\sum_{j<i} f_{v,j}$ 。考虑 $f$ 的前缀和 $g$ ，则有 $f_{u,i}=\prod_v g_{v,i}$ 。考虑优化。

看到只有连乘，可以猜想一下 $f_{u,i}$ 是一个关于 $i$ 的多项式 $F_u$ 。可以归纳证明。叶节点一定是。如果子节点是，那么子节点的前缀和（多项式相加）也必然是，所以多项式相乘也必然是。

所以，我们发现 $F_u[i]=f_{u,i}$ 必然是一个次数不大于 $sz_u-1$ 的多项式。因为转移为乘积，多项式的乘积仍然为多项式，并且次数为多项式的次数之和。也就是意味着我们可以得到 $F_1[1],...,F_1[n]$ 然后拉格朗日插值插出 $F_1[m]$ 。这部分可以 $O(n^2)$ 解决。

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

$ans=\sum_d \mu(d) F_1\left[\left\lfloor \frac{m}{d} \right\rfloor\right]\\$

$\lfloor \frac{m}{d} \rfloor$ 的取值很少，暴力做即可。

运用拉格朗日插值插出多项式系数后，多项式求值只需要 $O(n)$ 复杂度。所以总复杂度为 $O(m+n^2+n\sqrt m)$ 。

#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

D 的 $O(n)$ 做法

抱歉咕了这么久=_=

考虑先找出来原字符串中奇数的位置，设为 $q_1,q_2,\cdots,q_m$ 。

如果我们选出的 $k$ 个点分别是 $c_1,c_2,\cdots,c_k$ ，由于对每个 $i$ ，满足 $q_j\in [c_i,c_{i+1})$ 的 $q_j$ 的数量是回文的，因此，对每个 $i=1,2,\cdots,m$ ，满足 $c_j\in [q_i,q_{i+1})$ 的 $c_j$ 的数量同样应该是回文的。