Polaris6G's blog

Stay humble,stay hungry.

0%

算法基础01

Posted on Edited on Valine:
  • 快速排序
  • 归并排序
  • 二分法（整数、浮点数）
  • 高精度（java大数类）
  • 前缀和 差分
  • 双指针算法
  • 位运算
  • 离散化
  • 区间合并

看数据范围知算法

快速排序 （分治）平均nlogn

  • 确定分界点：q[l], q[r],q[(l+r)/2], 随机
  • 调整区间：保证左边所有的数小于等于x，右边所有的数大于等于x
  • 递归处理左右两段
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
#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

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);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

Java模板：

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
import java.util.Scanner;
    public class quick_sort {
    static void quickSort(int[] a, 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) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        quickSort(a, l, j);
        quickSort(a, j+1, r);
    }
    static int[] a = new int[100005];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        quickSort(a, 0, n-1);
        for(int i=0;i<n;i++)System.out.printf("%d ", a[i]);
    }
}

对边界小结下：

1
2
quickSort(q, l, j);
quickSort(q, j + 1, r);

或

1
2
quickSort(q, l, i - 1);
quickSort(q, i, r);

是因为对于第一次处理后的数组，索引i左侧的数字都是小于等于x，但不包括q[i]。索引i右侧的数字都是大于等于x，包括q[i]。故区间分为[l,i-1]和[i,r]。
同理，对于第一次处理后的数组，索引j左侧的数字都是小于等于x，包括q[j]。索引j右侧的数字都是大于等于x，不包括q[j]。故区间分为[l,j]和[j+1,r]。

再对x位置小结：

如果区间取[l,i-1]和[i,r]这种，那么x不应该取左边界(l、(l+r)/2)。（防止无限循环）
应取 x = q[r]; x = q[(l+r+1)/2];

如果区间取[l,j]和[j+1,r]这种，那么x不应该取右边界(如r、(l+r+1)/2)。
应取 x = q[l]; x = q[(l+r)/2];

自己选择其中一种即可。

归并排序 nlogn

  • 确定分界点：mid = (l+r)/2
  • 递归排序（left和right）
  • 归并->合二为一

C++模板

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
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];

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;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = 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];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    return 0;
}

Java模板

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
import java.util.Scanner;

public class merge_sort {
    static int[] a = new int[100005];
    static int[] tmp = new int[100005];

    static void mergeSort(int[] a, int l, int r) {
        if (l >= r) return;
        int mid = l + r >> 1;

        mergeSort(a, l, mid);
        mergeSort(a, mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else tmp[k++] = 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];
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        mergeSort(a, 0, n - 1);
        for (int i = 0; i < n; i++) System.out.printf("%d ", a[i]);
    }
}

二分

二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

C++ 代码模板：

1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

C++ 代码模板：

1
2
3
4
5
6
7
8
9
10
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;
}

这两个模板解决的是 找>=||<=||>||< 某个数的最左或最右的位置 但这个数不一定在二分的数组中如果在就能准确找到如果不在 找到的就是最接近答案的数（你要找大于等于5的第一个数）但数组中没有5 那找到的就是6的位置(如果有6的话)
所以二分是一定有答案的

整数二分

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
import java.util.Scanner;
//整数划分
public class binary_search {
    static int[] a = new int[100005];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        while (q-- != 0) {
            int k = sc.nextInt();
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (a[mid] >= k) r = mid;
                else l = mid + 1;
            }
            if (a[l] != k) System.out.println("-1 -1");
            else {
                System.out.printf("%d ", l);

                l = 0;
                r = n - 1;
                while (l < r) {
                    int mid = l + r + 1 >> 1;
                    if (a[mid] <= k) l = mid;
                    else r = mid - 1;
                }
                System.out.printf("%d\n", l);
            }
        }
    }
}

形象栗子：

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

public class Main{
    
