本周五参加了网易互娱2017实习生招聘在线笔试第一场(难倒还有好几场),题目总体上比较基础,一读题就有思路,不过手速快才能写完。
比赛链接

题目1 : 电子数字

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

描述

电子数字在生活中很常见,而许多的电子数字是由LED数码管制作而成。数字LED数码管一般由7个发光二极管封装在一起,组成’8’字型,引线在内部连接完成。如下图所示,我们可以对每个发光管进行编码从1到7。而数字0到数字9可以由这七根发光管的亮暗来表示。

对LED数码管的二极管进行编码

用LED数码管表示数字0-9

假设我们现在有从左到右排列好的K个LED数码管,并且我们已知每个数码管当前有哪些编号的二极管是亮着的,另外剩余的二极管由于某些原因,我们并不清楚它们的亮暗情况。由于已经有部分二极管是确定亮着的,所以每个LED数码管能表示的数字范围会有所缩小,譬如假设1号二极管已经确定是亮着的状态,那么这个LED数码管就不能表示数字1和4。

我们想知道的是,给定一个数N,在这K个LED数码管的当前亮暗的状态下,所有可能表示的数中,比N小的数有多少个。

注意,前导0是必须的,假设有4个数码管的话,’0000’表示0,’0123’表示123,即每个数的表示方法唯一。

输入

每个输入数据包含多个测试点。

第一行为测试点的个数 S ≤ 100。之后是 S 个测试点的数据。测试点之间无空行。

每个测试点的第一行为 K(1 ≤ K ≤ 5)和N(0 ≤ ≤ 109)。之后是K行,每行表示对应数码管已点亮的二极管的情况。每行至少包含一个数字,表示对应点亮的二极管的编号,即每个数码管至少有一根二极管是点亮的。二极管编号的范围保证在1到7之间,且每行无重复编号。

注意表示数码管点亮情况的每行数字之间以及行首行末之间可能存在冗余空格,每行的字符总长度不超过100。

输出

对于每个测试点,对应的结果输出一行,表示这K个数码管在当前状态下,所有可能表示的数中,比N小的数有多少个。

样例解释

第一个样例中,只有’020′, ‘026’, ‘028’符合要求。

第三个样例中,只有’000’符合要求。

样例输入
3
3 50
3  1
  1  4  5  
1   5  6 7
4 100
1 2 3
   4   5
6
  7  
1 1
  7
样例输出
3
0
1
读题意枚举,读好几行空格打乱的若干整型用sstream(之前directX项目读c++文档学到的)好舒服。

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
const int led[10][8] = { { 2,1,3,5,6,7 },{ 3,6 },{ 1,3,4,5,7 },{ 1,3,4,6,7 },{ 2,3,4,6 },{ 1,2,4,6,7 },{ 1,2,4,5,6,7 },{ 1,3,6 },{ 1,2,3,4,5,6,7 },{ 1,2,3,4,6,7 } };
int k, n;
int answer;
vector<int> validNumbers[10];//每个显示位数可能的数字
void dfs(int index, int number)
{ //因为N<=5 所以可以直接枚举
    if (index == k)
    {
        if (number < n)
            answer ++;
        return;
    }
    for (vector<int>::iterator it = validNumbers[index].begin(); it != validNumbers[index].end(); ++it)
        dfs(index + 1, number * 10 + *it);
}
int main()
{
    int s;
    cin >> s;
    while (s--)
    {
        cin >> k >> n;
        string line;
        getline(cin, line); // 读掉回车
        for (int i = 0; i < k; i++)
        {
            validNumbers[i].clear();
            getline(cin, line); // 读一整行 并用istringstream读该行被很多空格打乱的若干个整数
            istringstream sin(line);
            vector<int> ledNumbers;//当前数字亮的led编号
            int ledN;
            while (sin >> ledN)
            {
                ledNumbers.push_back(ledN);
            }
            for (int number = 0; number < 10; number++) //判断当前数字是否可以是0~9其中的若干个
            {
                bool isvalid = true;
                for (vector<int>::iterator it = ledNumbers.begin(); it != ledNumbers.end(); ++it)
                {
                    bool notexist = true; //如果当前数字亮的led编号不属于当前枚举的0~9中应该亮的led编号就不添加
                    for (int j = 0; j < sizeof(led[number]) / sizeof(int); ++j)
                    {
                        if (*it == led[number][j])
                        {
                            notexist = false;
                            break;
                        }
                        
                    }
                    if (notexist)
                    {
                        isvalid = false;
                        break;
                    }
                }
                if (isvalid)
                {
                    validNumbers[i].push_back(number);
                }
            }
        }
        answer = 0;
        dfs(0,0);
        cout << answer << endl;
    }
    return 0;
}

