noip模拟77

2021-10-16

考试总结:这次考试,题目较为简单,本来我觉得能A掉一个,但是不知道为啥A了两个。成绩还是可以的。
首先是阅读题面,然后按顺序开题,T1一看就有思路,首先明确一个性质,或运算是一种不进位加法,那么根据这个性质我们很容易得出取到最优值的策略,就是从高到低位贪心地填补空位。
T2,数据范围较小,当时我想到了折半搜索,但是就是没有想到利用二分求排名为\(k\)的数。
T3,刚开始我打了个暴力,跑最短路,但是后来我又想了想打了一个更简洁的算法,结果竟然A了,我把暴力交上去得了0分,原来是暴力假了。。
T4 没什么时间想了,就打了个暴力,想着用\(bitset\)水过70,但是\(bitset\)时间复杂度是\(O(n)\)的,不是\(O(1)\)的。而且这样做不太有正确性。
总结:1.不论题目难易,首先拿到暴力分,可以保住心态
2.可以在暴力的基础上进行优化和改进,也许就能想出正解
3.合理安排时间,最后要检查文件格式,输入输出

T1 最大或

思路:因为或运算是一种不进位加法,那么根据这个性质我们很容易得出取到最优值的策略,就是从高到低位贪心地填补空位。
一些细节不再赘述,代码如下:

AC_code

