Removals Game
题目
爱丽丝得到了[1，2，...，n]的置换al，a2，...，a，鲍勃得到了[1，2...，n]，的另一个置换b1，b2，...
在每个转折中，下列事件按顺序发生:
爱丽丝选择数组中的第一个或最后一个元素，并从数组中移除它;
鲍勃选择数组中的第一个或最后一个元素，并将它从数组中移除。游戏继续n-1轮，之后两个数组都将有一个完全剩余的元素:a数组中的x，b数组中的y。如果x=y，鲍勃赢，否则，爱丽丝赢。如果两个队员都发挥最佳，找出哪一个队员会赢
输入
每个测试包含多个测试用例，第一行包含测试用例数t (1<1<104)，测试用例的描述如下。
每个测试用例的第一行包含一个单整数n (1<n<3·105)。下一行包含n个整数al，a2，··，an (1<ai<n，所有a!都是不同的) -Alice的排列。下一行包含n个整数b1，b2，...，bn (1bi<n，所有b&都是不同的)--Bob的置换保证所有n的总和不超过3·105。
输出
对于每个测试案例，打印单行与获胜者的名字，假设两个队员发挥最佳。如果爱丽丝获胜，打印爱丽丝，否则，打印鲍勃。
做法
赛时找不到规律，直接模拟了。A要想赢的话，就得拿掉B还有的值，因为A不想和B一样。B要想赢的话，就要拿掉A没有的值，因为B想和A一样。A先拿的话，他要选择下一步B拿不到的值。然后模拟就行。
#include<bits/stdc++.h>
using namespace std;
int t,n;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
vector<int> a(n),b(n);
unordered_map<int,int> mpa,mpb;//不能用map，会超时
for(int i=0;i<n;i++) scanf("%d",&a[i]),mpa[a[i]]++;
for(int i=0;i<n;i++) scanf("%d",&b[i]),mpb[b[i]]++;
if(n<=2){
cout<<"Bob"<<endl;
continue;
}
int al=0,ar=n-1,bl=0,br=n-1;
for(int i=0;i<n-1;i++){
if(i==0){//A先要选下一步B拿不到的值
if(a[0]!=b[0]&&a[0]!=b[n-1]) {
mpa[a[0]]--;
al++;
}
else if(a[n-1]!=b[0]&&a[n-1]!=b[n-1]){
mpa[a[n-1]]--;
ar--;
}
else{//没有下一步B拿不到的值
mpa[a[0]]--;
al++;
}
}
else{
if(mpb[a[al]]){
mpa[a[al]]--;
al++;
}
else if(mpb[a[ar]]){
mpa[a[ar]]--;
ar--;
}
else{
mpa[a[al]]--;
al++;
}
}
if(mpa[b[bl]]==0){
mpb[b[bl]]--;
bl++;
}
else if(mpa[b[br]]==0){
mpb[b[br]]--;
br--;
}
else{
mpb[b[bl]]--;
bl++;
}
}
if(b[bl]==a[al]) cout<<"Bob"<<endl;
else cout<<"Alice"<<endl;
}
}wa的原因
我起初使用了erase来模拟数字被拿掉的过程，后来超时了，就改为al，ar，bl，br模拟了。然后用map也会超时，要用unordered_map
Black Circles
题目
二维平面上有n个圆，第i个圆的中心为 (xi，y;)，初始时，所有圆的半径都是0。
圆的半径以每秒1单位的速度增加。
你现在位于(x，y)，你的目标是到达(x，y而不碰到任何园的园周(包括到达(X，;的那一刻)。你可以朝任方向移动。但是，你的速度限制在每秒1个单位。
请确定这是否可能。
做法
这题就是算距离。然后比较。
#include<bits/stdc++.h>
using namespace std;
int t,n,m,k;
long long x[100010],y[100010];
long long sx,sy,tx,ty;
const double eps=1e-10;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&x[i],&y[i]);
}
scanf("%lld%lld%lld%lld",&sx,&sy,&tx,&ty);
long long dis=(sx-tx)*(sx-tx)+(sy-ty)*(sy-ty);
int sign=0;
for(int i=1;i<=n;i++){
long long dis2=(x[i]-tx)*(x[i]-tx)+(y[i]-ty)*(y[i]-ty);
if(dis2-dis<=0) {
sign=1;
break;
}
}
if(sign) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
}wa的原因
我赛时算距离用double了，然后没有去掉开方，然后精度问题不会处理……
标签：Circles,...,Removals,map,int,scanf,cf,爱丽丝,数组 From： https://blog.csdn.net/2301_80718054/article/details/141127317