2020-09-21 11:19 已编辑北京邮电大学

关注

牛客挑战赛43 部分题解

A

容易发现每一个数分一段是最优的，因为两个数或起来可能变小而绝不可能变大。

代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int n;

int main()
{
    scanf("%d",&n);
    long long ans=0;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        ans+=x;
    }
    printf("%lld",ans);
}

B

我的做法：

容易发现删除的时候肯定从小往大删，设删除的最后一个数为 $i$ ，那么前 $i-1$ 个数最多保留 $m$ 个，所以答案为：

$\sum_{i=1}^n \sum_{j=1}^{\min(i-1,m)}C_{i-1}^j$

拆一下就是个卷积的形式了：

$\sum_{i=1}^n (i-1)! \sum_{j=1}^{\min(i-1,m)} \frac 1 {j!} \frac 1 {(i-1-j)!}$

当时没多想，直接拷一手 $\text{ntt}$ 板子就过了。

代码如下：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 3000010
#define mod 998244353
#define bin(x) (1<<(x))

int n,m;
int add(int x){return x>=mod?x-mod:x;}
int dec(int x){return x<0?x+mod:x;}
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
void dec(int &x,int y){x=(x-y<0?x-y+mod:x-y);}
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
int inv[maxn];
struct NTT{
    int w[maxn];void prep(int lg){int N=bin(lg);
        inv[1]=1;for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
        for(int i=1,wn;i<N;i<<=1){
            w[i]=1;wn=ksm(3,(mod-1)/(i<<1));
            for(int j=1;j<i;j++)w[i+j]=1ll*w[i+j-1]*wn%mod;
        }
    }
    int limit,r[maxn];
    void work(int lg){for(int i=1;i<bin(lg);i++)r[i]=(r[i>>1]>>1)|((i&1)<<(lg-1));}
    void dft(int *f,int lg,int type=0){
        limit=bin(lg);if(type)reverse(f+1,f+limit);
        for(int i=1;i<limit;i++)if(i<r[i])swap(f[i],f[r[i]]);
        for(int mid=1,t;mid<limit;mid<<=1)for(int j=0;j<limit;j+=(mid<<1))for(int i=0;i<mid;i++)
        {t=1ll*f[j+i+mid]*w[i+mid]%mod;f[j+i+mid]=dec(f[j+i]-t);f[j+i]=add(f[j+i]+t);}
    }
}ntt;
int A[maxn],B[maxn];
struct POLY{
    vector<int> a;int len;void rs(int ln){a.resize(len=ln);}POLY(){rs(0);}
    int &operator [](int x){return a[x];}
    void dft(int *A_,int lg,int ln){for(int i=0;i<bin(lg);i++)A_[i]=i<min(len,ln)?a[i]:0;ntt.dft(A_,lg);}
    void idft(int *A_,int lg,int ln){ntt.dft(A_,lg,1);rs(ln);for(int i=0;i<ln;i++)a[i]=1ll*A_[i]*inv[bin(lg)]%mod;}
    POLY Mul(POLY b,int ln){
        int lg=ceil(log2(ln*2-1));ntt.work(lg);dft(A,lg,ln);b.dft(B,lg,ln);
        for(int i=0;i<bin(lg);i++)B[i]=1ll*A[i]*B[i]%mod;b.idft(B,lg,ln);return b;
    }
}F,G;
int fac[maxn],inv_fac[maxn];
void work(){
    fac[0]=inv_fac[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=1ll*fac[i-1]*i%mod;
        inv_fac[i]=1ll*inv_fac[i-1]*inv[i]%mod;
    }
}

int main()
{
    scanf("%d %d",&n,&m);
    ntt.prep(ceil(log2(n<<2)));work();
    F.rs(m+1);for(int i=0;i<=m;i++)F[i]=inv_fac[i];
    G.rs(n+1);for(int i=1;i<=n;i++)G[i]=inv_fac[i-1];
    F=F.Mul(G,n+1);
    int ans=1;
    for(int i=1;i<=n;i++)add(ans,1ll*F[i]*fac[i-1]%mod);
    printf("%d",ans);
}

官方题解做法：

考虑最后剩下的元素数量，假设为 $k$ ，那么删掉的 $n-k$ 个有 $\min(m+1,k+1)$ 个位置可以插，也是用组合数求一下就可以了。

C

我的做法：

当时大力猜结论，假设 $a=b$ 最优。

然后打了个表，发现 $a$ 的选取是有单调性的，于是直接三分出最优解，然后居然就过了，证明并不是很会……

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100010
#define ll long long

int n,a[maxn],b[maxn];
ll ans=0;
ll check(int x){
    for(int i=1;i<=n;i++)b[i]=abs(a[i]-x);
    sort(b+1,b+n+1);
    ll re=0;
    for(int i=1;i<=n;i++)re+=2ll*i*b[i]-b[i];
    return re;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]*=2;
    int l=0,r=1e9;
    while(r-l>2){
        int mid1=l+(r-l+1)/3,mid2=mid1+(r-l+1)/3;
        if(check(mid1)>check(mid2))l=mid1+1;
        else r=mid2-1;
    }
    int ans=l;
    if(check(ans)>check(l+1))ans=l+1;
    if(check(ans)>check(r))ans=r;
    printf("%lld",check(ans)%(int)(1e9+7));
}

官方题解做法：

