3.29 百度 笔试 三道编程题代码
（今天做了四场笔试，做到现在脑子都糊了）
第一题：
答案是取n和n-1，不知道为什么这样是对的，并感觉交了一发过了。
第二题：
如果一个数出现了三次，或者有多个出现次数大于1的，第一个人一定输
最后就形成了 0,1,2,3,4...n-1
到达这种情况必输，判断下奇偶就行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100050;
int a[maxn];
map<int,int>mp;
int main(){
int n,t;
scanf("%d",&t);
while(t--){
mp.clear();
scanf("%d",&n);
ll sum=0;
int flag=0,num=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(mp[a[i]]==0) mp[a[i]]=1;
else{
mp[a[i]]++;
if(mp[a[i]]==2) num++;
if(mp[a[i]]>2){
flag=1;
}
}
sum+=(ll)a[i];
sum-=(i-1ll);
}
if(flag||num>1){
printf("woman\n");
continue;
}
if(sum%2ll) printf("man\n");
else printf("woman\n");
}
return 0;
}
第三题：
二分答案x，然后如果两点的距离小于x，说明这两个点之间无法走通，用并查集维护一下， 最后上下边界都属于一个集合说明x大了，要取小一点，这样子二分答案。
k是6000，时间卡的有点紧，eps是关键，设打了wa，设小了T，交了好多发
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i = (int)b;i>=(int)a;i--)
#define pb push_back
#define mp map_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
const int maxn=100050;
typedef long long ll;
const double pi = acos(-1.0);//pi
const double eps=0.000003;
int dcmp(double x){
if(fabs(x)<eps) return 0;
if(x>eps) return 1;
else return -1;
}
struct node{
double x,y;
}a[maxn];
int check(int i,int j,double x){
double dis=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
if(dcmp(dis-x*2.0)<=0) return 1;
else return 0;
}
int fa[maxn];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
int fx=find(x);
int fy=find(y);
fa[fx]=fy;
}
int main(){
if(eps==0.00001) printf("1\n");
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
}
double l=0,r=min(n,m);
int t=100;
while(t--){
double x=(l+r)/2.0;
for(int i=0;i<=k+1;i++){
fa[i]=i;
}
for(int i=1;i<=k;i++){
int flag=0;
if(dcmp(1.0*m-a[i].y-x*2.0)<=0){
merge(i,0);
flag++;
}
if(dcmp(a[i].y-x*2.0)<=0){
merge(k+1,i);
flag++;
}
for(int j=i+1;j<=k;j++){
if(check(i,j,x)){
merge(i,j);
}
}
if(fa[find(0)]==fa[find(k+1)]){
break;
}
}
if(fa[find(0)]==fa[find(k+1)]) r=x;
else l=x;
if(dcmp(l-r)==0) break;
}
printf("%.4f\n",l);
return 0;
}
/*
*/
