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;
}
/*

*/

#百度笔试##百度##笔试题目#