微软2016实习生网申解题报告

一共有4个题，时间是2个半小时。题目都在这儿。比赛时，只做了前面两道，第三道一直TLE。比赛结束后，经一个同学的指点，明白了第三题的原理。第四题的解答在这里，是一道还比较复杂的动态规划，我之后如果理解并且敲出来了，在和大家分享，这边先简单介绍一下前三道题的解题思路。

Magic Box

时间限制:10000ms 单点时限:1000ms 内存限制:256MB

描述

The circus clown Sunny has a magic box. When the circus is performing, Sunny puts some balls into the box one by one. The balls are in three colors: red(R), yellow(Y) and blue(B). Let Cr, Cy, Cb denote the numbers of red, yellow, blue balls in the box. Whenever the differences among Cr, Cy, Cb happen to be x, y, z, all balls in the box vanish. Given x, y, z and the sequence in which Sunny put the balls, you are to find what is the maximum number of balls in the box ever.

For example, let's assume x=1, y=2, z=3 and the sequence is RRYBRBRYBRY. After Sunny puts the first 7 balls, RRYBRBR, into the box, Cr, Cy, Cb are 4, 1, 2 respectively. The differences are exactly 1, 2, 3. (|Cr-Cy|=3, |Cy-Cb|=1, |Cb-Cr|=2) Then all the 7 balls vanish. Finally there are 4 balls in the box, after Sunny puts the remaining balls. So the box contains 7 balls at most, after Sunny puts the first 7 balls and before they vanish.

输入

Line 1: x y z

Line 2: the sequence consisting of only three characters 'R', 'Y' and 'B'.

For 30% data, the length of the sequence is no more than 200.

For 100% data, the length of the sequence is no more than 20,000, 0 <= x, y, z <= 20.

输出

The maximum number of balls in the box ever.

样例输入

1 2 3
RRYBRBRYBRY

样例输出

7

第一道题相对比较简单。给定一个序列，序列中只有三个字母(R,B,Y)，代表放入一个袋子中的球的顺序。还会给三个差值，如果这个序列中任意一时刻，袋中三个球的差值，满足给定的三个差值，则将球全部清空。然后最后返回的是袋中存在球的最大值。

这个题最直接的做法就是模拟，编码起来也会比较快。维护两个量，一个是三个球在袋中分别的总数，另一个是袋中球的存在的最大值。每次加入一个球，就把相应球的个数+1，之后就test每两个球的差值是否满足给定的差值。这里要判断6种情况，分别是{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}，直接写死就可以了。

每当满足差值条件后，就把当前的记录值清空，并且更新最大值。

Professor Q's Software

时间限制:10000ms 单点时限:1000ms 内存限制:256MB

描述

Professor Q develops a new software. The software consists of N modules which are numbered from 1 to N. The i-th module will be started up by signal Si. If signal Si is generated multiple times, the i-th module will also be started multiple times. Two different modules may be started up by the same signal. During its lifecircle, the i-th module will generate Ki signals: E1, E2, ..., EKi. These signals may start up other modules and so on. Fortunately the software is so carefully designed that there is no loop in the starting chain of modules, which means eventually all the modules will be stoped. Professor Q generates some initial signals and want to know how many times each module is started.

signals.png

输入

The first line contains an integer T, the number of test cases. T test cases follows.

For each test case, the first line contains contains two numbers N and M, indicating the number of modules and number of signals that Professor Q generates initially.

The second line contains M integers, indicating the signals that Professor Q generates initially.

Line 3~N + 2, each line describes an module, following the format S, K, E1, E2, ... , EK. S represents the signal that start up this module. K represents the total amount of signals that are generated during the lifecircle of this module. And E1 ... EK are these signals.

For 20% data, all N, M <= 10 For 40% data, all N, M <= 103 For 100% data, all 1 <= T <= 5, N, M <= 105, 0 <= K <= 3, 0 <= S, E <= 105.

Hint: HUGE input in this problem. Fast IO such as scanf and BufferedReader are recommended.

输出

For each test case, output a line with N numbers Ans1, Ans2, ... , AnsN. Ansi is the number of times that the i-th module is started. In case the answers may be too large, output the answers modulo 142857 (the remainder of division by 142857).

样例输入

3
3 2
123 256
123 2 456 256
456 3 666 111 256
256 1 90
3 1
100
100 2 200 200
200 1 300
200 0
5 1
1
1 2 2 3
2 2 3 4
3 2 4 5
4 2 5 6
5 2 6 7

样例输出

1 1 3
1 2 2
1 1 2 3 5

第二题其实也就是一道输入输出相对较为复杂的模拟(就做出两道模拟，汗)。题目的意思是，会给出几个module，每个module有自己的唤醒signal，也就是如果这个信号被发出，这个module就会运行；每一个module还会发出其他signal来唤醒别的module。一开始Professor Q会进场自带几个signal，题目中比较重要的话是，不会出现循环，signal是有限的。然后需要返回的是每个module一共被调用的次数。

