"蔚来杯"2022牛客暑期多校训练营4
2022/8/4 6:22:55
本文主要是介绍"蔚来杯"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的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-12-28一步到位：购买适合 SEO 的域名全攻略
- 2024-12-27OpenFeign服务间调用学习入门
- 2024-12-27OpenFeign服务间调用学习入门
- 2024-12-27OpenFeign学习入门：轻松掌握微服务通信
- 2024-12-27OpenFeign学习入门：轻松掌握微服务间的HTTP请求
- 2024-12-27JDK17新特性学习入门：简洁教程带你轻松上手
- 2024-12-27JMeter传递token学习入门教程
- 2024-12-27JMeter压测学习入门指南
- 2024-12-27JWT单点登录学习入门指南
- 2024-12-27JWT单点登录原理学习入门