#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=510;
int t,l,r,ans,w1,w2,cnt;
int cun[80],jw[80];
ii read()
{
	int x=0;char ch=getchar();bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
ii lowbit(int x) {return x&(-x);}
signed main()
{
	freopen("maxor.in","r",stdin);
	freopen("maxor.out","w",stdout);
	cun[1]=1;
	for(re i=2;i<=59;i++) cun[i]=cun[i-1]+(1ll<<1ll*(i-1));
	t=read();
	while(t--)
	{
		l=read(),r=read();
		if(l==r) {printf("%lld\n",l);continue;}
		ans=0;
		w1=w2=0,cnt=0;
		int x=l,y=r,now=0,my=0;
		for(re i=1;i<=60;i++) jw[i]=0;
		while(x) w1++,x>>=1;
		while(y) w2++,y>>=1;
		y=r;
		while(y)
		{
			x=lowbit(y);
			jw[++cnt]=(int)log2(x);
			y-=x;
		}
		if(cun[w2-1]>=l)
			printf("%lld\n",cun[w2-1]|r);
		else
		{
			while(cnt>1)
			{
				my+=(1ll<<jw[cnt]);
				now=max(jw[cnt-1],1ll);
				cnt--;
				now=(1ll<<now)-1+my;
				if(now>=l) break;
			}
			printf("%lld\n",max(r|now,r|l));
		}
	}
	return 0;
}


T2 答题

思路:因为\(2^20\)是可接受的,所以考虑折半搜索。
image
代码如下:

AC_code

#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=50;
const int M=2e6+10;
int n,s1,s2,cnt_1,cnt_2;
double p;
int a[N];
int c1[M],c2[M];
bool vis[N];
ii read()
{
	int x=0;char ch=getchar();bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar(); 
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
iv dfs_1(int st)
{
	if(st>(n/2))
	{
		int ans=0;
		for(re i=1;i<=(n/2);i++) if(vis[i]) ans+=a[i];
		c1[++cnt_1]=ans;
		return; 	
	}
	vis[st]=1,dfs_1(st+1);
	vis[st]=0,dfs_1(st+1);
}
iv dfs_2(int st)
{
	if(st>n)
	{
		int ans=0;
		for(re i=s2;i<=n;i++) if(vis[i]) ans+=a[i];
		c2[++cnt_2]=ans;
		return;
	}
	vis[st]=1,dfs_2(st+1);
	vis[st]=0,dfs_2(st+1);
}
signed main()
{
	freopen("answer.in","r",stdin),freopen("answer.out","w",stdout);
	n=read();
	cin>>p;
	for(re i=1;i<=n;i++) a[i]=read();
	s1=1,s2=(n/2)+1;
	dfs_1(s1);
	for(re i=1;i<=n;i++) vis[i]=0;
	dfs_2(s2);
	sort(c1+1,c1+cnt_1+1),sort(c2+1,c2+cnt_2+1);
	double pos=p*(double) (1ll<<n);
	int now=(1ll<<n)-ceil(pos)+1;
	int L=0,R=c1[cnt_1]+c2[cnt_2],d=0,out;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		int t2=cnt_2;
		d=0;
		for(re i=1;i<=cnt_1;i++)
		{
			while(c1[i]+c2[t2]>=mid and t2) --t2;
			d+=cnt_2-t2;
		}
		if(d>=now) L=mid+1,out=mid;
		else R=mid-1;
	}
	printf("%lld\n",out);
	return 0;
}


T3 联合权值?改

思路:计算以每个点为中转点的答案,进行累加,更新最大值即可。可以用\(vector\)存储,用\(bitset\)判断连边
代码如下:

AC_code

#include<bits/stdc++.h>
#define ll long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=3e4+10;
const int M=6e4+10;
const int INF=1e8;
int n,m,t,tot;
bitset<30010> BS[30010];
vector<int> v[30010];
ll maxx,sum;
ll w[N];
ii read()
{
	int x=0;char ch=getchar();bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
signed main()
{
	freopen("link.in","r",stdin),freopen("link.out","w",stdout);
	n=read(),m=read(),t=read();
	int x,y;
	for(re i=1;i<=m;i++)
	{
		x=read(),y=read();
		BS[x][y]=1,BS[y][x]=1;
		v[x].push_back(y),v[y].push_back(x);		
	}
	for(re i=1;i<=n;i++) w[i]=read();
	for(re i=1;i<=n;i++)
	{
		for(re j=0;j<v[i].size();j++)
		{
			for(re k=j+1;k<v[i].size();k++)
			{
				if(!BS[v[i][j]][v[i][k]])
				{
					maxx=max(maxx,w[v[i][j]]*w[v[i][k]]);
					sum+=w[v[i][j]]*w[v[i][k]];
				}
			}
		}
	}
	sum=sum*2ll;
	if(t==1)
	{
		if(maxx) printf("%lld\n0",maxx);
		else printf("-1\n0");
	}
	else if(t==2) printf("0\n%lld\n",sum);
	else
	{
		if(maxx) printf("%lld\n%lld\n",maxx,sum);
		else printf("-1\n0");
	}
	return 0;
}

T4 主仆见证了 Hobo 的离别

image
代码如下:

AC_code

#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=5e5+10;
int n,m,cnt,timi,tot;
struct node
{
	int x,y;
}cun[N];
int to[N<<1],next[N<<1],head[N];
int fa[N],size[N],son[N],top[N],deep[N];
int B[N],J[N],st[N],be[N];
bool vis[N],in[N];
ii read()
{
	int x=0;char ch=getchar();bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
iv add(int x,int y)
{
	to[++tot]=y;
	next[tot]=head[x];
	head[x]=tot;
}
ii get_B(int x) {return B[x]==x?x:B[x]=get_B(B[x]);}
ii get_J(int x) {return J[x]==x?x:J[x]=get_J(J[x]);}
iv dfs(int st,int f,int g)
{
	vis[st]=1;
	be[st]=g;
	fa[st]=f;
	size[st]=1;
	deep[st]=deep[f]+1;
	for(re i=head[st];i;i=next[i])
	{
		int p=to[i];
		if(vis[p]) continue;
		dfs(p,st,g);
		size[st]+=size[p];
		son[st]=(size[son[st]]>size[p])?son[st]:p;
	}
}
iv dfs2(int st,int t)
{
	top[st]=t;
	if(!son[st]) return;
	dfs2(son[st],t);
	for(re i=head[st];i;i=next[i])
	{
		int p=to[i];
		if(p==fa[st] or p==son[st]) continue;
		dfs2(p,p);
	}
}
ii get_lca(int x,int y)
{
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(deep[x]<deep[y]) swap(x,y),swap(fx,fy);
		x=fa[fx],fx=top[x];
	}
	return deep[x]<deep[y]?x:y;
}
signed main()
{
	freopen("friendship.in","r",stdin),freopen("friendship.out","w",stdout);
	n=read(),m=read();
	for(re i=1;i<=500000;i++) B[i]=J[i]=i;
	int opt,k,x;
	timi=n;
	for(re i=1;i<=m;i++)
	{
		opt=read();
		if(opt==0)
		{
			opt=read(),k=read();
			++timi;
			if(opt==1)
			{
				for(re j=1;j<=k;j++)
				{
					x=read();
					add(timi,x);
					in[x]=1;
					int fx=get_B(x);
					B[fx]=timi;
					if(k==1) J[get_J(x)]=timi;
				}			
			}
			else
			{
				for(re j=1;j<=k;j++)
				{
					x=read();
					add(timi,x);
					in[x]=1;
					int fx=get_J(x);
					J[fx]=timi;
					if(k==1) B[get_B(x)]=timi;
				}	
			}
		}
		else
			cun[++cnt]=(node){read(),read()};
	}
	for(re i=1;i<=timi;i++)
		if(!vis[i] and !in[i]) dfs(i,0,i),dfs2(i,i);
	for(re i=1;i<=cnt;i++)
	{
		int x=cun[i].x,y=cun[i].y;
		if(be[x]!=be[y] or be[x]==0 or be[y]==0) printf("0\n");
		else
		{
			int lca=get_lca(x,y);
			if(lca==x)
			{
				int fx=get_J(x),fy=get_J(y);
				(fx==fy)?printf("1\n"):printf("0\n");
			}
			else if(lca==y)
			{
				int fx=get_B(x),fy=get_B(y);
				(fx==fy)?printf("1\n"):printf("0\n");
			}
			else printf("0\n");
		}
	}
	return 0;
}