输入很多。然后题目中希望我们选择用更快的输入方式。但是我们就是不用。因为我们有这样一句话。

cin.tie(0);cin.sync_with_stdio(0);

传说这句话，可以把cin的输入速度提到scanf一样的速度。再附送一个模板。

#include <bits/stdc++.h>
#define _ cin.tie(0);cin.sync_with_stdio(0);
using namespace std;

int main() {_
    return 0;
}

第一行似乎只有gcc-4.8以上支持，国外的几大OJ都是支持的，国内好像支持还不是特别全面。Mac上配置gcc-4.8看这里。包含了所有的C++标准库的头文件，感觉这个头文件也是为刷题而生。

回到本题。这道题其实module只是个幌子，每个module被唤醒的signal是唯一的，所以完全可以理解为signal唤醒signal，然后算每个signal出现的个数。

好了，既然事情已经挑明了，那么模拟的过程也十分明显了。我一共用了4个数据结构，其中一个队列，两个unordered_map，一个vector。队列模拟过程，一个map记录表格，一个map记录次数，vector记录输入module的顺序。

  1. 首先初始化一个队列，里面放着一开始的几个信号。
  2. 每次循环，pop_front，出现次数+1，查表，把将要唤醒的signal加入队尾。
  3. 循环直到队列为空。

输出根据vector中的顺序，查存次数的map输出。

Islands Travel

时间限制:10000ms 单点时限:1000ms 内存限制:256MB

描述

There are N islands on a planet whose coordinates are (X1, Y1), (X2, Y2), (X3, Y3) ..., (XN, YN). You starts at the 1st island (X1, Y1) and your destination is the n-th island (XN, YN). Travelling between i-th and j-th islands will cost you min{|Xi-Xj|, |Yi-Yj|} (|a| denotes the absolute value of a. min{a, b} denotes the smaller value between a and b) gold coins. You want to know what is the minimum cost to travel from the 1st island to the n-th island.

输入

Line 1: an integer N.

Line 2~N+1: each line contains two integers Xi and Yi.

For 40% data, N<=1000，0<=Xi,Yi<=100000.

For 100% data, N<=100000，0<=Xi,Yi<=1000000000.

输出

Output the minimum cost.

样例输入

3
2 2
1 7
7 6

样例输出

2

题目的意思就是，给出N个点，然后，给出每个的(X, Y)坐标。通过min(|X1 - X2|, |Y1 - Y2|)的方式定义两点间的距离，图是一个全连通图。求的是从第一个点道最后一个点的最短距离。

一开始，我直接吧这道题当成了全连通图的最短路做了，直接将输入预处理过后，开始最短路，明显超时，小数据也超时。

比赛过后，和一个同学交流后，理解了超时的原因。我在预处理的过程中就已经超时了，我们不应该把所有的路径都初始化，根据题目的一些性质，许多路径其实在预处理的时候，就可以排除了。

其实如果通过2维数组的方式，好像空间上也会超，所以数据中肯定有非常多的东西是冗余的，最后的图可能是一个非常稀疏的图，这样的图初始化和最后的最短路都会减少非常多的时间。

我们首先思考，有哪些路径是真的需要的。首先，我们不能只关注于我们是求解一个最短路问题，因为我们发现问题并不是存在在最短路的时间复杂度上，而是出在构图上！那么构图的时候，我们有什么是可以注意的呢？

现在假设，有A,B,C三点，如果A和B之间的距离是1，B和C之间的距离也是1，A和C之间的距离是2，那么对于我们要求以A为原点的最短路的时候，AC间的距离是无所谓的。也就是说这种情况下，经过中间点的不会弱于不经过中间点，那么我们只要在两个相邻的点之间构造一条边即可。

那么怎么才能让这道题中的信息利用到这个信息呢？排序。如果是按照位置排序，我们一定能得到经过中间点的不会弱于不经过中间点的特性。

但是题目中的距离可是涉及到了两个维度的。那么，让我们再看一下两点间的距离定义。

min(|X1 - X2|, |Y1 - Y2|)

我们如果先按照X轴排序，在相邻两点之间构造边，那么我们我可以保证，这两点之间的距离一定不会比这条边更差了(要么，Y轴构造的边比他好，比他差的话，根据定义，不影响)。再根据Y轴排序构边，如果更好，那么我们就要更新。

然后再根据最短路径算法进行求解就没有问题。

我使用的是unordered_map进行数据存储，应该会优化一些空间。因为我已经没有机会提交了，所以也不敢确定。后面我为了今年可能优化时间，敲了一个基于二项堆优化的最短路径，会在另一篇Blog中详解。尽请期待。

blogroll

social