AcWing
学习笔记
排序 快速排序AcWing 785. 快速排序
1
2
3
4
5
6
7
8
9
10
void quick_sort ( int q [], int l , int r ) {
if ( l >= r ) return ;
int x = q [ l + r >> 1 ], i = l - 1 , j = 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 );
}
快速选择AcWing 786. 第k个数
1
2
3
4
5
6
7
8
9
10
11
12
13
int q [ N ];
int quick_select ( int l , int r , int k ) { // 在[l, r]查找第k大的数
if ( l >= r ) return q [ l ];
int x = q [ l ], i = l - 1 , j = r + 1 ;
while ( i < j ) {
while ( q [ ++ i ] < x );
while ( q [ -- j ] > x );
if ( i < j ) swap ( q [ i ], q [ j ]);
}
int sl = j - l + 1 ;
if ( k <= sl ) return quick_select ( l , j , k );
return quick_select ( j + 1 , r , k - sl );
}
归并排序AcWing 787. 归并排序 AcWing 788. 逆序对的数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int q [ N ], t [ 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 ]) t [ k ++ ] = q [ i ++ ];
else t [ k ++ ] = q [ j ++ ]; // res += mid - i + 1; res为逆序对的数量
}
while ( i <= mid ) t [ k ++ ] = q [ i ++ ];
while ( j <= r ) t [ k ++ ] = q [ j ++ ];
for ( int i = l , j = 0 ; i <= r ; i ++ , j ++ ) q [ i ] = t [ j ];
}
二分 整数二分AcWing 789. 数的范围
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool check ( int x ) {};
int bsearch_1 ( int l , int r ) {
while ( l < r ) {
int mid = ( long long ) l + r >> 1 ;
if ( check [ mid ]) r = mid ;
else l = mid + 1 ;
}
return l ;
}
int bsearch_2 ( int l , int r ) {
while ( l < r ) {
int mid = l + r + 1ll >> 1 ;
if ( check ( mid )) l = mid ;
else r = mid - 1 ;
}
return l ;
}
浮点数二分AcWing 790. 数的三次方根
1
2
3
4
5
6
7
8
9
10
11
12
const double eps = 1e-6 ;
bool check ( double x ) {};
double bsearch_3 ( double l , double r ) {
while ( r - l > eps ) {
double mid = ( l + r ) / 2 ;
if ( check ( mid )) r = mid ;
else l = mid ;
}
return l ;
}
高精度 # define vint vector<int>
#define pb push_back
高精度加法AcWing 791. 高精度加法
1
2
3
4
5
6
7
8
9
10
vint add ( vint & a , vint & b ) {
vint c ;
for ( int i = 0 , t = 0 ; i < a . size () || i < b . size () || t ; i ++ ) {
if ( i < a . size ()) t += a [ i ];
if ( i < b . size ()) t += b [ i ];
c . pb ( t % 10 );
t /= 10 ;
}
return c ;
}
高精度减法AcWing 792. 高精度减法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isgreater ( vint & a , vint & b ) {
if ( a . size () != b . size ()) return a . size () > b . size ();
return vint ( a . rbegin (), a . rend ()) > vint ( b . rbegin (), b . rend ());
}
// 使用条件:a > b
vint sub ( vint & a , vint & b ) {
vint c ;
for ( int i = 0 , t = 0 ; i < a . size (); i ++ ) {
t = a [ i ] - t ;
if ( i < b . size ()) t -= b [ i ];
c . pb (( t + 10 ) % 10 );
if ( t >= 0 ) t = 0 ;
else t = 1 ;
}
while ( c . back () == 0 && c . size () > 1 ) c . pop_back ();
return c ;
}
高精度乘低精度AcWing 793. 高精度乘法
1
2
3
4
5
6
7
8
9
vint mul ( vint & a , int b ) {
vint c ;
for ( int i = 0 , t = 0 ; i < a . size () || t ; i ++ ) {
if ( i < a . size ()) t += a [ i ] * b ;
c . pb ( t % 10 );
t /= 10 ;
}
return c ;
}
高精度除低精度AcWing 794. 高精度除法
1
2
3
4
5
6
7
8
9
10
11
12
vint div ( vint a , int b , int & r ) {
vint c ;
r = 0 ;
for ( int i = a . size () - 1 ; i >= 0 ; i -- ) {
r = r * 10 + a [ i ];
c . pb ( r / b );
r %= b ;
}
reverse ( c . begin (), c . end ());
while ( c . size () > 1 && c . back () == 0 ) c . pop_back ();
return c ;
}
前缀和与差分 一维前缀和AcWing 795. 前缀和
S[i] = a[1] + a[2] +...+ a[i]
sum[l,r] = a[l] +···+ a[r] = S[r] - S[l-1]
二维前缀和AcWing 796. 子矩阵的和
前缀和S[i, j]
:
S[i,j]=S[i,j-1]+S[i-1,j]-S[i-1,j-1]+a[i,j]
(x1,y1),(x2,y2)
子矩阵之和为:
S[x2,y2]-S[x1-1,y2]-S[x2,y1-1]+S[x1-1,y1-1]
一维差分AcWing 797. 差分
给定原数列a[]
,构造差分数列b[]
,使得a[i] = b[1] + b[2] +... + b[i]
核心操作insert
:将a[l~r]
全部加上c
,等价于:b[l] += c, b[r + 1] -= c
一般假定初始b[]
全为0,用insert(i, i, a[i])
即可构造出b[]
二维差分AcWing 798. 差分矩阵
给定原矩阵a[][]
,构造差分矩阵b[][]
,使得a[][]
是b[][]
的二维前缀和。
核心操作insert
:给以(x1,y1),(x2,y2)
子矩阵中的所有数a[i][j]
加上c
,等价于b[x1][y1] += c,b[x2 + 1][y1] -= c, b[x1][y2 + 1] -= c, b[x2 + 1][y2 +1] += c;
一般用insert(i, j, i, j, a[i][j])
即可构造出b[][]
离散化 AcWing 802. 区间和
1
2
3
4
5
6
7
8
9
10
11
12
13
vector < int > alls ;
sort ( alls . begin (), alls . end ());
alls . erase ( unique ( alls . begin (), alls . end ()), alls . end ());
int find ( int 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 l + 1 ; // 映射到1.2.3...
}