3.9美团暑期实习笔试记录

考试时间：3月9日 10：00-12:00 是美团的第一场笔试，也是我的暑期实习的第一场笔试
题型：5道编程题，一道20分
前三题属于打卡题目，大部分都可以AC，但是第四题比较卡人，滑动窗口的设计也不是那么直接，卡了我1个小时；第五题难度比较大，我用普通的广度优先搜索超时了，只通过了10%，算下来能拿82分吧？做完告诉我可以做第二次，不知道要不要做第二次

这里只记录第四题与第五题

4. 小美拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。小美想知道，一共有多少种不同的删除方案？
输入：
    5 2
    2 5 3 4 20
输出：
    4
说明：
    一，删除[3]。
    二，删除[4]。
    三，删除[3,4]。
    四，删除[2]。

这道题我理解下来理解了很久，才看懂区间的意思是指连续子数组，可以删多少种连续子数组，我一开始用总乘积，和子数组乘积的方法进行滑动窗口，来看商是不是10^k的倍数，结果测试通过了，告诉我除数过大，无奈之下把所有数字都分解成5和2的倍数，计算5的个数和2的个数，结合滑动窗口得出答案

5. 小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。

现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？

事件共有 2 种：

1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。

2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。

注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。

输入描述：
第一行输入三个正整数n,m,q，代表总人数，初始的朋友关系数量，发生的事件数量。接下来的m行，每行输入两个正整数u,v，代表初始编号u的人和编号v的人是朋友关系。接下来的q行，每行输入三个正整数op,u,v，含义如题目描述所述。

输出描述
对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。

这道题会的大哥可以评论区留言