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

来源:本网整理

根据主函数来看,你每次输入都需要通过点击确认,程序才能继续运行,count(num)函数才能调用。然后就需要根据你的题目要求来看是否是允许多次输入。

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

1、如果是类似于行测的数量关系和判断推理,可以找行测这一类的书去看。 2、在公务员考试中,行测总共125道题,考试时间120分钟,也就是平均不到一分钟一道题,所以如果掌握好方法还是有可能的。

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

去年的题型: 1. 数学题,只要看懂题目都能做。 2. 阅读理解,一共有5、6道题目,估计是GRE,GMAT,TOEFL, IETLS里面的题目。 3. 逻辑推理,也是读懂题目就好做了。 4. 充分非充分的题目,应该是GMAT里的题目。 5. 作文,250字以上。去年的题目

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

没有必要啊,只是些简单的问题,如果你全都是标准答案企业绝对不会喊你面试。good luck 在线笔试时用百度能检测出来吗 分几种情况: 专用的考试系统是不能用百度的 限制了网络ip的不能用百度 有老师监考的不能用百度 考试系统不设检测ip功能的一

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

同样境地,表示有点晕

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

甲去买烟,烟29元,但他没火柴,跟店员说:“顺便送一盒火柴吧。”店员没给。  乙去买烟,烟29元,他也没火柴,跟店员说:“便宜一毛吧。”最后,他用这一毛买一盒火柴。  这是最简单的心理边际效应。第一种:店主认为自己在一个商品上赚钱了,另外一个没赚钱。赚钱感觉指数为1。第二种:店主认为两个商品都赚钱了,赚钱指数为2。当然心理倾向第二种了。同样,这种心理还表现在买一送一的花招上,顾客认为有一样东西不用付钱,就赚了,其实都是心理边际效应在作怪。  启示:变换一种方式往往能起到意想不到的效果!通常很多事情换一种做法结果就不同了。人生道路上,改善心智模式和思维方式是很重要的。

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

我在六年前开始长跑的习惯。那时纯粹因为每天坐办公室肩颈背绷得太紧,自觉应该做点运动,于是开了健身房的卡,选择了最简单的跑步。坚持半年之后体重没怎么变,身形小了两个码,从M码到XS码,所有人看到我都说你瘦了,其实是结实了,体脂比降了,线条也就出来了。不过我觉得长跑对于我最大的改变不只是身体状况方面的,而是性格上的变化。在坚持长跑的过程中所领悟到的那些是我这几年成长中最宝贵的财富。长跑讲究个人的节奏。不用看别人也不用追别人,单纯按着自己的呼吸调整节奏,才能达到自己的最好状态。--论独立的重要性。目标不宜太低,也不用太高,在本身能力之余,再给自己加点码,拉自己一把,所有后面凭意志坚持下去的那部分便是

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

部队确实是有这条规定,是因为飞行员很珍贵,举例来说如果飞机失事,宁肯牺牲飞机,也要保住飞行员,这是因为培养一名飞行员是十分困难的,不仅要求飞行员身体素质要高,同时心理素质也要过硬。再加上,培养一名飞行员的成本也是比较高的。据了解,培养一名能够担负作战值班任务的飞行员需要大概需要300万元人民币,轰炸机飞行员则需要500万元人民币,有这么一句话飞行员的价值等同于其自身体重的黄金了。在日常的生活中,为了保障飞行员的地面安全,避免和减少不必要的损失,空军部队都有专门规定,飞行员不得开车。其实还有一个主要的原因就是,飞行员经年累月的训练,脑中有的全是飞机的相关操作,许多退役飞行员都会不由自主的把汽车当

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

兔子肠胃很脆弱的,看你家兔子有多大,一般健康的兔子都会吃东西和喝水的。兔子三个月以前不能喂蔬菜,不然很容易拉肚子而死。三个月后也不能把蔬菜水果当主食。而且兔子当宠物养的话要健康喂养,我头条号里有篇关于养兔子的文章你可以去看看,如果有什么问题也可以问我。

本文地址: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所有

扩展阅读,根据您访问的内容系统为您准备了以下内容,希望对您有帮助。

事业单位考试笔试题网上有那种在线做题的吗?求指教

  事业单位考试笔试题网上有那种在线做题的,可以百度百度搜索:事业单位考试在线做题,可以找到很多这样在线做题的。例如:

  http://www.shiyebian.net/shiti/

  教育类事业单位,考试内容为教育学、教育心理学、教育教学相关知识。

求问招聘在线笔试环节在线编程题可以搜索网页吗

应该是不可以的,用的做了技术*的,只要在答题界面上出现其他界面就算是离开了当前页,基本上离开几次之后就直接自动提交你的试卷了本回答被提问者和网友采纳

求问招聘在线笔试环节在线编程题可以搜索网页吗

可以搜。

希望我的回答可以帮到你,有什么不懂可以追问。

我想问一下,阿里巴巴在线笔试答题的时候,如果使用百度搜索答案,算是作弊码?

算作弊吧,自己还不清楚?本回答被提问者采纳

百度实习生招聘在线笔试,进去之后怎么每题啊

百度实习生招聘在线笔试,进去之后没题,刷新一下就有了。看下在线笔试时间刷新即可。

  • 本文相关:
  • [从头读历史] 第307节 星球战争 BC2699 至 BC2600(公元前27世纪)
  • ISO8583报文协议详解
  • cs231n - assignment1 - neural net 梯度推导
  • 80x86微处理器结构及其工作模式
  • 五大NAT穿透方法,解决内网问题
  • 动态代理及其两种实现方式(JDK、CGLIB)
  • 【HDU5721 BestCoder 2nd AnniversaryD】【平面最近点对 分治写法+KD-tree写法】Palace 平面最近点对
  • 《UNIX环境高级编程》--5 标准IO库
  • 原型聚类总结
  • 游戏测试---------第2章
  • 免责声明 - 关于我们 - 联系我们 - 广告联系 - 友情链接 - 帮助中心 - 频道导航
    Copyright © 2017 www.zgxue.com All Rights Reserved