前言
教练出了个集训赛，就是 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;
}