• 【AcWing 学习】基础算法

    AcWing 基础算法

    参考：常用代码模板1——基础算法 - AcWing

    排序

    快速排序

    思想：分治

    流程：

    1. 确定分界点： q [ l ] q[l] q[l]、 q [ ( l + r ) / 2 ] q[(l+r)/2] q[(l+r)/2]、 q [ r ] q[r] q[r]、随机点，记值为 x
    2. 调整区间为，分界点左边的数都 <= x，分界点右边的数都 >= x
    3. 递归处理左右两段

    心得：有关边界问题建议背一个模板

    模板：

    // 使用 do-while
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[(l + r) >> 1]; // 轴点选择为中心元素
    while (i < j)
    {
        do i ++ ; while (q[i] < x); // *
        do j -- ; while (q[j] > x); // *
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

// 使用 while
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j)
    {
        while (q[++i] < x) {} // *
        while (q[--j] > x) {} // *
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    模板题785. 快速排序 - AcWing题库

    #include 
using namespace std;

const int N = 100010;
int a[N];

void quick_sort(int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = a[(l + r) >> 1];
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    quick_sort(0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    Leetcode：912. 排序数组 - 力扣（LeetCode）

    归并排序

    思想：分治

    流程：

    1. 确定分界点： m i d = ( l + r ) > > 1 mid = (l + r) >> 1 mid=(l+r)>>1
    2. 递归排序 left, right 部分
    3. 归并：合二为一

    模板：

    void merge_sort(int q[], int l, int r) {
	if (l >= r ) return;

	// 确定分界点
	int mid = (l + r) >> 1;
	// 递归排序左右两部分
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);

	// 归并：合二为一
	int k = 0, i = l, j = mid + 1;
	// 满足条件的情况下，将小的元素放入 tmp 中
	while (i <= mid && j <= r)
        tmp[k++] = (q[i] <= q[j]) ? q[i++] : q[j++];
	// 将剩余元素放到入 tmp
	while (i <= mid) tmp[k++] = q[i++];
	while (j <= r) tmp[k++] = q[j++];
	// 将 tmp 中的元素拷贝到 q
	for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    模板题：787. 归并排序 - AcWing题库

    #include 
using namespace std;
const int N = 1e5 + 10;

int a[N], tmp[N];

void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) >> 1;
    // 递归左右两部分
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    // 归并
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    merge_sort(0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    912. 排序数组 - 力扣（LeetCode）：

    class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    void mergeSort(int[] q, int l, int r) {
        if (l >= r) return;
        int mid = (l + r) >> 1;
        // 递归排序左右两部分
        mergeSort(q, l, mid);
        mergeSort(q, mid + 1, r);

        // 归并
        int[] tmp = new int[r - l + 1]; // 开太大的数组会超时
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) 
            tmp[k++] = (q[i] <= q[j]) ? q[i++] : q[j++];
        while (i <= mid) tmp[k++] = q[i++];
        while (j <= r) tmp[k++] = q[j++];
        for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; // 赋值
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    二分

    整数二分

    二分的本质：找到一个性质，可以将数据一分为二，一边满足一边不满足

    有序一定可以用二分，不有序不一定不可以用二分

    二分每次都会保证新的区间中一定会包含答案（处理边界问题）

    模板：

    bool check(int x) { /* ... */ } // 检查 x 是否满足某种性质

// 区间 [l, r] 被划分成 [l, mid] 和 [mid + 1, r] 时使用
int bsearch_1(int l, int r) {
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check(mid))	r = mid;
		else l = mid + 1;
	}
	if (check(l)) return l;
	return -1;
}

// 区间 [l, r] 被划分成 [l, mid - 1] 和 [mid, r] 时使用
int bsearch_2(int l, int r) {
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;	
	}
	return l;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    模板题：789. 数的范围 - AcWing题库

    import java.util.*;

class Main {
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
        
       int n = sc.nextInt();
       int q = sc.nextInt();
       
       int[] arr = new int[n];
       for (int i = 0; i < n; i++)
           arr[i] = sc.nextInt();
           
        while (q-- > 0) {
          int x = sc.nextInt();
           
          int l = 0, r = n - 1;
          while (l < r) {
              int mid = (l + r) >> 1;
              if (arr[mid] >= x) r = mid;
              else l = mid + 1;
          }
          if (arr[l] != x) System.out.println("-1 -1");
          else {
              System.out.print(l + " ");
              l = 0;  r = n - 1;
              while (l < r) {
                  int mid = (l + r + 1) >> 1;
                  if (arr[mid] <= x) l = mid;
                  else r = mid - 1;
              }
              System.out.print(r + "\n");
          }
      }
    }    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    浮点数二分

    浮点数二分比较简单，不需要考虑太多边界问题

    模板：

    bool check(double x) {/* ... */} // 检查 x 是否满足某种性质

double bsearch_3(double l, double r) 
{ 
	const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
	while (r - l > eps) {
		double mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}	
	return l;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    模板题：790. 数的三次方根 - AcWing题库

    import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double n = sc.nextDouble();
        
        double l = -10000, r = 10000;
        while (r - l > 1e-8) {
            double mid = (l + r) / 2;
            if (mid * mid * mid <= n) l = mid;
            else r = mid;
        }
        System.out.println(String.format("%.6f", l));
    }    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    高精度

    高精度加法

    模板：

    // C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B) {
	if (A.size() < B.size()) return add(B, A);

	vector<int> C;
	int t = 0; // 进位
	for (int i = 0; i < A.size(); i++) { // 根据长的来加
		t += A[i];
		if (i < B.size()) t += B[i];
		c.push_back(t % 10);
		t /= 10;
	}
	if (t) C.push_back(t);
	return C;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    模板题：791. 高精度加法 - AcWing题库

    Java 有大数类，可以直接用来进行大数运算

    import java.math.BigInteger;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		BigInteger a = new BigInteger(reader.readLine());
		BigInteger b = new BigInteger(reader.readLine());
		System.out.println(a.add(b));
		reader.close();
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    不使用大数类的做法：

    • 使用 String：
    import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        System.out.println(add(a, b));
    }
    
    public static String add(String a, String b) {
        if (a.length() < b.length()) return add(b, a);
        
        StringBuffer sb = new StringBuffer();
        int t = 0; // 进位
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
            int n1 = i >= 0 ? a.charAt(i) - '0' : 0;
            int n2 = j >= 0 ? b.charAt(j) - '0' : 0;
            t += n1 + n2;
            sb.append(t % 10);
            t /= 10;
        }
        if (t > 0) sb.append(t);
        
        return sb.reverse().toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 使用 List：
    import java.util.*;

