技术教程 11.2 正睿停课训练 Day15 正文

11.2 正睿停课训练 Day15

2022-11-12,,,

目录
2018.11.2 正睿停课训练 Day15
A 郁闷的小G(二分)
B 小G的树(树形DP)
C 数的距离(思路)
考试代码
B
C

2018.11.2 正睿停课训练 Day15

时间：3.5h

期望得分：100+20+20

实际得分：100+20+0

比赛链接

A 郁闷的小G(二分)

题目链接

//二分。

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

typedef long long LL;

inline LL read()

{

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

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

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

	return now;

}

inline bool Check(LL x,LL a,LL b,LL c,LL d,LL e)

{

	if(a<x) b-=x-a;

	if(e<x) d-=x-e;

	if(b<0||d<0) return 0;

	LL tmp=b+d;

	if(c<x) c+=tmp;

	return c>=x;

}

int main()

{

	LL a=read(),b=read(),c=read(),d=read(),e=read();

	LL l=0,r=2e18,mid,ans=0;

	while(l<=r)

		if(Check(mid=l+r>>1,a,b,c,d,e)) ans=mid,l=mid+1;

		else r=mid-1;

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

	return 0;

}/*

2 2 1 2 2

100 100 100 0 0

*/

B 小G的树(树形DP)

题目链接

求树的直径需要用到子树最长链与子树内的最大直径，都存下来就好了。

\(f[i][j][k]\)表示当前为点\(i\)，\(i\)子树最长链长度为\(j\)，\(i\)子树内最大直径为\(k\)，的概率（直径不一定过点\(i\)）。

转移\(O(n^4)\)就行了。

概率\(\frac 12\)可以最后乘，也就是两种可能的概率都算做\(1\)。同时存的数不会超过\(2^{60}\)，所以可以用longlong。

最后乘\(\frac{1}{2^{n-1}}\)，因为每条边的概率都乘了\(2\)。

//0ms	1080kb

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

typedef long long LL;

const int N=62;

int Enum,H[N],nxt[N<<1],to[N<<1],D[N];

LL f[N][N<<1][N<<1];

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 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;

}

void Merge(int x,int v,int d1,int d2,int d3,int d4)

{

	static LL g[N<<1][N<<1];

	LL (*fx)[N<<1]=f[x],(*fv)[N<<1]=f[v];

	LL tmp,tmp2;

	for(int a=0; a<=d1; ++a)

		for(int b=a; b<=d2; ++b)

			if((tmp=fx[a][b]))

				for(int c=0; c<=d3; ++c)

					for(int d=c; d<=d4; ++d)

					{

						if(!fv[c][d]) continue;

						tmp2=tmp*fv[c][d];

						g[std::max(a,c+1)][std::max(std::max(b,d),a+c+1)]+=tmp2,

						g[std::max(a,c+2)][std::max(std::max(b,d),a+c+2)]+=tmp2;

					}

	int l1=std::max(d1,d3+2),l2=std::max(std::max(d2,d4),d1+d3+2);

	for(int i=0; i<=l1; ++i)

		for(int j=i; j<=l2; ++j) fx[i][j]=g[i][j], g[i][j]=0;

}

int DFS(int x,int fa)

{

	int mxd=0,dia=0; f[x][0][0]=1;

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

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

		{

			d=DFS(v,x), Merge(x,v,mxd,dia,d,D[v]);

			dia=std::max(dia,std::max(D[v],mxd+d)), mxd=std::max(mxd,d);

		}

	return D[x]=dia, mxd+2;

}

int main()

{

	int n=read();

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

	int d=DFS(1,1);

	double ans=0;

	for(int i=0; i<=d; ++i)

		for(int j=i; j<=D[1]; ++j) ans+=1.0*f[1][i][j]*j;

	printf("%.10lf\n",ans/(1ll<<n-1));

	return 0;

}

C 数的距离(思路)

题目链接

原题：HDU5812。

对于\(dis(x,y)\)，把\(x,y\)质因数分解后（令\(x=\prod_{i=1}^k p_i^{a_i},y=\prod_{i=1}^k p_i^{b_i}\)），则\(dis(x,y)=\sum_{i=1}^k |a_i-b_i|\)。

实际上我们可以去掉\(x,y\)公共的部分，即令\(f(x)=x的质因子个数\)，则\(dis(x,y)=f(\frac{x}{\gcd(x,y)})+f(\frac{y}{\gcd(x,y)})\)。

\(f\)可以线性筛预处理，即\(f(\frac{x}{\gcd(x,y)})\)可以直接得到。然后我们可以枚举\(x\)的约数\(d\)作为\(\gcd(x,y)\)，然后求\(\min\{f(\frac yd)\}(y在集合中)\)。

