腾讯2024后台实习生笔试 473/500

小红的图上染色（100%）

• 1e5点数的无向图，有些边是红色，定义一个“好点”当且仅当该点所有邻边都是红边
• 碰到无色的边则标记两个点，最后未被标记的点数就是答案

小红的链表断裂（100%）

• 总长1e5的链表，元素不重复，如果可以把该链表一分为二重新拼接后升序则返回true，否则返回false
• 遍历一遍如果没有降序则为true，碰到第一个降序则标记位置重新拼接，整体升序返回true，否则false

小红的连通图（100%）

• 1e5点数的无向图，有多少种方法使得添加一条边后图连通
• 并查集合并，最后统计各个集合的点数，若：
• 只有一个集合：答案为n * (n - 1) / 2 - m（n个点m条边）
• 两个集合：答案为两个集合的数量乘积
• 否则：答案为0

小红的数组分割（73%）

• 大小为400的数组，元素大小为1e9，将数组分割成k段，使得每段内部按位异或后全部求和，求和的最大值
• 应该是区间dp，写了个假算法

小红的tencent矩阵（100%）

• 1000*1000的小写字母矩阵，可以从任意位置出发，有多少种方法使得走6步后恰好形成“tencent”
• BFS，记录当前是第几步，走满7步则统计答案