1.最长上升子序列二题目给定一个长度为 n 的数组a求它的最长严格上升子序列的长度。所谓子序列指一个数组删掉一些数也可以不删之后形成的新数组。例如 [1,5,3,7,3] 数组其子序列有[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。数据范围 0≤n≤1e5−1e9a[i]1e9要求时间复杂度 O(nlogn) 空间复杂度 O(n)实例1输入 [1,4,7,5,6] 返回值4 说明最长上升子序列为 [1,4,5,6] 长度为4。分析最长递增子序列又叫做LIS这道题的解法有两种一种是动态规划一种是贪心二分。动态规划比较好理解时间复杂度是O(N^2)贪心二分的时间复杂度是O(N^logN)。数据量比较小的情况下我们就用动态规划来做因为动态规划比较好理解而且好写如果数据量比较大就用贪心二分。这道题的数据就比较大了所以只能用贪心二分了。举个例子来讲解算法原理假设有一个数组【14756】。我们遍历这个数组当我们遍历到某一个位置的时候其实前面就已经形成了很多的上升子序列。比如我遍历到5的时候前面已经形成了【1】【4】【7】【14】【17】【47】【147】这几个上升子序列。当我们遍历这个5的时候我们一定是想把这个5接在已经形成了的序列的后面然后形成一个更长的上升子序列。如果我们把已经形成的序列都存起来的话我们就只需要看看5是否大于子序列的最后一个元素所以我们只需要存子序列最后一个元素的值以及子序列的长度。其实我们没有必要存这么多长度2子序列的末尾元素的值因为当我们遍历到5的时候只需要看看是否大于所有长度为2子序列的末尾的最小值就可以了。当我们遍历到5的时候与每个长度的子序列的末尾的最小值进行比较比1大说明可以形成长度为2的子序列比4大说明可以形成长度为3的子序列比7小说明遍历到5的时候最多只能形成长度为3的递增子序列此时长度为3的最长递增子序列的末尾的最小值就被更新成了5。但是如果这样遍历去一个一个比较5该放在哪里的话那时间复杂度不也是O(N^2)吗跟动态规划的解法没有区别啊因为我们要找的那个位置的值是大于等于5的不符合条件的位置是小于5的数组存在二段性并且由于插入规则数组还是升序的所以我们可以用二分这样我们的时间复杂度就降到了O(N^logN)。边界情况当数组中一个值都没有的时候或者要插入的值大于数组中的所有值的时候不需要二分查找特殊处理即可具体怎么处理看代码。代码class Solution { int dp[100010]{0};//数组下标i是子序列的长度i位置的值是长度为i的所有子序列中最后一个元素最小的值 int pos0;//填到dp数组的哪一个位置了 表示最长上升子序列的长度 public: int LIS(vectorint a) { for(auto e:a) { //处理插入第一个和插入的值比dp数组中的所有值都大的时候 if(pos0||edp[pos]) { dp[pos]e; } else { //二分找插入位置 int left1,rightpos; while(leftright) { int midleft(right-left)/2; if(dp[mid]e) rightmid; else leftmid1; } dp[left]e; } } return pos; } };2.爱吃素题目牛妹是一个爱吃素的小女孩所以很多素数都害怕被她吃掉。一天两个数字a和b为了防止被吃掉决定和彼此相乘在一起这样被吃掉的风险就会大大降低但仍有一定的可能被吃掉请你判断他们相乘后是否仍有被吃掉的风险。也就是说请你判断a×b是否是素数。素数是指大于1的正整数中有且仅有两个因子的数。输入描述:输入第一行是一个整数T(1≤T≤10)表示测试组数。 接下来T行每一行两个整数,(1≤,≤1e11)。输出描述对于每一行输入若输入满足a×b是素数输出一行YES否则输出一行NO没有引号。实例输入3 2 3 1 7 1 4输出NO YES NO分析说实话刚开始看到这道题我以为很简单以为考察的是试除法判断素数直接上手就写然后直接就错了。然后我就仔细看了看题发现数据量很大1e11我又把int改成long long又试了一下还是不对数据太大会循环1e11次会超时一般数据量1e8才能过所以只能单独判断一个数是否是素数不能乘在一起在判断其实乘在一起long long也存不下。由题可知ab都是大于等于1的。当a1并且b1时a*b一定不是素数因为a*b一定有ab这两个因子。所以a和b一定得有一个为1不能都大与1并且一个为1另一个也得是素数这样他们乘在一起才是素数。代码#includeiostream #includecmath using namespace std; bool isPrim(long long x) { if(x2) return false; for(int i2;isqrt(x);i) { if(x%i0) return false; } return true; } int main() { int t; cint; while(t--) { long long a,b; cinab; if((a1isPrim(b))||(b1isPrim(a))) { coutYESendl; } else { coutNOendl; } } return 0; }判断素数那里一定要注意小于2的一定不是素数