题目2 : 源代码编译

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

描述

在网易游戏的日常工作中,C++ 是一门常用的语言。面对众多的 C++ 代码,等待源文件编译的漫长时间是个令人糟心的时刻,一直以来大家对此怨声载道。终于有一天,大家找到了你,一位优秀的程序员,请你来帮忙分析一下编译速度的瓶颈。

经过一番调查和研究,你发现一些源代码之间是有依赖关系的。例如,某个源文件 a.cpp 编译链接生成了动态链接库 a.dll,而 b.cpp 编译链接生成的 b.dll 依赖于 a.dll。这个时候,必须等待 a.dll 生成之后才能生成 b.dll。为了表达简单,我们这个时候称 b.cpp 依赖于 a.cpp。

网易游戏内部使用了一个分布式并行的编译平台,可以同时编译多个不互相依赖的文件,大大提高了源代码的编译速度。然而当某些依赖链很长的时候,这个编译平台也无能为力,只能按照依赖顺序一个一个完成编译,从而造成了很长的编译时间。

为了验证这个想法,你决定着手通过代码分析这些文件之间的编译顺序。已知这些文件的文件名,以及这些文件所依赖的其他文件,你需要编写一个程序,输出一个可行的编译所有源文件的编译顺序。如果有多种可行的序列,请输出所有文件名序列中字典序最小的那一个(序列 (a1a2, …, an) 字典序小于序列 (b1b2, …, bn),当且仅当存在某个 i ,使得 ai 的字典序小于 bi,并且对于任意 j < i ,都有 aj = bj)。

输入

输入包含多组测试数据。

输入的第一行包含一个整数 T(T ≤ 100),表示输入中一共包含有 T 组测试数据。

每组测试数据第一行是一个整数 N(N ≤ 1000),表示一共有 N 个源代码文件。随后一共有 N 行数据,其中第 i(0 ≤ i < N) 行数据包含序号为 i 的源代码文件的依赖信息。每一行开头是一个字符串,表示这一个文件的文件名,随后一个整数 m(0 ≤ m ≤ N),表示编译这个源文件之前需要先编译 m 个依赖文件。之后是 m 个整数 j0 … jm-1,表示这 m 个依赖文件的序号(0 ≤ j < N) 。所有的文件名仅由小写字母、数字或“.”组成,并且不会超过 10 个字符。保证 n 个源代码文件的文件名互不相同。

输出

对于每一组输入,按照编译先后顺序输出一组可行的编译顺序,一行一个文件名。如果有多种可行的序列,请输出所有文件名序列中字典序最小的那一个。如果不存在可行的编译顺序,输出一行 ERROR。每组测试数据末尾输出一个空行。

样例输入
3
2
a.cpp 0
b.cpp 1 0
2
cb 0
c 0
2
a.cpp 1 1
b.cpp 1 0
样例输出
a.cpp
b.cpp

c
cb

ERROR
拓扑排序,优先队列保证字典序。

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int T, n;
char dic[1005][20]; //字典, 存文件名
int indeg[1005]; //点的入度
int head[1005], cnt; //链式前向星的表头和计数变量

struct edge // 边 n:next 同一出发点连出的下一条边在边表中的位置, t 终止点
{
    int n, t;
    edge(int a = 0, int b = 0) :n(a), t(b) {}
}e[1000006];

void ins(int a, int b) //在边表中插入边 a to b
{
    e[cnt] = edge(head[a], b);
    head[a] = cnt++;
}

struct cmp // 用于优先队列比较
{
    bool operator()(int a, int b)
    {
        return strcmp(dic[a], dic[b]) > 0;
    }
};

priority_queue<int, vector<int>, cmp> pq;
vector<int>ans;
void solve() // 拓扑排序,用优先队列,保证取出的点总是可用的点中文件名字典序比较最小的
{
    int i, u, v;
    while (!pq.empty())
    {
        u = pq.top();
        pq.pop();
        ans.push_back(u);
        for (i = head[u]; i != -1; i = e[i].n)
        {
            v = e[i].t;
            --indeg[v];
            if (!indeg[v])
                pq.push(v);
        }
    }
}
int main()
{
    scanf("%d", &T);
    int a, j;
    while (T--)
    {
        scanf("%d", &n);
        memset(indeg, 0, sizeof(indeg));
        memset(head, -1, sizeof(head));
        cnt = 0;
        ans.clear();
        for (int i = 0; i < n; ++i)
        {
            scanf(" %s", dic[i]);
            scanf("%d", &j);
            indeg[i] += j;
            while (j--)
            {
                scanf("%d", &a);
                ins(a, i);
            }
        }
        while (!pq.empty())// 清空优先队列
            pq.pop();
        for (int i = 0; i < n; ++i) // 入度为0 即可以编译
            if (!indeg[i])
                pq.push(i);
        
        solve();
        
        if (ans.size() == n)
            for (int i = 0; i < n; ++i)
                printf("%s\n", dic[ans[i]]);
        else puts("ERROR");
        putchar('\n');
    }
    return 0;
}

