技术教程 编程教程 10.24 正睿停课训练 Day8 AM 正文

10.24 正睿停课训练 Day8 AM

2023-05-28,,

目录
2018.10.24 正睿停课训练 Day8 AM
A 棒棒糖(组合)
B 彩虹糖(思路 博弈)
C 泡泡糖(DP)
考试代码
A
B
C

2018.10.24 正睿停课训练 Day8 AM

期望得分：70+21+xjbDP(好像昨天我也写了一个?->people in despair什么都能写...)

实际得分：75+10+0

比赛链接

A 棒棒糖(组合)

题目链接

倍增LCA的第二部分是没有问题的。第一部分的目的是利用深度差让\(u,v\)跳到同一深度上，但是\(dep[u]\)与\(dep[v]\)可能会改变。但只要让深度差在变化前后不变就能保证正确。

\(w=LCA(u,v)\)以上的部分是公共的，不需要考虑。记\(d_u=dep[u]-dep[w],d_v=de[v]-dep[w]\)，且设\(d_u\leq d_v,\ \Delta d=d_v-d_u\)。我们枚举\(d_u\)变成了多少，则\(d_v\)也应该变成\(d_u+\Delta d\)。

\(d_u\)变成\(x\)的概率是\(\frac{C_{d_u}^{x}}{2^{d_u}}\)。所以\(Ans=\frac{1}{2^{d_u+d_v}}\sum_{i=0}^{\min(d_u,d_v-\Delta d)}C_{du}^iC_{dv}^{i+\Delta d}\)。

直接这样是\(O(nq)\)的。考虑怎么化简。

把\(\Delta d\)拆开，\(Ans=\frac{1}{2^{d_u+d_v}}\sum_{i=0}^{d_u}C_{du}^iC_{dv}^{d_u-i}\)（或者，直接枚举\(u,v\)上面有多少条边消失了也可以得到这个式子）。

\[\sum_{i=0}^{d_u}C_{du}^iC_{dv}^{d_u-i}
\]

考虑这个东西的意义，就是枚举从\(d_u\)中选多少个，然后再从\(d_v\)中补若干个，使得选出的数总共有\(d_u\)个的所有方案。也就是\(C_{d_u+d_v}^{d_u}\)。

然后就可以\(O(1)\)计算了。复杂度\(O(q)\)。

上面的式子可以扩展到任意多个的情况，即：范德蒙德卷积。

我就记得有这样的式子。。但是看到T2T3直接弃疗了，还有具体数学不在手上。

//621ms	18032kb

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 200000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

#define mod 998244353

#define Mod(x) x>=mod&&(x-=mod)

#define C(n,m) (1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod)

typedef long long LL;

const int N=2e5+5;

int n,Enum,H[N],nxt[N<<1],to[N<<1],fa[N],dep[N],sz[N],son[N],top[N];

int fac[N<<1],ifac[N<<1],pw[N<<1],ipw[N<<1];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline int FP(int x,int k)

{

	int t=1;

	for(; k; k>>=1,x=1ll*x*x%mod)

		if(k&1) t=1ll*t*x%mod;

	return t;

}

inline void AE(int u,int v)

{

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;

	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;

}

inline int LCA(int u,int v)

{

	while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];

	return dep[u]<dep[v]?u:v;

}

void DFS1(int x)

{

	int mx=0; sz[x]=1;

	for(int i=H[x],v; i; i=nxt[i])

		if((v=to[i])!=fa[x])

		{

			fa[v]=x, dep[v]=dep[x]+1, DFS1(v), sz[x]+=sz[v];

			if(sz[v]>mx) mx=sz[v], son[x]=v;

		}

}

void DFS2(int x,int tp)

{

	top[x]=tp;

	if(son[x])

	{

		DFS2(son[x],tp);

		for(int i=H[x],v; i; i=nxt[i])

			if((v=to[i])!=fa[x]&&v!=son[x]) DFS2(v,v);

	}

}

int main()

