PDD算法8.17秋招提前批笔试

记录一下. 总共4题，过题情况4/4第一题：给一个年份，输出一个比当前年份大，每一位均不相等的年份。数据10组以内，年份不超过6位数第二题：给n个二维坐标点，每个点有个ri，如果某个点与当前点距离不超过ri，则激活当前点时也会激活这个ri距离内的其他点，激活可以连锁。问激活任意一个点之后可以激活的最多总点数。n<=100第三题：给一个序列，每次可以花费1的代价让一个元素+1，求把序列变成单峰序列的最小代价。n<=10^5第四题：n个点，每个点有一个数字a[i]，有m条边，保证边是从编号小的点连向编号大的点，每条边有权值b[i]，表示走这条边至少需要b[i]个补给包。初始时补给包为0个，从1号点出发，每次从一个点i出发，可以选择拿不超过a[i]个补给包，拿了就不能丢，走过边也不会消耗补给包。问能不能走到终点n，如果可以，走到终点n时身上补给包最少是多少个。n<=10^5,m<=5*10^5第一题就是不断重复+1枚举年份，暴力判断即可。值得注意的是，测试数据的输入格式和样例的格式似乎有不同，我使用python写第一题直接在输入这就报错了，最后写了两种输入，用try给干过去了。如果直接用cpp的scanf应该不会有这个问题。第二题直接枚举初始激活点，然后暴力dfs每个次级激活点即可。这样做最坏是O(n^3)的，python直接超时了，优化了一下，不难发现，如果点x被点y激活，那么初始激活x的答案肯定<=初始激活y的答案，因此一个点如果在dfs中被找过，那就不需要将它作为初始激活点了，这样复杂度降低到O(n^2)第三题考虑设f[i]表示前i个数字组成递增序列的最小代价，g[i]表示从i开始到最后一个数字组成递减序列的最小代价，顺便记录达到最小代价时位置i的数字是多少，最后枚举峰的位置，统计代价最小值即可。复杂度O(n)第四题，如果直接按照题意硬做，我是不会的，因为选取更少的补给包这个决策是不利于最后走到n这个目标的。先考虑判断有无解该怎么做，可以发现，找到最大的边权，最终答案肯定不超过这个边权，设为mx。则我们可以在走的过程中进行贪心，记录f[i]表示走到位置i时，能获得的最大补给包数量。按顺序枚举点i（注意，这样枚举肯定是无后效性的，因为边都是小编号连向大编号），然后枚举点i的出边，假设有边(i,y,b[x])，如果f[i]>=b[x]说明这条边能走，则更新f[y]为max(f[y],f[i]+a[y])，注意，f[y]的值不应该超过mx，最后验证f[n]是否有正常转移过来的值即可判断是否有解。不难发现，如果我们限制了补给包的上限，我们就可以判断在这个上限下有没有解，且如果上限c1是可行的，那么对于任意c2>c1都是可行的，存在一个边界区分有无解，这是很好的性质，可以直接二分补给包上限，用上面的判定决定往左还是往右二分即可。复杂度O((n+m)logm)总体来说还是稍微有点trick的，前三题贪图代码简单直接用python写了，第四题怕py超时，用cpp过了。整体写起来需要想的东西比较多，只能说有几个月没写算法题了，略有生疏。希望给个面试。。。

1. 挑一个你最有成就感的项目，简单讲讲项目的目标是什么，你具体做了哪些事，最后效果怎么样？2. 假设你负责的某个产品功能，周一到周五的日活跃用户（DAU）很稳定，但上个周末的DAU比平时周末低了10%。你会从哪几个方面去分析，判断这到底是一次正常的波动，还是真的出了问题？3. 我们想优化一个功能，设计了一个A/B实验。实验结果显示，新版的点击率比旧版高，而且统计显著。但是，我们发现用户的次日留存率却比旧版低了。 a. 遇到这种情况，你会怎么办？你会建议全量上线新版本吗？为什么？ b. 如果要继续分析，你会重点看哪些数据，来找出留存率下降的原因？4. 很多推荐系统都有“信息茧房”的问题，就是用...

1.从 n 个商品中选取两个商品，如果它们的价值之和是 m 的倍数，那么这两个商品就可以免费拿走。问题是求有多少种这样的商品组合。解法思路类似两数之和：使用哈希表记录每个数对 m 取余的结果，满足条件的两个数需要它们的余数之和等于 m（或者两者余数都为 0），即 (a % m + b % m) % m == 0。2.每天都会有一只 ​​小动物来到你的农场 ，总共有 ​​n 只小动物​​会在 ​​n 天内依次到来​​，每个小动物需要每天吃si框食物，再总消耗不超过总食物框数的前提下，求最后能养多少动物解法：计算每只动物的总消耗（n -i * （nums[i]））,排序后从头开始累加到超过总食物框数即可3.从 N 个任务中，选出一个连续的区间（任务序列），使得这个区间内所有任务的分数之和 至少为 T​​（也就是满足总分数 ≥ T 的最小窗口）。而在这个满足条件的窗口中，找到一个 ​​最优解：即该窗口中 所有任务的难度的最大值 尽可能小​​。解法：滑动窗口+单调队列，双指针维护一个窗口，保证窗口内的分数总和 ≥ T；单调递减队列维护当前窗口中的最大难度值；4.在一条道路旁种了一排树，每棵树都有一个美观值。要求这条道路上任意一段连续的树的美观值之和都不能等于 M。为了达到这个目标，可以在任意位置插入一棵新的树（可自定义其美观值），问最少需要插入多少次新树，才能保证整条道路上不存在任何一段连续子序列的美观值和为 M。第四题我就单纯的计算了前缀和==m的个数，通过了20%。总体来说难度不大（点名mt），一小时a了3.2，最后一题没啥思路也不想写了。直接交卷。

选择没啥好说的算法第一图打了一个暴力拿了15%的分，看数据量必须nlogn，感觉得用线段树或者树状数组去logn维护，但到最后也没理清第二题手撕PCA，第一次用python写acm读入，大概写了一个结果输入有问题晕了第三题找满足条件的路径，写了一个dfs打了一发，T了，75%第四题看都没看，感觉是数学推导，肯定来不及写了这么难我是在打比赛么团子？Look at me！