【在線筆試題解題報告系列】微軟在線筆試之 2016微軟探星夏令營在線技術筆試(時間:2016.07.17)

來源:本網整理

這好像并不難呀~至少3架。先同時起飛2架。飛到 1/4 圈時一架把剩余的油全部給另一架。這樣有油的這架可以飛到 3/4。等這架飛到一半時讓第3架往相反方向起飛。這樣正好可以在前面那架飛到 3/4 時相遇并把油全部給它。讓它完成整圈飛行。還有更少的辦法嗎?www.13333515.buzz防采集請勿采集本網。

當然這個做得好還是不好和我無關了·(微軟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.13333515.buzz請勿采集。

免責聲明 - 關于我們 - 聯系我們 - 廣告聯系 - 友情鏈接 - 幫助中心 - 頻道導航
Copyright © 2017 www.13333515.buzz All Rights Reserved
3排列五开奖结果