题目3 : 画线

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

描述

小王最近在开发一种新的游戏引擎,但是最近遇到了性能瓶颈。于是他打算从最基本的画线功能开始分析优化。画线其实就是调用一次drawline命令,根据给出的两端坐标,在屏幕画出对应的线段。但是小王发现,很多的drawline其实可以合并在一起,譬如下图中的线段(2,3)-(4,5)和线段(3,4)-(6,7),其实可以合并为一次drawline命令,直接画出线段(2,3)-(6,7)。当然有些线段是无法合并的,如线段(-3,8)-(1,8)和线段(3,8)-(6,8),就必须调用两次drawline命令。

画线示意图。注意颜色只是用于区分,实际线段都是黑色

给出N条drawline指令以及对应的线段坐标,小王想知道,实际最少用多少次drawline指令就可以画出来。

小王想先从最简单的情况开始分析优化,所以线段只包含四种情况:水平线段,垂直线段以及正反45度的线段。

输入

每个输入数据包含多个测试点。

第一行为测试点的个数 S ≤ 10。之后是 个测试点的数据。

每个测试点的第一行为 N(≤ 105)。之后是 行,每行包含4个整数:x0y0x1y1,表示线段(x0,y0)-(x1,y1),坐标的范围在[-108, 108],保证线段的长度大于0。

输出

对于每个测试点,对应的结果输出一行,表示最少用多少次指令即可完成所有的画线。

样例输入
2
4
3 8 6 8
-3 8 1 8
2 3 4 5
3 4 6 7
5
1 1 2 2
2 2 3 3
3 3 4 2
4 2 5 1
1 0 100 0
样例输出
3
3
排序贪心。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int T, n, ans;
struct line //
{
    int id, x, y; // id:象征该类线段可能重合的属性,如竖线的x,而为另一个属性的小值和大值
    line(int a = 0, int b = 0, int c = 0) :id(a), x(b), y(c) {}
    bool operator<(const line&tt)const //先按重合属性排序,再按小值排序
    {
        if (id == tt.id)
        {
            return x < tt.x;
        }
        return id < tt.id;
    }
};
vector<line> vec[4]; //总共4个方向的线段,分别处理
void solve()
{
    int i, a, b, n;
    for (i = 0; i < 4; ++i)
        sort(vec[i].begin(), vec[i].end());
    for (i = 0; i < 4; ++i) //合并重合线段
    {
        n = vec[i].size();
        for (a = 0; a < n; a = b)
        {
            for (b = a + 1; b < n; ++b)
            {
                if (vec[i][b].id != vec[i][a].id)
                    break;
                if (vec[i][b].x <= vec[i][a].y)
                {
                    --ans;
                    vec[i][a].y = max(vec[i][a].y, vec[i][b].y);
                } else break;
            }
        }
    }
}
int main()
{
    scanf("%d", &T);
    int i, a, b, c, d;
    while (T--)
    {
        for (i = 0; i < 4; ++i)
            vec[i].clear();
        scanf("%d", &n);
        for (i = 1; i <= n; ++i)
        {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            if (a == c) // 竖线段
                vec[0].push_back(line(a, min(b, d), max(b, d))); // x作为id,y的最大值最小值作为特征
            else if (b == d) //横线段
                vec[1].push_back(line(b, min(a, c), max(a, c)));
            else if (a + b == c + d) //斜率为负的线段
                vec[2].push_back(line(a + b, min(a, c), max(a, c)));
            else //斜率为正的线段
                vec[3].push_back(line(a - b, min(a, c), max(a, c)));
        }
        ans = n;
        solve();
        printf("%d\n", ans);
    }
    return 0;
}

「Unity Shaders」Surface Shaders and Texture Mapping

 本文内容参考《Unity 5.x Shaders and Effects Cookbook》 表面着色器和材质贴图 总的来说,一个表面着色器有两个关键的步骤。第一,必须确定材质的物理...

阅读全文

「Unity Shaders」Creating First Shader

创建第一个着色器 最近学习了一段时间Unity Shader相关知识,在进一步自顶向下学习计算机图形学之前,先将之前看《Unity 5.x Shaders and Effects Cookbook...

阅读全文

《Effective c++》、《Inside C++ Model》 小结(一)

最近瞻仰了一下Scott Meyers久负盛名的《effective c++》,特来总结一下,以加深一下印象与防止自己今后记忆力衰退。这本书里很多都是工程上很有意思的tips...

阅读全文

欢迎留言