平凡

某次腾讯校招笔试解析

2018/09/19 Share

1 小Q怼序列

题目描述

小Q有一个长度为n并包含1~n的整数序列。

在最开始,序列是升序排列,即1在序列首部,n在序列尾部。

小Q将会对序列进行m次操作,第i次操作,小Q会把xi从序列中取出来并放到序列首部。

小Q想知道m次操作后,序列变成什么样。

输入描述

  • 输入包括m+1
  • 第一行包括两个整数n,m(1 <= n, m <= 100000)
  • 接下来m行,每行一个正整数xi,表示小Q每次操作的数。

输出描述

输出一行,即m次操作之后的序列,以空格分割,行末无空格。

示例1

输入

5 4
4
3
1
4

输出

4 1 3 2 5


分析:

  • 问题可转化为:有一个数组arr[1, 2, ……n]和一个操作栈stack[x1, x2 …… xm],每次从stack中取出一个数xi,把数组中值为xi的数放到最前面。最后输出arr的结果。

  • 如果用代码完全模拟上述过程,每次要从arr中找到xi,再将其放到最前面,单次操作时间复杂度为O(n)。共有m次操作,所以时间复杂度为O(m * n), 考虑到n,m(1 <= n, m <= 100000),所以这种解法可能会超时。

  • 后来想到用哈希表来解,这样时间复杂度降为O(n)

代码:

"""输入处理,得到stack数组"""
n, m = map(int, input().split())
stack = []
for i in range(m):
    stack.append(int(input()))

"""使用哈希表来表示arr数组,初始将每个元素置为false,表示该元素未被访问"""
visited = [False] * (n + 1)

"""res是最终返回的序列"""
res = []
for i in stack[::-1]: # 由于stack中最后的操作数反而是在最前面,所以要逆序。
    """如果当前的元素未访问过,就将它放到最前面,并把visited数组相应位置置为True,表示已访问"""
    if not visited[i]:
        res.append(i)
        visited[i] = True

"""在visited数组中,如果某数未被访问,将其放到res中,由于是顺序遍历,可以保证其有序性"""
for i, v in enumerate(visited):
    if i != 0 and v == False:
        res.append(i)

print(" ".join(map(str, res)))

2 小Q怼方格纸

题目描述

小Q有一个W*H 的白色方格纸,小Q还有M毫升的红色颜料,每毫升可以把一个白色方格涂为红色。

小Q现在需要在方格纸上涂画出一个红色矩形,小Q想知道他能涂画出的最大的矩形面积是多少。

输入描述

输入包括三个正整数W,H,M(1 <= W, H <= 10^6, 1 <= M <= 10^12),以空格分割。

输出描述

输出一个正整数,表示能涂画出的最大矩形面积。

示例1

输入

4 4 10

输出

9


分析

  • 瞄了一眼数据规模:W,H,M(1 <= W, H <= 10^6, 1 <= M <= 10^12)。很明显算法时间复杂度不应过高,最好在O(n)量级上。
  • 一开始准备使用动态规划,但当时脑子有点糊,没想到从何处下手。后来想到使用贪心算法,时间复杂度可以很好的控制在O(n)
  • 暴力枚举宽度W,对于每次枚举的宽度Wi,此时最佳(最贪心)的高度targetH是多少?肯定是M//Wi啦!(//表示取整操作)。但实际高度H一定会满足H > targetH吗?所以要做判断,分两种情况处理,如果满足条件,则此时area = Wi * targetH;如果不满足条件,则area = Wi * h
  • 将每次计算的中间结果area保存下来,取最大值即可。

代码

w, h, m = map(int, input().split())
result = 0
for i in range(1, w + 1):
    targetH = m // i  # 理想的高度

    """如果理想破灭(targetH超出了实际高度h),则取h * i; h大于targetH,取 i * targetH"""
    if targetH > h:
        result = max(result, h * i)
    else:
        result = max(result, i * targetH)
print(result)

3 小Q怼士兵

题目描述

小Q将军掌管着n名士兵,第i名士兵有一个战斗力vi

小Q现在要把所有士兵分为三个分队,保证每个士兵都要进入一个分队,每个分队都至少有一名士兵。

每一只分队的战斗力值等于该分队中所有的士兵的战斗力按位异或(xor)起来。

