21牛客多校第五场

2024-01-11 22:31:10

A

圆方树 咕

B

显然开盒子的顺序应按照\(w\)升序，而\(hint\)若选择使用应该在一开始就使用

在使用\(hint\)的情况下，因为知道\(01\)的总数，每种情况应当在最后一段连续的\(0/1\)前终止

即\(100\cdots 0\)此类情况，在\(0\)处截止，其花费为\(sum_i\)即到\(0\)处\(w\)的前缀和

而此类情况的概率为后\(n-i\)一样且第\(i\)个不同，\(p=\frac{2}{2^{n-i+1}}=\frac{1}{2^{n-i}}\)

最后比较使用\(hint\)的答案与暴力全开哪个较小

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b)+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;db x,w[MAXN],ans;
int main()
{
	n=read();scanf("%lf",&x);
	rep(i,1,n) scanf("%lf",&w[i]);
	sort(w+1,w+n+1);rep(i,1,n) w[i]+=w[i-1];
	db pw=0.5;
	dwn(i,n-1,1) ans+=w[i]*pw,pw*=0.5;
	ans=min(ans+x,w[n]);
	printf("%.7lf\n",ans);
}

C

由于调和级数，需要\(O(1)\)查询对\(i=t\)的情况终止点在哪里

考虑先预处理每个位置的\(W,L\)前缀和以及每个\(W,L\)位置，这样可以找到从位置\(x\)开始后先到\(i\)球的位置

若此时\(W,L\)的差\(>1\)则显然胜负已分，否则需要处理一个从每个点开始何时破局，设为\(nxt_x\)

对位置\(x\)来说，若接下来是两球不同，则仍然是平局，\(nxt_x=nxt_{x+2}\)；否则在\(x+1\)时刻该局结束

预处理完毕后模拟

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 1001001
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b)+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,cnt[MAXN][2],pos[MAXN][2],nxt[MAXN],ans;
char s[MAXN];
int main()
{
	n=read();scanf("%s",s+1);
	rep(i,1,n)
	{
		rep(j,0,1) cnt[i][j]=cnt[i-1][j];
		if(s[i]=='L') pos[++cnt[i][0]][0]=i;
		else pos[++cnt[i][1]][1]=i;
	}
	nxt[n]=nxt[n+1]=n+1;
	dwn(i,n-1,1) nxt[i]= s[i]==s[i+1]?i+1:nxt[i+2];
	int p1,p2,p,c1,c2,pw=1,res;
	rep(t,1,n)
	{
		res=0;rep(i,0,n)
		{
			p1=p2=n+1;
			if(cnt[i][0]+t<=cnt[n][0]) p1=pos[cnt[i][0]+t][0];
			if(cnt[i][1]+t<=cnt[n][1]) p2=pos[cnt[i][1]+t][1];
			p=min(p1,p2);if(p==n+1) break;
			c1=cnt[p][0]-cnt[i][0],c2=cnt[p][1]-cnt[i][1];
			if(abs(c1-c2)==1) p=nxt[p];
			if(p==n+1) break;
			c1=cnt[p][0]-cnt[i][0],c2=cnt[p][1]-cnt[i][1];
			res+=(c1<c2);i=p-1;
		}
		ans=pls(ans,mul(res,pw)),pw=mul(pw,n+1);
	}
	printf("%d\n",ans);
}

D

可以在每次找到一对相同\(a_i=b_j\)时统计答案，设\(f[i][j]\)表示前面范围内以\(i,j\)结尾的公共子序列个数，\(g[i][j]\)表示后面范围内符合条件的点对个数

\(f[i][j]\)简单\(dp\)即可，\(g[i][j]\)的计算过程中，每次找到一对符合答案的\(a_i<b_j\)需要\(+\sum\limits_{i=0}^{min(x,y)} \binom{x}{i}\binom{y}{i}\)这样的东西

不妨令\(x\le y\) 有\(\sum\limits_{i=0}^{x} \binom{x}{i}\binom{y}{i}=\sum\limits_{i=0}^{x} \binom{x}{x-i}\binom{y}{i}=\sum\limits_{i=0}^{x} \binom{x+y}{x}\)

