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);
}
}#腾讯暑期实习##腾讯##笔试题目#