小Q将军希望设计一个士兵分配方案使得三支分队的总战斗力之和最大,希望你能帮帮他。

输入描述

输入包括两行。
输入的第一行包括一个正整数n( 3 <= n <= 50) 表示士兵的人数。

输入的第二行包括n个正整数vi(0 <=vi <=255),表示每个士兵的战斗力。

输出描述

输出一个正整数,表示三支分队的总战斗力值最大是多少。

示例

输入

4
2 3 5 7

输出
17

说明:

一种有6种分配方案,战斗力之和分别是:
3 + 2 + (7 xor 5) = 7
5 + 2 + (7 xor 3) = 11
……
7 + 3 + (5 xor 2) = 17
最大战斗力之和为17.


分析

  • 看了题目就知道一定要用动态规划(虽然本人动态规划渣的一批,但还是能看出来要用这种思路的)
  • 随便google了下类似题目,没想到找到了原题(tencent这创新能力也是没谁了)原题链接: http://www.voidcn.com/article/p-xaeubejc-ko.html
  • 厚着脸皮把别代码copy下来,自己改了下,没想到通过了……

#include <vector>
#include <algorithm>
#include <iostream>


using namespace std;

#define ll long long

struct node {
    short a, b, c;

    node(int a = 0, int b = 0, int c = 0) : a(a), b(b), c(c) {

    }

    bool operator<(const node &other) const {
        if (a != other.a) {
            return a < other.a;
        }
        if (b != other.b) {
            return b < other.b;
        }
        return c < other.c;
    }
};

node que[2][256 * 51 * 51];

class TrySail {
public:

    int get(vector<int> strength) {
        int cur = 0;
        int pre = 1;
        int psz = 1;
        int csz = 0;
        que[pre][psz++] = node(0, 0, 0);
        int len = strength.size();

        for (int i = 0; i < len; i++) {
            int ss = strength[i];
            for (int j = 0; j < psz; j++) {
                que[cur][csz++] = que[pre][j];
                que[cur][csz++] = que[pre][j];
                que[cur][csz++] = que[pre][j];

                que[cur][csz - 1].a ^= ss;
                que[cur][csz - 2].b ^= ss;
                que[cur][csz - 3].c ^= ss;
            }

            sort(que[cur], que[cur] + csz);

            int newsz = 1;
            for (int k = 1; k < csz; k++) {
                if (que[cur][k - 1] < que[cur][k]) {
                    que[cur][newsz++] = que[cur][k];
                }
            }

            csz = newsz;
            swap(cur, pre);
            swap(csz, psz);
            csz = 0;
        }

        int ans = 0;
        for (int i = 0; i < psz; i++) {
            ans = max(ans, que[pre][i].a + que[pre][i].b + que[pre][i].c);
        }
        return ans;
    }
};

int main() {
    int n;
    int element;
    cin >> n;
    vector<int> input;
    for (int i = 0; i < n; ++i) {
        cin >> element;
        input.push_back(element);
    }
    TrySail *trySail = new TrySail();
    cout << trySail->get(input);
    return 0;
}
  • 一开始报内存不足错误,后来定位到错误是在第29行,node que[2][256 * 256 * 256];

把这个值改小,改成node que[2][256 * 51 * 51];后,通过所有测试。

感想:

  • 此次笔试题目前两题难度适中。最后一题有点难度,莫不是在考察面向搜索编程(逃)?

  • 动态规划还得再练练啊

发表日期: September 19th 2018

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 1 小Q怼序列
    1. 1.0.1. 题目描述
    2. 1.0.2. 输入描述
    3. 1.0.3. 输出描述
    4. 1.0.4. 示例1
    5. 1.0.5. 分析:
    6. 1.0.6. 代码:
  • 2. 2 小Q怼方格纸
    1. 2.0.1. 题目描述
    2. 2.0.2. 输入描述
    3. 2.0.3. 输出描述
    4. 2.0.4. 示例1
    5. 2.0.5. 分析
    6. 2.0.6. 代码
  • 3. 3 小Q怼士兵
    1. 3.0.1. 题目描述
    2. 3.0.2. 输入描述
    3. 3.0.3. 输出描述
    4. 3.0.4. 示例
    5. 3.0.5. 分析