    public static void main(String[] args){
        int[] a = {2,5,5,6,8,10};
        int l = 0, r = a.length - 1;
        while(l < r){//第一个>=5的数
            int mid = l + r >> 1;
            if(a[mid] >= 5)r = mid;
            else l = mid + 1;
        }
        System.out.println(l);//1
        
        l = 0; r = a.length - 1;
        while(l < r){//最后一个>=5的数
            int mid = l + r + 1>> 1;
            if(a[mid] <= 5)l = mid;
            else r = mid - 1;
        }
        System.out.println(l);//2
        
        l = 0; r = a.length - 1;
        while(l < r){//最后一个<5的数
            int mid = l + r + 1 >> 1;
            if(a[mid] < 5)l = mid;
            else r = mid - 1;
        }
        System.out.println(l);//0
        
        l = 0; r = a.length - 1;
        while(l < r){//第一个>5的数
            int mid = l + r + 1 >> 1;
            if(a[mid] > 5)r = mid;
            else l = mid + 1;
        }
        System.out.println(l);//3
    }
}

浮点数二分

求sqrt(x)：Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Scanner;

//浮点数二分
public class binary_search_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double x = sc.nextDouble();
        double l = 0, r = Math.max(1, (int) x + 1);
        while (r - l > 1e-8) {
            double mid = (l + r) / 2;
            if (mid * mid >= x) r = mid;
            else l = mid;
        }
        System.out.printf("%f", l);
        sc.close();
    }
}

高精度

C++加法模板

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
#include <iostream>
#include <vector>

using namespace std;

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;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    
	auto C = add(A, B);
    
	for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
	cout << 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
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
#include <iostream>
#include <vector>

using namespace std;

const int base = 1000000000;

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 % base);
    	t /= base;
	}

	if (t) C.push_back(t);
	return C;

}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;

	for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
	{
    	s += (a[i] - '0') * t;
    	j ++, t *= 10;
    	if (j == 9 || i == 0)
    	{
        	A.push_back(s);
        	s = j = 0;
        	t = 1;
    	}
	}
	for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
	{
    	s += (b[i] - '0') * t;
    	j ++, t *= 10;
    	if (j == 9 || i == 0)
    	{
        	B.push_back(s);
        	s = j = 0;
        	t = 1;
    	}
	}

	auto C = add(A, B);

	cout << C.back();
	for (int i = C.size() - 2; i >= 0; i -- ) printf("%09d", C[i]);
	cout << endl;

	return 0;
}

C++减法模板

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
#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();

	for (int i = A.size() - 1; i >= 0; i -- )
    	if (A[i] != B[i])
        	return A[i] > B[i];

	return true;

}

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

	while (C.size() > 1 && C.back() == 0) C.pop_back();	//去掉前导0
	return C;

}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

	vector<int> C;

	if (cmp(A, B)) C = sub(A, B);
	else C = sub(B, A), cout << '-';

	for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
	cout << endl;

	return 0;

}

C++乘法模板

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
#include <iostream>
#include <vector>

using namespace std;


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;

}


int main()
{
    string a;
    int b;
	cin >> a >> b;

	vector<int> A;
	for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

	auto C = mul(A, b);

	for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
	return 0;
}

C++除法模板

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    vector<int> A;

	int B;
	cin >> a >> B;
	for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

	int r;
	auto C = div(A, B, r);

	for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
	cout << endl << r << endl;
	return 0;
}

Java大数类

BigInteger和BigDecimal都位于java.math包中(不要和java.lang.Math搞混了!!).

BigInteger类提供了四个最基本的BigInteger常量,分别是

1
2
3
4
System.out.println(BigInteger.ONE);//输出1
System.out.println(BigInteger.TEN);//输出10
System.out.println(BigInteger.TWO);//输出2
System.out.println(BigInteger.ZERO);//输出0

常用构造方法：

  • BigInteger(String val)
    将BigInteger的十进制String表示转换为BigInteger。
  • BigInteger(String val, int radix) 将指定基数中的BigInteger的String表示转换为BigInteger。