public class Main {
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in) ;
	    String a = sc.next();
	    String b = sc.next();
	    
	    List<Integer> res = add(a, b);
	    for (int i = res.size() - 1; i >= 0; i--)
	        System.out.print(res.get(i));
	}

	public static List<Integer> add(String a, String b) {
	    List<Integer> temp = new ArrayList<>();
	    int t = 0; // 进位
	    for (int i = a.length() - 1, j = b.length() - 1;; i >= 0 || j >= 0; i--, j--) {
	        int n1 = i >= 0 ? a.charAt(i) - '0' : 0;
	        int n2 = j >= 0 ? b.charAt(j) - '0' : 0;
	        t += n1 + n2;
	        temp.add(t % 10); 
	        t /= 10;
	    }
	    if (t > 0) temp.add(t);
	    return temp;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    高精度减法

    模板：

    // C = A - B, 满足 A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vsctor<int> &B) {
	vector<int> C;
	int t = 0;
	for (int i = 0; i < A.size(); i++) {
		t  = A[i] - t;	
		if (i < B.size()) t  -= B[i];
		C.push_back((t + 10) % 10);
		t = (t < 0) ? 1 : 0;
	}
	// 去掉前置的 0
	while (C.size() > 1 && C.back() == 0) c.pop_back();
	return C;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    模板题：792. 高精度减法 - AcWing题库

    import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        String a, b;
        Scanner sc = new Scanner(System.in);
        a = sc.next();
        b = sc.next();
        char[] A = new char[a.length()], B = new char[b.length()];
        for (int i = a.length() - 1; i >= 0; i --) A[a.length() - 1 - i] = a.charAt(i);
        for (int i = b.length() - 1; i >= 0; i --) B[b.length() - 1 - i] = b.charAt(i);       
        if (cmp(A, B)) {
            String c = sub(A, B);
            System.out.println(c);
        }else{
            String c = sub(B, A);
            System.out.println("-" + c);
        }
    }
    
    public static String sub(char[] A, char[] B){
        StringBuffer sb = new StringBuffer();
        int t = 0;
        for (int i = 0; i < A.length; i ++) {
            t = A[i] - '0' - t; // 剪去借位
            if (i < B.length) t -= B[i] - '0'; 
            sb.append((t + 10) % 10);
            t = (t < 0) ? 1 : 0;
        }
        String s = sb.reverse().toString();
        // 截去开头的 0
        int i = 0;
        for (; i < s.length() - 1; i ++)
            if (s.charAt(i) != '0') break;
        return s.substring(i, s.length());
    }

    public static boolean cmp(char[] A, char[] B) {
        if (A.length != B.length) return A.length > B.length;
        // 相等从高位进行比较
        for (int i = A.length - 1; i >= 0; i --)
            if(A[i] != B[i]) return A[i] > B[i];
        return true;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    高精度乘法

    模板：高精度 乘 低精度

    // C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    模板题：793. 高精度乘法 - AcWing题库

    import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        int b = sc.nextInt();
        
        // 逆序存放
        char[] A = new char[a.length()];
        for (int i = a.length() - 1; i >= 0; i--) 
	        A[a.length() - i - 1] = a.charAt(i);
        
        System.out.println(mul(A, b)); 
    }
    
    public static String mul(char[] A, int b) {
        int t = 0; // 进位
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < A.length || t != 0; i++) {
            if (i < A.length) t += (A[i] - '0') * b;
            sb.append(t % 10);
            t /= 10;
        }
        String s = sb.reverse().toString();
        
        // 截去前面的 0
        int i = 0;
        for (i = 0; i < A.length - 1; i++)
            if (s.charAt(i) != '0') break;
        return s.substring(i);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    高精度除法 TODO

    前缀和差分

    一维前缀和

    模板：

    S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

    • 1
    • 2

    前缀和下标从 1 开始，方便操作

    模板题：795. 前缀和 - AcWing题库

    import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

		// 多开一位方便操作
        int[] arr = new int[n + 1]; // arr[0] = 1
        int[] S = new int[n + 1]; // S[0] = 0
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
            S[i] = S[i - 1] + arr[i];
        }
        
        while (m-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(S[r] - S[l - 1]);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    二维前缀和

    模板：

    S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

求 S[i, j] :
S[i, j] = S[i - 1, j] + S[i, j - 1]  - S[i - 1][j - 1] + a[i][j]

求 (x1, y1), (x2, y2) 子矩阵中的和：
f(x1, y1, x2, y2) = S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    题解：AcWing 796. 子矩阵的和_Java - AcWing

    模板题：796. 子矩阵的和 - AcWing题库

    import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 输入值进行初始化
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        // 初始化 arr
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                arr[i][j] = in.nextInt();
        // 求解 s[i][j]
        int[][] s = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j];

        // 循环输出
        while (q-- > 0) {
            // 定位获取区间大小
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();

            // 计算, 结合图来理解
            int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            System.out.println(res);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    差分 TODO

    双指针

    模板：

    for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;
    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    模板题：799. 最长连续不重复子序列 - AcWing题库

    #include 
using namespace std;

const int N = 100010;
int n;
int a[N], s[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int res = 0; 
    for (int i = 0, j = 0; i < n; i++)
    {
        s[a[i]]++;
        while (s[a[i]] > 1)
        {
            s[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    } 
    cout << res << endl;
    
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    题目：800. 数组元素的目标和 - AcWing题库

    本题用 哈希、二分 也可以做，核心关注 双指针 的思路

    #include 
using namespace std;

const int N = 100010;
int A[N], B[N];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < m; i++) cin >> B[i];

    for (int i = 0, j = m - 1; A[i] < x; i++) 
    {
        while (A[i] + B[j] > x) j--;
        if (A[i] + B[j] == x)
        {
            cout << i << " " << j;
            return 0;
        }
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    题目：2816. 判断子序列 - AcWing题库

    #include 
using namespace std;

const int N = 100010;
int a[N], b[N];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    int i = 0;
    for (int j = 0; j < m; j++)
    {
        if (i < n && a[i] == b[j]) i++;
    }

    if (i == n) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    位运算

    原码、反码、补码：

    x = 1010
原码 x ：0....01010
反码 -x ：1....10101
补码 -x + 1 ：1....10110

    • 1
    • 2
    • 3
    • 4

    模板：

    求 n 的第 k 位数字: n >> k & 1
返回 n 的最后一位 1：lowbit(n) = n & -n

    • 1
    • 2

    模板题：801. 二进制中1的个数 - AcWing题库

    #include 
using namespace std;

// 返回末尾的 1
// 11000 ---> 1000
// 1010 ---> 10
int lowbit(int x)  
{
    return x & -x;
}

int main()
{
    int n; cin >> n;
    while (n --) {
        int x;
        cin >> x;
        
        int res = 0;
		// 写法 1
        while (x) x -= lowbit(x), res++;
		// 写法 2
		// while (x) x &= (x - 1), res++;
        cout << res << " ";
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    离散化

    模板：

    vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出 x 对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    模板题：802. 区间和 - AcWing题库

    离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。

    import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = 300010; // 坐标 x 的上限为 1e5，两个坐标 l, r 的上限也为 1e5, 所以需要 3*1e5
        int[] a = new int[N]; // 离散量
        int[] s = new int[N]; // 前缀和
        // 将所有用到的数存到 alls 中 (包含 x, l, r)，真实下标和映射下标的关系
        // 其中会有先后顺序的差别以及重复，需要排序及去重
        List<Integer> alls = new ArrayList<>();
        List<Pairs> add = new ArrayList<>(); // n 次操作
        List<Pairs> query = new ArrayList<>(); // m 次询问
        
        int n = sc.nextInt();
        int m = sc.nextInt();

		// n 次操作
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int c = sc.nextInt();
            add.add(new Pairs(x, c));
            alls.add(x); // 存入下标，统一离散化
        } 

		// m 次询问
        for (int i = 0; i < m; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            query.add(new Pairs(l, r));
			// 存入左右端点
            alls.add(l);
            alls.add(r);
        }
        
        // 到此为止，alls 中存好了所有会被用到的数轴上的点，可以进行离散化操作
        Collections.sort(alls); // 1. 排序
        int unique = unique  (alls); // 2. 去重
        alls = alls.subList(0, unique); // 保存去重后的 List

		// 离散化操作（做映射）
        for (Pairs item : add) {
            int index = find(item.first, alls);
            a[index] += item.second;
        }        
        
        // 求前缀和
        for (int i = 1; i <= alls.size(); i++) 
	        s[i] = s[i - 1] + a[i];

		// 输出结果
        for (Pairs item: query) {
            int l = find(item.first, alls);
            int r = find(item.second, alls);
            System.out.println(s[r] - s[l - 1]);
        }
    }
    
    // 去重
    static int unique(List<Integer> list) {
        int j = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0 || list.get(i) != list.get(i - 1)) {
                list.set(j, list.get(i));
                j++;
            }  
        }
        return j;
    } 
    
    // 二分搜索，查找 List 中 x 的位置
    static int find(int x, List<Integer> list) {
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (list.get(mid) >= x) r = mid;
            else l = mid + 1;
        }
        return l + 1; // 考虑到前缀和
    }
}

