百度0313机试

单选题

考的很杂。

SQL指令：NULL值相关概念。EXISTS。SELECT NULL，SELECT 0，SELECT FALSE区别。聚合函数AVG。

计算机网络： TCP拥塞控制，快恢复啥的。

数据结构：n个数出栈有几种情况（有公式但是忘了），经典前序中序构造树结构，哈希表。

操作系统：银行家算法，死锁避免

Linux指令：SSH（如何把客户机的公钥添加到服务器的列表中），VIM（替换，删除等指令），Top（如何查看指定PID的）

---忘得差不多了

多选题

C++八股

将3*3的二维数组复制到一维数组中，void fun(int (*p)[3], *q) {....}，问这个函数怎么写

const char * p, const char * const p, char * const p的区别。

vector<string>::iterator iter， 下列操作错误的是 *iter.empty() iter->empty() ++ *iter iter++ ->empty()

---两年没怎么用，忘了都。。。

编程题

1 判断输入字符串排序后是不是“Baidu”

2 构造字符串，使用 'r' 'e' 'd'三种字符构造回文子串为x的字符串，构造结果长度不超过10000.

先用相同的字符使得回文子串逼近x，然后用不同的字符补齐剩下的就好了。（1个字符就是1个回文子串）

def f(n):
    return n * (n + 1) // 2

chars = 'red'
x = int(input())
if x <= 10000:
    print(''.join(chars[i % 3] for i in range(x)))
else:
    b = 0
    while True:
        b += 1
        if f(b) > x:
            b -= 1
            break
    res = 'd'*b
    extra = []
    for i in range(x - f(b)):
        extra.append(chars[i % 3])
    print(res + ''.join(extra))

3 一个树，每个节点有红蓝两种颜色，树上每条边的权值定义为将这条边删除构成的两棵树中，不同颜色连通区域之差的绝对值

两遍DFS，第一遍求每个子树的连通区域个数，第二次求每条边的权值 n <= 20w，不知道为啥只能50%，理论上复杂度不高e，大佬们ddbug吧。

n = int(input())
color = input()
g = [[] for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    g[u].append(v)
    g[v].append(u)
value = [0]*n
vis = [0]*n
def dfs(x):
    vis[x] = 1
    same = 0
    res = 0
    for nx in g[x]:
        if vis[nx]:
            continue
        if color[nx] == color[x]:
            same += 1
        res += dfs(nx)

    if same:
        res = res - same + 1
    else:
        res += 1
    value[x] = res
    return res

dfs(0)
ret = 0


def dfs1(x):
    global ret
    vis[x] = 2
    for nx in g[x]:
        if vis[nx] == 2:
            continue
        if color[nx] == color[x]:
            ret += abs(value[0] + 1 - value[nx] - value[nx])
        else:
            ret += abs(value[0] - value[nx] - value[nx])
        dfs1(nx)

dfs1(0)
print(ret)

---------------------------------------

考研时做烂的东西，现在全忘光了。。。