数码控科技猎奇Iphone动漫星座游戏电竞lolcosplay王者荣耀攻略allcnewsBLOGNEWSBLOGASKBLOGBLOGZSK全部技术问答问答技术问答it问答代码软件新闻开发博客电脑/网络手机/数码笔记本电脑互联网操作系统软件硬件编程开发360产品资源分享电脑知识文档中心IT全部全部分类 全部分类技术牛文全部分类教程最新 网页制作cms教程平面设计媒体动画操作系统网站运营网络安全服务器教程数据库工具网络安全软件教学vbscript正则表达式javascript批处理更多»编程更新教程更新游戏更新allitnewsJava 新闻网络医疗信息化安全创业站长电商科技访谈域名会议专栏创业动态融资创投创业学院 / 产品经理创业公司人物访谈营销 开发数据库服务器系统虚拟化云计算 嵌入式移动开发作业作业1常见软件all电脑网络手机数码生活游戏体育运动明星影音休闲爱好文化艺术社会民生教育科学医疗健康金融管理情感社交地区其他电脑互联网软件硬件编程开发360相关产品手机平板其他电子产品摄影器材360硬件通讯智能设备购物时尚生活常识美容塑身服装服饰出行旅游交通汽车购房置业家居装修美食烹饪单机电脑游戏网页游戏电视游戏桌游棋牌游戏手机游戏小游戏掌机游戏客户端游戏集体游戏其他游戏体育赛事篮球足球其他运动球类运动赛车健身运动运动用品影视娱乐人物音乐动漫摄影摄像收藏宠物幽默搞笑起名花鸟鱼虫茶艺彩票星座占卜书画美术舞蹈小说图书器乐声乐小品相声戏剧戏曲手工艺品历史话题时事政治就业职场军事国防节日风俗法律法规宗教礼仪礼节自然灾害360维权社会人物升学入学人文社科外语资格考试公务员留学出国家庭教育学习方法语文物理生物工程学农业数学化学健康知识心理健康孕育早教内科外科妇产科儿科皮肤科五官科男科整形中医药品传染科其他疾病医院两性肿瘤科创业投资企业管理财务税务银行股票金融理财基金债券保险贸易商务文书国民经济爱情婚姻家庭烦恼北京上海重庆天津黑龙江吉林辽宁河北内蒙古山西陕西宁夏甘肃青海新疆西藏四川贵州云南河南湖北湖南山东江苏浙江安徽江西福建广东广西海南香港澳门台湾海外地区

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

来源:本网整理

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

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


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

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

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

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所有

  • 本文相关:
  • [从头读历史] 第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