预处理阶乘后直接\(dp\)

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 1000000007
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b)+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,dp[5050][5050],f[5050][5050];
int fac[MAXN],ifac[MAXN],ans;
char a[5050],b[5050];
int qp(int x,int t,int res=1)
{
	for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);
	return res;
}
#define inv(x) qp(x,MOD-2)
int C(int n,int m)
{
	return mul(fac[n],mul(ifac[n-m],ifac[m]));
}
int main()
{
	scanf("%s%s",a+1,b+1);n=strlen(a+1),m=strlen(b+1);
	ifac[0]=fac[0]=1;rep(i,1,1e4+10) fac[i]=mul(fac[i-1],i),ifac[i]=inv(fac[i]);
	dwn(i,n,1) dwn(j,m,1)
	{
		f[i][j]=mns(pls(f[i][j+1],f[i+1][j]),f[i+1][j+1]);
		if(a[i]<b[j]) f[i][j]=pls(f[i][j],C(m-j+n-i,m-j));
	}
	ans=f[1][1];
	rep(i,1,n) rep(j,1,m) 
	{
		if(a[i]==b[j])
		{
			  dp[i][j]=pls(dp[i-1][j-1],1);
			ans=pls(ans,mul(dp[i][j],f[i+1][j+1]));
		}
		dp[i][j]=pls(mns(pls(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]),dp[i][j]);
	}
	printf("%d\n",ans);
}

E

树\(dp\) 咕

F

三分套三分 咕

G

设\(F_S\)表示该位为\(1\)的质因数取满其余随意组合出的数和\(a\)的最小差，\(G_S\)表示和\(b\)的差，答案即为所有\(F_{i}+G_{U-i}\)取\(min\)

而搜索的时候可以搜索出： 该位为\(1\)的质因数取满其余不取满组合出的数和\(a\)的最小差，记为\(f_S\)

令\(F=f\)，\(F_S\)可以更新所有\(F_{S-(1<<j)}\)，\(O(n2^n)\)计算出所有\(F\)，\(G\)同理

最后统计答案

#include<bits/stdc++.h>
#define inf 2139062143
#define ll __int128
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b)+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x)
{
	int st[40],tp=0;
	if(!x) {putchar('0');return ;}
	while(x) st[++tp]=x%10,x/=10;
	while(tp) putchar(st[tp--]+'0');
}
int n;ll w[20],tot[20],a,b;
ll f[1<<18],g[1<<18],ans;
void dfs(int x,int st,ll now)
{
	if(x==n+1) 
	{
		if(now>=a) f[st]=min(f[st],now-a);
		if(now>=b) g[st]=min(g[st],now-b);
		return ;
	}
	dfs(x+1,st,now);
	rep(i,1,tot[x]-1) {now*=w[x];dfs(x+1,st,now);}
	now*=w[x],st|=(1<<x-1);dfs(x+1,st,now);
}
int main()
{
	n=read();rep(i,1,n) w[i]=read(),tot[i]=read();
	a=read(),b=read(),ans=1;
	int mxs=(1<<n)-1;rep(i,1,33) ans=ans*10;
	rep(i,0,mxs) f[i]=g[i]=ans;dfs(1,0,1);
	dwn(i,mxs,0) rep(j,0,n-1) if(!((i>>j)&1))
		f[i]=min(f[i|(1<<j)],f[i]),g[i]=min(g[i|(1<<j)],g[i]);
	rep(i,0,mxs) ans=min(ans,f[i]+g[mxs^i]);
	write(ans);
}

H

考虑如下形式的矩阵，在任何情况下均满足条件：

\[\begin{pmatrix} 0&1&0&1&0&\cdots\\ 0&1&0&1&0&\cdots\\ 1&0&1&0&1&\cdots\\ 1&0&1&0&1&\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix} \]

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b)+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m; 
int main()
{
	n=read(),m=read();
	rep(i,0,n-1) {rep(j,0,m-1) printf("%d",(i/2+j)&1);puts("");}
}

