笔试-201909204腾讯-笔试题解

Posted on | Edited on | In | Views:

2019年09月20日，腾讯笔试，共5道题。整理下题解做下总结，希望下次做的更好。

目录

  1. 电话号码
  2. 两两配对
  3. 分组
  4. 最小非零元素
  5. 异或值

题解

1. 电话号码

题意

电话号码是一个长度为11的以8开头的数字串。
给定一个数字串S，每次可以任选一个数字删除，可以操作任意次，是否可以把S变成一个合法的电话号码？

数据范围

$ T ≤ 100 $ 组测试
每组测试，字符串长度 $ n ≤ 100 $

解法

约定8为开头称为在左边，方便解法的描述。
从左向右扫一遍数字串str[0,n)，找第一个出现8的位置。
如果没有出现，肯定形不成合法电话号码，输出NO。
如果存在8，设位置为p，判断字符串str[p, n)的长度是否够11即可。

2. 两两配对

题意

$M$名员工每人工作都有个拖延时间 $t_i$。
现有$M/2$个工作，每个都需要两名员工参与，第$i$份工作所需完成的时间为两员工的拖延时间总和。
如何分配使完成所有工作的时间最短？输出最短时间。

数据范围

$ (1 ≤ n ≤ 1e5) $ 行
每行一个x和y表示x名员工的拖延时间为y $ (1 ≤ y ≤ 10^9) $
保证所有x的和为M $ (2 ≤ M ≤ 10^9) $ 且 M 为偶数

解法

贪心。耗时长的员工尽可能和耗时短的员工分配到一块儿。
具体做法：先按照时间进行排序，然后从两端向中间遍历，找和值最大的即可。

3. 分组

题意

$n$名员工每人有个战斗值$x_i$，现将他们分为两组，人数只差不超过$1$且战斗力之和相差尽可能小。

数据范围

$ (1 ≤ T ≤ 10) $ 组测试
对于每组测试 员工数 $ 2 ≤ n ≤ 100 $ ，战斗力 $ 1 ≤ x_i ≤ 10^5 $，保证战斗力之和不超过 $ 10^5 $。

解法

二维01背包。
设所有人总和为sum，
求出来n/2和n-n/2人分别能组成的战力之和的所有状态dp[][]，然后找dp[][]和sum - dp[][]的差值最小的情况。

动态规划的状态含义为dp[j][k]表示j个人构成总和为k的方案，其转移方程为dp[j][k] |= dp[j-1][k-x[i]]

关键代码如下，已加入一些优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定义以及数据读入部分略
dp[0][0] = 1;
for(int i = 0; i < n; ++i){
    for(int j = min(i, n-n/2) - 1; j >= 0; --j){
        for(int k = sum/2; k >= 0; --k){
            dp[j + 1][k + x[i]] |= dp[j][k];
        }
    }
}
for(int i = sum >> 1; i >= 0; --i){
    if(dp[n>>1][i] || dp[n-(n>>1)][i]){
        printf("%d %d\n", i, sum - i);
        break;
    }
}

容易发现，其实dp[][]的状态，我们只标记0和1即可，因此可以用char或bool甚至bitset来减少些常数。

唉，弄巧成拙，想用set优化一下结果反而多了个log，心塞塞的。

4. 最小非零元素

题意

对长度为$n$的正整数序列$a_i$执行$k$轮如下操作：

  1. 发现最小的非零数字$x$
  2. 打印$x$
  3. 将序列中所有非零元素减$x$

数据范围

第一行 $ 1 ≤ n, k ≤ 10^5 $
第二行 $ 1 ≤ a_i ≤ 10^9 $

解法

本质是不断找序列中的最小值，需要排个序先，具体写法不限于一下两种。

写法1：
从小到大排序。
设置一个变量v记录之前的最小值，初始设v=0。
然后从小端开始遍历，每次遇到x[i] > v得到一个ans = x[i] - v并重新设置v = x[i].
一直遍历输出k个值，不够的话就输出0。

写法2:
从小到大排序。
对排序后的序列$a_i$求其差分序列$b_i$，新序列$b_i$的前k个非零数字即为答案，不够补0。

5. 异或值

题意

两个长度均为$n$的序列中各取一个数求和会有$n^2$个值，求所有和的异或值。

数据范围

$ 1 ≤ n ≤ 200000 $
$ 0 ≤ a_i ≤ 2^{30} $

解法

吃鲸，竟然是ARC92b !!!

这题并没有及时做出来，心塞塞的

回顾总结

第1题比较简单，但是一开始忽略了长度11。修改后又把11错成了判断12。再修改竟然只过了90%，多交了几次后来竟然过了，看来是哪里出现了问题但是主办方及时修正了。

第2题和第4题比较顺利。

第3题想了下背包dp，本来想用set优化一下，结果反而造成了复杂度的增加，平白无故多了个log。感觉用unordered_set就好了。
事后讨论，发现直接用个char型的就行，当然也可以用bitset来优化些常数。

第5题没来的及做，知道是算算每个位的贡献，但是没来得及做。去修第3题去了。

还是需要多加练习，有许多优化的小技巧需要提高熟练度，有些题目的解题思路需要学习比如第5题。

感谢各位大佬走过路过还不忘打赏！！！