{

	n=read();

	for(int i=1; i<n; ++i) AE(read(),read());

	fac[0]=fac[1]=1, pw[0]=1, pw[1]=2;

	for(int i=2; i<=n; ++i) fac[i]=1ll*fac[i-1]*i%mod;

	for(int i=2; i<=n<<1; ++i) pw[i]=pw[i-1]<<1, Mod(pw[i]);

	ifac[n]=FP(fac[n],mod-2);

	for(int i=n; i; --i) ifac[i-1]=1ll*ifac[i]*i%mod;

	ipw[n<<1]=FP(pw[n<<1],mod-2);

	for(int i=n<<1; i; --i) ipw[i-1]=ipw[i]<<1, Mod(ipw[i-1]);

	DFS1(1), DFS2(1,1);

	for(int Q=read(),u,v,w; Q--; )

	{

		w=LCA(u=read(),v=read());

		int du=dep[u]-dep[w],dv=dep[v]-dep[w];

		printf("%d\n",(int)(1ll*C(du+dv,du)*ipw[du+dv]%mod));

	}

	return 0;

}

B 彩虹糖(思路 博弈)

题目链接

因为集合\(A,B\)不相交，所以每个人的操作顺序可以是任意的（能由他操作的堆不会由另一个人去操作）。所以我们只需要计算每一堆的贡献（或者说一堆中有\(x\)个时的贡献）。

对于先手能操作的一堆糖果，设有\(x\)个，把它分成两堆可能会给先手增加操作次数，也可能会给后手更多操作机会。而先手要最大化 \(它能操作的次数-后手能操作的次数\)。

记\(f(x)\)表示一堆中有\(x\)个糖果时（对应情况的）\(先手可操作次数-后手可操作次数\)。直接\(O(m)\)枚举把\(x\)分成\(i\)和\(x-i\)，对于先手，求\(\max_{i=1}^{x-1}\{f(i)+f(i-x)\}\)就可以了。先手也可以不选，所以要对\(0\)取\(\max\)。

后手同理，不过是对于它能选的\(x\)，要最小化\(f(x)\)的值（同样要与\(0\)取\(\min\)）。

\(O(m^2)\)求出所有\(f(i)\)，然后判一下\(\sum_{x=1}^nf(P[x])\)是否\(>0\)就行了。

ps：因为\(A,B\)集合不相交，所以这是平等博弈，大多可以用SG函数解决；

如果\(A,B\)集合可以相交，则是不平等博弈问题，要用超现实数解决。（见dls课件？反正我见了也没什么用）

其实也不难啊，怎么就是想不到啊。

//649ms	804kb

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 300000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=1e6+5,M=1e4+5;

int f[M];

bool okA[M],okB[M];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

int main()

{

	int n=read(),m=read();

	for(int totA=read(); totA--; okA[read()]=1);

	for(int totB=read(); totB--; okB[read()]=1);

	for(int i=2; i<=m; ++i)

		if(okA[i])

			for(int j=1; j<=i>>1; ++j)

				f[i]=std::max(f[i],f[j]+f[i-j]+1);//0

		else if(okB[i])

			for(int j=1; j<=i>>1; ++j)

				f[i]=std::min(f[i],f[j]+f[i-j]-1);//0

	int ans=0;

	for(int i=1,p; i<=n; ++i)

		if((p=read())<=m) ans+=f[p];

	puts(ans>0?"Pomegranate":"Orange");

	return 0;

}

C 泡泡糖(DP)

题目链接

神仙dp优化？

dls：这题太难了我们咕了吧。

咕了

考试代码

A

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 200000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

#define mod 998244353

#define Mod(x) x>=mod&&(x-=mod)

typedef long long LL;

const int N=2e5+5;

int n,Enum,H[N],nxt[N<<1],to[N<<1],fa[N],dep[N],sz[N],son[N],top[N],dfn[N],Index,out[N];

int fac[N<<1],ifac[N<<1],pw[N<<1],ipw[N<<1];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline int FP(int x,int k)

{

	int t=1;

	for(; k; k>>=1,x=1ll*x*x%mod)

		if(k&1) t=1ll*t*x%mod;

	return t;

}

