[2017/6/6]福建四校联考

编程入门 行业动态 更新时间:2024-10-11 15:19:48

[2017/6/6]<a href=https://www.elefans.com/category/jswz/34/1750622.html style=福建四校联考"/>

[2017/6/6]福建四校联考

来自FallDream的博客,未经允许,请勿转载,谢谢。


 

昨晚打cf修仙,今早还有联考。。八点勉强起来看了看题目,打了T1sb题,然后躺床上想T2,一觉起来就12点了。。。。。赶紧写完了暴力。

然后发现我的mac上不用#include<cstring>就可以memset,T1CE了。。。。T2瞎推式子爆0了。。T3混到60分。

23333 

A.给定一棵树,每次询问一些点,两两距离的和、最小值、最大值是多少。

n,询问的点的总数不超过500000

建出虚树之后dp

(其实没ce我也过不去,把五十万看成了五万 盲人做题)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MD 19
#define MN 500000
#define INF 2000000000
#define ll long long
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
bool b[MN+5];
ll ans1;int ans2,ans3;
int n,m,head[MN+5],K,a[MN+5],dfn[MN+5],dn=0,mn[MN+5],mx[MN+5],cnt=0;
int Fa[MD+1][MN+5],size[MN+5],q[MN*2+5],top,dep[MN+5],num=0,B[MN+5];
struct edge{int to,next,w;}e[MN*2+5];
inline void ins(int f,int t)
{int W=dep[t]-dep[f];e[++cnt]=(edge){t,head[f],W};head[f]=cnt;e[++cnt]=(edge){f,head[t],W};head[t]=cnt;
}void Dfs(int x,int fa)
{dfn[x]=++dn;for(int i=head[x];i;i=e[i].next)if(e[i].to!=fa){dep[e[i].to]=dep[x]+1;Fa[0][e[i].to]=x;Dfs(e[i].to,x);}
}inline int lca(int x,int y)
{if(dep[x]<dep[y]) swap(x,y);for(int k=dep[x]-dep[y],j=0;k;k>>=1,++j)if(k&1) x=Fa[j][x];if(x==y) return x;for(int i=MD;~i;--i)if(Fa[i][x]!=Fa[i][y])x=Fa[i][x],y=Fa[i][y];return Fa[0][x];
}void Build()
{for(int i=1;i<=K;++i){if(top){int x=lca(a[i],q[top]);if(x==q[top]) q[++top]=a[i];else{while(top>1&&dep[q[top-1]]>=dep[x])--top,ins(q[top],q[top+1]);if(top&&q[top]!=x&&dep[q[top-1]]<dep[x])ins(x,q[top]),q[top]=x;q[++top]=a[i];}}elseq[++top]=a[i];}for(;top>1;--top) ins(q[top-1],q[top]);
}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void Solve(int x,int fa)
{mx[x]=0;size[x]=b[x];B[++num]=x;mn[x]=b[x]?0:INF;for(int i=head[x];i;i=e[i].next)if(e[i].to!=fa){Solve(e[i].to,x);ans1+=1LL*size[e[i].to]*(K-size[e[i].to])*e[i].w;ans3=min(ans3,(b[x]?0:mn[x])+mn[e[i].to]+e[i].w);ans2=max(ans2,mx[x]+mx[e[i].to]+e[i].w);mx[x]=max(mx[x],mx[e[i].to]+e[i].w);mn[x]=min(mn[x],mn[e[i].to]+e[i].w);size[x]+=size[e[i].to];}
}
int main()
{freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);n=read();for(int i=1;i<n;++i)ins(read(),read());dep[1]=1;Dfs(1,0);m=read();memset(head,0,sizeof(head));for(int i=1;i<=MD;++i)for(int j=1;j<=n;++j)Fa[i][j]=Fa[i-1][Fa[i-1][j]];for(int i=1;i<=m;++i){K=read();cnt=top=num=0;ans1=ans2=0;ans3=INF;for(int j=1;j<=K;++j) b[a[j]=read()]=1;sort(a+1,a+K+1,cmp);Build();Solve(a[1],0);printf("%lld %d %d\n",ans1,ans3,ans2);for(int j=1;j<=num;++j) head[B[j]]=b[B[j]]=mx[B[j]]=size[B[j]]=0;}return 0;
}

B.有n个石子,两个人轮流行动,每个人可以投硬币,如果是正面就拿一个石子,并且投出自己想要的的概率分别是p和q,问先手拿到最后一个石子的概率。

T<=100,n<=10^8 0.5<=p,q<1

f[i]表示剩i个石子,先手的胜率,g[i]表示剩i个石子,后手的胜率。

假如f[i-1]>g[i-1],那么先手显然不会去拿,后手也不会,反之两者都会,列出式子。

f[i]=p*g[i-1]+(1-p)*g[i],g[i]=q*f[i-1]+(1-q)*f[i]

化简即可。另一种情况就是把p=1-p,q=1-q;

另外发现这个概率很快就不变了,所以算到10^5就够了。

#include<iostream>
#include<cstdio>
using namespace std;
int T,n;double p,q;
double f[100005],g[100005];
int main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);for(cin>>T;T--;){scanf("%d%lf%lf",&n,&p,&q);n=min(n,100000);f[0]=0;g[0]=1;for(int i=1;i<=n;++i){if(f[i-1]<g[i-1]) p=1-p,q=1-q;f[i]=((1-q)*p*f[i-1]+(1-p)*g[i-1])/(1-p*q);g[i]=((1-p)*q*g[i-1]+(1-q)*f[i-1])/(1-p*q);if(f[i-1]<g[i-1]) p=1-p,q=1-q;}printf("%.7lf\n",f[n]);}return 0;
}

C题数论,骗到60分,先挖个坑。

转载于:.html

更多推荐

[2017/6/6]福建四校联考

本文发布于:2024-03-23 21:32:17,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1743078.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:福建   联考   四校

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!