20240503比赛总结

T1 [CF1279C]Stack of Presents

https://gxyzoj.com/d/hzoj/p/3686

数据出锅了，100->40

按题意模拟即可，可以发现，最优情况下，一定是将取出的数按后面的拿的顺序排序，O(1)取出，而在取之前未排序的，则需要花2k+1的时间排序并取出

代码：

#include<cstdio>
#define ll long long
using namespace std;
int T,n,m,a[100005],b[100005],vis[100005];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			vis[a[i]]=i;
		}
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&b[i]);
			b[i]=vis[b[i]];
		}
		ll ans=0;
		int id=0;
		for(int i=1;i<=m;i++)
		{
			if(b[i]<id) ans++;
			else
			{
				ans=ans+1ll*2*(b[i]-i)+1;
				id=b[i];
			}
		//	printf("%d\n",ans);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

T2 [luogu5522]棠梨煎雪

https://gxyzoj.com/d/hzoj/p/3667

树状数组+卡常

没事千万别写线段树！！！

可以发现，如果同一位上既有0，又有1，则这个区间必然无解，而如果所有的都是？,则这一位有两种情况，乘法原理求解即可

如何判断0与1的情况？

直接用60个树状数组，记录每一位0和1的情况，然后求和即可

代码：

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
int n,m,q;
string s[100010];
int lowbit(int x)
{
	return x & (-x);
}
struct tree{
	int a[100010];
	void add(int x,int val)
	{
		while(x<=m)
		{
			a[x]+=val;
			x+=lowbit(x);
		}
	}
	int query(int x)
	{
		int res=0;
		while(x)
		{
			res+=a[x];
			x-=lowbit(x);
		}
		return res;
	}
}tr[65];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
		cin>>s[i];
		for(int j=0;j<n;j++)
		{
			int x=s[i][j]-'0';
			if(s[i][j]!='?')
			tr[j*2+x].add(i,1);
		}
	}
	int ans=0;
	while(q--)
	{
		int opt;
		cin>>opt;
		if(opt==0)
		{
			int l,r;
			cin>>l>>r;
			int sum=1;
			for(int i=0;i<n;i++)
			{
				int x=tr[i*2].query(r)-tr[i*2].query(l-1);
				int y=tr[i*2+1].query(r)-tr[i*2+1].query(l-1);
				if(x!=0&&y!=0)
				{
					sum=0;
					break;
				}
				if(x==0&&y==0) sum<<=1;
			}
			ans^=sum;
		//	cout<<sum<<"\n";
		}
		else
		{
			int x;
			string st;
			cin>>x>>st;
			for(int i=0;i<n;i++)
			{
				int tmp=s[x][i]-'0';
				if(s[x][i]!='?') 
				tr[i*2+tmp].add(x,-1);
				tmp=st[i]-'0';
				if(st[i]!='?')
				tr[i*2+tmp].add(x,1);
			}
			s[x]=st;
		}
	}
	cout<<ans;
	return 0;
}

T3 [luogu1174]打砖块

https://gxyzoj.com/d/hzoj/p/3685