模拟77 考试总结

2023-11-30 09:05:22

怎一个 惨字了得

考试经过

开场感觉状态不错，发现T1可做半小时冲完，精神状态较佳，直接开T2
先冲爆搜然后思考部分分，发现可以背包，仔细算了空间会炸，于是选择部分分打满，数据范围很可折半但没思路
T3直接爆枚出边，认为不太能全是菊花，于是愉快写完走人
T1拍200万组，T2两个部分分相互拍5万组，T3也拍了3万组
T4认为bitset分巨多，于是冲上了，认为不太能假就没拍,最后反复检查了十分钟文件
预期得分100+50+（20-100）+70，结果70+30+45+40=185
原以为只要#define int long long就万事大吉了，殊不知1竟然默认是int。。。
T1我1左移60位完美挂掉30，T21左移40位完美挂掉30。。。
T3交成了改之前的代码，只有45，在ftp上交的是85，只被菊花卡了三个点
T4bitset确实不能处理又并又交的，只有40但算高了
（upd：今天早上发现T1是隐藏比赛之前交的没算上，相当于爆零了emmmmm）

一定要开1ll ！

一定要查文件并备份

一定要开1ll ！

一定要查文件并备份

一定要开1ll ！

一定要查文件并备份

T1.最大或

把每一位分开考虑，如果\(l,r\)最高位不同一定最后全是1，否则往后看，判一下相等情况

#include <bits/stdc++.h>
using namespace std;
#define int long long
int bit[65];
inline int getsum(int x)
{
	int s=0;
	while(x)
	{
		s++;
		x>>=1;
	}
	return s;
}
signed main()
{
	freopen("maxor.in","r",stdin);
	freopen("maxor.out","w",stdout);
	bit[0]=1;
	for(int i=1;i<=60;i++)bit[i]=bit[i-1]*2;
	int t;cin>>t;
	while(t--)
	{		
		int l,r;scanf("%lld%lld",&l,&r);
		int ans=0;if(l==r){printf("%lld\n",l);continue;}
		int p1=getsum(l),p2=getsum(r);
		while(p1==p2)
		{
			ans+=1ll<<(p1-1);
			l-=1ll<<(p1-1),r-=1ll<<(p2-1);
			p1=getsum(l),p2=getsum(r);
		}
		ans+=bit[p2]-1;
		printf("%lld\n",ans);
	}
	return 0;
}

T2.答题

太菜想不到正解
其实就是让你求所有能构成的数中的第\(k\)大值是几
前后分别搜出来存起来，二分答案，双指针扫一遍判定即可，复杂度\(2^{n/2}\log 4e7\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector <int> s1,s2;
int a[45],n,b1[21],b2[21],tot1,tot2,ga;
double p;
inline bool check(int x)
{
	int ans=0,j=s2.size();
	for(int i=0;i<s1.size();i++)
	{	
		while(j&&s1[i]+s2[j-1]>=x)j--;
		ans+=(s2.size()-j);
	}
	if(ans>=ga)return 1;
	else return 0;
}
signed main()
{
	freopen("answer.in","r",stdin);
	freopen("answer.out","w",stdout);
	cin>>n>>p;int ss=0;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),ss+=a[i];
	for(int i=1;i<=n/2;i++)b1[++tot1]=a[i];
	for(int i=n/2+1;i<=n;i++)b2[++tot2]=a[i];
	for(int i=0;i<(1<<tot1);i++)
	{
		int sum=0;
		for(int j=1;j<=tot1;j++)
		 if((i>>(j-1))&1)sum+=b1[j];
		s1.push_back(sum);
	}
	for(int i=0;i<(1<<tot2);i++)
	{
		int sum=0;
		for(int j=1;j<=tot2;j++)
		 if((i>>(j-1))&1)sum+=b2[j];
		s2.push_back(sum);
	}
	ga=(1ll<<n)-ceil((double)(1ll<<n)*p)+1;
	sort(s1.begin(),s1.end());
	sort(s2.begin(),s2.end());
	int l=0,r=ss,ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<ans<<endl;
	return 0;
}

T3.联合权值

