今天上午参加了网易游戏暑期实习第三场笔试，一共3小时，包括10道选择题，3道编程题。编程题目大约一个半小时搞定。
这里分享一下编程题目的题解，有任何疑问，可在评论区回复^^。

题目1

网易游戏的数据挖掘研究员每天需要和海量的玩家数据打交道，在大数据的基础上完成数据挖掘、机器学习、个性化推荐、人工智能等各项研究工作，而对SQL的熟练掌握也成了他们工作中必备的技能之一。假设数据仓库中有一张玩家行为表tb_player_action，记录着所有玩家购买道具的行为，表结构如下：

请仔细阅读以下SQL，根据上述表的输入数据，输出该SQL的执行结果。

SELECT uid1, COUNT(DISTINCT uid2) as val
FROM (
    SELECT a.uid AS uid1, b.uid AS uid2
    FROM (
        SELECT uid, iid FROM tb_player_action
    ) a
    LEFT OUTER JOIN (
        SELECT uid, iid FROM tb_player_action
    ) b
    ON (a.uid != b.uid AND a.iid == b.iid)
) c
WHERE uid2 IS NOT NULL
GROUP BY uid1
HAVING val > 0
ORDERED BY uid1 ASC;

输入描述

第一行一个整数 $n$，表示表中数据的记录数；
接下来 $n$ 行，每行三个整数 $id, uid, iid$，数值之间用空格分隔，表示数据表中的一条记录。

输出描述

输出上述SQL的执行结果，每行数据的字段用空格分隔；

样例

输入：

9
1 1 2
2 2 1
3 3 3
4 2 4
5 6 5
6 5 5
7 5 6
8 4 4
9 3 2

输出：

1 1
2 1
3 1
4 1
5 1
6 1

算法

(哈希表,集合操作) $O(n^2)$

首先，我们要先理解SQL做了什么：

1. 对于每条记录，找出（uid与其不同，iid与其相同）的记录的集合；
2. 将所有记录及其对应的集合，按uid排序；
3. 将uid相同的记录所对应的集合合并；
4. 依次考虑每条记录及其对应的集合，如果集合非空，则输出集合中所有不同uid的个数；

然后考虑怎么实现这个过程：

1. 我们先找出每种iid对应的不同uid的集合，这可以用哈希表来做：
   定义unordered_map<int,unordered_set<int>>（不了解其用法的同学可以点此链接 ），表示iid及其对应的不同uid的集合。
2. 将所有记录按uid排序。
3. 对于每个不同的uid，新开一个unordered_set<int>，用来合并所有该uid对应的集合；
4. 如果合并后的集合元素个数大于1，则输出uid及集合元素个数减一（除去自身）；

时间复杂度分析：

1. 第一步每条记录遍历一次，哈希表插入操作复杂度是 $O(1)$，因此第一步的复杂度是 $O(n)$；
2. 第二步排序复杂度 $O(nlogn)$；
3. 第三步最坏情况下，所有uid均不同，所有iid均相同，则每个集合的元素个数是 $n$，进行n次集合合并操作，每次 $O(n)$，因此复杂度是 $O(n^2)$;
4. 第四步输出 $O(n)$ 行，复杂度是 $O(n)$

因此总时间复杂度是 $O(n^2)$.

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int main()
{
    int n;
    unordered_map<int, unordered_set<int>> hash;
    vector<pair<int, int>> users;
    cin >> n;
    for (int i = 0, a, b, c; i < n; i++)
    {
        cin >> a >> b >> c;
        hash[c].insert(b);
        users.push_back(make_pair(b, c));
    }
    sort(users.begin(), users.end());
    unordered_set<int> merge;
    for (int i = 0; i < users.size();)
    {
        int j = i;
        while (j<users.size() && users[i].first==users[j].first)
            j++;
        merge.clear();
        for (int k = i; k < j; k++)
            for (auto x : hash[users[k].second])
                merge.insert(x);
        if (merge.size() > 1)
        {
            cout << users[i].first << ' ' << merge.size()-1;
            cout << endl;
        }
        i = j;
    }

    return 0;
}

