4.26号腾讯笔试题(AK)

虽然AK了但是不知道能不能有面试机会 O_O .

问题1

模拟队列操作

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
int q[N];
int head,tail;
int main(){
    int t;cin>>t;
    while(t--){
        int n;sc("%d",&n);
        head=1,tail=0;
        char s[10];
        while(n--){
            sc("%s",s);
            if(s[0]=='P'&&s[1]=='U'){
                int x;sc("%d",&x);
                q[++tail]=x;
            }else if(s[0]=='T'){
                if(tail>=head){
                    printf("%d\n",q[head]);
                }else pr("-1\n");
            }else if(s[0]=='P'&&s[1]=='O'){
                if(tail>=head){
                    head++;
                }else pr("-1\n");
            }
            else if(s[0]=='S'){
                pr("%d\n",tail-head+1);
            }else{
                head=1,tail=0;
            }
        }
    }
}

问题二

更新下原题链接
平面上有2*n个点，n个点属于A集合，n个点属于B集合，
各从俩集合中选择一个数，求最近点对。

平面最近点对，只要记录在哪个集合就ok。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}

const ll INF=1e11;
int n;
int flag[N];
int z[N];
struct Po{
    double x,y;
    int id;
}AB[N];
bool cmp(Po a,Po b){
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
bool cmps(const int &a,const int &b){
    return AB[a].y<AB[b].y;
}
double dis(int i,int j){
    double x=(AB[i].x-AB[j].x)*(AB[i].x-AB[j].x);
    double y=(AB[i].y-AB[j].y)*(AB[i].y-AB[j].y);
    return sqrt(x+y);
}
double merge(int l,int r){
    double d=INF;
    if(l==r)return d;
    if(l+1==r){
        if(AB[l].id==AB[r].id)return d;
        return dis(l,r);
    }
    int mid=l+r>>1;
    double d1=merge(l,mid);
    double d2=merge(mid+1,r);
    d=min(d1,d2);
    int i,j,k=0;
    for(i=l;i<=r;i++){
        if(fabs(AB[mid].x-AB[i].x)<=d){
            flag[i]=AB[i].id;
            z[k++]=i;
        }
    }
    sort(z,z+k,cmps);
    for(i=0;i<k;i++){
        for(j=i+1;j<k&&AB[z[j]].y-AB[z[i]].y<d;j++){
            if(flag[z[i]]!=flag[z[j]]){
                double d3=dis(z[i],z[j]);
                if(d>d3)d=d3;
            }
        }
    }
    return d;
}
void solve(){
    sc("%d",&n);
    for(int i=0;i<n;i++){
        sc("%lf%lf",&AB[i].x,&AB[i].y);
        AB[i].id=1;
    }
    for(int i=n;i<2*n;i++){
        sc("%lf%lf",&AB[i].x,&AB[i].y);
        AB[i].id=2;
    }
    n<<=1;
    sort(AB,AB+n,cmp);
    pr("%.3f\n",merge(0,n-1));
}


int main(){
    int t;I(t); while(t--)solve();
}

问题三

更新下原题链接
这是一道很难的题，看别人居然冒泡随便搞搞就过了，腾讯的出题组造数据太水了吧。

有n张卡牌， 正面时 ai ,反面时 bi ,每次可以任意选择相邻俩张卡牌，交换位置，
然后并且翻转，并且使得 a不减 ，求最小操作次数。
状压dp , 不过要预处理下 ，将偶数下标的 a_i, b_i ,swap 。
跑子集dp ，我的更新是 dp[S][k]=min(dp[S][k],dp[S-k][j]+合法的) k属于 S集合
有点不好描述啊

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
int n,a[20],b[20];
int dp[1<<20][20];
const int INF=1e9;
int main(){
    I(n);
    for(int i=0;i<n;i++)sc("%d",&a[i]);
    for(int i=0;i<n;i++)sc("%d",&b[i]);
    for(int i=1;i<n;i+=2)swap(a[i],b[i]);
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            dp[i][j]=INF;
        }
    }
    for(int i=0;i<n;i++)dp[1<<i][i]=0;
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(dp[i][j]==INF)continue;
            for(int k=0;k<n;k++){
                if(i>>k&1)continue;
                int x=__builtin_popcount(i)&1;
                if(x){
                    if(b[k]<a[j])continue;
                }else{
                    if(a[k]<b[j])continue;
                }
                int ans=0;
                for(int l=k+1;l<n;l++){
                    if(i>>l&1)ans++;
                }
                dp[i|1<<k][k]=min(dp[i|1<<k][k],dp[i][j]+ans);
            }
        }
    }
    int ans=INF;
    for(int i=0;i<n;i++)ans=min(ans,dp[(1<<n)-1][i]);
    if(ans==INF)O(-1);
    else O(ans);
}

问题四

不知道要表达什么

int main(){
    int n;sc("%d",&n);
    deque<int>v;
    char s[10];
    while(n--){
        sc("%s",s);
        if(s[0]=='a'){
            int x;sc("%d",&x);
            v.push_back(x);
        }else if(s[1]=='e'){
            pr("%d\n",v[0]);
        }else{
            v.pop_front();
        }
    }
}

问题五

一颗无限深的满二叉树，标号1,2,3,....
求x的祖先(深度必须是k)。

int main(){
    int Q;I(Q);
    while(Q--){
        ll x;int k;
        sc("%lld%d",&x,&k);
        int d_x=0;ll y=x;
        while(y)y>>=1,d_x++;
        if(d_x<=k){
            pr("-1\n");continue;
        }
         while(d_x!=k){
            x>>=1;
            d_x--;
        }
        pr("%lld\n",x);
    }
}