百度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)
---------------------------------------
考研时做烂的东西，现在全忘光了。。。