inline void AE(int u,int v)

{

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;

	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;

}

inline int LCA(int u,int v)

{

	while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];

	return dep[u]<dep[v]?u:v;

}

void DFS1(int x)

{

	int mx=0; sz[x]=1;

	for(int i=H[x],v; i; i=nxt[i])

		if((v=to[i])!=fa[x])

		{

			fa[v]=x, dep[v]=dep[x]+1, DFS1(v), sz[x]+=sz[v];

			if(sz[v]>mx) mx=sz[v], son[x]=v;

		}

}

void DFS2(int x,int tp)

{

	dfn[x]=++Index, top[x]=tp;

	if(son[x])

	{

		DFS2(son[x],tp);

		for(int i=H[x],v; i; i=nxt[i])

			if((v=to[i])!=fa[x]&&v!=son[x]) DFS2(v,v);

	}

	out[x]=Index;

}

int main()

{

//	freopen("ex_BBT2.in","r",stdin);

//	freopen(".out","w",stdout);

	n=read();

	for(int i=1; i<n; ++i) AE(read(),read());

	fac[0]=fac[1]=1, pw[0]=1, pw[1]=2;

	for(int i=2; i<=n; ++i) fac[i]=1ll*fac[i-1]*i%mod;

	for(int i=2; i<=n<<1; ++i) pw[i]=pw[i-1]<<1, Mod(pw[i]);

	ifac[n]=FP(fac[n],mod-2);

	for(int i=n; i; --i) ifac[i-1]=1ll*ifac[i]*i%mod;

	ipw[n<<1]=FP(pw[n<<1],mod-2);

	for(int i=n<<1; i; --i) ipw[i-1]=ipw[i]<<1, Mod(ipw[i-1]);

//	for(int i=1; i<=n; ++i) printf("Inv(%d)=%d\n",i,ipw[i]);

	DFS1(1), DFS2(1,1);

	for(int Q=read(),u,v,w; Q--; )

	{

		u=read(), v=read(), w=LCA(u,v); if(dep[u]>dep[v]) std::swap(u,v);

		LL ans=0;

		int du=dep[u]-dep[w],dv=dep[v]-dep[w],delta=dv-du,lim=std::min(du,dv-delta);

		for(int i=0; i<=lim; ++i) ans+=1ll*ifac[i]*ifac[du-i]%mod*ifac[i+delta]%mod*ifac[dv-i-delta]%mod;

		ans=ans%mod*fac[du]%mod*fac[dv]%mod*ipw[du+dv]%mod;

		printf("%d\n",(int)ans);

	}

	return 0;

}

B

没有暴力分的原因：把飞飞侠想傻了。。

#include <cstdio>

#include <cctype>

#include <cstdlib>

#include <algorithm>

#define gc() getchar()

#define MAXIN 300000

//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=1e6+5;

int n,m,P[N],totA,A[N],totB,B[N],sg[2][N];

bool okA[N],okB[N];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

namespace Subtask1

{

	void DFS(int now)

	{

		bool f=0;

		for(int i=1; i<=n; ++i)

			if(!now)

			{

				if(!okA[P[i]]||P[i]<=1) continue;

				f=1;

				for(int x=1; x<P[i]; ++x)

					P[i]-=x, P[++n]=x, DFS(now^1), P[i]+=x, --n;

			}

			else

			{

				if(!okB[P[i]]||P[i]<=1) continue;

				f=1;

				for(int x=1; x<P[i]; ++x)

					P[i]-=x, P[++n]=x, DFS(now^1), P[i]+=x, --n;

			}

		if(!f)

		{

			if(!now) return;

			else {puts("Pomegranate"); exit(0);}

		}

	}

	void Main()

	{

		DFS(0), puts("Orange");

	}

}

void Init()

