AT_zone2021 部分

前言

教练出了个集训赛，就是 AT_zone2021 vp，赛时没切 E，赛后也不想做 E，所以不写。

ZONe_a

用 substr 拆出来，然后检查是不是 ZONe。

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int ans=0;
	for(int i=0;i<s.size()-4;i++) if(s.substr(i,4)=="ZONe") ans++;
	cout<<ans;
	return 0;
}

ZONe_b

每个障碍物顶点和 UFO 可以连出直线，将所有障碍物的直线与 \(y\) 轴交点取 \(\max\)，然后输出。

Code

#include <bits/stdc++.h>
using namespace std;
double maxn=-1,maxd=-1;
int main()
{
	double n,d,h,ans=0;
	cin>>n>>d>>h;
	for(int i=1;i<=n;i++)
	{
		double a,b;
		cin>>a>>b;
		ans=max(ans,h-(h-b)/(d-a)*d);
	}
	cout<<fixed<<setprecision(3)<<ans;
	return 0;
}

ZONe_c

比 D 难。又是最大又是最小，想到二分，令当前二分假设的答案为 \(x\)。首先每个人有五个值，要么开五维数组（太麻烦，我没写），要么考虑离散为二进制数，这个二进制数第 \(j\) 位是 \(1\) 就表示这个人的第 \(j\) 个值达到了 \(x\)。只要存在三个人这个二进制数按位或为 \((11111)_2=31\)，就说明 \(x\) 可行。但是注意到 \(O(n^3)\) 不能通过，我们先枚举前两人，即两人二进制数异或为 \(now\)，则我们需要证明存在或证明不存在子集为 \(31\oplus now\) 的数，所以开 \(mp\) 数组，\(mp_i\) 表示 \(i\) 是不是某个人二进制数的子集，枚举两位后查 \(mp_{31\oplus now}\) 即可。

Code

#include <bits/stdc++.h>
using namespace std;
int sta[3010],v[3010][6],mp[128],n;
int check(int mid)
{
	memset(mp,0,sizeof mp);
	memset(sta,0,sizeof sta);
	mp[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<5;j++)
		if(v[i][j]>=mid) sta[i]|=(1<<j);
		for(int j=sta[i];j;j=((j-1)&sta[i])) mp[j]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		if(mp[31^(sta[i]|sta[j])])
		{
			return 1;
		}
	}
	return 0;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=0;j<5;j++)
	cin>>v[i][j];
	int l=1,r=1e9,mid,ans;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	} 
	cout<<ans;
	return 0;
}

ZONe_d

水。两端的维护，想到 deque。开一个 \(flag\)，表示序列是否被翻转了。对于类似消消乐的操作，只需要等到插入时检查队头或队尾（取决于 \(flag\)）元素是否与当前的一样，来判断是否要消除，最后根据 \(flag\) 决定正序或倒序输出 deque。

Code

#include <bits/stdc++.h>
using namespace std;
deque<char> t; 
int main()
{
	int flag=0;//是否被翻转 
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='R') flag^=1;
		else
		{
			if(flag)
			{
				if(!t.empty()&&s[i]==t.back()) t.pop_back();
				else t.push_back(s[i]);
			}
			else
			{
				if(!t.empty()&&s[i]==t.front()) t.pop_front();
				else t.push_front(s[i]);
			}
		}
	}
	if(flag)
	while(!t.empty())
	{
		cout<<t.front();
		t.pop_front();
	}
	else
	while(!t.empty())
	{
		cout<<t.back();
		t.pop_back();
	}
	return 0;
}

ZONe_f

贴篇自己的题解。

注意到本题与异或有关，并且涉及到关于很多个数的异或结果，想到线性基。把 \(1\sim N\) 除 \(a_i\) 之外的全部加入线性基，并且存下线性基 \(p_i\) 的“原 \(x\)”\(ori_i\)，于是如果存在线性基没有值，输出 \(-1\)，因为这代表有岛连不上。否则输出它和它最大的位数上的原 \(x\)。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1<<19;
int cnt[N],p[N],ori[N];
void insert(int x)
{
	int tp=x;
	for(int i=19;~i;i--)
	{
		if(x&(1<<i))
		{
			if(!p[i])
			{
				p[i]=x;
				ori[i]=tp;
				return;
			}
			else x^=p[i];
		}
	}
}
int check(int x)
{
	for(int i=19;~i;i--)
	{
		if(x&(1<<i))
		{
			return x^ori[i];
		}
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		cnt[x]++;
	}
	for(int i=1;i<n;i++) if(!cnt[i]) {insert(i);}
	int l;
	for(int i=19;~i;i--) if((1<<i)<=n)
	{
		l=i;
		break;
	}
	for(int i=0;i<l;i++) if(!p[i])
	{
		cout<<-1;
		return 0;
	}
	for(int i=1;i<n;i++) cout<<i<<' '<<check(i)<<endl;
	return 0;
}