前言

感觉最近太飘了，这次考试是挺好的一次打击（好像也不算是）。

犯了一个智障错误（双向边一倍数组 100pts->30pts）别的就。。

T1 最大或

解题思路

一开始我以为是一个找规律，然而在打表找规律 20min 后无果。。

然后开始考虑二进制位上的东西，画了一颗 Tire 树，发现从高位到低位相同的位我们无论如何或贡献都是一样的。。

直到第一个不同的位开始都是可以通过 \(or\) 操作成为 1 的。

然后扩展一下，我试了试左右短点在 \([1000,1000]\) 区间内的情况把询问改成 \(xor\) 也是类似的关系，只不过之前的位都是 0了。

代码也就和题目做法差了一句话 for(int i=60;i>=0;i--)if(((l>>i)&1)!=((r>>i)&1)){ans+=(1ll<<i+1)-1;break;}

code

#include <bits/stdc++.h>

#define int long long

#define ull unsigned long long

#define f() cout<<"Failed"<<endl

using namespace std;

inline int read()

{

	int x=0,f=1;char ch=getchar();

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

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

	return x*f;

}

int T,l,r,pre,ans;

void solve()

{

	l=read(); r=read(); ans=0;

	for(int i=60;i>=0;i--)

		if(((l>>i)&1)==((r>>i)&1)) ans=ans+(l&(1ll<<i));

		else{ans+=(1ll<<i+1)-1;break;}

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

}

signed main()

{

	freopen("maxor.in","r",stdin); freopen("maxor.out","w",stdout);

	T=read(); while(T--) solve();

	return 0;

}

T2 答题

解题思路

个人感觉这个题的思路较于这个题目本身要重要。

本道题的实质其实是求用所给的 \(n\) 个数组成的 \(2^n\) 个数中的第 \(\operatorname{ceil}(2^n\times p)\) 大值。

直接枚举显然不能通过，所以我们需要进行折半枚举（\(meet\;in\;the\;middle\)），即枚举求出前 \(\frac{n}{2}\) 个数可以组成的所有值，以及后 \(\frac{n}{2}\) 个数可以组成的所有值。

二分需要求的最后答案是多少。

对于每一个二分到的值，我们要求出所有组合中小于它的数字个数。

双指针扫一遍即可。

code

#include <bits/stdc++.h>

#define int long long

#define f() cout<<"Failed"<<endl

using namespace std;

inline int read()

{

	int x=0,f=1;char ch=getchar();

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

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

	return x*f;

}

const int N=3e6+10;

int n,l,r,ans,cnt,t1,t2,s[N],a[N],b[N];

double p,temp;

bool check(int x)

{

	int pos=t2;double sum=0;

	for(int i=1;i<=t1&&a[i]<=x;i++){while(pos>=1&&a[i]+b[pos]>=x) pos--;sum+=pos;}

	return sum<=temp;

}

signed main()

{

	freopen("answer.in","r",stdin); freopen("answer.out","w",stdout);

	n=read(); cnt=n>>1; scanf("%lf",&p); temp=p*(1ll<<n);

	for(int i=1;i<=n;i++) s[i]=read(),r+=s[i];

	for(int sta=0;sta<(1ll<<cnt);sta++){t1++;for(int i=1;i<=cnt;i++)a[t1]+=((sta>>i-1)&1)*s[i];}

	for(int sta=0;sta<(1ll<<n-cnt);sta++){t2++;for(int i=1;i<=n-cnt;i++)b[t2]+=((sta>>i-1)&1)*s[i+cnt];}

	sort(a+1,a+t1+1);sort(b+1,b+t2+1);while(l<=r){int mid=(l+r)>>1;if(check(mid))l=mid+1,ans=mid;else r=mid-1;}

	printf("%lld",ans); return 0;

}

T3 联合权值?改

解题思路

正解不是特别会，但是 bitset 卡空间卡时间可以跑过。。（建边数组开两倍。。。）

思路就比较简单了，枚举每一个三元组的中转点，再枚举连边判断两者之间是否有连边。

时间复杂度 \(\mathcal{O}((n+m)m)\) 空间复杂度 \(\mathcal{O}(\frac{n^2}{32})\)

code

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define f() cout<<"Failed"<<endl

using namespace std;

inline int read()

{

	int x=0,f=1;char ch=getchar();

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

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

	return x*f;

}