{

	static int vis[10005],A[2][N];

	int Time=0,mx=0,tot[2]={totA,totB};

	for(int i=1; i<=n; ++i) mx=std::max(mx,P[i]);

	for(int i=1; i<=totA; ++i) A[0][i]=::A[i];

	for(int i=1; i<=totB; ++i) A[1][i]=::B[i];

	A[0][totA+1]=A[1][totB+1]=1e9;

	for(int i=1; i<=mx; ++i)

		for(int now=0; now<2; ++now)

		{

			++Time;

			for(int j=1; A[now][j]<=i; ++j)

				vis[sg[now^1][i-A[now][j]]]=Time;

			for(int j=0; ; ++j)

				if(vis[j]!=Time) {sg[now][i]=j; break;}

		}

}

int main()

{

//	freopen("B3.in","r",stdin);

//	freopen(".out","w",stdout);

	n=read(),m=read(),totA=read();

	for(int i=1; i<=totA; ++i) okA[A[i]=read()]=1;

	totB=read();

	for(int i=1; i<=totB; ++i) okB[B[i]=read()]=1;

	int cnt=0;

	for(int i=1,p; i<=n; ++i) if((p=read())<=m&&p>1) P[++cnt]=p;

	n=cnt;

	bool f=0;

	for(int i=1; i<=n; ++i) if(okA[P[i]]&&P[i]>1) {f=1; break;}

	if(!f) return puts("Orange"),0;

//Pomegranate Orange

	if(!totA) return puts("Orange"),0;

	if(!totB) return puts("Pomegranate"),0;

	if(n<=8||1) return Subtask1::Main(),0;

	std::sort(A+1,A+1+totA), std::sort(B+1,B+1+totB);

	Init();

	int sum=0;

	for(int i=1; i<=n; ++i) sum^=sg[0][P[i]];

	puts(sum?"Pomegranate":"Orange");

	return 0;

}

C

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

#define MAXIN 200000

//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=5e4+5,INF=2e9;

int n,m,L[6][N],R[6][N],row[6][N],col[6][N];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

namespace Subtask4

{

	int f[2][10005];

	void Main()

	{

		int n=::n,m=::m,now=0,las=1;

		for(int j=2; j<=m; ++j)

			for(int a=L[1][j]; a<=R[1][j]; ++a)

			{

				int tmp=INF;

				for(int k=L[1][j-1]; k<=R[1][j-1]; ++k)

					tmp=std::min(tmp,f[las][k]+std::abs(a-k)*row[1][j-1]);

				f[now][a]=tmp;

			}

		int ans=INF;

		for(int i=L[n][m]; i<=R[n][m]; ++i) ans=std::min(ans,f[now][i]);

		printf("%d\n",ans);

	}

}

namespace Subtask5

{

	int f[6][N][2];

	void Main()

	{

		int n=::n,m=::m;

		for(int i=1; i<=n; ++i)

			for(int j=1; j<=m; ++j)

				for(int a=L[i][j]; a<=R[i][j]; ++a)

				{

					int tmp=INF;

					for(int k=L[i][j-1]; k<=R[i][j-1]; ++k)

						for(int l=L[i-1][j]; l<=R[i-1][j]; ++l)

							tmp=std::min(tmp,f[i][j-1][k]+std::abs(a-k)*row[i][j-1]+f[i-1][j][l]+std::abs(a-l)*col[i-1][j]);

					f[i][j][a]=tmp;

				}

		int ans=INF;

		for(int i=L[n][m]; i<=R[n][m]; ++i) ans=std::min(ans,f[n][m][i]);

		printf("%d\n",ans);

	}

}/*

3 1

2 2 3 5 5 5

4 4

*/

int main()

{

//	freopen("C1.in","r",stdin);

//	freopen(".out","w",stdout);

	m=read(),n=read();//n行m列

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=m; ++j) L[i][j]=read(),R[i][j]=read();

	for(int i=1; i<=n; ++i)

		for(int j=1; j<m; ++j) row[i][j]=read();

	for(int i=1; i<n; ++i)

		for(int j=1; j<=m; ++j) col[i][j]=read();

	if(n==1) return Subtask4::Main(),0;

	return Subtask5::Main(),0;

	return 0;

}

10.24 正睿停课训练 Day8 AM的相关教程结束。

《10.24 正睿停课训练 Day8 AM.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!