class Pairs {
    int first;
    int second;
    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91

    区间合并

    模板：

    // 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    模板题：803. 区间合并 - AcWing题库

    import java.util.*;

public class Main {
    public static void main(String[] args){
	    int N = 100010;
	    ArrayList<int[]> list = new ArrayList();

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int[] pair = new int[2];
            pair[0] = sc.nextInt();
            pair[1] = sc.nextInt();
            list.add(pair);
        }
        
        // 根据区间的开始位置排序
        list.sort((o1, o2) -> o1[0] - o2[0]); 
        
        int k = 0, r = Integer.MIN_VALUE;
        for (int[] a : list) {
            if (a[0] > r) k++;
            r = Math.max(r, a[1]);
        } 

        System.out.println(k);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
  • 相关阅读:
    本周投融报：CeFi积聚风投吸引力
    flink中配置Rockdb的重要配置项
    yolov5与yolov7算法
    threejs 加载各种格式的3d模型 封装
    JS中数组的遍历方法有那些？
    同事都说有SQL注入风险，我非说没有
    python 另一种将内容写入记事本的方式
    【Mobx和React的职责划分】Todos综合案例分析（附源码）
    智慧客服，为保险服务强力打call
    Vuex
  • 原文地址：https://blog.csdn.net/weixin_43734095/article/details/126266765