返回信息流1、给定S, A, B, P, 初始arr[0] = S, 接下来arr[i+1] = (arr[i] * A + B) % P, 并且arr数组里的每个数字最多出现两次，当某个数字已经出现2次时，终止序列生成。给定两组S, A, B, P分别生成两个序列，求两个序列的最长公共子序列
这题我暴力法生成两个序列，然后用动态规划求最长公共子序列。结果超时。
自测的时候当 P 特别大的时候，生成的序列太长。总感觉不需要生成两个序列，但是没有思路。。。
2、三维坐标系中，有一个半径为1球心在原点的圆球，还有一个没有限制的椭球，分别求圆球在椭球内部和椭球外部的表面积。椭球公式为：(x-a)^2/d^2 + (y-b)^2/e^2 + (z-c)^2/f^2 = 1。
输入为 a,b,c,d,e,f， 输出为2个值，分别代表两个表面积。
完全没有思路的一题。。。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #98873同步于 2020/3/25
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】快手暑期实习笔试的两道算法题，大神们帮帮忙
lyrgwlr
2020/3/25镜像同步35 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
第一题的P是素数吗？
推了一下感觉只用讨论A和P是不是互素或者这是两个等价序列；
讨论过后如果是互素的话序列长度不会超过5(猜测)
第二题椭球和单位球截面是个圆形，联立一下求解平面方程然后算距离就可以了？可能需要注意一下椭球可能和圆球有两个截面。
当然，以上纯属猜测，勿喷。
额，试着做一下第一题。本来按照题主的最后的想法，试图不依靠序列的生成来解决，但是没想到好的方法，所以换了一个思路。
按照之前的做法，生成序列需要p1+p2的时间复杂度，按照一般的最长公共子序列的做法需要p1*p2的时间复杂度，近似平方级别的时间复杂度。所以尝试优化到NlogN(线性的以及更小的复杂度没想出来）。
对于两个序列a和b，已知它们之中的元素不会重复，构造出一个以，其中一个序列的元素在另外一个序列出现时的下标（下标唯一或不存在，如果不存在那就不考虑），做为元素并原顺序依次排列的新数组。构造过程可以借助哈希方法以线性复杂度构造。这道题就转化为了求最长递增子序列了，我记得这个可以优化到NlogN, 不知道对不对(~_~;) 大佬们轻拍