以下是大整数相关的api

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import java.util.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        //随便打的两个数,不过用生成随机大整数不是更香嘛
        BigInteger number1 = new BigInteger("347238462384523623645237465237415234165234615246742354");
        BigInteger number2 = new BigInteger("42673547263541874637462394142837645");
        //返回一个BigInteger，其值为该BigInteger的绝对值。
        System.out.println("abs():" + number1.abs().toString());
        //返回值为BigInteger (this / val)。
        System.out.println("divide():" + number1.divide(number2));
        //返回值为的BigInteger (this % val)。
        System.out.println("remainder():" + number1.remainder(number2));
        //返回值为的BigInteger (this + val)。
        System.out.println("add():" + number1.add(number2).toString());
        //返回值为的BigInteger (this << n)。
        System.out.println("shiftLeft():" + number1.shiftLeft(1));
        //返回值为的BigInteger (this >> n)。
        System.out.println("shiftRight():" + number1.shiftRight(1));
        //返回此BigInteger的signum函数 返回-1,0,1作为BigInteger的符号
        System.out.println("signum():" + number1.signum());
        //返回此BigInteger的整数平方根。
        System.out.println("sqrt():" + number1.sqrt());
        //返回值为的BigInteger (this & val)。
        System.out.println("and():" + number1.and(number2));
        //返回值为的BigInteger (this & ~val)。
        System.out.println("andNot():" + number1.andNot(number2));
        //返回此BigInteger的二进制补码表示形式中不同于其符号位的位数.
        //此方法在此BigInteger，从它的符号位不同的补码表示返回的比特数
        System.out.println("bitCount():" + number1.bitCount());
        // 返回此BigInteger的最小2补码表示形式中的位数，不包括符号位。
        System.out.println("bitLength():" + number1.bitLength());
        //将其转换BigInteger为byte，以检查是否丢失了信息。如果超出了,会丢出一个ArithmeticException异常
        //System.out.println("byteValueExact():"+number1.byteValueExact());
        //返回一个BigInteger，其值等于该BigInteger，并且清除了指定的位。
        System.out.println("clearBit:" + number2.clearBit(0));
        //将此BigInteger与指定的BigInteger进行比较。
        System.out.println("compareTo():" + number1.compareTo(number2));

        //返回两个BigIntegers组成的数组，其中包含(this / val) 后跟(this % val)。
        System.out.println("divideAndRemainder():" + Arrays.toString(number1.divideAndRemainder(number2)));
        //将此BigInteger转换为double。
        System.out.println("doubleValue():" + number1.doubleValue());
        //将此BigInteger转换为float。
        System.out.println("floatValue():" + number1.floatValue());

//     返回此BigInteger和的最大值val。
        System.out.println("max():" + number1.max(number2));
        //返回此BigInteger和的最小值val。
        System.out.println("min():" + number1.min(number2));
        //返回值为的BigInteger (this mod m)。
        System.out.println("mod():" + number1.mod(number2));
        //返回值为(this-1 的BigInteger mod m)。
        System.out.println("modInverse():" + number1.modInverse(number2));
        //返回值为的BigInteger 。(thisexponent mod m)
        System.out.println("modPow():" + number1.modPow(BigInteger.valueOf(1), number2));
        //返回值为的BigInteger (this * val)。
        System.out.println("multiply():" + number1.multiply(number2));
        //返回值为的BigInteger (-this)。 
        System.out.println("negate():" + number1.negate());
        //将此BigInteger与指定的Object比较是否相等。
        System.out.println("equals()就不说了,大家都明白....");
        //返回一个BigInteger，其值等于该BigInteger的指定位被翻转。
        System.out.println("flipBit():" + number1.flipBit(1));
        //返回一个BigInteger，其值是abs(this)和的最大公约数 abs(val)。
        System.out.println("gcd():" + number1.gcd(number2));
        //返回此BigInteger中最右边（最低位）的一位的索引（最右边一位的右边的零位数）。
        System.out.println("getLowestSetBit():" + number1.getLowestSetBit());
        //返回此BigInteger的哈希码。
        System.out.println("hashCode():" + number1.hashCode());
        //将此BigInteger转换为int。
        System.out.println("intValue():" + number1.intValue());
        // 将此转换BigInteger为int，以检查是否丢失了信息。
        //System.out.println("intValueExact():"+number1.intValueExact());
        //true如果此BigInteger可能是质数，false则返回， 如果它绝对是复合的。
        System.out.println("isProbablePrime():" + number1.isProbablePrime(10));
        //将此BigInteger转换为long。
        System.out.println("longValue():" + number1.longValue());
        //将其转换BigInteger为long，以检查是否丢失了信息。
        //System.out.println("longValueExact()"+number1.longValueExact());
        //将其转换BigInteger为short，以检查是否丢失了信息。
        //System.out.println("shortValueExact"+number1.shortValueExact());


        //返回大于此BigInteger可能是质数的第一个整数。
        System.out.println("nextProbablePrime():" + number1.nextProbablePrime());
        //返回值为的BigInteger (~this)。
        System.out.println("not():" + number1.not());
        //返回值为的BigInteger (this | val)。
        System.out.println("or():" + number1.or(number2));
        //返回值为的BigInteger 。(thisexponent)
        System.out.println("pow():" + number1.pow(2));
        //返回带有指定bitLength的正BigInteger（可能是素数）。
        System.out.println("probablePrime():" + number1.probablePrime(10, new Random(10)));


        //返回一个BigInteger，其值与此指定位设置的BigInteger等效。
        System.out.println("setBit():" + number1.setBit(5));

        //分别返回包含整数平方根两个BigInteger的平方根 s的this和它的其余部分this - s*s。
        BigInteger[] arr1 = number1.sqrtAndRemainder();
        System.out.println(arr1[0] + " " + arr1[1]);
        //返回值为的BigInteger (this - val)。        
        System.out.println("subtract():" + number1.subtract(number2));
        // true仅当设置了指定位时返回。
        System.out.println("testBit():" + number1.testBit(1));
        // 返回一个字节数组，其中包含此BigInteger的二进制补码表示形式
        System.out.println("toByteArray():" + Arrays.toString(number1.toByteArray()));
        //返回此BigInteger的十进制String表示形式。
        System.out.println("toString()不多说了....");
        //以给定的基数返回此BigInteger的String表示形式。
        //返回此BigInteger在给定的基数的字符串表示形式。如果基数是从Character.MIN_RADIX到Character.MAX_RADIX包容的范围内，它会默认为10(因为Integer.toString的情况下)
        //说白了就是修改进制...
        System.out.println("toString(int radix):" + number1.toString(10));
        //返回一个BigInteger，其值等于指定的long。
        System.out.println("valueOf():" + BigInteger.valueOf(8));
        //返回值为的BigInteger (this ^ val)
        System.out.println("xor(BigInteger val):" + number1.xor(number2));

    }

}