不妨在插入\(y\)时，也枚举\(y\)的每个约数\(d\)，然后更新\(g(d)=\min\{g(d),f(\frac yd)\}\)。\(g(d)\)表示\(f(\frac yd)(y在集合中)\)的最小值。

这样就可以\(O(1)\)求\(\min\{f(\frac yd)\}\)了。

但是还有删除操作，我们需要维护\(g(d)\)的最小值。

注意到\(f(x)\)不会超过\(20\)，且我们只关心\(f(\frac yd)\)的大小，所以可以用\(cnt[d][t]\)表示\(g(d)\)中满足\(g(d)=t\)的\(y\)的个数，用一个二进制数\(s[d]\)表示\(g(d)\)中每个值的存在性。这样就可以\(O(1)\)更新\(g(d)\)，并在查询时直接用位运算找到最小的\(g(d)\)。

（事实上用不到\(f\)数组，因为只需要在枚举约数的时候算下个数就行了）

质因数种类是最多\(7\)个，但不代表就是\(2,3,5,7,11,13,17\)这些啊。。

可以处理出每个数的一个质因数\(p\)，\(n\)每次直接除\(p[n]\)，就不用枚举质数了。

另外看到这个就想到\(k\)维曼哈顿距离。。最大好像能做吧（就是复杂度有点大），求最小距离是不是不能做啊。。

//646ms	87836kb

#include <cstdio>

#include <cctype>

#include <vector>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 300000

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

const int N=1e6+3,INF=1e9;//P[7]={2,3,5,7,11,13,17};

int Opt,Ans,A[7],P[7],p[N],cnt[N][20],s[N];//A[N][7],P[N][7] //卡我内存还行

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;

}

void Init(const int n)

{

	static int P[N>>3];

	static bool not_P[N];

	for(int cnt=0,i=2; i<=n; ++i)

	{

		if(!not_P[i]) P[++cnt]=i, p[i]=i;

		for(int j=1,v; j<=cnt&&(v=i*P[j])<=n; ++j)

		{

			not_P[v]=1, p[v]=P[j];

			if(!(i%P[j])) break;

		}

	}

}

int Div(int x)

{

	int lim=-1,cnt;

	while(x!=1)

	{

		P[++lim]=p[x], cnt=0;

		while(!(x%P[lim])) ++cnt, x/=P[lim];

		A[lim]=cnt;

	}

	return lim;

}

void DFS(int x,int sum,int d)

{

	if(x==-1)

	{

		switch(Opt)

		{

			case 0: if(++cnt[d][sum]==1) s[d]^=1<<sum; break;

			case 1: if(--cnt[d][sum]==0) s[d]^=1<<sum; break;

			case 2: if(s[d]) Ans=std::min(Ans,sum+__builtin_ctz(s[d])); break;

		}

		return;

	}

	for(int i=0; i<=A[x]; ++i)

		DFS(x-1,sum+A[x]-i,d), d*=P[x];

}

int main()

{

	Init(1000000);

	for(int x,tot=0,Q=read(); Q--; )

	{

		Opt=read()-1, x=read();

		if(Opt==2)

			if(tot) Ans=INF;

			else {puts("-1"); continue;}

		else if(cnt[x][0]^Opt) continue;

		DFS(Div(x),0,1);

		switch(Opt)

		{

			case 0: ++tot; break;

			case 1: --tot; break;

			case 2: printf("%d\n",Ans==INF?-1:Ans); break;

		}

	}

	return 0;

}

考试代码

B

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

#define eps 1e-10

typedef long long LL;

const int N=64;

int n,Enum,H[N],nxt[N<<1],to[N<<1],dgr[N];

double f[N][N];

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 void AE(int u,int v)

{

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

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

}

int DFS(int x,int fa)

{

	if(dgr[x]==1&&x!=fa)

		for(int i=0; i<=2*n; ++i) f[x][i]=1;

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

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

		{

			DFS(v,x);

			for(int d=1; d<=2*n; ++d)

			{

				if(f[x][d]<eps) f[x][d]=1;

				f[x][d]*=(f[v][d-1]*0.5+(d>1?f[v][d-2]*0.5:0));

			}

		}

	for(int i=0; i<=2*n; ++i) printf("f[%d][%d]=%.5lf\n",x,i,f[x][i]);

}

int main()

