Basic Algorithm

2022/2/14 6:12:17

编程Tag： Algorithm return int back size basic vector mid

本文主要是介绍Basic Algorithm，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Sort
- 2D Prefix Sum

Sort

## Quick Sort
1. Determine demarcation point 2. Swap two numbers with incorrect positions 3. Recursively process left and right segments
```c++ 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);

}


<br>
## Merge Sort
<br>
1. Determine demarcation point (midpoint)
2. Recursively sort left and right segments
3. Merge left and right segments
<br>
```c++
int tmp[MN];
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 idx = 0, i = l, j = mid + 1;
  	while (i <= mid && j <= r)
    {
      	if (q[i] <= q[j]) tmp[idx++] = q[i++];
        else tmp[idx++] = q[j++];
    }
  
  	while (i <= mid) tmp[idx++] = q[i++];
  	while (j <= r) tmp[idx++] = q[j++];
  
  	for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

# Binary Search
## Binary Search for Integer
```c++ bool check(int x) {/* ... */}

// r = mid
int bsearch(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}

// l = mid
int bsearch(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}


<br>
## Binary Search for Rational Numbers
<br>
```c++
const double eps = 1e-6;
bool check(double x) {/* .. */}

double bsearch(double l, double r)
{
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

# Large Integer Operation
## Large Integer Addition
1. $C = A + B$ 2. $condition：A \geq 0,\ B \geq 0$
```c++ // C = A + B // require A >= B >= 0 vector add(vector &A, vector &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;

}


<br>
## Large Integer Subtraction
<br>
1. $C = A - B$
2. $condition:A \geq B \geq 0$
<br>
```c++
vector<int> sub(vector<int> &A, vector<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);
      	if (t < 0) t = 1;
      	else t = 0;
    }
  	while (C.size > 1 && C.back() == 0) C.pop_back();
  	return C;
}

## Large Integer Multiplied by Small Integer
1. $C = A \times b$ 2. $condition:A\geq0,\ b\geq0$
```c++ vector mul(vector &A, int b) { vector 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;

}


<br>
## Large Integer Divided by Small Integer
<br>
1. $A/B=C\dots r$
2. $condition:A\geq0,\ b>0$
<br>
```c++
vector<int> div(vector<int> &A, int b, int &r)
{
  	vector<int> C;
  	r = 0;
  
  	for (int i = A.size() - 1; ~i; --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;
}

# Prefix Sum
## 1D Prefix Sum
$S[i] = a[1] + a[2] + ... a[i]\\$

$a[l] + ... + a[r] = S[r] - S[l - 1]$

2D Prefix Sum

$S[i, j] =$ sum of all in upper left part of $[i,j]$

sum of submatrix with $[x_1,y_1]$ as upper left coner and $[x_2, y_2]$ as lower right corner $=$

$S[x_1 - 1, y_2] - S[x_2, y_1 - 1] + S[x_1 - 1, y_1 - 1]$

# Finite Difference
## 1D Finite Difference
Add c to each number in interval $[l, r]$:

B[l]\ += c, B[r + 1] -= c;

## 2D Finite Difference
Add c to all in submatrix with $(x_1, y_1)$ as the upper left corner and $(x_2, y_2)$ as the lower right corner:

S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c;

# Bitwise Operation
Find the $k_{th}$ digit of $n$:

n >> k & 1;

Return the last 1 of $n$:

lowbit(n) = n & -n;

# Discretization
```c++ vector alls; // all to be discretized sort(alls.begin(), alls.end()); // sort all.erase(unique(alls.begin(), alls.end()), alls.end()); // remove duplicate elements

int find(int x) // solve the discretized value corresponding to x
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r / 2;
if (alls[mid] >= x) r = mid; // find the first number >= x
else l = mid + 1;
}
return r + 1; // map to 1, 2, ..., n
}


<br>
# Merge Intervals
<br>
```c++
#define pair<int, int> PII;
vector<PII> segs; // segments to be merged
void merge(vector<PII> &segs)
{
  	vector<PII> res;
  
  	sort(segs.begin(), segs.end());
  	
  	int st = -2e9, end = -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}); // consider the last segment
  
  	segs = res;
}

这篇关于Basic Algorithm的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Basic Algorithm

Sort

2D Prefix Sum

相关编程文章