"蔚来杯"2022牛客暑期多校训练营4

本文主要是介绍"蔚来杯"2022牛客暑期多校训练营4，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接

\(A:Task Computing\)

微扰法可以证明，若 \(i\) 排在 \(j\) 前面，则 \(w_i(p_j-1) < w_j(p_i-1)\) 。
先将其按该方法排序，我们只需要选出 \(m\) 个按顺序排即可。
\(m\) 很小，考虑 \(dp\) ，\(f_{i,j}\) 表示从前 \(i\) 个中选出 \(j\) 个的最大值。
但从前向后还有 \(p\) 会对后续答案产生影响，不好处理。
发现后面的对前面没有影响，我们可以从后往前 \(dp\) ，豁然开朗。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define LF double
using namespace std;
const int N=1e5+3;
const LF inf=1e18;
struct hh{
	int w,op;LF p;
	bool operator<(const hh &a) const{
		if(op^a.op) return op>a.op;
		return w*(a.p-1)<a.w*(p-1);
	}
}a[N];
int n,m;
LF f[N][22];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
int main()
{
	int x,y;
	n=in(),m=in();
	for(int i=1;i<=n;++i) a[i].w=in();
	for(int i=1;i<=n;++i){
		x=in();
		if(x<10000) a[i].op=0;
		else if(x==10000) a[i].op=1;
		else a[i].op=2;
		a[i].p=1.0*x/10000;
	}
	sort(a+1,a+n+1);
	f[n+1][0]=0;
	for(int i=1;i<=m;++i) f[n+1][i]=-inf;
	for(int i=n;i;--i)
	  for(int j=0;j<=m;++j){
	  	f[i][j]=f[i+1][j];
	  	if(j) f[i][j]=max(f[i][j],a[i].w+a[i].p*f[i+1][j-1]);
	  }
	printf("%.12lf\n",f[1][m]);
  return 0;
}

\(C:Easy Counting Problem\)