爆扫用bitset优化判定就能过
正解采用了无向三元环的证明与运用，由于太懒直接复制粘贴了，写的也挺清楚
模拟77 考试总结
学到的主要是找三元环方法：
1)给边定向，度数大的连向小的，度数相同标号小的连向大的
2)枚举第一个点，将所有出边标记
3)枚举第二个点的出边，如果标记是被第一个点访问就是三元环
这样保证了不重不漏，复杂度可以证明是\(n\sqrt n\)的
贴一个板子吧,P1989

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=200050;
int du[N],ans,px[N],py[N];
vector <int> p[N];int v[N];
signed main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&px[i],&py[i]);
		du[px[i]]++;du[py[i]]++;
	}
	for(int i=1;i<=m;i++)
	{
		int x=px[i],y=py[i];
		if(du[x]<du[y]||(du[x]==du[y]&&x>y))swap(x,y);
		p[x].push_back(y);		
	}
	for(int x=1;x<=n;x++)
	{
		for(int j=0;j<p[x].size();j++)v[p[x][j]]=x;
		for(int j=0;j<p[x].size();j++)
		{
			int y=p[x][j];
			for(int k=0;k<p[y].size();k++)
			{
				int z=p[y][k];
				if(v[z]==x)ans++;
			}			
		}
	}
	cout<<ans<<endl;
	return 0;
}

T4.主仆见证了 Hobo 的离别

神仙题，感觉难点应该在建模
由于每个最多被融合一次，所以可以把关系建一棵树，询问离线处理
那么一组询问合法首先要求\(x,y\)有一个是他们的LCA，这个可以dfs序判断是否子树包含
如果\(x\)是\(y\)的祖先，合法当且仅当他们路径上都是交，另一种是都是并
\(k=1\)时并交等价特判一下，我用了树上查分可以方便维护

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
const int N=500050;
struct node{
	int from,to,next,op;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y,int op)
{
	a[mm].from=x;a[mm].to=y;a[mm].op=op;
	a[mm].next=head[x];head[x]=mm++;
}
int n,m,xx[N],yy[N],cnt,tot;bool p[N];
int id[N],d[N],size[N],sum1[N],sum2[N];
void dfs(int x)
{
	id[x]=++tot;
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;d[y]=d[x]+1;
		sum1[y]=sum1[x],sum2[y]=sum2[x];
		if(a[i].op==0)sum1[y]++;
		else if(a[i].op==1)sum2[y]++;
		else sum1[y]++,sum2[y]++;
		dfs(y);size[x]+=size[y];
	}
	size[x]++;
}
signed main()
{
	freopen("friendship.in","r",stdin);
	freopen("friendship.out","w",stdout);
	n=read(),m=read();int ma=n;
	for(int i=1;i<=m;i++)
	{
		int opt=read();
		if(opt)xx[++cnt]=read(),yy[cnt]=read();
		else
		{
			int op=read(),k=read();ma++;
			if(k==1)
			{
				int x=read();p[x]=1;
				add(ma,x,2);continue;
			}
			for(int j=1;j<=k;j++)
			{
				int x=read();p[x]=1;
				add(ma,x,op);
			}
		}
	}
	int root=++ma;
	for(int i=1;i<root;i++)if(!p[i])add(root,i,2);
	d[root]=1;dfs(root);
	for(int i=1;i<=cnt;i++)
	{
		int x=xx[i],y=yy[i];bool fg=0;
		if(d[x]>d[y])swap(x,y),fg=1;
		if(id[y]<id[x]||id[x]+size[x]-1<id[y]){puts("0");continue;}
		if(fg)swap(x,y);
		assert(x==xx[i]&&y==yy[i]);
		if(d[x]<d[y])
		{
			if(sum1[y]-sum1[x]==d[y]-d[x])puts("1");
			else puts("0");
		}
		else
		{
			if(sum2[x]-sum2[y]==d[x]-d[y])puts("1");
			else puts("0");
		}
	}
	return 0;
}

考试总结

挂了分的一个好处是下次就能注意了
做的好的地方应该是该拍的都拍了，不好的就是1ll这种不注意就死的东西
算是吃一堑长一智吧，毕竟比赛之前，问题暴露的越多越好

上一篇：a^b mod q


下一篇：【模板】字符串哈希