【在线笔试题解题报告系列】微软在线笔试之 2016微软探星夏令营在线技术笔试(时间:2016.07.17)

来源:本网整理

这好像并不难呀~至少3架。先同时起飞2架。飞到 1/4 圈时一架把剩余的油全部给另一架。这样有油的这架可以飞到 3/4。等这架飞到一半时让第3架往相反方向起飞。这样正好可以在前面那架飞到 3/4 时相遇并把油全部给它。让它完成整圈飞行。还有更少的办法吗?www.zgxue.com防采集请勿采集本网。

当然这个做得好还是不好和我无关了·(微软4月实习生在线笔试解题报告以后补),只是心血来潮,听说有就做一做,

此题应该是一个脑筋急转弯吧。应该是1、2、4,这样是两次弄断,实为三段(一段、二段、四段)。第一天,给一段 第二天,给第二段,让其还回第一段, 第三天,给第一、二段, 第四天,收回第一、

然后发现,有些难啊,比Google今年的Round 1难(在思考难度上,和代码总长度上)

微软PM(Program Manager)面试答题思路浅见》对了,跟前面 从厦门大学-哥大生物统计-美国Market Research公司offer:通过一亩三分地找内推成功求职的例子 主人公一样, 泡面也是厦门大学本科毕业的,厦大的

题目地址在下面:(你需要注册一个hihocoder账号以查看题面和提交)

1、结构化面试答题时间一般是20-25分钟, 2、结构化面试题量一般为4-5道 3、结构化面试,也称标准化面试,是相对于传统的经验型面试而言的。之所以叫结构化面试,就是评分标准结构化,评分考官一致化,

http://hihocoder.com/problemset/problem/1341

【中公解题思路】 1、表明态度:这看似是一件公交车因为让座而引起的一场小风波,但是这场小风波却应当引起我们的反思。2、论证观点:对于两位当事人的看法,我们很难去评判谁对谁错的问题,似乎谁都错了

http://hihocoder.com/problemset/problem/1342

面试城管,首先你要知道城管的主要职责是: 1、贯彻实施国家及本市有关城市管理方面的法律、法规及规章,治理和维护城市管理秩序。2、组织起草本市有关城市管理综合行政执法方面的地方性法规、

http://hihocoder.com/problemset/problem/1343

http://hihocoder.com/problemset/problem/1344

题目翻译仍然不做了,毕竟在微软工作读英语能力还是不要太烂的好。

本文地址:http://blog.csdn.net/fcxxzux/article/details/51946204

开始扯吧。

Problem A Constraint Checker

思前想后,最后还是决定用面向对象的方法了。

把一长句接在一起的限制条件,拆成多个由2个数与比较符号在一起的短限制条件,这是一个类。

操作数,仍然设计成一个类,记录数值类型(字符变量,还是立即数)以及其值,然后查询的时候立即数就马上返回,字符变量就查字符变量的表。

然后?然后就直接创建条件对象们,读进来变量赋值,一个个条件检查过去,都满足就Yes,有一个不满足就No(这简直是废话……)

#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>#include <limits.h>#include <math.h>#include <algorithm>#include <map>#include <set>#include <vector>using namespace std;typedef long long ll;set<int> appear;map<int,int> variable;char tk[15];char str[1000005];struct Token{ int val; int type; int getVal(){ if(type==0) return val; else return variable[val]; } void set(char * s){ if(s[0]<='Z' && s[0]>='A'){ val=s[0]; type=1; appear.insert(s[0]); }else{ val=0; for(int i=0;s[i];++i)val=val*10+(s[i]-'0'); type=0; } }};struct Constrain{ Token a,b; int op; bool check(){ int va=a.getVal(),vb=b.getVal(); if(op==0)return va<vb; else return va<=vb; }};vector<Constrain> vlist;int main(){ int n,t; for(scanf("%d",&n);n--;){ scanf("%s",str); int len=strlen(str),p=0,tkp=0; Constrain cons; while(str[p]!='<'){ tk[tkp++]=str[p++]; } tk[tkp]=0; cons.a.set(tk); tkp=0; while(p<len){ if(str[p+1]=='='){ cons.op=1; p+=2; }else{ cons.op=0; p+=1; } while(str[p]!='<' && str[p]){ tk[tkp++]=str[p++]; } tk[tkp]=0; cons.b.set(tk); tkp=0; vlist.push_back(cons); cons.a=cons.b; } } for(scanf("%d",&t);t--;){ variable.clear(); for(int i=0;i<appear.size();i++){ char v[2];int num; scanf("%s%d",v,&num); variable[v[0]]=num; } bool flag=true; for(int i=0;i<vlist.size() && flag;++i){ flag=flag&&vlist[i].check(); } puts(flag?"Yes":"No"); } return 0;}

