个人博客
www.tothefor.com
蓝桥杯复习知识点汇总
纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。
目录计算最长上升子序列的长度。
动态规划时间复杂度：O(n*n)
数组 d[ i ] 表示前 i 个数以 A[ i ] 结尾的最长上升子序列长度。
例如：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。
前1个数 d(1)=1 子序列为2；
前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7
前3个数 在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1
前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5
前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6
前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4
前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3
前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8（d[5]>d[6]）
前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9（前面中d[8]最大）
最后求d数组中的最大值即可。
状态：
F [ i ] = max { F [ j ] + 1 ，F [ i ] } (1 <= j < i，A[ j ] < A[ i ])
当然了，开始每一个数都是长度为1的，F [ i ] = 1 (1 <= i <= n)
代码实现import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
public static Scanner sc = new Scanner(System.in);
public static int maxd = 10000+7;
public static int INF = 0x3f3f3f3f;
public static int mod = 998244353;
public static int[] a = new int[maxd];
public static int[] f = new int[maxd];
public static int ans = -1*INF;
public static void main(String[] args) throws Exception {
int n = nextInt();
for(int i=1;i<=n;++i){
a[i]=nextInt();
f[i]=1;
}
for(int i=1; i<=n; i++){
for(int j=1; j
输入输出：
//输入
6
1 5 2 4 6 9
//输出
5
二分
时间复杂度：O(n*logn)
新建一个 low 数组，low [ i ]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护 low 数组，对于每一个a[ i ]，如果a[ i ] > low [当前最长的LIS长度]，就把 a [ i ]接到当前最长的LIS后面，即low [++当前最长的LIS长度] = a [ i ]。 否则，就用 a [ i ] 去更新 low 数组（在 low 数组中找到第一个大于等于a [ i ] 的位置。）。
具体更新方法：在low数组中找到第一个大于等于a [ i ]的元素low [ j ]，用a [ i ]去更新 low [ j ]。如果从头到尾扫一遍 low 数组的话，时间复杂度仍是O(n^2)。我们注意到 low 数组内部一定是单调不降的，所有我们可以二分 low 数组，找出第一个大于等于a[ i ]的元素。
代码实现
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
public static Scanner sc = new Scanner(System.in);
public static int maxd = 100000+7;
public static int INF = 0x3f3f3f3f;
public static int mod = 998244353;
public static int[] low = new int[maxd];
public static int[] a = new int[maxd];
public static int bin_query(int[] arr,int r,int x){ //在arr数组中找第一个大于等于x的位置
int l = 1;
while(l<=r){
int mid = (r+l)/2;
if(arr[mid]<=x) l=mid+1;
else r = mid-1;
}
return l;
}
public static void main(String[] args) throws Exception {
int n = nextInt();
for(int i=1;i<=n;++i){
a[i] = nextInt();
low[i] = INF;
}
low[1]=a[1];
int ans = 1; //初始化长度为1
for(int i=1;i<=n;++i){
if(a[i]>low[ans]) low[++ans] = a[i];
else{
int ind = bin_query(low,ans,a[i]);
low[ind] = a[i];
}
}
System.out.println(ans);
closeAll();
}
public static void cinInit(){
cin.wordChars('a', 'z');
cin.wordChars('A', 'Z');
cin.wordChars(128 + 32, 255);
cin.whitespaceChars(0, ' ');
cin.commentChar('/');
cin.quoteChar('"');
cin.quoteChar(''');
cin.parseNumbers(); //可单独使用来还原数字
}
public static int log(int x){ //log方法是以2为底,求x的对数。java自带的log是以e为底的
return (int) (Math.log(x)/Math.log(2));
}
public static int nextInt() throws Exception{
cin.nextToken();
return (int) cin.nval;
}
public static long nextLong() throws Exception{
cin.nextToken();
return (long) cin.nval;
}
public static double nextDouble() throws Exception{
cin.nextToken();
return cin.nval;
}
public static String nextString() throws Exception{
cin.nextToken();
return cin.sval;
}
public static void closeAll() throws Exception {
cout.close();
in.close();
out.close();
}
}
输入输出：
//输入
10
2
3
4
5
6
7
8
9
10
1
//输出
9