以下是结果

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
abs():347238462384523623645237465237415234165234615246742354
divide():8137089242665013774
remainder():534213018473473171115567876020124
add():347238462384523623687911012500957108802697009389579999
shiftLeft():694476924769047247290474930474830468330469230493484708
shiftRight():173619231192261811822618732618707617082617307623371177
signum():1
sqrt():589269431062331302776634508
and():42188789727018586573424610810872576
andNot():347238462384523623603048675510396647591810004435869778
bitCount():82
bitLength():178
clearBit:42673547263541874637462394142837644
compareTo():1
divideAndRemainder():[8137089242665013774, 534213018473473171115567876020124]
doubleValue():3.4723846238452363E53
floatValue():Infinity
max():347238462384523623645237465237415234165234615246742354
min():42673547263541874637462394142837645
mod():534213018473473171115567876020124
modInverse():17920544566730946678389678251539389
modPow():534213018473473171115567876020124
multiply():14817896936285576249282678241822399816218930984900061135427897710474330996361247767116330
negate():-347238462384523623645237465237415234165234615246742354
equals()就不说了,大家都明白....
flipBit():347238462384523623645237465237415234165234615246742352
gcd():1
getLowestSetBit():1
hashCode():-79126074
intValue():1848206162
isProbablePrime():false
longValue():4432267828819223378
nextProbablePrime():347238462384523623645237465237415234165234615246742411
not():-347238462384523623645237465237415234165234615246742355
or():347238462384523623645722222773938522229272398578707423
pow():120574549759168227502336599248901286606998151874104553572496655773107041720898305500980652795649209257461316
probablePrime():761
setBit():347238462384523623645237465237415234165234615246742386
589269431062331302776634508 683332853438534624230340290
subtract():347238462384523623602563917973873359527772221103904709
testBit():true
toByteArray():[3, -96, 22, 50, -125, 1, -106, 62, 10, -24, 25, 111, -23, -33, -88, 61, -126, -108, 27, 110, 41, 99, 82]
toString()不多说了....
toString(int radix):164005431203003130760256403133764737520366024501555612261522
valueOf():10
xor(BigInteger val):347238462384523623603533433046919935655847787767834847