{

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

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

	n=read();

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

	double ans=0; int cnt=0;

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

	{

		if(dgr[x]>1) continue;

		++cnt;

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

		{

			f[i][0]=0;

			for(int j=1; j<=2*n; j+=4) f[i][j]=f[i][j+1]=f[i][j+2]=f[i][j+3]=0;

			f[i][2*n-2]=f[i][2*n-1]=f[i][2*n]=0;

		}

		printf("\nnow:%d\n",x);

		DFS(x,x);

		for(int i=1; i<=2*n; ++i) ans+=(f[x][i]-f[x][i-1])*i, printf("ans+=%.5lf*%d=%.5lf\n",f[x][i]-f[x][i-1],i,(f[x][i]-f[x][i-1])*i);

	}

	printf("%.10lf\n",ans);

	printf("%.10lf\n",ans/cnt);

	return 0;

}/*

5

1 2 2 3 3 4 4 5

4

1 2 1 3 1 4

7

1 2 2 3 3 4 3 5 4 6 4 7

*/

C

#include <set>

#include <queue>

#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,P[7]={2,3,5,7,11,13,17};//7

int A[N][7],L[N],R[N];

bool vis[N],ins[N];

std::multiset<int> st[130];

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 void Div(int x)

{

	vis[x]=1;

	for(int s=x,i=0; i<7; ++i)

		if(!(x%P[i]))

		{

			int cnt=1; x/=P[i];

			while(!(x%P[i])) ++cnt, x/=P[i];

			A[s][i]=cnt;

		}

}

int main()

{

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

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

	int Q=read(); const int all=1<<7;

//	for(int s=0; s<all; ++s) st[s].insert(-1),st[s].insert(100000000);

	for(int x,tot=0,ed=0; Q--; )

	{

		switch(read())

		{

			case 1:

			{

				if(ins[x=read()]) break;

				ins[x]=1, ++tot;

				if(!vis[x]) Div(x);

				R[ed]=x, L[x]=ed, ed=x;

				break;

			}

			case 2:

			{

				if(!ins[x=read()]) break;

				ins[x]=0, --tot;

				L[R[x]]=L[x], R[L[x]]=R[x];

				if(x==ed) ed=L[x];

				break;

			}

			case 3:

			{

				x=read();

				if(!tot) {puts("-1"); break;}

				if(!vis[x]) Div(x);

				int *a=A[x],ans=1e9;

				for(int i=R[0]; ; i=R[i])

				{

					int sum=0;

					for(int j=0; j<7; ++j) sum+=std::abs(a[j]-A[i][j]);

					ans=std::min(ans,sum);

					if(i==ed) break;

				}

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

				break;

			}

		}

	}

//	return 0;

	for(int x,tot=0,ed=0; Q--; )

	{

		switch(read())

		{

			case 1:

			{

				if(ins[x=read()]) break;

				ins[x]=1, ++tot;

				if(!vis[x]) Div(x);

				int *a=A[x];

				printf("A[%d]: ",x); for(int i=0; i<7; ++i) printf("%d ",a[i]); puts("");

				for(int s=0; s<all; ++s)

				{

					int sum=0;

					for(int i=0; i<7; ++i)

						sum+=(s>>i&1?a[i]:-a[i]);

					st[s].insert(sum);

					printf("Insert(%d,%d)\n",s,sum);

				}

				break;

			}

			case 2:

			{

				if(!ins[x=read()]) break;

				ins[x]=0, --tot;

				int *a=A[x];

				for(int s=0; s<all; ++s)

				{

					int sum=0;

					for(int i=0; i<7; ++i)

						sum+=(s>>i&1?a[i]:-a[i]);

//					printf("Delete(%d)\n",sum);

					st[s].erase(st[s].find(sum));

				}

				break;

			}

			case 3:

			{

				x=read();

				if(!tot) {puts("-1"); break;}

				if(!vis[x]) Div(x);

				int *a=A[x],ans=0;

				printf("A[%d]: ",x); for(int i=0; i<7; ++i) printf("%d ",a[i]); puts("");

				for(int s=0; s<all; ++s)

				{

					int sum=0;

					for(int i=0; i<7; ++i)

						sum+=(s>>i&1?a[i]:-a[i]);

//					std::multiset<int>::iterator it=st[s].upper_bound(sum);

					ans=std::max(ans,std::max(*st[s].rbegin()-sum,sum-*st[s].begin()));

					printf("s:%d sum:%d big:%d ",s,sum,*st[s].rbegin());

					printf("small:%d\n",*st[s].begin());

//					ans=std::min(ans,*it-sum);

//					printf("s:%d sum:%d big:%d ",s,sum,*it);

//					ans=std::min(ans,sum-*(--it));

//					printf("small:%d\n",*it);

				}

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

				break;

			}

		}

	}

	return 0;

}/*

12

3

1 20

1 15

3 30

1 30

3 30

2 10

3 27

1 15

2 15

2 20

2 30

3 5

*/

11.2 正睿停课训练 Day15的相关教程结束。

《11.2 正睿停课训练 Day15.doc》

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

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