https://www.nowcoder.com/acm/contest/145/E 给定k 构造一个包含k个四阶完全子图的图 打表找规律可得 70阶完全图中四阶完全子图的数量略微小于1e6 所以再用剩下的五个点来凑 数量上可以满足1e6 找最大的p阶完全图 其四阶完全子图的数量小于等于k 四个for循环来枚举剩下的五个点 如何凑出k即可 #include <bits/stdc++.h>

https://www.nowcoder.com/acm/contest/143/H 首先数据有毒 不止1e5 题目要求下标字典序第k小的LIS 既然是以下标决定字典序 那就维护一个dp[i]代表以a[i]为首项的所有LIS个数 这个可以提前线段树之类的搞出来 为求第k小 故i从最小的下标1开始遍历 如果dp[i]<k 说明当前这个下标太小了不合要求 k减去dp[i] 如果以a[i]为首的L

https://www.nowcoder.com/acm/contest/143/F 第i个钻石被拿<=>[1,i-1]中所有比第i个钻石大的钻石都没被拿 算出这个概率 乘上次数1 就是期望 累加即可 菜的一批 #include <bits/stdc++.h>using namespace std;#define ll long long#define M 998244353struc

https://www.nowcoder.com/acm/contest/143/D 给一个1 3 ... n-1的a序列 和一个2 4 ... n的排列的b序列 问归并后最小逆序对数 肯定考虑用a插b 因为a是有序的(无脑解释) 首先有个结论 a序列插入时 a[i+1]插入的最优位置一定在a[i]的右边 //(1,i)|(b[j]>a[i]) 代表[1,n]内有多少b[j]大于a[i]

https://www.nowcoder.com/acm/contest/147/G 首先要了解LCS和LIS可以相互转换 题目保证前三个串中每个数最多出现两次 所以拿四串中数的下标和前三个串中的所有相同数的下标组成四维偏序 然后CDQ求解 但是要注意的是 用CDQ求LIS时和普通CDQ不太一样 要先处理左区间内部 再处理左区间对右区间的影响 最后处理右区间内部 比如 1 2 3 4这个例

链接：https://www.nowcoder.com/acm/contest/143/D 来源：牛客网   Kanade has an even number n and a permutation b of all of the even numbers in [1,n] Let a denote an array [1,3,5....n-1] , now you need to find