另外需要大整数的题目对于Scanner一般都不友好,所以可能需要修改一下…

1
2
3
//一个小小的模板,贼好使..
BufferedReader inScanner = new BufferedReader(new InputStreamReader(System.in));    
String[] liStrings=inScanner.readLine().split(" ");

运算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.io.*;
import java.math.BigInteger;

public class Big_Operation {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger a = new BigInteger(br.readLine());
        BigInteger b = new BigInteger(br.readLine());
        System.out.println(a.add(b));
        System.out.println(a.subtract(b));
        System.out.println(a.multiply(b));
        BigInteger[] c = a.divideAndRemainder(b);
        System.out.println(c[0]);
        System.out.println(c[1]);
    }
}

前缀和差分

前缀和

一维：

Si = a1 + a2 + ... + ai

S0 = 0

初始化算法：S[i] = S[i-1] + a[i]

作用：S[r] - S[l-1] = sum[l,r]

预处理：O(n) 询问：O(1)

二维：

S[i][j]表示矩阵0~i-1行， 0~j-1列的所有元素的和

S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1] = sum[x1~x2][y1~y2]

S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j]

一维模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;

public class Prefix_add {
    static int[] a = new int[100005];
    static int[] s = new int[100005];

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

        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[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
24
25
26
27
import java.util.Scanner;

public class Prefix_add_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        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] = sc.nextInt();
            }
        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];
            }
        while (q-- != 0) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            System.out.println(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
        }

    }
}

差分

一维

a[1],a[2],…,a[n]

构造b[1],b[2],…,b[n]

使得a[n] = b[1] + b[2] + … + b[n]

即a为b的前缀和， b为a的差分

b[1] = a[1] b[2] = a[2] - a[1] bn = a[n] - a[n-1]

O(n) B->A

一维模板：

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
import java.util.Scanner;

public class Main{
    static int[] a = new int[100005];
    static int[] b = new int[100005];
    
	static void insert(int l, int r, int c){//b数组是a数组的前缀和
    	b[l] += c;
    	b[r+1] -= c;
	}

	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int m = sc.nextInt();
    	for(int i = 1;i <= n; i++){
        	a[i] = sc.nextInt();
        	insert(i, i, a[i]);//构造原始b数组
    	}
    	while(m--!=0){
        	int l = sc.nextInt();
        	int r = sc.nextInt();
        	int c = sc.nextInt();
        	insert(l, r, c);
    	}
    