题目相当于要求找到一个点 $(a,b)$ 使其到所有其他点 $(A_i,A_j)$ 的切比雪夫距离之和最小，而两个点 $(x,y),(a,b)$ 的切比雪夫距离等于 $(x+y,x-y),(a+b,a-b)$ 两点的曼哈顿距离除以 $2$ ，这个转化很秀，手玩一下就能证明出来。

令所有点转化为 $(A_i+A_j,A_i-A_j)$ ，然后就是要找一个点 $a,b$ 使其到所有其他点的曼哈顿距离之和最小，显然两维坐标可以分开考虑，以 $x$ 坐标为例， $a$ 一定是所有 $A_i+A_j$ 的中位数，用二分 $a$ 的大小用尺取法判断是否合法即可。

D

对于一个位置 $d$ ，考虑构造他的 $EGF$ ，设 $x^i$ 的系数为 $k$ 次操作中 $d$ 被操作了 $i$ 次，最后 $d$ 位上是 $0$ 的方案数，注意到只有最后一次操作决定这一位是什么，即前 $i-1$ 次操作可以随意操作，令 $v1$ 表示有 $v1$ 个操作使 $d$ 变 $0$ ，有 $v2$ 个操作与 $d$ 相关，那么 $EGF$ 为：
$ $v1\sum_{i=1}^{\infty}\frac {v2^{i-1}x^i} {i!}=v1\frac {e^{v2x}-1} {v2}$ $

如果 $A_d=0$ ，那么还要 $+1$ ，即加上 $x_0$ 表示可以不操作。

然后考虑分治 $ntt$ 将这些 $EGF$ 乘起来，将多项式维护成 $\sum_i a_ie^{ix}$ 的形式，发现计算方式其实和普通多项式相同。

最后的答案就是 $x^k$ 的系数，对于第 $i$ 项 $a_ie^{ix}$ ，他对 $x^k$ 的贡献为 $a_i\dfrac {i^kx^k} {k!}\times k!=a_ii^k$ ，于是求和一下就做完了。

代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 300010
#define mod 998244353
#define bin(x) (1<<(x))

int add(int x){return x>=mod?x-mod:x;}
int dec(int x){return x<0?x+mod:x;}
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
void dec(int &x,int y){x=(x-y<0?x-y+mod:x-y);}
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
int inv[maxn];
struct NTT{
    int w[maxn];void prep(int lg){int N=bin(lg);
        inv[1]=1;for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
        for(int i=1,wn;i<N;i<<=1){
            w[i]=1;wn=ksm(3,(mod-1)/(i<<1));
            for(int j=1;j<i;j++)w[i+j]=1ll*w[i+j-1]*wn%mod;
        }
    }
    int limit,r[maxn];
    void work(int lg){for(int i=1;i<bin(lg);i++)r[i]=(r[i>>1]>>1)|((i&1)<<(lg-1));}
    void dft(int *f,int lg,int type=0){
        limit=bin(lg);if(type)reverse(f+1,f+limit);
        for(int i=1;i<limit;i++)if(i<r[i])swap(f[i],f[r[i]]);
        for(int mid=1,t;mid<limit;mid<<=1)for(int j=0;j<limit;j+=(mid<<1))for(int i=0;i<mid;i++)
        {t=1ll*f[j+i+mid]*w[i+mid]%mod;f[j+i+mid]=dec(f[j+i]-t);f[j+i]=add(f[j+i]+t);}
    }
}ntt;
int A[maxn],B[maxn];
struct POLY{
    vector<int> a;int len;void rs(int ln){a.resize(len=ln);}POLY(){rs(0);}
    int &operator [](int x){return a[x];}
    void dft(int *A_,int lg,int ln){for(int i=0;i<bin(lg);i++)A_[i]=i<min(len,ln)?a[i]:0;ntt.dft(A_,lg);}
    void idft(int *A_,int lg,int ln){ntt.dft(A_,lg,1);rs(ln);for(int i=0;i<ln;i++)a[i]=1ll*A_[i]*inv[bin(lg)]%mod;}
    POLY Mul(POLY b,int ln){
        int lg=ceil(log2(ln*2-1));ntt.work(lg);dft(A,lg,ln);b.dft(B,lg,ln);
        for(int i=0;i<bin(lg);i++)B[i]=1ll*A[i]*B[i]%mod;b.idft(B,lg,ln);return b;
    }
}F;
int n,m,k,a[maxn];
int v1[maxn],v2[maxn];
POLY solve(int l,int r){
    if(l==r){
        POLY re;re.rs(v2[l]+1);
        if(!v2[l])return re[0]=1,re;
        re[0]=1ll*((a[l]?mod:v2[l])-v1[l])*inv[v2[l]]%mod;
        re[v2[l]]=1ll*v1[l]*inv[v2[l]]%mod;
        return re;
    }
    int mid=l+r>>1;
    POLY p1=solve(l,mid),p2=solve(mid+1,r);
    return p1.Mul(p2,p1.len+p2.len-1);
}

int main()
{
    scanf("%d %d %d",&n,&m,&k);ntt.prep(ceil(log2((m+1)<<1)));
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1,x,y;i<=m;i++)scanf("%d %d",&x,&y),v1[x]+=(y==0),v2[x]++;
    for(int i=1;i<=n;i++)if(a[i]&&!v1[i])return printf("0"),0;
    F=solve(1,n);int ans=0;
    for(int i=1;i<=m;i++)ans=(ans+1ll*F[i]*ksm(i,k)%mod)%mod;
    printf("%d",ans);
}