滴滴软开秋招笔试——算法真题

时间：2024.10

1、小A正在玩游戏，在游戏中一共有n个不同星球，星球间共有m条双向航道，小A的任务是摧毀这些星球。若有多个星球间两两可达，则我们称它们展于同一个联盟。特别的，若一个星球与其他星球都没有航道，则也称这个星球为一个联盟。小A将按照星球的编号从小到大依次推毀各个星球，当一个星球被摧毁后，与之相连的航道也将相继摧毁，现在小A想知道在每个星球被摧毁时，还剩下多少个联盟。不同星球间可能有多条航道，但每条航道连接的两个星球必然不同。上述题意可以被简化为，给定n个点，m条边的无向图，按照编号大小依次删除各个节点，请问在每个节点被删除时，还剩下多少个连通块。保证给定图无自环，但可能有重边。
输入描述：第一行两个正整数n,m，表示星球数与航道数。接下来m行，每行2个正整数u, v表示两星球有一条航道
输出描述：输出一行n个正整数，表示答案
示例：输入：
5 6
1 2
2 3
3 1
4 5
5 1
2 4
输出：1 2 1 1 0

2、小明有一个含有n个数的序列a1,a2, ...,an，对这个序列进行Q次询问，每次询问的形式为l r m，表示他要找到一个非负整数k，使得0<=k<=m且al异或al+1异或...异或ar异或k最大，对于每次询问，小明想要知道al异或al+1异或...异或ar异或k最大値。
输入描述：第一行输入两个正整数n,Q，分别表示序列中数的个数以及询向次数
第二行输入n个非负整数a1,a2, ...,an
第三行输入Q个正整数l1,l2, ...,lQ，表示每次询问对应的左端点
第四行输入Q个正整数r1,r2, ...,rQ，表示每次询问对应的右端点
第五行输入Q个非负整数m1,m2, ...,mQ，表示每次询问对应的k能选择的最大值
输出描述：为了避免较大的输出量，你需要将所有询问得到的答案全部异或起来再输出，也就是仅输出一个非负整数
示例：输入：
5 6
2 0 3 6 5
2 1 3
4 3 5
3 1 0
输出：6