    	for(int i=1;i<=n;i++){
        	b[i] += b[i-1];//a[i] = a[i-1] + b[i];
        	System.out.printf("%d ", b[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
34
35
36
37
38
39
40
41
import java.util.Scanner;

public class difference_2 {
    static int N = 1010;
    static int[][] a = new int[N][N];
    static int[][] b = new int[N][N];

    static void insert(int x1, int y1, int x2, int y2, int c) {
        b[x1][y1] += c;
        b[x1][y2 + 1] -= c;
        b[x2 + 1][y1] -= c;
        b[x2 + 1][y2 + 1] += c;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                a[i][j] = sc.nextInt();
                insert(i, j, i, j, a[i][j]);
            }
        while (q-- != 0) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            int c = sc.nextInt();
            insert(x1, y1, x2, y2, c);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];//前缀和还原
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
}

双指针算法

将O(n^2)降到0(n)

栗子：

单词输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<string.h>

using  namespace std;

int main(){
	char str[1000];
    gets(str);
    int n = strlen(str);
    
    for(int i = 0; i < n; i++){
        int j = i;
        while(j<n && str[j] != ' ')j++;
        
        //这道题的具体逻辑
        for(int k = i; k < j; k++)cout << str[k];
        cout<<endl;
    }
    return 0;
}

关键：看i,j之间有无单调关系

位运算

  • n的二进制表示中第k位（个位是第0位）是几：
  1. 先把第k位移到最后一位 n >> k
  2. 看个位是几 x & 1

-> n >> k & 1

1
2
3
4
5
6
7
8
9
10
#include<iostream>

using namespace std;

int main(){
	int n = 10;
    for(int k = 3; k >= 0; k--)cout << (n >> k & 1);
    
    return 0;
}
  • lowbit 树状数组基本操作

返回x的最后一位1

x & -x

  1. 求一个数二进制表示中1的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;

public class Main {
    static int[] a = new int[100005];

    static int lowbit(int x) {
        return x & -x;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            int j = 0;
            while (a[i] != 0) {
                a[i] -= lowbit(a[i]);
                j++;
            }
            System.out.printf("%d ", j);
        }
    }
}

离散化

值域：0~10^9 个数：10^5

  1. a[]中可能重复元素（去重）
  2. 如何算出a[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
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
import java.util.*;

public class discretization { //离散化
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int N = 300010;//2m + n <= 300000
        int[] a = new int[N];//离散化后数组存值
        int[] s = new int[N];//a数组的前缀和

        List<Integer> alls = new ArrayList<>();//用来存所有下标 x, l, r

        List<Pair> add = new ArrayList<>();//用来存n次加法

        List<Pair> query = new ArrayList<>();//用来存m次询问

        //输入n次加法
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int c = sc.nextInt();
            add.add(new Pair(x, c));
            alls.add(x);
        }
        //输入m次询问
        for (int i = 0; i < m; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            query.add(new Pair(l, r));
            alls.add(l);
            alls.add(r);
        }

        Collections.sort(alls); //对取到的所有值排序
        int unique = unique(alls); //去重
        alls = alls.subList(0, unique);

        for (Pair 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 (Pair item : query) {
            int l = find(item.first, alls);
            int r = find(item.second, alls);
            System.out.println(s[r] - s[l - 1]);
        }
    }

    //二分查找,返回要找元素下标
    public static int find(int x, List<Integer> list) {
        int l = 0;
        int r = list.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (list.get(mid) >= x) r = mid;
            else l = mid + 1;
        }
        return r + 1;//映射下标为1,2,...,n
    }
	//去重
    public static int unique(List<Integer> list) {
        int j = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0 || !Objects.equals(list.get(i), list.get(i - 1))) {
                list.set(j, list.get(i));
                j++;
            }
        }
        return j;
    }
    
    static class Pair {
        int first;
        int second;

        public Pair(int x, int c) {
            this.first = x;
            this.second = c;
        }
    }
}

使用HashMap和TreeSet的方式

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
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;
import java.util.TreeSet;


public class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static class Pair{
        int a, b;
        public Pair(int a, int b){
            this.a = a; this.b = b;
        }
    }
    static List<Pair> insert = new ArrayList<>();
    static List<Pair> query = new ArrayList<>();
    static TreeSet<Integer> set = new TreeSet<>();
    static HashMap<Integer, Integer> map = new HashMap<>();
    static int N = 100010 * 3;
    static long[] s = new long[N];

    public static void main(String[] args) throws IOException {
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        for(int i = 1; i <= n; i++){
            str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int c = Integer.parseInt(str[1]);
            insert.add(new Pair(x, c));
            set.add(x);
        }
        for(int i = 1; i <= m; i++){
            str = br.readLine().split(" ");
            int l = Integer.parseInt(str[0]);
            int r = Integer.parseInt(str[1]);
            query.add(new Pair(l, r));
            set.add(l); set.add(r);
        }
        int p = 1;
        for(Integer i : set){
            map.put(i, p++);
        }
        for(Pair pair : insert){
            int x = pair.a;
            int c = pair.b;
            int pos = map.get(x);
            s[pos] += c;
        }
        for(int i = 1; i <= p; i++){
            s[i] += s[i - 1];
        }

        for(Pair pair : query){
            int l = map.get(pair.a);
            int r = map.get(pair.b);
            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
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
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class interval_merge {
    static class Interval implements Comparable<Interval> {
        public int start, end;

        public Interval(int l, int r) {
            this.start = l;
            this.end = r;
        }

        @Override
        public int compareTo(Interval object) {
            return Integer.compare(start, object.start);
        }
    }

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

        List<Interval> intervals = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            intervals.add(new Interval(l, r));
        }
        Collections.sort(intervals);

        int start = intervals.get(0).start;
        int end = intervals.get(0).end;

        int res = 1;//初始已经取了一个
        for (Interval interval : intervals) {
            if (interval.start <= end) end = Math.max(end, interval.end);
            else {
                start = interval.start;
                end = interval.end;
                res++;
            }
        }
        System.out.println(res);
    }
}