题目2

爱玩游戏是小朋友的天性，为了小朋友在玩游戏的同时智力可以得到同步训练，你开发了一款益智的数学谜题小游戏，为了验证小朋友算的对不对，你需要一个程序来计算结果答案。
益智小游戏是一道简单的数字谜题，由以下5部分组成：
一个整数，运算符号’+’或’-‘，一个整数，等号’=’，一个整数。
其中整数由数字或者大写字母组成，大写字母代表某个数字，也是小游戏要求小朋友输入的通关答案，相同的字母代表同一个数字，不同的字母代表不同数字，整数都小于十亿并且不为负数，数字谜题保证有唯一解。

输入描述

一行等式，育儿益智游戏的题目，包含未知字符的数字谜题；

输出描述

对每个字母按照字母顺序输出每个字母代表的数字，每个字母一行，字母与所代表的的数字间空格分开；

样例

输入：

12A+BB4=239

输出：

A 5
B 1

算法

(暴力枚举) $O(n!)$

由于不同字母代表不同数字，所以未知变量个数最多只有10个，因此我们可以直接暴力枚举来做。

为了优化时间效率，我们先对原来的等式做变形：$12A+BB4=239 =>$$100 + 20 + A + 100B + 10B + 4 $$ = 200 + 30 + 9$
然后将所有常数移到等式右边，所有自变量移到等式左边，合并同类项，得到：
$$ A + 110B = 115 $$
此时，我们得到了所有自变量和它们的系数，以及和是多少。
然后我们枚举所有自变量的可能取值，并带入验证即可。

时间复杂度分析：假设自变量个数是 $n$，由于要枚举 $n$ 个变量的所有可能取值，且取值不可重复，因此计算量是个排列数：$A_{10}^n$，复杂度是$O(n!)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <vector>
#include <string>

using namespace std;

typedef long long LL;

unordered_map<char, LL> S;
int st[10];
LL target;
vector<pair<char, LL>> adds;
int path[35];

LL work(string number, int sg)
{
    LL s = 0;
    for (int i = number.size() - 1, t = 1; i >= 0; i--, t *= 10)
    {
        if (number[i] <= '9') s += (number[i] - '0') * t * sg;
        else S[number[i]] += t * sg;
    }
    return s;
}

bool check()
{
    LL s = 0;
    for (int i = 0; i < adds.size(); i++)
    {
        s += adds[i].second * path[i];
    }
    return s == target;
}

bool dfs(int u)
{
    if (u == adds.size())
    {
        if (check())
        {
            for (int i = 0; i < adds.size();  i++)
                cout << adds[i].first << ' ' << path[i] << endl;
            return true;
        }
        return false;
    }

    for (int i = 0; i < 10; i ++ )
        if (!st[i])
        {
            st[i] = 1;
            path[u] = i;
            if (dfs(u + 1)) return true;
            st[i] = 0;
        }
    return false;
}

int main()
{
    string str;
    cin >> str;
    int cp = str.find('+', 0), sg = 1;
    if (cp == -1)
    {
        cp = str.find('-', 0);
        sg = -1;
    }
    int ce = str.find('=', 0);
    int a = work(str.substr(0, cp), 1);
    int b = work(str.substr(cp + 1, ce - cp - 1), sg);
    int c = work(str.substr(ce + 1), -1);
    target = -(a + b + c);
    for (auto item : S)
        adds.push_back(make_pair(item.first, item.second));
    sort(adds.begin(), adds.end());
    dfs(0);
    return 0;
}

题目3

任务链是网易开发运营的网络游戏梦幻西游中的常规任务，该任务由一系列连续的小任务组成任务系统，一次小任务被称为一环，玩家每完成一环任务都可以得到一定的随机经验奖励。任务链中，小任务分为{找人、寻物、战斗、捕捉}等4种类型，玩家第一个小任务的类型按照一定概率随机分配，例如：

