牛客挑战赛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
我的做法：
容易发现删除的时候肯定从小往大删，设删除的最后一个数为 ，那么前
个数最多保留
个，所以答案为：
拆一下就是个卷积的形式了：
当时没多想，直接拷一手 板子就过了。
代码如下：
#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);
} 官方题解做法：
考虑最后剩下的元素数量，假设为 ，那么删掉的
个有
个位置可以插，也是用组合数求一下就可以了。
C
我的做法：
当时大力猜结论，假设 最优。
然后打了个表，发现 的选取是有单调性的，于是直接三分出最优解，然后居然就过了，证明并不是很会……
代码如下：
#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));
} 官方题解做法：
题目相当于要求找到一个点 使其到所有其他点
的切比雪夫距离之和最小，而两个点
的切比雪夫距离等于
两点的曼哈顿距离除以
，这个转化很秀，手玩一下就能证明出来。
令所有点转化为 ，然后就是要找一个点
使其到所有其他点的曼哈顿距离之和最小，显然两维坐标可以分开考虑，以
坐标为例，
一定是所有
的中位数，用二分
的大小用尺取法判断是否合法即可。
D
对于一个位置 ，考虑构造他的
，设
的系数为
次操作中
被操作了
次，最后
位上是
的方案数，注意到只有最后一次操作决定这一位是什么，即前
次操作可以随意操作，令
表示有
个操作使
变
，有
个操作与
相关，那么
为：
$$
如果 ，那么还要
，即加上
表示可以不操作。
然后考虑分治 将这些
乘起来，将多项式维护成
的形式，发现计算方式其实和普通多项式相同。
最后的答案就是 的系数，对于第
项
，他对
的贡献为
，于是求和一下就做完了。
代码如下：
#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);
} 
蔚来公司氛围 186人发布
