21.6.23 test

省选模拟赛

今天考的是一套题目背景和描述会被【数据删除】的模拟赛。

犯了几个傻逼错。

\(T1\) 把两种情况的概率看反了，写的暴力。\(35->5\) pts.

\(T2\) 以为想到了正解，写了一堆树剖线段树甚至还有树上差分，码农一样码了一半发现比暴力的复杂度只有玄学优化了一些，不过可以过两个部分分。\(40\) pts.

\(T3\) 直接输出“infinity”就有20分，但是我稍微挣扎了一下，写了个if else，挣扎失败后 if 没删干净就交了/ll。CE \(20->0\) pts.

省选难度于是要尝试赛后AK。

艹，头一次发现我这么菜，看了一个下午加一个晚上，愣是没改完T1。

update on 21.6.24

T1T2改完了。

暂时不想写题解，放下代码。

两道题分别是T1和T2

\(T1\)：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define ld long double

ll n;ld p;

ld ans1(){

	ll t=1;

	ld ans=0;

	while(t<=n){

		double k=double(n/t/2*t)/n+double(max(0LL,n%(t*2)-t))/n;

		ans+=2*k*(1-k)*t;

		t*=2;

	}

	return ans;

}

ll a[101],an,k;

ld ans3(ll m,int an){

	if(an==1){

		if(a[an]==0)return 1.0/n;

		else return 2.0/n;

	}

	ll t=pow(2,an-1);

	ld ans=0;

	if(a[an]==1){

		ans+=double(t)/n*(m+t);

		ans+=ans3(m/2,an-1);

	}

	else{

		ans+=double(t)/n*t;

		ans+=2*ans3(m/2,an-1);

	}

	return ans;

}

ld ans2(ll m){

	if(m==0)return 0;

	memset(a,0,sizeof(a));

	an=0,k=m;

	while(k){

		if(k&1)a[++an]=1;

		else a[++an]=0;

		k>>=1;

	}

	ll t=pow(2,an-1);

	ld ans=double((t*2-1))/n*(m-t+1)+double(t)/n*t;

	if(an>1) ans+=ans3(t-1,an-1);

	return ans;

}

signed main(){

	scanf("%lld%Lf",&n,&p);

	printf("%.6Lf",p*ans2(n-1)+(1-p)*ans1());

    return 0;

}

\(T2\)：

#include<bits/stdc++.h>

using namespace std;

#define in read()

#define int long long

const int N=300005;

inline int read(){

	int p=0,f=1;

	char c=getchar();

	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}

	return p*f;

}

struct edge{

	int v,next;

}e[2*N];

int head[N],en;

void insert(int u,int v){

	e[++en].v=v;

	e[en].next=head[u];

	head[u]=en;

}

int n,q;

int fa[N],deep[N],size[N],dfn[N],df;

void dfs(int p,int f){

	size[p]=1;fa[p]=f;deep[p]=deep[f]+1;dfn[p]=++df;

	for(int i=head[p];i;i=e[i].next){

		int v=e[i].v;

		if(v==f)continue;

		dfs(v,p);

		size[p]+=size[v];

	}

}

//segment_tree---------------

#define sum(x) st[x].sum

#define ls(x) st[x].ls

#define rs(x) st[x].rs

int rt[N],tot=1;

struct node{

	int sum,ls,rs;

}st[N<<6];

int built(int p,int l,int r){

	if(l==r)return p;

	int mid=(l+r)>>1;

	ls(p)=built(++tot,l,mid);

	rs(p)=built(++tot,mid+1,r);

	return p;

}

void cover(int p,int pre){

	sum(p)=sum(pre);

	ls(p)=ls(pre);

	rs(p)=rs(pre);

}

void newroot(int x){

	rt[x]=++tot;

	cover(rt[x],rt[x-1]);

}

void modify(int &now,int pre,int l,int r,int pos,int d){

	now=++tot;

	cover(now,pre);

	sum(now)+=d;

	if(l==r&&l==pos)return ;

	int mid=(l+r)>>1;

	if(pos<=mid)modify(ls(now),ls(now),l,mid,pos,d);

	else modify(rs(now),rs(now),mid+1,r,pos,d);

}

int query(int now,int l,int r,int ql,int qr){

	if(l>=ql&&r<=qr) return sum(now);

	int mid=(l+r)>>1,res=0;

	if(ql<=mid)res+=query(ls(now),l,mid,ql,qr);

	if(qr>mid)res+=query(rs(now),mid+1,r,ql,qr);

	return res;

}

//---------------------------

signed main(){

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

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

	n=in,q=in;rt[0]=1;

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

		int u=in,v=in;

		insert(u,v);

		insert(v,u);

	}

	dfs(1,0);

	built(1,1,n);

	newroot(1);

	queue<int> qu;qu.push(1);

	int tem=0,temp=1,last=1;df=1;

	while(!qu.empty()){

		int p=qu.front();qu.pop();

		modify(rt[df],rt[df],1,n,dfn[p],size[p]-1);

		for(int i=head[p];i;i=e[i].next){

			int v=e[i].v;

			if(v==fa[p])continue;

			qu.push(v);

			last++;

		}

		tem++;

		if(tem==temp){

			df++;

			temp=last;

			newroot(df);

		}

	}

	df--;

	for(int i=1;i<=q;i++){

		int p=in,k=in,ans=0;

		ans+=min(deep[p]-1,k)*(size[p]-1);

		int x=deep[p],y=min(deep[p]+k,df);

		if(x<=y&&size[p]-1)

			ans+=query(rt[y],1,n,dfn[p]+1,dfn[p]+size[p]-1)-query(rt[x],1,n,dfn[p]+1,dfn[p]+size[p]-1);

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

	}

    return 0;

}

巴特西

21.6.23 test

省选模拟赛

最新文章

热门文章

巴特西

21.6.23 test

省选 模拟赛

最新文章

热门文章

省选模拟赛