假设玩家每次接到的小任务类型仅与前一次小任务类型相关，且不同类型任务之间的转换存在固定概率转移矩阵。例如，如下转移概率矩阵表示如果第T环类型为“找人”，则第T+1环接到的任务有50%的概率是找人，20%的概率是寻物或捕捉，10%是战斗；

假设每一环完成后经验奖励分{S, A, B, C, D}共5个档次随机发放，且每种类型的小任务有不同的概率分布，举例如下：

求给定初始任务类型分布，转移概率矩阵及奖励分布的情况下，玩家获得指定任务链的奖励序列的概率为多少（结果以$log10$变换给出）

输入描述

第1行，初始任务类型分布，数值以空格分隔；
第2-5行，每行内数值以空格分隔的转移概率矩阵(4x4矩阵)，其中矩阵行列对应的任务类型的顺序与第一行一致；
第6-9行，每行内数值以空格分隔的奖励分布矩阵(4x5矩阵)，矩阵行对应的任务类型顺序与2-5行一致，矩阵列对应奖励等级从左到右对应S,A,B,C,D；
第10行，由{S,A,B,C,D}等字符组成的不定长度的序列(长度<=50)，不同字符以空格分隔，第一个字符表示玩家接到的第一个小任务的奖励；

输出描述

在题目给定的类型转移概率和奖励分布概率下，得到输入序列的概率(浮点数精度1e-4)

样例

输入：

0.4 0.3 0.2 0.1
0.5 0.2 0.2 0.1
0.1 0.4 0.1 0.4
0.3 0.1 0.3 0.3
0.2 0.4 0.2 0.2
0.05 0.10 0.20 0.30 0.35
0.08 0.15 0.25 0.35 0.17
0.15 0.25 0.30 0.20 0.10
0.20 0.40 0.20 0.15 0.05
D B B A

输出：

-2.5928

算法

(动态规划) $O(n)$

状态表示： $f[i][j]$ 表示已经满足给定序列中前 $i$ 个奖励，且第 $i$ 个任务是 $j$ 的概率。

状态转移：

$$ f[i][j] = (\sum_{k=0}^3{f[i-1][k] * tr[k][j]}) * bonus[j][seq[i]] $$

解释:
我们先求出满足奖励序列的前提下，第 $i$ 个任务是 $j$ 的概率。这可以从第 $i-1$ 个任务的4种任务类型转移而来，每种路径乘上状态转移概率再加和，即可得到第 $i$ 个任务是 $j$ 的概率。
最后再乘上任务 $j$ 获得奖励 $seq[i]$ 的概率即可得到 $f[i][j]$。

时间复杂度分析：假设奖励序列的长度是 $n$，则状态数量是 $4n$，状态转移的计算量是常数，所以总时间复杂度是 $O(n)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>

using namespace std;

int n;
double tr[4][4], f[55][4], bns[4][5];

int main()
{
    for (int i = 0; i < 4; i++) cin >> f[0][i];
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            cin >> tr[i][j];
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 5; j++)
            cin >> bns[i][j];
    char str[200], c;
    cin.getline(str, 200);
    cin.getline(str, 200);

    stringstream seq_in(str);
    vector<int> seq;
    unordered_map<char, int> S;
    S['S'] = 0;
    for (int i = 0; i < 4; i++) S['A' + i] = i + 1;
    while (seq_in >> c)
    {
        seq.push_back(S[c]);
        n++;
    }
    for (int i = 0; i < 4; i++) f[0][i] *= bns[i][seq[0]];
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < 4; j++)
        {
            for (int k = 0; k < 4; k++)
                f[i + 1][j] += f[i][k] * tr[k][j];
            f[i + 1][j] *= bns[j][seq[i + 1]];
        }
    double res = 0;
    for (int i = 0; i < 4; i++) res += f[n - 1][i];
    printf("%.4lf\n", log10(res));
    return 0;
}