Problem B Full Binary Tree Picture

首先,我不保证暴力不能过。

所谓暴力方法,就是,对每个查询,重新生成每个树上的点的坐标,然后判断这些坐标是不是在矩形范围内。

因为最多20层,相当于2^20 -1 个点,100个查询,计算量刚好1亿左右,时限刚好1秒,但是有点风险,写着也烦,于是我就没写了。

有没有什么办法,只用生成一次树上的所有点,然后能高效算完所有的答案,不用重新遍历所有点?

注意到,高度最高20,如果20层的情况下,最底下一层会有2^(n-1)个点,太多了,一个个检查过去很不科学。

——我们学过对有序序列高效查找的办法是什么?二分查找!

所以做法是,对每层,生成相应的x,还有一个数组y[],从小到大存每个点的y坐标。

这个生成过程可以由上一层的点坐标,加上往左偏移和往右偏移得到,具体请自己推算。

之后对每个查询,先判断这层高度在不在范围内,如果在范围内,二分查找所有落在范围内的点,把20层的答案累加起来,就是我们要的结果了。

时间复杂度非常的乐观,O(2^n+n*n)。

#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>#include <limits.h>#include <math.h>#include <algorithm>#include <vector>using namespace std;typedef long long ll;int treeSize[25];int n,m;int query[105][4];int answer[105];void checkAll(int x,vector<int>& y){ for(int i=0;i<m;i++){ if(query[i][0]<=x && x<=query[i][2]){ int idx1=lower_bound(y.begin(),y.end(),query[i][1])-y.begin(); int idx2=lower_bound(y.begin(),y.end(),query[i][3])-y.begin(); while(idx2!=y.size() && y[idx2]<=query[i][3])++idx2; answer[i]+=idx2-idx1; } }}int main(){ treeSize[1]=2; treeSize[2]=3; for(int i=3;i<=20;++i) treeSize[i]=treeSize[i-1]*2; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d%d%d",query[i]+0,query[i]+1,query[i]+2,query[i]+3); } int x=0; vector<int> ynow,ylast; ylast.push_back(0); checkAll(0,ylast); for(int i=n-1;i>=1;--i){ x+=treeSize[i]; ynow.clear(); for(int j=0;j<ylast.size();++j){ ynow.push_back(ylast[j]-treeSize[i]); ynow.push_back(ylast[j]+treeSize[i]); } checkAll(x,ynow); ynow.swap(ylast); } for(int i=0;i<m;i++){ printf("%d\n",answer[i]); } return 0;}

接下来我们将来到Hard领域。请做好心理准备(顺带当做Google在线笔试之后比较难的题目的预演吧。)

顺带一提,接下来2题都是去请教了Claris 松扬老师得到的思路,在此膜拜(当然实现还是我自己的。)

Problem C Stable Members

“我的直觉是,要用拓扑排序。”

“然后呢?”

“不知道。”

于是直接把题目扔给Claris老师,然后他马上说,

这是ZJOI 2012一个题,灾难,同一个道理的东西。