考虑 \(EGF\) ，答案为 \(\prod\limits_{i=0}^{w-1}(e^x-\sum\limits_{j=0}^{c_i-1}\frac{1}{j!})\) 的第 \(n\) 项系数乘上 \(n!\) 。
因为 \(n\) 很大，而 \(\sum\limits_{i=0}^{w-1}c_i\) 较小，将式子拆开，是一个容斥的形式，我们可以用背包预处理出选出 \(k\) 个项相乘的系数之和，枚举计算即可。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+3,M=1e7+3,p=998244353,G=3,Gi=332748118;
int r[N],fac[M],inv[M],_a[N],_b[N],_c[N],d[N],pw[M];
int w,f[11][N],c[N],len[11],g[11][N];
IL int in(){
	char c;int f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	int x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
IL int mod(int x){return x>=p?x-p:x;}
IL int ksm(int a,int b){
  int c=1;
  while(b){
  	if(b&1) c=1ll*c*a%p;
  	a=1ll*a*a%p,b>>=1;
  }
  return c;
}
IL void calc(int lim){
	for(int i=0;i<lim;++i)
	  r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
IL void init(int n){
	fac[0]=1;for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%p;
	inv[n]=ksm(fac[n],p-2);
	for(int i=n;i;--i) inv[i-1]=1ll*inv[i]*i%p;
}
IL void NTT(int *a,int lim,int op){
	calc(lim);
	for(int i=0;i<lim;++i)
	  if(i<r[i]) swap(a[i],a[r[i]]);
	for(int i=1;i<lim;i<<=1){
		int wn=ksm(~op?G:Gi,(p-1)/(i<<1));
		for(int j=0;j<lim;j+=i<<1){
			int w=1;
			for(int k=0;k<i;++k,w=1ll*w*wn%p){
				int x=a[j+k],y=1ll*w*a[j+i+k]%p;
				a[j+k]=mod(x+y),a[j+i+k]=mod(x-y+p);
			}
		}
	}
	if(op==-1){
		int inv=ksm(lim,p-2);
		for(int i=0;i<lim;++i) a[i]=1ll*a[i]*inv%p;
	}
}
IL void mul(int *a,int *b,int *c,int n,int m){
	int lim=1,_a[N],_b[N];
	while(lim<n+m-1) lim<<=1;
	memcpy(_a,a,4*n),memcpy(_b,b,4*m),
	memset(_a+n,0,4*(lim-n)),memset(_b+m,0,4*(lim-m));
	NTT(_a,lim,1),NTT(_b,lim,1);
	for(int i=0;i<lim;++i) c[i]=1ll*_a[i]*_b[i]%p;
	NTT(c,lim,-1);
}
int main()
{
	init(1e7);
	w=in();for(int i=0;i<w;++i) c[i]=in();
	for(int i=0;i<w;++i)
	  for(int j=0;j<c[i];++j)
	  	g[i][j]=inv[j];
	f[0][0]=1,len[0]=1;
	for(int i=0;i<w;++i)
	  for(int j=i+1;j;--j){
	  	mul(f[j-1],g[i],d,len[j-1],c[i]);
	  	len[j]=max(len[j],len[j-1]+c[i]-1);
	  	for(int k=0;k<len[j-1]+c[i]-1;++k) f[j][k]=mod(f[j][k]+d[k]);
	  }
	int q=in();
	while(q--){
		int n=in(),ans=0,op=1;
		for(int i=0;i<w;++i,op*=-1)
		  for(int j=min(n,len[i]-1),mu=ksm(w-i,n-j);~j;--j,mu=1ll*mu*(w-i)%p)
		    ans=(ans+1ll*op*f[i][j]*mu%p*inv[n-j]%p+p)%p;
		if(n<len[w]) ans=(ans+1ll*op*f[w][n]%p+p)%p;
		ans=1ll*ans*fac[n]%p;
		printf("%d\n",ans);
	}
	return 0;
}

\(D:Jobs (Easy Version)\)

三维前缀和即可。

\(E:Jobs (Hard Version)\)

对每个公司的工作，考虑容斥，对三维空间的点处理使得求出前缀和后，满足能到该公司的点为 \(1\)，否则为 \(0\) 。
直接枚举子集容斥复杂度肯定会爆，需要想个更聪明的办法。
考虑二维的情况，可以将工作抽象成一个个矩形，如果一个矩形覆盖另一个矩形，则前者没有意义，我们可以无视它。
这样就会得到一个长度单调递增，高度单调递减的一堆矩阵。显然我们要在矩阵右上角顶点处加 \(1\)，在恰好覆盖相邻两个矩阵的矩阵右上角处减 \(1\) 以去重，可以用 \(set\) 维护。
对于三维情况，我们将点按第三维排序，从下往上将矩阵插入，即可转化成二维情况。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#include<random>
#define IL inline
#define LL long long
using namespace std;
const int N=2e6+3,M=4e2,p=998244353;
struct hh{
	int a,b,c;
	bool operator<(const hh &d) const{
		return a^d.a?a<d.a:b<d.b;
	}
}a[N];
bool cmp1(const hh &a,const hh &b){
	return a.c<b.c;
};
int n,m,q,flag,pre[M+2][M+2][M+2];
multiset<hh>st;
multiset<hh>::iterator it,it1,it2;
IL int in(){
	char c;int f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	int x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
void dele(multiset<hh>::iterator pos,int h){
	--pre[pos->a][pos->b][h];
	if(pos==st.begin()){
		if(pos!=--st.end()){
			it1=pos,++it1;
			++pre[it1->a][pos->b][h];
		}
	}
	else if(pos==--st.end()){
		it1=pos,--it1;
		++pre[pos->a][it1->b][h];
	}
	else{
		it1=it2=pos,--it1,++it2;
		++pre[pos->a][it1->b][h],
		++pre[it2->a][pos->b][h],
		--pre[it2->a][it1->b][h];
	}
	st.erase(pos);
}
void ins(hh x){
	it=st.insert(x);
	++pre[x.a][x.b][x.c];
	if(it==st.begin()){
		if(++it!=st.end()) --pre[it->a][x.b][x.c];
	}
	else if(it==--st.end()){
		if(it!=st.begin()) --it,--pre[x.a][it->b][x.c];
	}
	else{
		it1=it,--it1,it2=it,++it2;
		++pre[it2->a][it1->b][x.c];
		--pre[it2->a][it->b][x.c];
		--pre[it->a][it1->b][x.c];
	}
}
IL int chk(hh x){
	it=st.upper_bound(x);
	if(it!=st.end()){if(it->b>=x.b){dele(it,x.c);return 0;}}
	if(it!=st.begin()){if((--it)->b<=x.b){flag=0;return 1;}}
	return 1;
}
int main()
{
	n=in(),q=in();
	for(int i=1;i<=n;++i){
		int k=in();
		for(int j=1;j<=k;++j)
		  a[j]=(hh){in(),in(),in()};
		st.clear(),sort(a+1,a+k+1,cmp1);
		for(int j=1;j<=k;++j){
			flag=1;while(!chk(a[j]));
			if(flag) ins(a[j]);
		}
	}
	for(int i=1;i<=M;++i)
	  for(int j=0;j<=M;++j)
	    for(int k=0;k<=M;++k)
	      pre[i][j][k]+=pre[i-1][j][k];
	for(int i=0;i<=M;++i)
	  for(int j=1;j<=M;++j)
	    for(int k=0;k<=M;++k)
	      pre[i][j][k]+=pre[i][j-1][k];
	for(int i=0;i<=M;++i)
	  for(int j=0;j<=M;++j)
	    for(int k=1;k<=M;++k)
	      pre[i][j][k]+=pre[i][j][k-1];	
	int ans=0,lastans=0,seed=in();
	std::mt19937 rng(seed);
	std::uniform_int_distribution<> u(1,400);
	while(q--){
	    int IQ=(u(rng)^lastans)%400+1;
	    int EQ=(u(rng)^lastans)%400+1;
	    int AQ=(u(rng)^lastans)%400+1;
	    ans=(1ll*ans*seed%p+(lastans=pre[IQ][EQ][AQ]))%p;
	}
	printf("%d\n",ans);
	return 0;
}

\(G:Wall Builder I\)

细节题，分 \(1,2,3\) 条线构成矩形分别讨论取最大值即可。。。即可个鬼！

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define LF double
using namespace std;
const int N=1e5+3;
int k,n,m,a[4][N],b[2][N];
LL ans;
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void solve(){
	int x,y;ans=0;
	k=in(),n=in(),m=in();
	a[0][0]=a[1][0]=a[2][0]=a[3][0]=0,b[0][0]=b[1][0]=0;
	for(int i=1;i<=k;++i){
		x=in(),y=in();
		if(!x) a[0][++a[0][0]]=y,b[0][++b[0][0]]=y;
		else if(y==m) a[1][++a[1][0]]=x,b[1][++b[1][0]]=x;
		else if(x==n) a[2][++a[2][0]]=y,b[0][++b[0][0]]=y;
		else a[3][++a[3][0]]=x,b[1][++b[1][0]]=x;
	}
	sort(a[0]+1,a[0]+a[0][0]+1),
	sort(a[1]+1,a[1]+a[1][0]+1),
	sort(a[2]+1,a[2]+a[2][0]+1),
	sort(a[3]+1,a[3]+a[3][0]+1),
	sort(b[0]+1,b[0]+b[0][0]+1),
	sort(b[1]+1,b[1]+b[1][0]+1);
	
	if(b[0][0]&&!a[3][0]) ans=max(ans,1ll*b[0][1]*n);
	if(b[0][0]&&!a[1][0]) ans=max(ans,1ll*(m-b[0][b[0][0]])*n);
	if(b[1][0]&&!a[0][0]) ans=max(ans,1ll*b[1][1]*m);
	if(b[1][0]&&!a[2][0]) ans=max(ans,1ll*(n-b[1][b[1][0]])*m);
	
	for(int i=2;i<=b[0][0];++i) ans=max(ans,1ll*(b[0][i]-b[0][i-1])*n);
	for(int i=2;i<=b[1][0];++i) ans=max(ans,1ll*(b[1][i]-b[1][i-1])*m);
	
	for(int i=1;i<=a[0][0];++i){
		if(i==1&&a[3][0]) ans=max(ans,1ll*a[0][1]*a[3][1]);
		if(i==a[0][0]&&a[1][0]) ans=max(ans,1ll*(m-a[0][i])*a[1][1]);
		if(a[3][0]&&(!a[2][0]||a[2][1]>a[0][i])) ans=max(ans,1ll*a[0][i]*(n-a[3][a[3][0]]));
		if(a[1][0]&&(!a[2][0]||a[2][a[2][0]]<a[0][i])) ans=max(ans,1ll*(m-a[0][i])*(n-a[1][a[1][0]]));
	}
	
	for(int i=1;i<=a[1][0];++i){
		if(i==1&&a[0][0]) ans=max(ans,1ll*a[1][1]*(m-a[0][a[0][0]]));
		if(i==a[1][0]&&a[2][0]) ans=max(ans,1ll*(n-a[1][i])*(m-a[2][a[2][0]]));
		if(a[0][0]&&(!a[3][0]||a[3][1]>a[1][i])) ans=max(ans,1ll*a[1][i]*a[0][1]);
		if(a[2][0]&&(!a[3][0]||a[3][a[3][0]]<a[1][i])) ans=max(ans,1ll*(n-a[1][i])*a[2][1]);
	}
	
	for(int i=1;i<=a[2][0];++i){
		if(i==1&&a[3][0]) ans=max(ans,1ll*a[2][1]*(n-a[3][a[3][0]]));
		if(i==a[2][0]&&a[1][0]) ans=max(ans,1ll*(m-a[2][a[2][0]])*(n-a[1][a[1][0]]));
		if(a[3][0]&&(!a[0][0]||a[0][1]>a[2][i])) ans=max(ans,1ll*a[2][i]*a[3][1]);
		if(a[1][0]&&(!a[0][0]||a[0][a[0][0]]<a[2][i])) ans=max(ans,1ll*(m-a[2][i])*a[1][1]);
	}
	
	for(int i=1;i<=a[3][0];++i){
		if(i==1&&a[0][0]) ans=max(ans,1ll*a[3][1]*a[0][1]);
		if(i==a[3][0]&&a[2][0]) ans=max(ans,1ll*(n-a[3][i])*a[2][1]);
		if(a[0][0]&&(!a[1][0]||a[1][1]>a[3][i])) ans=max(ans,1ll*a[3][i]*(m-a[0][a[0][0]]));
		if(a[2][0]&&(!a[1][0]||a[1][a[1][0]]<a[3][i])) ans=max(ans,1ll*(n-a[3][i])*(m-a[2][a[2][0]]));
	}
	for(int i=2;i<=a[0][0];++i) if(b[1][0]) ans=max(ans,1ll*(a[0][i]-a[0][i-1])*b[1][b[1][0]]);
	for(int i=2;i<=a[1][0];++i) if(b[0][0]) ans=max(ans,1ll*(a[1][i]-a[1][i-1])*(m-b[0][1]));
	for(int i=2;i<=a[2][0];++i) if(b[1][0]) ans=max(ans,1ll*(a[2][i]-a[2][i-1])*(n-b[1][1]));
	for(int i=2;i<=a[3][0];++i) if(b[0][0]) ans=max(ans,1ll*(a[3][i]-a[3][i-1])*b[0][b[0][0]]);
	if(a[1][0]){
		for(int i=1,j=1;i<=a[0][0];++i){
			while(j<=a[2][0]&&a[2][j]<a[0][i]) ++j;
			if(j==a[2][0]+1) break;
			ans=max(ans,1ll*(n-a[1][1])*(a[2][j]-a[0][i]));
		}
	}
	if(a[3][0]){
		for(int i=a[0][0],j=a[2][0];i;--i){
			while(j&&a[2][j]>a[0][i]) --j;
			if(!j) break;
			ans=max(ans,1ll*(n-a[3][1])*(a[0][i]-a[2][j]));
		}
	}
	if(a[2][0]){
		for(int i=1,j=1;i<=a[1][0];++i){
			while(j<=a[3][0]&&a[3][j]<a[1][i]) ++j;
			if(j==a[3][0]+1) break;
			ans=max(ans,1ll*a[2][a[2][0]]*(a[3][j]-a[1][i]));
		}
	}
	if(a[0][0]){
		for(int i=a[1][0],j=a[3][0];i;--i){
			while(j&&a[3][j]>a[1][i]) --j;
			if(!j) break;
			ans=max(ans,1ll*a[0][a[0][0]]*(a[1][i]-a[3][j]));
		}
	}
	if(a[1][0]){
		for(int i=1,j=1;i<=a[2][0];++i){
			while(j<=a[0][0]&&a[0][j]<a[2][i]) ++j;
			if(j==a[0][0]+1) break;
			ans=max(ans,1ll*a[1][a[1][0]]*(a[0][j]-a[2][i]));
		}
	}
	if(a[3][0]){
		for(int i=a[2][0],j=a[0][0];i;--i){
			while(j&&a[0][j]>a[2][i]) --j;
			if(!j) break;
			ans=max(ans,1ll*a[3][a[3][0]]*(a[2][i]-a[0][j]));
		}
	}
	if(a[2][0]){
		for(int i=1,j=1;i<=a[3][0];++i){
			while(j<=a[1][0]&&a[1][j]<a[3][i]) ++j;
			if(j==a[1][0]+1) break;
			ans=max(ans,1ll*(m-a[2][1])*(a[1][j]-a[3][i]));
		}
	}
	if(a[0][0]){
		for(int i=a[3][0],j=a[1][0];i;--i){
			while(j&&a[1][j]>a[3][i]) --j;
			if(!j) break;
			ans=max(ans,1ll*(m-a[0][1])*(a[3][i]-a[1][j]));
		}
	}
	printf("%lld\n",ans);
}
int main()
{
	int T=in();
	while(T--) solve();
  return 0;
}

\(H:Wall Builder II\)

枚举矩形的长宽贪心放尽量长的砖块即可。
（代码打表，过长不放。）

\(J:Counting Fish Again\)

对于 \(x+y=k\) 的线，若向右上延伸则无限制，若向左下延伸，对于三角形直角顶点 \((x,y)\) ，最左下方的点为 \((2x+y-k,2y+x-k)\) ，要满足横纵坐标皆大于等于 \(0\) ，相当于两个半平面交，求其与一个直角三角形交集的整数点数。用 \(set\) 维护各个 \(x+y\) 不相等的线段。

\(K:NIO's Sword\)

若进行 \(k\) 次，\(x -> x \cdot 10^k +(0\) ~ \((10^k-1)) \mod n\) ，枚举判断即可。
注意 \(n=1\) 是答案为 \(0\) 。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pb push_back
using namespace std;
const int N=1e6+3;
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void solve(){
	int n=in();int val=0,ans=0;
	if(n==1){puts("0");return;}
	for(int i=1;i<=n;++i){
		val=i-1;
		for(int j=1,k=10;;++j,k*=10){
			val=val*10%n;
			if(val<=i%n&&val+k-1>=i%n){ans+=j;break;}
			if(val>i%n&&val+k-1>=i%n+n){ans+=j;break;}
		}
	}
	cout<<ans<<endl;
}
int main()
{
    solve();
    return 0;
}

\(N:Particle Arts\)

最后肯定会变为对于任意 \(i,j\) ，若 \(a_i \leq a_j\) ,则 \(a_i \& a_j =a_i\) 。
我们提取出所有 \(a\) 的每一位，将 \(1\) 都分配到最右端，显然这样是唯一满足其的方案。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=1e5+3;
int n,buk[N];
LL a[N],b[N],sum;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
struct kk{
	LL a,b;
	kk operator+(const kk &c) const{
		LL d=gcd(b,c.b);
		LL a0=a*c.b/d+c.a*b/d,b0=b*c.b/d;
		d=gcd(a0,b0);
		return (kk){a0/d,b0/d};
	}
	kk operator-(const kk &c) const{
		LL d=gcd(b,c.b);
		LL a0=a*c.b/d-c.a*b/d,b0=b*c.b/d;
		d=gcd(a0,b0);
		return (kk){a0/d,b0/d};
	}
	void maintain(){
		LL d=gcd(a,b);
		a/=d,b/=d;	
	}
	kk pf(){return (kk){a*a,b*b};}
	kk operator/(const int &k){
		LL d=gcd(a,b*k);
		return (kk){a/d,b*k/d};
	}
}s,mi;
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
int main()
{
	n=in();
	for(int i=1;i<=n;++i){
		sum+=(a[i]=in());
		for(int j=0;j<15;++j)
		  if(a[i]>>j&1) ++buk[j];
	}
	for(int i=0;i<15;++i)
	  for(int j=1;j<=buk[i];++j)
	    b[j]|=1<<i;
	mi.a=sum*sum,mi.b=n,mi.maintain();
	for(int i=1;i<=n;++i) s.a+=b[i]*b[i];
	s.b=1,s=s-mi,s=s/n;
	printf("%lld/%lld\n",s.a,s.b);
	return 0;
}

这篇关于"蔚来杯"2022牛客暑期多校训练营4的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

"蔚来杯"2022牛客暑期多校训练营4

链接

\(A:Task Computing\)

\(C:Easy Counting Problem\)

\(D:Jobs (Easy Version)\)

\(E:Jobs (Hard Version)\)

\(G:Wall Builder I\)

\(H:Wall Builder II\)

\(J:Counting Fish Again\)

\(K:NIO's Sword\)

\(N:Particle Arts\)

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