I

还挺裸的回滚莫队，用链表维护一下每个区间的左右端点，每次更新答案总复杂度\(O(n\sqrt{n}+k)\)

回滚莫队时可以把一个更改操作的指针和值一起放到\(vector\)里，写起来非常方便

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b)+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void inc(int &x,int y){x=pls(x,y);}
int n,Q,sz,g[MAXN],bl[MAXN],ans[MAXN],cnt[MAXN],res,l[MAXN],r[MAXN];
vector<pair<int*,int> > opt;
struct Ask{int id,l,r,k;}q[MAXN];
bool operator < (Ask &a,Ask &b){return bl[a.l]==bl[b.l]?a.r<b.r:a.l<b.l;}
inline void mdf(int *x,int w){opt.pb({x,*x});*x=w;}
inline void add(int x)
{
	if(cnt[g[x]]) return ;x=g[x];mdf(&cnt[x],1);
	//cout<<"add: "<<x<<endl;
	int pre=l[x-1],suf=r[x+1];
	if(pre==-1) pre=x;if(suf==-1) suf=x;
	mdf(&r[pre],suf);mdf(&l[suf],pre);
	if(suf-pre+1>res) mdf(&res,suf-pre+1);
}
void del(int t)
{
	while(opt.size()>t)
		{*opt.back().fi=opt.back().se;opt.pop_back();}
}
int main()
{
	n=read(),Q=read(),sz=sqrt(n+5);Fill(l,0xff);Fill(r,0xff);
	rep(i,1,n) g[i]=read(),bl[i]=i/sz;
	rep(i,1,Q) q[i].l=read(),q[i].r=read(),q[i].k=read()-1,q[i].id=i;
	sort(q+1,q+Q+1);int ed,pos,tag,pw;
	rep(i,1,Q)
	{
		if(i==1||bl[q[i].l]!=bl[q[i-1].l])
			{ed=bl[q[i].l]*sz+sz,pos=ed+1;del(0);}
		rep(j,pos,q[i].r) add(j);if(q[i].r>=pos) pos=q[i].r+1;tag=opt.size();
		dwn(j,min(ed,q[i].r),q[i].l) add(j);
		pw=1;inc(ans[q[i].id],res);
		rep(j,1,q[i].k)
		{
			pw=mul(pw,n+1);add(q[i].l-j);add(q[i].r+j);
			inc(ans[q[i].id],mul(res,pw));
		}
		del(tag);
	}
	rep(i,1,Q) printf("%d\n",ans[i]);
}

J

KM 咕

K

考虑对于每个左端点\(l\)找到一个\(r\)使得\([l,r]\)符合条件，则\([l,r+1],\dots [l,n]\)这些区间均符合条件

容易发现当\(l\)右移时，\(r\)也一定右移，不可能左移；因此可以使用滑动窗口

对于区间内的最大值与最小值，可以用单调队列维护

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b)+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,k,mn[MAXN],mx[MAXN],g[MAXN],h1,t1,h2,t2;
ll ans;
int main()
{
	n=read(),m=read();rep(i,1,n) g[i]=read();
	rep(t,1,m)
	{
		k=read();h1=h2=1,t1=t2=0;ans=0;int l=1;
		rep(i,1,n)
		{
			while(h1<=t1&&g[mx[t1]]<=g[i]) t1--;mx[++t1]=i;
			while(h2<=t2&&g[mn[t2]]>=g[i]) t2--;mn[++t2]=i;
			while(h1<=t1&&h2<=t2&&g[mx[h1]]-g[mn[h2]]>k)
			{
				ans+=n-i+1,l++;
				if(mx[h1]<l) h1++;
				if(mn[h2]<l) h2++;
			}
		}
		printf("%lld\n",ans);
	}
}
上一篇：ARC125 C - LIS to Original Sequence（构造）


下一篇：V-rep 逆运动学（IK）4-twoIkGroupsWithEachOneIkElement-resolutionOrderIsRelevant 示例重建