2022.10.08-地平线笔试第四场-75分钟-70左右

气死，做完后复制了两个编程题代码，题目都抄到注释里了，还有输入输出，结果一出来就去写合见工业软件的笔试复盘了，忘了把历史剪贴板里的代码粘贴出来。。。

两个编程题 25'*2

都只过了60%，-20分

第一题是输入一个无向图，n个节点，任意两个节点之间都有边，
其中有m条边的权值为1，其他边权值为0，10万级的顶点和边数
求最小生成树

思路：vector<unordered_set<int>>(n+1) 存储权为 1 的邻居顶点号，
并查集，合并那些权值为0的边的顶点，每合并一个把它的visit标为1，后续只处理为false的顶点。</int>

错在：比如 1--2--4，3--4，这些边的权全为0，处理1时把2标成true，之后不会处理2了，处理3时把4标成true，之后不会处理4了，于是2--4这条边不会被遍历到去合并了，于是12、34被割裂开来了，需要消耗1条权为 1 的边。

第二题是求 max f(x), 其中 1<=x<=m
输入一个数组 a[0~n-1] n个数，如果x的第i位为1，那么ai就会加入到f(x)里，1<=ai<=10000, 1<=m<=100000
即 f(x) 就是 x 为 1 的那些位对应的 ai 的和
输入的m有n个二进制位，从低位往高位输入构成一个01字符串

思路：记录a的前缀和，sa[i] 表示 a[0~i] 的和，从 n-1 往 1 遍历 m，用 p 记录 m 上为 1 的那些位对应的 ai 的和，初始化 p=0
如果字符m[i]为0，continue
如果字符m[i]为1，maxs=max(maxs, sa[i-1]+p)，然后更新当前位置的 p = p + a[i]
最后单独考虑m[0], 如果为 1 就更新 p，这时 p 就是 f(m)
也就是说只考虑把m的某一位从1改成0，低位就都可以是1了。

错在：不知道。

多 1*5'

which 参数用于gcc的链接阶段
A. --which-archive
B. --no-as-needed
C. -Wno-unused-function
D. --unresolved-symbols=ignore-in-shared-libs

填空 5*5'

template<int T>
class A{
public:
    A(){cout<<T<<"\n";
};

int main(){
    const int x=5;
    A<x> a;
    *(int*)(&x)=6;
    A<x> b;
    const int* p=&x<<"\n";
    return 0;
}

输出：556
why？

5*4' 单选

不属于数据库中用于实现索引的数据结构是

A. Bitmap
B. Hash 表
C. B+树
D. Skip List

B?