const int N=3e4+10;

ll n,m,task,ans1=-1,ans2,s[N];

vector<int> v[N];

bitset<N> e[N];

void add_edge(int x,int y){v[x].push_back(y);}

signed main()

{

	freopen("link.in","r",stdin); freopen("link.out","w",stdout);

	n=read(); m=read(); task=read();

	for(int i=1,x,y;i<=m;i++)

		x=read(),y=read(),e[x][y]=e[y][x]=true,

		add_edge(x,y),add_edge(y,x);

	for(int i=1;i<=n;i++) s[i]=read();

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

		for(int j=0;j<v[i].size();j++)

		{

			int x=v[i][j];

			for(int k=j+1;k<v[i].size();k++)

			{

				int y=v[i][k];

				if(e[x][y]) continue;

				ans1=max(ans1,1ll*s[x]*s[y]);

				ans2+=1ll*s[x]*s[y];

			}

		}

	if(task!=2) printf("%lld\n",ans1); else printf("0\n");

	if(task!=1) printf("%lld",ans2*2); else printf("0");

	return 0;

}

主仆见证了 Hobo 的离别

解题思路

发现把新建的点与之前点的关系当做连边的话，其实就形成了一棵树（毕竟题目保证了每个节点最多被融合一次）

那么我们考虑如何维护，可以对于不同的关系视为不同的边权。

对于询问的 \(X,Y\) 之间一定存在着祖先关系，因此可以利用 DFS 序进行判断。

如果 \(X\) 是 \(Y\) 的祖先那么着一路的关系都只能是交。

同样的，如果 \(X\) 是 \(Y\) 的祖先那么着一路的关系都只能是并。

并茶几维护即可，注意特判 \(K=1\) 也就是两个完全相同的点的情况。

code

#include <bits/stdc++.h>

using namespace std;

inline int read()

{

	int x=0,f=1;char ch=getchar();

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

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

	return x*f;

}

const int N=5e5+10;

int n,m,cnt,lab,tim,dfn[N],siz[N],du[N];

int tot=1,head[N],ver[N<<1],nxt[N<<1],edge[N<<1];

pair<int,int> q[N];

struct DSU

{

	int fa[N];

	void init(){for(int i=1;i<=lab;i++)fa[i]=i;}

	int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);}

	void merge(int x,int y){if(find(x)!=find(y)) fa[find(x)]=find(y);}

}T0,T1;//0->&,1->|

void add_edge(int x,int y,int val)

{

	ver[++tot]=y; edge[tot]=val; du[y]++;

	nxt[tot]=head[x]; head[x]=tot;

}

void dfs(int x)

{

	dfn[x]=++tim; siz[x]=1;

	for(int i=head[x];i;i=nxt[i])

	{

		int to=ver[i],val=edge[i]; dfs(to); siz[x]+=siz[to];

		if(val!=1) T0.merge(x,to); if(val) T1.merge(x,to);

	}

}

bool judge(int x,int y){return dfn[x]<=dfn[y]&&dfn[x]+siz[x]-1>=dfn[y];}

void solve(int x,int y)

{

	if(judge(x,y)&&T0.find(x)==T0.find(y)) return printf("1\n"),void();

	else if(judge(y,x)&&T1.find(x)==T1.find(y)) return printf("1\n"),void();

	else printf("0\n");

}

signed main()

{

	freopen("friendship.in","r",stdin); freopen("friendship.out","w",stdout);

	lab=n=read(); m=read();

	for(int i=1,opt,link,t,x,y;i<=m;i++)

	{

		opt=read();x=y=t=link=0;

		if(!opt)

		{

			link=read();t=read();lab++; if(t==1) link=2;

			for(int j=1;j<=t;j++) x=read(),add_edge(lab,x,link);

		}

		else{x=read();y=read();q[++cnt]=make_pair(x,y);}

	}

	T0.init(); T1.init(); for(int i=1;i<=lab;i++) if(!du[i]) dfs(i);

	for(int i=1;i<=cnt;i++) solve(q[i].first,q[i].second);

	return 0;

}

巴特西

NOIP模拟77

前言

T1 最大或

解题思路

code

T2 答题

解题思路

code

T3 联合权值?改

解题思路

code

主仆见证了 Hobo 的离别

解题思路

code

最新文章

热门文章