(题面参见:http://www.cnblogs.com/JS-Shining/archive/2013/01/12/2857429.html)

做法如下:

1、从master出发做拓扑排序,求出被依赖关系的拓扑序列。(如果觉得莫名其妙,请把图上所有边反向)

2、对之前求出的拓扑序列从前往后,一个个试图加入一棵树中。

这里加入的时候,要给新节点定父亲对吧?

新节点的父亲=新节点的直接mentor们的最近公共祖先(LCA)

(当然,master肯定是最先加进树里的,当时树是空的,直接一个master节点留在那里就行了。)

3、最后统计,和master直接相连的节点数量。

具体实现上,存图、拓扑排序没什么好讲的……

求最近公共祖先,请使用高效的做法(复杂度是logn的),比如下面代码里实现的,基于二分搜索/倍增思想求最近公共祖先。

#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>#include <limits.h>#include <math.h>#include <algorithm>#include <vector>#include <queue>using namespace std;typedef long long ll;int n;vector<int> G[100005];int indeg[100005];int logk[100005][11];int kk[100005];int parent[20][100005];int depth[100005];int lca(int u,int v){ if(depth[u]>depth[v])swap(u,v); for(int k=0;k<19;++k){ if((depth[v]-depth[u])>>k&1){ v=parent[k][v]; } } if(u==v)return u; for(int k=18;k>=0;--k){ if(parent[k][u]!=parent[k][v]){ u=parent[k][u]; v=parent[k][v]; } } return parent[0][u];}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int k,id; scanf("%d",&k); kk[i]=k; indeg[i]=k; for(int j=0;j<k;j++){ scanf("%d",&id); logk[i][j]=id; G[id].push_back(i); } } vector<int> seq; queue<int> q; q.push(0); while(!q.empty()){ int x=q.front();q.pop(); seq.push_back(x); for(int i=0;i<G[x].size();++i){ int y=G[x][i]; --indeg[y]; if(!indeg[y]){ q.push(y); } } } int ans=0; for(int i=0;i<20;i++)parent[0][i]=-1; depth[0]=0; for(int i=0;i<=n;++i){ if(seq[i]==0)continue; int x=seq[i]; int par=logk[x][0]; for(int i=1;i<kk[x] && par>0;++i){ par=lca(par,logk[x][i]); } if(par==0) ++ans; parent[0][x]=par; depth[x]=depth[par]+1; for(int k=0;k<18;++k){ if(parent[k][x]<0) parent[k+1][x]=-1; else parent[k+1][x]=parent[k][parent[k][x]]; } } printf("%d\n",ans); return 0;}

然后Claris老师告诉我——

其实这道题,就是求以master为根的Dominator Tree(支配树)。

对于这题的有向无环图DAG,可以用拓扑+LCA求。

对任意图,有一种时间复杂度近似线性的tarjan算法,直接贴模板就行了。

(补充:

1、去百度,然后发现,怎么Java内存分析工具里会提到这个概念?

因为分析出支配树,就可以知道,删除某个点后,哪些点不可能访问到了,也要一并删除掉了

2、学会了这个写法,去挑战一下zjoi 2012的灾难那题如何?轻车熟路吧?

3、什么?想看看Claris老师的求Dominator Tree的tarjan算法模板?请做好心理准备,然后看下一题吧……

Problem D Part-Time Jobs

OK,明显贪心很不理智,我们考虑做规划。

对10000个点做规划很不理智,考虑缩小。

因为我们只在意完成任务的顺序安排,那不妨把这个图缩小到Q个任务点+1个起点,新图的2点之间的边权为旧图上2点之间最短路。

剩下最多21个点,我们需要用二进制位表示状态的状态压缩动态规划。

状态用我们完成的任务S,和最后一个被完成的任务 i 组成,最小化目标是完成时间。

dp[S][i]表示已经走过的任务集合为S,最后一个任务为 i 时,完成最后一个任务的最早时间。

在状态转移的时候,选择一个未完成的任务去做,注意,还得要检查,能不能做这个任务。

考虑可行的开始时间=max(任务自身的最早开始时间,当前状态用时+走到任务地点用时)。如果可行的开始时间比最迟开始时间还要迟,那就别做了。

最早完成时间顺其自然的更新为 (最早可行的开始时间 + 任务耗时) 了。

最后一步很显然了,考虑所有更新过的集合,取完成任务价值和最大的集合,作为答案。

注意这题对写法有一点点要求(当然主要自己习惯不好,老老实实完整的spfa也行……),为了不再TLE,折腾了非常多……

最后整理一遍思路

1、用最短路算法,求出只剩下起点+有任务的点的小规模完全图

2、使用状态压缩动态规划,dp[S][i]表示已经走过的任务集合为S,最后一个任务为 i 时,完成最后一个任务的最早时间。转移顺其自然的来就行。

3、被转移到的任务集合中选一个价值和最大的,作为答案。

#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>#include <limits.h>#include <math.h>#include <algorithm>#include <vector>#include <queue>using namespace std;typedef long long ll;template <class T>inline void scan(T &ret) { char c; ret=0; while((c=getchar())<'0'||c>'9'); while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();}template<class X,int MaxSize>struct LoopQueue{X data[MaxSize];int head,tail,sz;LoopQueue(){init();}void init(){head=0;tail=0;sz=0;}void push(const X& x){data[tail]=x;tail++;if(tail>=MaxSize)tail-=MaxSize;sz++;}void pop(){head++;if(head>=MaxSize)head-=MaxSize;sz--;}X& front(){return data[head];}int size(){return sz;}bool empty(){return head==tail;}};int n,m,q;vector<pair<int,int> > G[10005];struct Job{ int L,S,E,T,C; void get(){ scan(L);scan(S);scan(E);scan(T);scan(C); }}job[25];struct State{ int mask; int lastp; State(){} State(int _m,int _p):mask(_m),lastp(_p){}};LoopQueue<State,10000000> qu;int matDis[25][25];int dp[1<<21][20];bool checked[1<<21][20];bool vis[1<<21];int dis[10005];void dij(int x){ fill(dis,dis+n+1,INT_MAX/2); dis[x]=0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; q.push(make_pair(0,x)); while(!q.empty()){ pair<int,int> tx=q.top();q.pop(); if(tx.first!=dis[tx.second])continue; int p=tx.second; for(int i=0;i<G[p].size();++i){ pair<int,int> edge=G[p][i]; int y=edge.first,w=edge.second; if(dis[y]>dis[p]+w){ dis[y]=dis[p]+w; q.push(make_pair(dis[y],y)); } } }}int ans=0;void checkAns(int mask){ int tans=0; for(int i=1;i<=q;++i){ if((mask & (1<<(i-1)))){ tans+=job[i].C; } } ans=max(ans,tans);}int main(){ scan(n);scan(m);scan(q); for(;m--;){ int u,v,w; scan(u);scan(v);scan(w); G[u].push_back(make_pair(v,w)); G[v].push_back(make_pair(u,w)); } for(int i=1;i<=q;i++){ job[i].get(); } job[0].L=1; for(int i=0;i<=q;i++){ matDis[i][i]=0; if(i==q)break; bool flag=false; for(int j=0;j<i;j++){ if(job[i].L==job[j].L){ flag=true; for(int k=0;k<=q;k++){ matDis[i][k]=matDis[j][k]; } break; } } if(flag)continue; dij(job[i].L); for(int j=i+1;j<=q;j++){ matDis[i][j]=matDis[j][i]=dis[job[j].L]; } } fill(dp[0],dp[(1<<q)+1]+20,INT_MAX/2); dp[0][0]=0; qu.push(State(0,0)); while(!qu.empty()){ State& x=qu.front();qu.pop(); if(!vis[x.mask])checkAns(x.mask),vis[x.mask]=1; for(int i=1;i<=q;++i){ if(!(x.mask & (1<<(i-1)))){ int startTime=max(job[i].S,dp[x.mask][x.lastp]+matDis[x.lastp][i]); if(startTime>job[i].E)continue; State y(x.mask|(1<<(i-1)),i); if(dp[y.mask][i]>startTime+job[i].T){ dp[y.mask][i]=startTime+job[i].T; if(checked[y.mask][y.lastp])continue; checked[y.mask][y.lastp]=1; qu.push(y); } } } } printf("%d\n",ans); return 0;}

谢谢大家看我扯了这么多。

本文转载自fcxxzux博客,版权归fcxxzux所有

解答:首先第一个人首先要保证剩余的人必须比他多或者少,他首先会计算,自己拿x个,那么第二人就会选择x-1,保证自己不是最大的,剩余的人可定会比自己小,依次为X-2,X-3,X-4.计算一下:5X-10=100 X=14 也就是说第一人应该会那十四颗才是最安全的我从第二人分析:他摸出剩余的豆子数,很容易就判断出第一人拿了14,所以可定会拿13颗,首先自己不是最大的,再有就是别人为了保命肯定不会拿13颗。如此成立的话第三人的思路是:根据剩余豆子数判断,前两人一共是27个,平均13.5个,也就是说同理的情况下自己拿12个是最安全的同理到第五个人就没有选择 必死无疑所以在大家都是聪明人的前提下,没有人会例外选择,就此看来 最起码中间三人的安全程度是一样的,因为收尾两个人是无法选择的内容来自www.zgxue.com请勿采集。

免责声明 - 关于我们 - 联系我们 - 广告联系 - 友情链接 - 帮助中心 - 频道导航
Copyright © 2017 www.zgxue.com All Rights Reserved