本篇博文是笔者归纳汇总的AcWing基础课题集，方便读者后期复盘巩固~
PS：本篇文章只给出完整的算法实现，并没有讲解具体的算法思路。如果想看算法思路，可以阅读笔者往期写过的文章（或许会有），也可以移步AcWing官网看详情。
本篇文章的特点：每道题会给出多种解法，不局限于一种思路，可以帮助读者从不同角度思考题目。算法代码简洁，适合背诵记忆~
完整笔记已上传至GitHub：传送门
欢迎Star
第一讲 基础算法
快速排序
AcWing785.快速排序
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
void quick_sort(int l, int r)
{
if (l >= r) return ;
swap(a[l], a[l + rand() % (r - l + 1)]);
int i = l - 1, j = r + 1, x = a[l];
while (i < j)
{
while (a[ ++ i] < x) ;
while (a[ -- j] > x) ;
if (i < j) swap(a[i], a[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
quick_sort(0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
void quick_sort(int l, int r)
{
if (l >= r) return ;
swap(a[l], a[l + rand() % (r - l + 1)]);
int i = l, j = r, x = a[l];
while (i < j)
{
while (i < j && a[j] > x) j -- ;
if (i < j) a[i ++ ] = a[j];
while (i < j && a[i] < x) i ++ ;
if (i < j) a[j -- ] = a[i];
}
a[i] = x;
quick_sort(l, i - 1);
quick_sort(i + 1, r);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
quick_sort(0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}
AcWing786. 第k个数
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, k;
int quick_select(int l, int r, int k)
{
if (l >= r) return a[l];
swap(a[l], a[l + rand() % (r - l + 1)]);
int i = l - 1, j = r + 1, x = a[l];
while (i < j)
{
while (a[ ++ i] < x) ;
while (a[ -- j] > x) ;
if (i < j) swap(a[i], a[j]);
}
int s = j - l + 1;
if (k <= s) return quick_select(l, j, k);
return quick_select(j + 1, r, k - s);
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
printf("%d\n", quick_select(0, n - 1, k));
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, k;
int quick_select(int l, int r, int k)
{
swap(a[l], a[l + rand() % (r - l + 1)]);
int i = l, j = r, x = a[l];
while (i < j)
{
while (i < j && a[j] > x) j -- ;
if (i < j) a[i ++ ] = a[j];
while (i < j && a[i] < x) i ++ ;
if (i < j) a[j -- ] = a[i];
}
a[i] = x;
int s = i - l + 1; // [l, i]区间个数 i - l + 1
if (k == s) return a[i];
if (k < s) return quick_select(l, i - 1, k);
return quick_select(i + 1, r, k - s);
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
printf("%d\n", quick_select(0, n - 1, k));
return 0;
}
归并排序
AcWing787. 归并排序
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N], 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 i = l, j = mid + 1, k = l;
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 (int i = l; i <= r; i ++ ) a[i] = tmp[i];
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
merge_sort(0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}
AcWing788. 逆序对的数量
传送门
// 归并排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using LL = long long ;
int a[N], tmp[N], n;
LL merge_sort(int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r)
{
if (a[i] > a[j])
{
res += mid - i + 1;
tmp[k ++ ] = a[j ++ ];
}
else tmp[k ++ ] = a[i ++ ];
}
while (i <= mid) tmp[k ++ ] = a[i ++ ];
while (j <= r) tmp[k ++ ] = a[j ++ ];
for (int i = l; i <= r; i ++ ) a[i] = tmp[i];
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
printf("%lld\n", merge_sort(0, n - 1));
return 0;
}
// 树状数组：写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using LL = long long ;
int a[N], b[N], tr[N], n, m;
int find(int x) {
int l = 1, r = m;
while (l < r) {
int mid = l + r >> 1;
if (b[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
inline int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= m; i += lowbit(i)) tr[i] += v;
}
LL query(int x) {
LL s = 0;
for (int i = x; i; i -= lowbit(i)) s += tr[i];
return s;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + 1 + n);
m = unique(b + 1, b + 1 + n) - (b + 1);
LL ans = 0;
for (int i = 1; i <= n; i ++ ) {
int x = find(a[i]);
ans += query(m) - query(x); // 这里也可以写成 i - query(x)
add(x, 1);
}
printf("%lld\n", ans);
return 0;
}
// 树状数组：写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using LL = long long ;
int n, m;
vector<int> a, b, tr;
inline int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= m; i += lowbit(i)) tr[i] += v;
}
LL query(int x) {
LL s = 0;
for (int i = x; i; i -= lowbit(i)) s += tr[i];
return s;
}
int main()
{
scanf("%d", &n);
(n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
b = a;
sort((), ());
(unique((), ()), ());
m = ();
tr = vector<int>(m + 1, 0);
LL ans = 0;
for (int i = 0; i < n; i ++ ) {
int x = lower_bound((), (), a[i]) - () + 1;
ans += query(m) - query(x); // 这里也可以写成 i - query(x)
add(x, 1);
}
printf("%lld\n", ans);
return 0;
}
二分
AcWing789. 数的范围
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
while (m -- )
{
int x;
scanf("%d", &x);
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
if (a[l] != x) puts("-1 -1");
else
{
printf("%d ", l);
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[mid] <= x) l = mid;
else r = mid - 1;
}
printf("%d\n", r);
}
}
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
while (m -- )
{
int x;
scanf("%d", &x);
int l = -1, r = n;
while (l + 1 < r)
{
int mid = l + r >> 1;
if (a[mid] >= x) r = mid;
else l = mid;
}
if (a[r] != x) puts("-1 -1");
else
{
printf("%d ", r);
int l = -1, r = n;
while (l + 1 < r)
{
int mid = l + r >> 1;
if (a[mid] <= x) l = mid;
else r = mid;
}
printf("%d\n", l);
}
}
return 0;
}
AcWing790. 数的三次方根
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
double n;
int main()
{
cin >> n;
double l = -10000, r = 10000;
while (l + eps < r)
{
double mid = (l + r) / 2;
if (mid * mid * mid > n) r = mid;
else l = mid;
}
printf("%lf\n", l);
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
double x;
int main()
{
scanf("%lf", &x);
double l = -10000, r = 10000;
for (int i = 1; i <= 100; i ++ )
{
double mid = (l + r) / 2;
if (mid * mid * mid > x) r = mid;
else l = mid;
}
printf("%.6lf\n", l);
return 0;
}
高精度
AcWing791. 高精度加法
传送门
#include <bits/stdc++.h>
using namespace std;
vector<int> add(vector<int> A, vector<int> B)
{
vector<int> C;
int t = 0;
for (int i = 0; i < () || i < () || t; i ++ )
{
if (i < ()) t += A[i];
if (i < ()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = () - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
for (int i = () - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
auto C = add(A, B);
for (int i = () - 1; i >= 0; i -- ) printf("%d", C[i]);
return 0;
}
AcWing792. 高精度减法
传送门
#include <bits/stdc++.h>
using namespace std;
bool cmp(vector<int> A, vector<int> B)
{
if (() != ()) return () > ();
for (int i = () - 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;
int t = 0;
for (int i = 0; i < (); i ++ )
{
t = A[i] - t;
if (i < ()) t -= B[i];
C.push_back((t + 10) % 10);
t = t < 0 ? 1 : 0;
}
while (() > 1 && () == 0) C.pop_back();
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = () - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
for (int i = () - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
if (cmp(A, B))
{
auto C = sub(A, B);
for (int i = () - 1; i >= 0; i -- ) printf("%d", C[i]);
}
else
{
printf("-");
auto C = sub(B, A);
for (int i = () - 1; i >= 0; i -- ) printf("%d", C[i]);
}
}
AcWing793. 高精度乘法
传送门
// 高精度 * 低精度
#include <bits/stdc++.h>
using namespace std;
vector<int> mul(vector<int> A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < () || t; i ++ )
{
if (i < ()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (() > 1 && () == 0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
vector<int> A;
cin >> a >> b;
for (int i = () - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
auto C = mul(A, b);
for (int i = () - 1; i >= 0; i -- ) printf("%d", C[i]);
return 0;
}
// 高精度 * 高精度
#include <bits/stdc++.h>
using namespace std;
vector<int> mul(vector<int> A, vector<int> B)
{
int n = (), m = ();
vector<int> C(n + m);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
C[i + j] += A[i] * B[j];
for (int i = 0, t = 0; i < (); i ++ )
{
t += C[i];
C[i] = t % 10;
t /= 10;
}
while (() > 1 && () == 0) C.pop_back();
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = () - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
for (int i = () - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
auto C = mul(A, B);
for (int i = () - 1; i >= 0; i -- ) printf("%d", C[i]);
return 0;
}
AcWing794. 高精度除法
传送门
#include <bits/stdc++.h>
using namespace std;
vector<int> div(vector<int> A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = () - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse((), ());
while (() > 1 && () == 0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
vector<int> A;
cin >> a >> b;
for (int i = () - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
int r;
auto C = div(A, b, r);
for (int i = () - 1; i >= 0; i -- ) printf("%d", C[i]);
printf("\n%d\n", r);
return 0;
}
前缀和与差分
AcWing795. 前缀和
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int s[N];
int n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}
AcWing796. 子矩阵的和
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int s[N][N], n, m, k;
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &s[i][j]);
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 (k -- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int s[N][N], n, m, k;
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &s[i][j]);
// 先求行的前缀和
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i][j - 1];
// 再对整体求前缀和
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i - 1][j];
while (k -- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}
AcWing797. 差分
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
b[i] = a[i] - a[i - 1];
}
while (m -- )
{
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
b[l] += c, b[r + 1] -= c;
}
for (int i = 1; i <= n; i ++ )
{
a[i] = a[i - 1] + b[i];
printf("%d ", a[i]);
}
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], n, m;
void ins(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
ins(i, i, a[i]);
}
while (m -- )
{
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
ins(l, r, c);
}
for (int i = 1; i <= n; i ++ )
{
a[i] = a[i - 1] + b[i];
printf("%d ", a[i]);
}
return 0;
}
AcWing798. 差分矩阵
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N], n, m, k;
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
while (k -- )
{
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
b[x1][y1] += c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y1] -= c;
b[x2 + 1][y2 + 1] += c;
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
a[i][j] = b[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++)
printf("%d ", a[i][j]);
puts("");
}
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int s[N][N], n, m, k;
void ins(int x1, int y1, int x2, int y2, int c)
{
s[x1][y1] += c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y1] -= c;
s[x2 + 1][y2 + 1] += c;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
int c;
scanf("%d", &c);
ins(i, j, i, j, c);
}
}
while (k -- )
{
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
ins(x1, y1, x2, y2, c);
}
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];
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++)
printf("%d ", s[i][j]);
puts("");
}
return 0;
}
// 写法3
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int s[N][N], n, m, k;
void ins(int x1, int y1, int x2, int y2, int c)
{
s[x1][y1] += c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y1] -= c;
s[x2 + 1][y2 + 1] += c;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
int c;
scanf("%d", &c);
ins(i, j, i, j, c);
}
}
while (k -- )
{
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
ins(x1, y1, x2, y2, c);
}
// 先对行求前缀和
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i][j - 1];
// 再对整体求前缀和
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i - 1][j];
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++)
printf("%d ", s[i][j]);
puts("");
}
return 0;
}
双指针算法
AcWing799. 最长连续不重复子序列
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], s[N], n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int ans = 0;
for (int l = 0, r = 0; r < n; r ++ )
{
s[a[r]] ++ ;
while (s[a[r]] > 1)
{
s[a[l]] -- ;
l ++ ;
}
ans = max(ans, r - l + 1);
}
printf("%d\n", ans);
return 0;
}
AcWing800. 数组元素的目标和
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], n, m, x;
int main()
{
scanf("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
for (int i = 0, j = m - 1; i < n; i ++ )
{
while (j >= 0 && a[i] + b[j] > x) j -- ;
if (a[i] + b[j] == x)
{
printf("%d %d\n", i, j);
break;
}
}
return 0;
}
AcWing2816. 判断子序列
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
int i = 0, j = 0;
while (i < n && j < m)
{
if (a[i] == b[j]) i ++ ;
j ++ ;
}
puts(i == n ? "Yes" : "No");
return 0;
}
位运算
AcWing801. 二进制中1的个数
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
int n;
inline int lowbit(int x)
{
return x & -x;
}
int main()
{
scanf("%d", &n);
while (n -- )
{
int x;
scanf("%d", &x);
int ans = 0;
while (x)
{
x -= lowbit(x);
ans ++ ;
}
printf("%d ", ans);
}
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
int n;
inline int lowbit(int x)
{
return x & -x;
}
int main()
{
scanf("%d", &n);
while (n -- )
{
int x;
scanf("%d", &x);
int ans = 0;
for (int i = 0; i < 32; i ++ )
if (x >> i & 1)
ans ++ ;
printf("%d ", ans);
}
return 0;
}
离散化
AcWing802. 区间和
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
typedef pair<int, int> PII;
vector<PII> add, query;
vector<int> alls;
int s[N], n, m;
int find(int x)
{
int l = 0, r = () - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
// 加1是因为我们想让离散化后的坐标是从1开始 因为前缀和是从下标1开始计算
return r + 1; // 其实加不加都无所谓
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
{
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l), alls.push_back(r);
}
// 离散化的核心：排序+去重
sort((), ()); // 排序
(unique((), ()), ()); // 去重
for (auto &it : add)
{
int nx = find();
s[nx] += ;
}
// 前缀和
for (int i = 1; i <= (); i ++ ) s[i] += s[i - 1];
for (auto &it : query)
{
int nl = find(), nr = find();
printf("%d\n", s[nr] - s[nl - 1]);
}
return 0;
}
区间合并
AcWing803. 区间合并
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
#define x first
#define y second
vector<PII> segs, ans;
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({l, r});
}
sort((), ());
int lastL = segs[0].x, lastR = segs[0].y;
for (int i = 1; i < n; i ++ )
{
if (segs[i].x > lastR)
{
ans.push_back({lastL, lastR});
lastL = segs[i].x;
lastR = segs[i].y;
}
else lastR = max(lastR, segs[i].y);
}
ans.push_back({lastL, lastR});
printf("%d\n", ());
return 0;
}
第二讲 数据结构
单链表
AcWing826. 单链表
传送门
// 写法1：单链表
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], head, idx;
int m;
void init()
{
head = -1, idx = 0;
}
void add_to_head(int x)
{
e[idx] = x, ne[idx] = head, head = idx ++ ;
}
void add(int k, int x)
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
init();
scanf("%d", &m);
while (m -- )
{
int k, x;
char op[5];
scanf("%s", op);
if (*op == 'H')
{
scanf("%d", &x);
add_to_head(x);
}
else if (*op == 'D')
{
scanf("%d", &k);
if (!k ) head = ne[head];
else remove(k - 1);
}
else
{
scanf("%d%d", &k, &x);
add(k - 1, x);
}
}
for (int i = head; ~i; i = ne[i]) printf("%d ", e[i]);
return 0;
}
// 写法2：双链表
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], head, idx;
int m;
void init() // 初始化,默认以[0]为head指针(无实际值). 从[1]开始存第1个结点
{
ne[0] = -1, idx = 1;
}
void add(int k, int x) // 在第[k]个位的右边,插入新元素
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
void remove(int k) // 删除第[k]位的右边的元素
{
ne[k] = ne[ne[k]];
}
int main()
{
init();
scanf("%d", &m);
while (m -- )
{
int k, x; // 在第k个位置,k对应的下标从1,2,3,....,n ; 由于[0]已被head使用,所以不需要k-1
char op[5];
scanf("%s", op);
if (*op == 'H')
{
scanf("%d", &x);
add(0, x); // [0]的右边即实际第1个结点
}
else if (*op == 'D')
{
scanf("%d", &k);
remove(k);
}
else
{
scanf("%d%d", &k, &x);
add(k, x);
}
}
// ne[0] 是第1个实际有值的结点
for (int i = ne[0]; ~i; i = ne[i]) printf("%d ", e[i]);
return 0;
}
双链表
AcWing827 双链表
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int l[N], r[N], e[N], idx;
int m;
void init()
{
r[0] = 1, l[1] = 0, idx = 2;
}
void add(int k, int x)
{
e[idx] = x;
r[idx] = r[k], l[idx] = k;
l[r[k]] = idx, r[k] = idx ++ ;
}
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
init();
scanf("%d", &m);
while (m -- )
{
int k, x;
string op;
cin >> op;
if (op == "L")
{
scanf("%d", &x);
add(0, x);
}
else if (op == "R")
{
scanf("%d", &x);
add(l[1], x);
}
else if (op == "D")
{
scanf("%d", &k);
remove(k + 1);
}
else if (op == "IL")
{
scanf("%d%d", &k, &x);
add(l[k + 1], x);
}
else if (op == "IR")
{
scanf("%d%d", &k, &x);
add(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);
return 0;
}
栈
AcWing828. 模拟栈
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int stk[N], top, m;
int main()
{
scanf("%d", &m);
while (m -- )
{
int x;
string op;
cin >> op;
if (op == "push")
{
scanf("%d", &x);
stk[++ top ] = x;
}
else if (op == "pop") top -- ;
else if (op == "empty") {
puts(top ? "NO" : "YES");
}
else printf("%d\n", stk[top]);
}
return 0;
}
AcWing3302. 表达式求值
传送门
// 写法1：先将中缀转成后缀，然后对后缀表达式求值
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> pr{
{"(", 0}, {"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}
};
vector<string> post; // 保存转化后的后缀表达式
string s;
// 将中缀表达式 转换成 后缀表达式
void convert()
{
int n = ();
stack<string> stk; // 在这里栈stk是用来存储运算符的
for (int i = 0; i < n; i ++ )
{
string str;
// 遇到数字直接加入后缀表达式post中
if (isdigit(s[i]))
{
while (i < n && isdigit(s[i])) str += s[i ++ ];
post.push_back(str);
if (i == n ) break;
}
// 遇到左括号直接入栈
if (s[i] == '(') ("(");
// 遇到右括号,将栈顶符号依次弹出并加入后缀表达式post中, 直到碰到匹配的左括号
else if (s[i] == ')')
{
while (!())
{
string item = (); ();
if (item == "(") break;
else post.push_back(item);
}
}
// 遇到运算符号 + - * /
else
{
int s_pr; // 判断当前运算符的优先级
if (s[i] == '+' || s[i] == '-' ) s_pr = 1;
else s_pr = 2;
// 若栈顶运算符优先级不低于当前运算符，则将栈顶运算符弹出到post中
while (!() && pr[()] >= s_pr)
{
post.push_back(());
();
}
(1, s[i]);
}
}
// 遍历结束之后：将栈顶所有的符号弹出加入后缀表达式post中
while (!())
{
post.push_back(());
();
}
}
// 后缀表达式求值
int evalRPN()
{
stack<int> stk; // 在这里栈stk是用来存储操作数
for (string &s : post)
{
if (s == "+" || s == "-" || s == "*" || s == "/")
{
int b = (); ();
int a = (); ();
if (s == "+") a += b;
else if (s == "-") a -= b;
else if (s == "*") a *= b;
else a /= b;
(a);
}
else (stoi(s));
}
return ();
}
int main()
{
cin >> s;
convert();
printf("%d\n", evalRPN());
return 0;
}
// 写法2：双栈直接求解中缀表达式
#include<iostream>
#include<cstring>
#include<stack>
#include<algorithm>
#include<unordered_map>
using namespace std;
stack<int> nums;
stack<char> op;
unordered_map<char, int> pr{
{'(', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}
};
string s, str;
void eval()
{
int b = (); ();
int a = (); ();
char c = (); ();
if (c == '+') a += b;
else if (c == '-') a -= b;
else if (c == '*') a *= b;
else if (c == '/') a /= b;
(a);
}
int main()
{
cin >> str;
for (auto &c : str) // 若输入的序列存在空格 则先抛去空格
if (c != ' ')
s += c;
int n = ();
for (int i = 0; i < n; i ++ )
{
char c = s[i];
if (isdigit(c))
{
int x = 0, j = i;
while (j < n && isdigit(s[j]))
{
x = x * 10 + s[j] - '0';
j ++ ;
}
i = j - 1;
(x);
if (i == n) break;
}
else if (c == '(') (c);
else if (c == ')')
{
while (() != '(' ) eval();
();
}
else
{
// i==0针对的是 +5-6这种数据
// 后面的是针对 1-(-2)这种把加和减当作正负号的
if (!i || s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-') (0);
while (!() && pr[()] >= pr[c]) eval();
(c);
}
}
while (!() ) eval();
printf("%d\n", ());
return 0;
}
队列
AcWing829. 模拟队列
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
// 队首和队列的初始化：hh = 0, tt = -1 或者 hh = 1, tt = 0 看个人习惯
int q[N], hh, tt = -1, m;
int main()
{
scanf("%d", &m);
while (m -- )
{
string op;
cin >> op;
if (op == "push")
{
int x;
scanf("%d", &x);
q[ ++ tt] = x;
}
else if (op == "pop") hh ++ ;
else if (op == "empty") {
puts(hh <= tt ? "NO" : "YES");
}
else cout << q[hh] << endl;
}
return 0;
}
单调栈
AcWing830. 单调栈
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int stk[N], top, n;
int main()
{
scanf("%d", &n);
while (n -- )
{
int x;
scanf("%d", &x);
while (top && stk[top] >= x) top -- ;
if (top) printf("%d ", stk[top]);
else printf("-1 ");
stk[ ++ top] = x;
}
return 0;
}
单调队列
AcWing154. 滑动窗口
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N], n, k;
void getMin()
{
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
q[ ++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
puts("");
}
void getMax()
{
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
q[ ++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
puts("");
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
getMin();
getMax();
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N], n, k;
void getMin()
{
int hh = 1, tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (hh <= tt && a[q[tt]] >= a[i]) tt --;
q[ ++ tt] = i;
// 不需要写hh<=tt 而且该判断条件必须在while后面而不能在前面
if (q[hh] < i - k + 1) hh ++ ;
if (i >= k) printf("%d ", a[q[hh]]);
}
puts("");
}
void getMax()
{
int hh = 1, tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (hh <= tt && a[q[tt]] <= a[i]) tt --;
q[ ++ tt] = i;
if (q[hh] < i - k + 1) hh ++ ;
if (i >= k) printf("%d ", a[q[hh]]);
}
puts("");
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
getMin();
getMax();
return 0;
}
KMP
AcWing831. KMP字符串
传送门
// 下标从0开始的写法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char p[N], s[N]; // p是模式串, s是主串
int ne[N], n, m; // n是主串的长度, m是模式串的长度
void getNext()
{
ne[0] = 0;
for (int i = 1, j = 0; i < m; i ++ )
{
while (j && p[i] != p[j]) j = ne[j - 1];
if (p[i] == p[j]) j ++ ;
ne[i] = j;
}
}
void KMP()
{
for (int i = 0, j = 0; i < n; i ++ )
{
while (j && s[i] != p[j]) j = ne[j - 1];
if (s[i] == p[j]) j ++ ;
if (j == m) printf("%d ", i - m + 1);
}
}
int main()
{
scanf("%d%s%d%s", &m, p, &n, s);
getNext();
KMP();
return 0;
}
// 下标从1开始的写法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char p[N], s[N];
int ne[N], n, m;
void getNext()
{
ne[0] = ne[1] = 0;
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
}
void KMP()
{
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
printf("%d ", i - m);
j = ne[j]; // 这一句可以不用
}
}
}
int main()
{
scanf("%d%s%d%s", &m, p + 1, &n, s + 1);
getNext();
KMP();
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char p[N], s[N];
int ne[N], f[N], n, m;
void getNext()
{
ne[0] = ne[1] = 0;
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
}
void KMP()
{
for (int i = 1, j = 0; i <= n; i ++ )
{
// j == m 可以不写
while (j == m || (j && s[i] != p[j + 1])) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
f[i] = j;
}
for (int i = 1; i <= n; i ++ )
if (f[i] == m)
printf("%d ", i - m);
}
int main()
{
scanf("%d%s%d%s", &m, p + 1, &n, s + 1);
getNext();
KMP();
return 0;
}
// 写法3
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
char p[N], s[N];
int ne[N], f[N], n, m;
void KMP()
{
p[m + 1] = '#'; // 形成新的字符串：模式串 + '#' + 主串
for (int i = 1, j = m + 2; i <= n; i ++ , j ++ )
p[j] = s[i];
ne[0] = ne[1] = 0;
for (int i = 2, j = 0; i <= n + m + 1; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
for (int i = m + 2; i <= n + m + 1; i ++ )
if (ne[i] == m)
printf("%d ", i - 2 * m - 1); // 本来要输出s串中的第i-m位,但是由于s串前面增加了m+1位,所以还得减去m+1, 即i-m-(m+1)=i-2*m-1
}
int main()
{
scanf("%d%s%d%s", &m, p + 1, &n, s + 1);
KMP();
return 0;
}
Trie
AcWing835. Trie字符串统计
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int cnt[N], tr[N][26], idx;
char str[N];
void ins(char s[])
{
int p = 0;
for (int i = 0; s[i]; i ++ )
{
int u = s[i] - 'a';
if (!tr[p][u]) tr[p][u] = ++ idx;
p = tr[p][u];
}
cnt[p] ++ ;
}
int query(char s[])
{
int p = 0;
for (int i = 0; s[i]; i ++ )
{
int u = s[i] - 'a';
if (!tr[p][u]) return 0;
p = tr[p][u];
}
return cnt[p];
}
int main()
{
int n;
scanf("%d", &n);
while (n -- )
{
char op[5];
scanf("%s%s", op, str);
if (*op == 'I') ins(str);
else printf("%d\n", query(str));
}
return 0;
}
AcWing143 最大异或对
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 31 * N;
int tr[M][2], idx;
void ins(int x)
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int u = x >> i & 1;
if (!tr[p][u]) tr[p][u] = ++ idx;
p = tr[p][u];
}
}
int query(int x) // 找到能与整数x异或得到最大值的"某个数"t
{
int p = 0, t = 0;
for (int i = 30; i >= 0; i -- )
{
int u = x >> i & 1;
if (tr[p][!u])
{
t = (t << 1) + !u; // 也可以写成 t = t * 2 + !u
p = tr[p][!u];
}
else
{
t = (t << 1) + u; // 也可以写成 t = t * 2 + u
p = tr[p][u];
}
}
return t;
}
int main()
{
int n, ans = 0;
scanf("%d", &n);
while (n -- )
{
int x;
scanf("%d", &x);
ins(x);
int t = query(x);
ans = max(ans, x ^ t);
}
printf("%d\n", ans);
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 31 * N;
int tr[M][2], idx;
void ins(int x)
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int u = x >> i & 1;
if (!tr[p][u]) tr[p][u] = ++ idx;
p = tr[p][u];
}
}
int query(int x) // 这里的ans是两个数异或后得到的最大值
{
int p = 0, ans = 0;
for (int i = 30; i >= 0; i -- )
{
int u = x >> i & 1;
if (tr[p][u ^ 1])
{
ans += 1 << i;
p = tr[p][u ^ 1];
}
else
{
ans += 0 << i;
p = tr[p][u];
}
}
return ans;
}
int main()
{
int n, ans = 0;
scanf("%d", &n);
while (n -- )
{
int x;
scanf("%d", &x);
ins(x);
ans = max(ans, query(x));
}
printf("%d\n", ans);
return 0;
}
并查集
AcWing836. 合并集合
传送门
// 写法1：路径压缩
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], n, m;
int find(int x)
{
if (x != p[x])
p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
while (m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
a = find(a), b = find(b);
if (*op == 'M')
{
if (a == b) continue;
p[a] = b;
}
else puts(a == b ? "Yes" : "No");
}
return 0;
}
// 写法2：启发式合并
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], sz[N], n, m;
int find(int x)
{
if (x != p[x])
p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i, sz[i] = 1;
while (m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
a = find(a), b = find(b);
if (*op == 'M')
{
if (a == b) continue;
if (sz[a] > sz[b]) swap(a, b);
p[a] = b;
sz[b] += sz[a];
}
else puts(a == b ? "Yes" : "No");
}
return 0;
}
// 写法3：按深度合并
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], dep[N], n, m;
int find(int x)
{
if (x != p[x])
p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
while (m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
a = find(a), b = find(b);
if (*op == 'M')
{
if (a == b) continue;
if (dep[a] > dep[b]) swap(a, b);
p[a] = b;
if (dep[a] == dep[b]) dep[b] ++ ;
}
else puts(a == b ? "Yes" : "No");
}
return 0;
}
AcWing837. 连通块中点的数量
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], sz[N], n, m;
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i, sz[i] = 1;
while (m -- )
{
string op;
int a, b;
cin >> op;
if (op == "C")
{
scanf("%d%d", &a, &b);
a = find(a), b = find(b);
if (a == b) continue;
p[a] = b;
sz[b] += sz[a];
}
else if (op == "Q1")
{
scanf("%d%d", &a, &b);
puts(find(a) == find(b) ? "Yes" : "No");
}
else
{
scanf("%d", &a);
printf("%d\n", sz[find(a)]);
}
}
return 0;
}
AcWing240. 食物链
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int p[N], dep[N], n, m, ans;
int find(int x)
{
if (x != p[x])
{
int fa = find(p[x]); // 找到x所在集合的代表元fa
dep[x] = (dep[x] + dep[p[x]]) % 3;
p[x] = fa;
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i, dep[i] = 0;
while (m -- )
{
int c, x, y;
scanf("%d%d%d", &c, &x, &y);
// x或y大于n,或者是x吃y,并且x==y,即同类吃同类 则为假话
if (x > n || y > n || (c == 2 && x == y)) ans ++ ;
else
{
int a = find(x), b = find(y);
// 如果集合号相同,说明x和y在同一个集合中,那么不需要合并
if (a == b)
{
if ((dep[x] - dep[y] + 3) % 3 != c - 1)
ans ++ ;
}
// 否则说明集合号不同,说明x和y不在同一个集合中,那么就需要进行合并操作了
else
{
p[a] = b;
dep[a] = (dep[y] - dep[x] + 3 + c - 1) % 3;
}
}
}
printf("%d\n", ans);
return 0;
}
堆
AcWing838. 堆排序
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int q[N], n, m, len;
void down(int k)
{
int mx = k;
if (2 * k <= len && q[2 * k] < q[mx]) mx = 2 * k;
if (2 * k + 1 <= len && q[2 * k + 1] < q[mx]) mx = 2 * k + 1;
if (k != mx)
{
swap(q[k], q[mx]);
down(mx);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);
len = n;
for (int i = n / 2; i >= 1; i -- ) down(i);
while (m -- )
{
printf("%d ", q[1]);
swap(q[1], q[len]);
len -- ;
down(1);
}
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int q[N], n, m, len;
void up(int k)
{
while (k > 1 && q[k] < q[k / 2])
{
swap(q[k], q[k / 2]);
k /= 2;
}
}
void down(int k)
{
while (2 * k <= len)
{
int j = 2 * k;
if (j + 1 <= len && q[j + 1] < q[j]) j ++ ;
if (q[k] <= q[j]) break;
swap(q[k], q[j]);
k = j;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
q[ ++ len] = x;
up(len);
}
while (m -- )
{
printf("%d ", q[1]);
swap(q[1], q[len]);
len -- ;
down(1);
}
return 0;
}
AcWing839 模拟堆
传送门
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 100010;
// s[N]表示堆中某个位置上存放的是第几次插入 s存储(堆中数组下标为i的这个位置)里面存放的是(哪一次插入的数)
// ph[N]表示第几次插入的数在堆中的什么位置 ph存储的是(第k个插入的数)在(数组中的下标)
int q[N], s[N], pos[N], n, len;
void change(int a, int b)
{
// 这三个swap的顺序没有要求
swap(q[a], q[b]); // 交换数组中的元素值，也就是交换堆中的结点的元素
swap(s[a], s[b]); // 交换两个结点所对应的是"第几次插入"
swap(pos[s[a]], pos[s[b]]); // 交换第几次插入的两个结点的数组下标
}
void up(int k)
{
while (k > 1 && q[k] < q[k / 2])
{
change(k, k / 2);
k /= 2;
}
}
void down(int k)
{
int mx = k;
if (k * 2 <= len && q[k * 2] < q[mx]) mx = k * 2;
if (k * 2 + 1 <= len && q[k * 2 + 1] < q[mx]) mx = k * 2 + 1;
if (mx != k)
{
change(k, mx);
down(mx);
}
}
int main()
{
int idx = 0; // idx表示当前第几个插入，初始化为0，每次插入一个数后，idx++
cin >> n;
while (n--)
{
string op;
int k, x;
cin >> op;
// 插入一个数x
if (op == "I")
{
int x;
cin >> x;
++ idx;
q[ ++ len] = x;
pos[idx] = len; // 表示第idx个插入的元素在堆中的位置是idx
s[len] = idx; // 表示堆数组中下标为len的那个位置的元素是第idx次插入的
up(len);
}
// 输出当前集合中的最小值
else if (op == "PM") {
printf("%d\n", q[1]);
}
// 删除当前集合中的最小值
else if (op == "DM")
{
change(1, len);
-- len;
down(1);
}
// 删除第k个插入的数
else if (op == "D")
{
cin >> k;
int i = pos[k]; // 找到要删除的第k个数它所在堆中的数组下标
change(i, len);
-- len;
up(i), down(i);
}
// 修改第k个插入的数，将其变为x
else if (op == "C")
{
cin >> k >> x; // 表示修改第k个插入的数,将其改为x
int i = pos[k]; // 找到第k个插入的数在堆中的位置数组下标为i
q[i] = x; // 将堆中i位置的里面的数组元素修改为x
up(i), down(i);
}
}
return 0;
}
哈希表
AcWing840. 模拟散列表
传送门
#include <bits/stdc++.h>
using namespace std;
const int P = 13331;
vector<int> c[P];
bool find(int x)
{
int v = (x % P + P) % P, len = c[v].size();
for (int i = 0; i < len; i ++ )
if (c[v][i] == x)
return true;
return false;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < P; i ++ ) c[i].clear();
while (n -- )
{
int x;
char op[5];
scanf("%s%d", op, &x);
if (*op == 'I') c[(x % P + P) % P].push_back(x);
else puts(find(x) ? "Yes" : "No");
}
return 0;
}
AcWing841. 字符串哈希
传送门
// 写法1：自然溢出
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, base = 131;
using ULL = unsigned long long ;
ULL h[N], c[N];
char s[N];
int n, m;
ULL get(int l, int r)
{
return h[r] - h[l - 1] * c[r - l + 1];
}
int main()
{
scanf("%d%d%s", &n, &m, s + 1);
c[0] = 1;
for (int i = 1; i <= n; i ++ )
{
c[i] = c[i - 1] * base;
h[i] = h[i - 1] * base + s[i];
}
while (m -- )
{
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
// 写法二：单哈希
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, base = 131, P = 9999971;
int c[N], h[N], n, m;
char s[N];
int get(int l, int r)
{
return (h[r] - 1ll * h[l - 1] * c[r - l + 1] % P + P) % P;
}
int main()
{
scanf("%d%d%s", &n, &m, s + 1);
c[0] = 1;
for (int i = 1; i <= n; i ++ )
{
c[i] = c[i - 1] * base % P;
h[i] = (h[i - 1] * base + s[i]) % P;
}
while (m -- )
{
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
// 写法3：双哈希
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, base1 = 131, base2 = 137, P1 = 13331, P2 = 9999971;
int c1[N], c2[N], h1[N], h2[N], n, m;
char s[N];
int get1(int l, int r)
{
return (h1[r] - 1ll * h1[l - 1] * c1[r - l + 1] % P1 + P1) % P1;
}
int get2(int l, int r)
{
return (h2[r] - 1ll * h2[l - 1] * c2[r - l + 1] % P2 + P2) % P2;
}
int main()
{
scanf("%d%d%s", &n, &m, s + 1);
c1[0] = c2[0] = 1;
for (int i = 1; i <= n; i ++ )
{
c1[i] = c1[i - 1] * base1 % P1;
h1[i] = (h1[i - 1] * base1 + s[i]) % P1;
c2[i] = c2[i - 1] * base2 % P2;
h2[i] = (h2[i - 1] * base2 + s[i]) % P2;
}
while (m -- )
{
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get1(l1, r1) == get1(l2, r2) && get2(l1, r1) == get2(l2, r2))
puts("Yes");
else puts("No");
}
return 0;
}
第三讲 搜索与图论
DFS
AcWing842 排列数字
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int path[N], n;
bool st[N];
void dfs(int u)
{
if (u > n)
{
for (int i = 1; i <= n; i ++ ) printf("%d ", path[i]);
puts("");
}
for (int i = 1; i <= n; i ++ )
{
if (!st[i])
{
path[u] = i;
st[i] = true;
dfs(u + 1);
st[i] = false;
path[u] = 0;
}
}
}
int main()
{
scanf("%d", &n);
dfs(1);
return 0;
}
// 写法2：调用next_permutation函数
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int a[N], n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) a[i] = i + 1;
do {
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
puts("");
} while (next_permutation(a, a + n));
return 0;
}
AcWing843. n-皇后问题
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
bool col[N], dg[N], udg[N];
char g[N][N];
int n;
void dfs(int u)
{
if (u >= n)
{
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
return ;
}
for (int i = 0; i < n; i ++ )
{
if (!col[i] && !dg[u + i] && !udg[u - i + n])
{
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[u - i + n] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[u - i + n] = false;
g[u][i] = '.';
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0);
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
bool row[N], col[N], dg[N], udg[N];
char g[N][N];
int n;
void dfs(int x, int y, int s) // x表示行，y表示列，s表示当前皇后的个数
{
if (y == n) y = 0, x ++ ;
if (x == n) // 如果全部行已经扫描完了，那么就输出全部皇后所在的位置
{
if (s == n)
{
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
}
return ;
}
// 如果(x,y)这个位置不放皇后,那么就递归它的下一个位置(x,y+1)
dfs(x, y + 1, s);
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
{
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
dfs(x, y + 1, s + 1); // 递归下一个位置(x,y+1)的位置，因为之前放了皇后，所以s+1
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
g[x][y] = '.';
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0, 0, 0);
return 0;
}
BFS
AcWing844. 走迷宫
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int g[N][N], dist[N][N], n, m;
PII q[N * N];
int bfs()
{
memset(dist, -1, sizeof dist);
dist[0][0] = 0;
int hh = 0, tt = 0;
q[0] = {0, 0};
while (hh <= tt)
{
PII t = q[hh ++ ];
for (int i = 0; i < 4; i ++ )
{
int a = + dx[i], b = + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m || ~dist[a][b] || g[a][b])
continue;
dist[a][b] = dist[][] + 1;
q[ ++ tt] = {a, b};
}
}
return dist[n - 1][m - 1];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
scanf("%d", &g[i][j]);
printf("%d\n", bfs());
return 0;
}
AcWing845. 八数码
传送门
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int bfs(string S)
{
string T = "12345678x";
queue<string> q;
unordered_map<string, int> dist;
dist[S] = 0;
(S);
while (())
{
string t = ();
();
int d = dist[t];
if (t == T) return d;
int k = ('x');
int x = k / 3, y = k % 3;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3)
{
swap(t[k], t[a * 3 + b]);
if (!(t))
{
dist[t] = d + 1;
(t);
}
swap(t[k], t[a * 3 + b]);
}
}
}
return -1;
}
int main()
{
string s;
for (int i = 0; i < 9; i ++ )
{
char c;
cin >> c;
s += c;
}
printf("%d\n", bfs(s));
return 0;
}
树与图的深度优先遍历
AcWing846. 树的重心
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int n, ans = 1 << 30;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs(int x, int fa) // 返回以x为根的这棵子树的大小(包括x)
{
int cnt = 0, s = 1;
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (y == fa ) continue;
int t = dfs(y, x);
cnt = max(cnt, t);
s += t;
}
ans = min(ans, max(cnt, n - s));
return s;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs(1, -1);
printf("%d\n", ans);
return 0;
}
// 写法2：vector建图
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N];
int n, ans = 1 << 30;
int dfs(int x, int fa) // 返回以x为根的这棵子树的大小(包括x)
{
int cnt = 0, s = 1;
for (auto &y : e[x])
{
if (y == fa) continue;
int t = dfs(y, x);
cnt = max(cnt, t);
s += t;
}
ans = min(ans, max(cnt, n - s));
return s;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
e[a].push_back(b), e[b].push_back(a);
}
dfs(1, -1);
printf("%d\n", ans);
return 0;
}
树与图的广度优先遍历
AcWing847. 图中点的层次
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N;
int h[N], e[M], ne[M], idx;
int dist[N], q[N], n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int bfs()
{
memset(dist, -1, sizeof dist);
dist[1] = 0;
int hh = 0, tt = 0;
q[0] = 1;
while (hh <= tt)
{
int u = q[hh ++ ];
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if (dist[v] == -1)
{
dist[v] = dist[u] + 1;
q[ ++ tt] = v;
}
}
}
return dist[n];
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
printf("%d\n", bfs());
return 0;
}
拓扑排序
AcWing848. 有向图的拓扑序列
传送门
// BFS求拓扑排序：add建图
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N;
int h[N], e[M], ne[M], idx;
int d[N], q[N], n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int u = q[hh ++ ];
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if (-- d[v] == 0)
q[ ++ tt] = v;
}
}
return tt == n - 1;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
d[b] ++ ;
}
if (topsort())
{
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
puts("");
}
else puts("-1");
return 0;
}
// BFS求拓扑排序：vector建图
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N];
int d[N], q[N], n, m;
bool topsort()
{
int front = 1, rear = 0;
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ rear] = i;
while (front <= rear)
{
int u = q[front ++ ];
for (auto &v : e[u])
if (-- d[v] == 0)
q[ ++ rear] = v;
}
return rear == n;
}
int main()
{
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
e[a].push_back(b);
d[b] ++ ;
}
if (topsort())
{
for (int i = 1; i <= n; i ++ ) printf("%d ", q[i]);
puts("");
}
else puts("-1");
return 0;
}
// DFS求拓扑排序
/*
思路：DFS时候，遇到u->v边，通过在DFS函数快退出时将结点加入到答案ans中
实现v在序中列的位置始终在u的前面逆序输出即为所求的拓扑序列
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N;
int h[N], e[M], ne[M], idx;
int c[N], n, m;
vector<int> ans;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
/*
c[u] = 1 表示之前已经访问过了,并且还递归访问过它的所有子孙(即dfs(u)曾经被调用过并已经返回) 过去
c[u] = -1 表示当前正在访问(即递归调用dfs(u)正在栈帧中,尚未返回) 现在
c[u] = 0 表示从来没有访问过,未来或许会被访问到(从来没有调用过dfs(u) 未来
*/
bool dfs(int u)
{
c[u] = -1; // 标记当前正在访问u
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
// 如果v正在被访问(则与u正在被访问矛盾)
if (c[v] == -1) return false;
if (!c[v])
if (!dfs(v))
return false;
}
c[u] = 1; // 标记已经访问过节点u了,对u的访问结束
/*
将节点u存入拓扑序列中, 可以理解为递归到了叶子节点后把这个叶子节点存入拓扑序列中,
之后回溯时就会把叶子节点的父节点...根节点也都存入拓扑序列中, 因此到时候逆序输出就可以得到正确的拓扑序列了
*/
ans.push_back(u);
return true;
}
bool topsort()
{
memset(c, 0, sizeof c); // 初始化为都还没有被访问过
for (int i = 1; i <= n; i ++ )
if (!c[i])
if (!dfs(i))
return false;
return true;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
if (topsort())
{
// 逆序输出dfs得到的结果,那么就是拓扑序列
for (int i = () - 1; i >= 0; i -- ) printf("%d ", ans[i]);
puts("");
}
else puts("-1");
return 0;
}
Dijkstra
AcWing849. Dijkstra求最短路 I
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], dist[N], n, m;
bool st[N];
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if (dist[n] == INF) puts("-1");
else printf("%d\n", dist[n]);
}
int main()
{
memset(g, 0x3f, sizeof g);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
}
dijkstra();
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
vector<pair<int, int>> e[N];
int dist[N], n, m;
bool st[N];
void dijkstra()
{
memset(dist, 127, sizeof dist);
dist[1] = 0;
while (1)
{
int x = -1;
for (int i = 1; i <= n; i ++ )
if (!st[i] && (x == -1 || dist[i] < dist[x]))
x = i;
if (x == -1 || x == n) break;
st[x] = true;
for (auto &it : e[x])
dist[] = min(dist[], dist[x] + );
}
if (dist[n] < 1 << 30) printf("%d\n", dist[n]);
else puts("-1");
}
int main()
{
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
e[a].push_back({b, c});
}
dijkstra();
return 0;
}
AcWing850. Dijkstra求最短路 II
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = N, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int h[N], e[N], ne[N], w[N], idx;
int dist[N], n, m;
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue < PII, vector<PII>, greater<PII>> q;
({0, 1});
while (())
{
auto t = (); ();
int u = ;
if (u == n) break;
if (st[u]) continue;
st[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if (dist[v] > dist[u] + w[i])
{
dist[v] = dist[u] + w[i];
({dist[v], v});
}
}
}
if (dist[n] == INF) puts("-1");
else printf("%d\n", dist[n]);
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
dijkstra();
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
vector<PII> e[N];
set<PII> q;
int dist[N], n, m;
void dijkstra()
{
memset(dist, 127, sizeof dist);
dist[1] = 0;
();
for (int i = 1; i <= n; i ++ )
({dist[i], i});
while (!())
{
int x = ()->second;
if (x == n || dist[x] > 1 << 30) break;
(());
for (auto &it : e[x])
{
if (dist[] > dist[x] + )
{
({dist[], });
dist[] = dist[x] + ;
({dist[], });
}
}
}
if (dist[n] < 1 << 30) printf("%d\n", dist[n]);
else puts("-1");
}
int main()
{
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
e[a].push_back({b, c});
}
dijkstra();
return 0;
}
bellman-ford
AcWing853. 有边数限制的最短路
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 10010, INF = 0x3f3f3f3f;
int dist[N], backup[N], n, m, k;
struct Edge {
int a, b, c;
} e[M];
void Bellman_Ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
while (k -- )
{
memcpy(backup, dist, sizeof dist);
for (int i = 0; i < m; i ++ )
{
int a = e[i].a, b = e[i].b, c = e[i].c;
dist[b] = min(dist[b], backup[a] + c);
}
}
if (dist[n] > INF / 2) puts("impossible");
else printf("%d\n", dist[n]);
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i ++ )
scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
Bellman_Ford();
return 0;
}
spfa
AcWing851. spfa求最短路
传送门
// 手写循环队列实现 也可以使用STL中的queue
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], q[N], n, m;
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
int hh = 0, tt = 1;
q[tt ++ ] = 1;
st[1] = true;
while (hh != tt)
{
int u = q[hh ++ ];
if (hh == N) hh = 0;
st[u] = false;
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if (dist[v] > dist[u] + w[i])
{
dist[v] = dist[u] + w[i];
if (!st[v])
{
q[tt ++ ] = v;
if (tt == N) tt = 0;
st[v] = true;
}
}
}
}
if (dist[n] == INF) puts("impossible");
else printf("%d\n", dist[n]);
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%dd", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
spfa();
return 0;
}
AcWing852. spfa判断负环
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 10010;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N], q[N], n, m; // cnt记录1号顶点到图的某个顶点的最短路径中的边的个数
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool spfa()
{
int hh = 0, tt = 1;
for (int i = 1; i <= n; i ++ )
{
q[tt ++ ]= i;
st[i] = true;
}
while (hh != tt)
{
int u = q[hh ++ ];
if (hh == N) hh = 0;
st[u] = false;
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if (dist[v] > dist[u] + w[i])
{
dist[v] = dist[u] + w[i];
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return true;
if (!st[v])
{
q[tt ++ ] = v;
if (tt == N) tt = 0;
st[v] = true;
}
}
}
}
return false;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
puts(spfa() ? "Yes" : "No");
return 0;
}
Floyd
AcWing854. Floyd求最短路
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int dist[N][N], n, m, Q;
void Floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int main()
{
scanf("%d%d%d", &n, &m, &Q);
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i ++ ) dist[i][i] = 0;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
dist[a][b] = min(dist[a][b], c);
}
Floyd();
while (Q -- )
{
int a, b;
scanf("%d%d", &a, &b);
if (dist[a][b] > INF / 2) puts("impossible");
else printf("%d\n", dist[a][b]);
}
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int dist[N][N], n, m, Q;
void Floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (dist[i][k] < 1 << 30 && dist[k][j] < 1 << 30)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int main()
{
scanf("%d%d%d", &n, &m, &Q);
memset(dist, 127, sizeof dist);
for (int i = 1; i <= n; i ++ ) dist[i][i] = 0;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
dist[a][b] = min(dist[a][b], c);
}
Floyd();
while (Q -- )
{
int a, b;
scanf("%d%d", &a, &b);
if (dist[a][b] < 1 << 30) printf("%d\n", dist[a][b]);
else puts("impossible");
}
return 0;
}
Prim
AcWing858. Prim算法求最小生成树
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], dist[N], n, m;
bool st[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
int ans = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
if (dist[t] == INF) return INF;
ans += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], g[t][j]);
}
return ans;
}
int main()
{
memset(g, 0x3f, sizeof g);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
int ans = prim();
if (ans == INF) puts("impossible");
else printf("%d\n", ans);
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], dist[N], n, m;
bool st[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
int ans = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
if (i && dist[t] == INF) return INF;
if (i) ans += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], g[t][j]);
}
return ans;
}
int main()
{
memset(g, 0x3f, sizeof g);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
int ans = prim();
if (ans == INF) puts("impossible");
else printf("%d\n", ans);
return 0;
}
// 写法3
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
vector<pair<int, int>> e[N];
int dist[N], n, m;
bool st[N];
void prim()
{
memset(dist, 127, sizeof dist);
dist[1] = 0;
int ans = 0, tot = 0;
while (1)
{
int x = -1;
for (int j = 1; j <= n; j ++ )
{
if (!st[j] && dist[j] < 1 << 30)
if (x == -1 || dist[j] < dist[x])
x = j;
}
if (x == -1) break;
tot ++ ;
st[x] = true;
ans += dist[x];
for (auto it : e[x])
dist[] = min(dist[], );
}
if (tot != n) printf("impossible");
else printf("%d\n", ans);
}
int main()
{
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
e[a].push_back({b, c});
e[b].push_back({a, c});
}
prim();
return 0;
}
// 写法4：堆优化版
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
typedef pair<int, int> PII;
vector<PII> e[N];
set<PII> q;
int dist[N], n, m;
bool st[N];
void prim()
{
memset(dist, 127, sizeof dist);
dist[1] = 0;
();
for (int i = 1; i <= n; i ++ )
({dist[i], i});
int ans = 0, tot = 0;
while (!())
{
int x = ()->second;
(());
if (dist[x] > 1 << 30) break;
tot ++ ;
ans += dist[x];
st[x] = true;
for (auto &it : e[x])
{
if (!st[] && < dist[])
{
({dist[], });
dist[] = ;
({dist[], });
}
}
}
if (tot != n) puts("impossible");
else printf("%d\n", ans);
}
int main()
{
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
e[a].push_back({b, c});
e[b].push_back({a, c});
}
prim();
return 0;
}
Kruskal
AcWing859. Kruskal算法求最小生成树
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
struct Edge {
int a, b, c;
bool operator < (const Edge &t) const {
return c < ;
}
} e[M];
int p[N], n, m;
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
void Kruskal()
{
sort(e + 1, e + 1 + m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int ans = 0, cnt = 0; // cnt表示最小生成树中的边的总数
for (int i = 1; i <= m; i ++ )
{
int a = find(e[i].a), b = find(e[i].b), c = e[i].c;
if (a != b)
{
p[a] = b;
ans += c;
cnt ++ ;
}
}
if (cnt < n - 1) puts("impossible");
else printf("%d\n", ans);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
Kruskal();
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
struct Edge {
int a, b, c;
bool operator < (const Edge &t) const {
return c < ;
}
} e[M];
int p[N], n, m;
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
void Kruskal()
{
sort(e + 1, e + 1 + m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int ans = 0, cnt = n;
for (int i = 1; i <= m; i ++ )
{
int a = find(e[i].a), b = find(e[i].b), c = e[i].c;
if (a != b)
{
p[a] = b;
ans += c;
cnt -- ;
}
}
if (cnt != 1) puts("impossible");
else printf("%d\n", ans);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
Kruskal();
return 0;
}
染色法判定二分图
AcWing860. 染色法判定二分图
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int c[N], n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool dfs(int x)
{
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (!c[y])
{
c[y] = 3 - c[x];
if (!dfs(y)) return false;
} else if (c[x] == c[y]) return false;
}
return true;
}
bool check()
{
for (int i = 1; i <= n; i ++ )
{
if (!c[i])
{
c[i] = 1;
if (!dfs(i)) return false;
}
}
return true;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
puts(check() ? "Yes" : "No");
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N];
int c[N], n, m;
bool dfs(int x)
{
for (auto y : e[x])
{
if (!c[y])
{
c[y] = 3 - c[x];
if (!dfs(y))
return false;
} else if (c[x] == c[y]) return false;
}
return true;
}
bool check()
{
memset(c, 0, sizeof c);
for (int i = 1; i <= n; i ++ )
{
if (!c[i])
{
c[i] = 1;
if (!dfs(i))
return false;
}
}
return true;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
{
int x, y;
scanf("%d%d", &x, &y);
e[x].push_back(y);
e[y].push_back(x);
}
if (check()) puts("Yes");
else puts("No");
return 0;
}
匈牙利算法
AcWing861. 二分图的最大匹配
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e5 + 10;
int h[N], e[M], ne[M], idx;
int n1, n2, m, v[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool find(int x)
{
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (!st[y])
{
st[y] = true;
if (!v[y] || find(v[y]))
{
v[y] = x;
return true;
}
}
}
return false;
}
void solve()
{
int ans = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, 0, sizeof st);
if (find(i)) ans ++ ;
}
printf("%d\n", ans);
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d%d", &n1, &n2, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
solve();
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
vector<int> e[N];
int n1, n2, m, v[N];
bool st[N];
bool find(int x)
{
st[x] = true;
for (auto &y : e[x])
{
if (!v[y] || (!st[v[y]] && find(v[y])))
{
v[y] = x;
return true;
}
}
return false;
}
void solve()
{
int ans = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, 0, sizeof st);
if (find(i)) ans ++ ;
}
printf("%d\n", ans);
}
int main()
{
scanf("%d%d%d", &n1, &n2, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
e[a].push_back(b);
}
solve();
return 0;
}
第四讲 数学知识
质数
AcWing866. 试除法判定质数
传送门
#include <bits/stdc++.h>
using namespace std;
bool check(int n)
{
if (n < 2) return false;
for (int i = 2; i <= n / i; i ++ )
if (n % i == 0)
return false;
return true;
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int x;
scanf("%d", &x);
puts(check(x) ? "Yes" : "No");
}
return 0;
}
AcWing867. 分解质因数
传送门
#include <bits/stdc++.h>
using namespace std;
void solve(int n)
{
for (int i = 2; i <= n / i; i ++ )
{
if (n % i == 0)
{
int s = 0;
while (n % i == 0)
{
n /= i;
s ++ ;
}
printf("%d %d\n", i, s);
}
}
if (n > 1) printf("%d 1\n", n);
puts("");
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int x;
scanf("%d", &x);
solve(x);
}
return 0;
}
AcWing868. 筛质数
传送门
// 埃式筛
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt, n;
bool st[N];
void solve()
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
for (int j = 2 * i; j <= n; j += i)
st[j] = true;
}
}
}
int main()
{
scanf("%d", &n);
solve();
printf("%d\n", cnt);
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt, n;
bool st[N];
void solve()
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
for (int j = i; j <= n / i; j ++ )
st[i * j] = true;
}
}
}
int main()
{
scanf("%d", &n);
solve();
printf("%d\n", cnt);
return 0;
}
// 线性筛
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt, n;
bool st[N];
void solve()
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; j < cnt && primes[j] <= n / i; j ++ )
{
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
int main()
{
scanf("%d", &n);
solve();
printf("%d\n", cnt);
return 0;
}
约数
AcWing869. 试除法求约数
传送门
#include <bits/stdc++.h>
using namespace std;
void solve(int n)
{
vector<int> res;
for (int i = 1; i <= n / i; i ++ )
{
if (n % i == 0)
{
res.push_back(i);
if (i != n / i) res.push_back(n / i);
}
}
sort((), ());
for (auto &i : res)
printf("%d ", i);
puts("");
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int x;
scanf("%d", &x);
solve(x);
}
return 0;
}
AcWing870. 约数个数
传送门
#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
using LL = long long ;
unordered_map<int, int> primes;
void solve(int n) // 分解质因子
{
for (int i = 2; i <= n / i; i ++ )
{
while (n % i == 0)
{
primes[i] ++ ;
n /= i;
}
}
if (n > 1) primes[n] ++ ;
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int x;
scanf("%d", &x);
solve(x);
}
LL ans = 1;
for (auto &it : primes)
ans = ans * ( + 1) % P;
printf("%lld\n", ans);
return 0;
}
AcWing871. 约数之和
传送门
#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
using LL = long long ;
unordered_map<int, int> primes;
void solve(int n) // 分解质因子
{
for (int i = 2; i <= n / i; i ++ )
{
while (n % i == 0)
{
primes[i] ++ ;
n /= i;
}
}
if (n > 1) primes[n] ++ ;
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int x;
scanf("%d", &x);
solve(x);
}
LL ans = 1;
for (auto &it : primes)
{
// p是质因子,s是该质因子的个数
LL p = , s = , t = 1;
while (s -- )
t = (t * p + 1) % P;
ans = ans * t % P;
}
printf("%lld\n", ans);
return 0;
}
AcWing872 最大公约数
传送门
#include <bits/stdc++.h>
using namespace std;
inline int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", gcd(a, b));
}
return 0;
}
欧拉函数
AcWing873. 欧拉函数
传送门
#include <bits/stdc++.h>
using namespace std;
void solve(int n)
{
int ans = n;
for (int i = 2; i <= n / i; i ++ )
{
if (n % i == 0)
{
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) ans = ans / n * (n - 1);
printf("%d\n", ans);
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int x;
scanf("%d", &x);
solve(x);
}
return 0;
}
Acwing874. 筛法求欧拉函数
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
using LL = long long ;
int phi[N], primes[N], cnt, n;
bool st[N];
void solve()
{
phi[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
phi[i] = i - 1;
}
for (int j = 0; j < cnt && primes[j] <= n / i; j ++ )
{
st[i * primes[j]] = true;
if (i % primes[j] == 0)
{
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
LL ans = 0;
for (int i = 1; i <= n; i ++ ) ans += phi[i];
printf("%lld\n", ans);
}
int main()
{
scanf("%d", &n);
solve();
return 0;
}
快速幂
AcWing875. 快速幂
传送门
#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
int qmi(LL a, int b, int p)
{
LL ans = 1;
while (b)
{
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int a, b, p;
scanf("%d%d%d", &a, &b, &p);
printf("%lld\n", qmi(a, b, p));
}
return 0;
}
AcWing876. 快速幂求逆元
传送门
#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
LL qmi(LL a, int b, int p)
{
LL ans = 1;
while (b)
{
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int a, p;
scanf("%d%d", &a, &p);
if (a % p == 0) puts("impossible");
else printf("%lld\n", qmi(a, p - 2, p));
}
return 0;
}
扩展欧几里得算法
AcWing877. 扩展欧几里得算法
传送门
#include <bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int a, b, x, y;
scanf("%d%d", &a, &b);
exgcd(a, b, x, y);
printf("%d %d\n", x, y);
}
return 0;
}
AcWing878. 线性同余方程
传送门
#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
int main()
{
int m;
scanf("%d", &m);
while (m -- )
{
int a, b, m, x, y;
scanf("%d%d%d", &a, &b, &m);
int d = exgcd(a, m, x, y);
if (b % d) puts("impossible");
else printf("%lld\n", (LL) x * (b / d) % m);
}
return 0;
}
中国剩余定理
AcWing204. 表达整数的奇怪方式
传送门
这题其实是扩展中国剩余定理，而不是中国剩余定理。P1495才是中国剩余定理的模板题。
// P1495 中国剩余定理
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
using LL = long long ;
LL a[N], m[N], M = 1;
int n;
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
// 中国剩余定理的模板
LL CRT() {
LL ans = 0;
for (int i = 1; i <= n; i ++ ) {
LL Mi = M / m[i];
LL x, y;
exgcd(Mi, m[i], x, y); // 利用扩展欧几里得求出x和y
// 此时的x就是Mi模mi意义下的逆元
ans = ((ans + a[i] * Mi * x) % M + M) % M; // 保证最小正整数解
}
// 这里也可以写成reutnr ans 因为上面已经保证求出来的ans是最小正整数解了
return (ans % M + M) % M; // 保证最小正整数解
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
// 这里m[i]就是题目中猪圈数,a[i]就是无家可归的猪数
scanf("%lld%lld", &m[i], &a[i]);
M *= m[i]; // 累乘每个式子中模数mi 得到M
}
printf("%lld\n", CRT());
return 0;
}
// 本题，扩展中国剩余定理
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using LL = long long ;
LL a[N], m[N], n;
// 注意数据范围可能会爆long long需要用到龟速乘
LL mul(LL a, LL b, LL mod) {
LL ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return ans % mod;
}
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
// 扩展中国剩余定理
LL EXCRT() {
// ans表示前i-1个方程式的通解(余数), M为前i-1个方程式的模数的最小公倍数
LL ans = a[1], M = m[1];
for (int i = 2; i <= n; i ++ ) {
LL t, y;
// res其实就是(a2-a1)%m[i] 不过为了防止负数 需要这么写
LL res = ((a[i] - ans) % m[i] + m[i]) % m[i];
// 使用扩欧求出最大公约数d,并且求出了整数t
LL d = exgcd(M, m[i], t, y);
// 无解
if (res % d) return -1;
t = mul(t, res / d, m[i]);
// 注意下面的这两个式子不能颠倒
ans += t * M; // 得到前i个方程的通解
M = m[i] / d * M; // M等于lcm(M,mi),注意乘法要在除法后面做,否则会爆long long
// 让通解范围限定在0~(M-1)内,防止会出现负数
ans = (ans % M + M) % M; // 求出最小非负整数解
}
return (ans % M + M) % M; // 求出最小非负整数解
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%lld%lld", &m[i], &a[i]);
printf("%lld\n", EXCRT());
return 0;
}
高斯消元
AcWing883. 高斯消元解线性方程组
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const double eps = 1e-6;
double a[N][N];
int n;
int gauss()
{
int r, c; // r表示当前所在的行数,c表示当前所指向的列数
for (r = 0, c = 0; c < n; c ++ ) {
// step1: 找到当前列下绝对值最大的行t
// 寻找绝对值最大的数是因为可以避免系数变得太大,精度较高.
int t = r;
for (int i = r; i < n; i ++ )
if (fabs(a[t][c]) < fabs(a[i][c]))
t = i;
// 如果当前这一列的最大数都是0,那么所有数都是0,那么就跳过该列,继续枚举下一列
if (fabs(a[t][c]) < eps) continue;
// 如果当前列下绝对值最大的数所在的行t和当前枚举的行r不同 那么执行step2
// step2: 让第t行与未固定的行(第r行)的第一行交换
if (t != r) {
for (int j = c; j <= n; j ++ )
swap(a[t][j], a[r][j]);
}
// step3: 将该行中的第一个非0的数化为1
// 这里必须从后往前做,假设我们从前往后做,那么就先把该行中的第一个非0的数a[r][c]化为1了,此时a[r][c]=1
// 但是它是一直循环的做,那么之后的数a[r][j]/=a[r][c]就等于a[r][j]/=1,也就等于a[r][j] 并没有改变
// 主要的原因就是你从前往后的话就先把a[r][c]变为1了 那么后面的数除以的就是被更新后的a[r][c] 而不是最初的a[r][c]
for (int j = n; j >= c; j -- )
a[r][j] /= a[r][c];
// step4: 将下面所有行的第c列变为0
for (int i = r + 1; i < n; i ++ ) {
// 只有当前行它的数不为0,才要进行削为0的操作
// 如果当前行它的数为零,说明不用进行削为零的操作
if (fabs(a[i][c]) > eps) {
// 这里也需要倒着做 原理同上
// 从后往前,当前i行的每个数字,都减去第i行的第c列a[i][c] * 第r行从第n列开始到第c列的每个数a[r][j]
for (int j = n; j >= c; j -- )
a[i][j] -= a[i][c] * a[r][j];
}
}
r ++ ; // 这一行的工作做完,换下一行
}
// 说明剩下方程的个数是小于n的,说明不是唯一解,判断是无解还是无穷多解
if (r < n) {
// 因为已经是阶梯型,所以r~n-1的值应该都为0
for (int i = r; i < n; i ++ )
if (fabs(a[i][n]) > eps) // 第i行的结果a[i][n]结果不是0 即出现了0 = 非0 所以无解
return 2;
return 1; // 否则,0=0,就是r~n-1的方程都是多余方程 所以有无穷多组解
}
// 说明有唯一解 自底向上回代结果
for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
a[i][n] -= a[i][j] * a[j][n];
return 0;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j <= n; j ++ )
scanf("%lf", &a[i][j]);
int t = gauss();
if (!t) { // 有唯一解
for (int i = 0; i < n; i ++ ) {
// 可能会出现输出-0.00的情况 因此需要特判掉
if (fabs(a[i][n]) < eps) a[i][n] = 0;
printf("%.2lf\n", a[i][n]);
}
} else if (t == 1) { // 有无穷多组解
puts("Infinite group solutions");
} else puts("No solution"); // 无解
return 0;
}
AcWing884. 高斯消元解异或线性方程组
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N], n;
int gauss() {
int r, c;
for (r = 0, c = 0; c < n; c ++ ) {
int t = r;
for (int i = r; i < n; i ++ ) {
if (a[i][c]) {
t = i;
break;
}
}
if (!a[t][c]) continue;
if (t != r) {
for (int j = c; j <= n; j ++ )
swap(a[t][j], a[r][j]);
}
for (int i = r + 1; i < n; i ++ ) {
if (a[i][c]) {
for (int j = n; j >= c; j -- )
a[i][j] ^= a[r][j]; // 也可以写成a[i][j] ^= a[i][c] & a[r][j]
}
}
r ++;
}
if (r < n) {
for (int i = r; i < n; i ++ )
if (a[i][n])
return 2;
return 1;
}
for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
a[i][n] ^= a[i][j] & a[j][n];
return 0;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n + 1; j++)
scanf("%d", &a[i][j]);
int t = gauss();
if (!t) {
for (int i = 0; i < n; i++)
printf("%d\n", a[i][n]);
}
else if (t == 1)
puts("Multiple sets of solutions");
else
puts("No solution");
return 0;
}
求组合数
AcWing885. 求组合数 I
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int C[N][N], T;
void init() {
for (int i = 0; i < N; ++ i) {
for (int j = 0; j <= i; ++ j) {
if (j == 0 || j == i) C[i][j] = 1;
else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
}
int main()
{
init();
scanf("%d", &T);
while (T -- ) {
int n, m;
scanf("%d%d", &n, &m);
printf("%d\n", C[n][m]);
}
return 0;
}
AcWing886. 求组合数 II
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, P = 1e9 + 7;
using LL = long long ;
int fact[N], infact[N];
int T;
int qmi(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (LL)ans * a % P;
a = (LL)a * a % P;
b >>= 1;
}
return ans;
}
void init() {
fact[0] = infact[0] = 1;
for (int i = 1; i < N; ++ i) {
fact[i] = (LL)fact[i - 1] * i % P;
infact[i] = (LL)infact[i - 1] * qmi(i, P - 2) % P;
}
}
int main()
{
init();
scanf("%d", &T);
while (T -- ) {
int n, m;
scanf("%d%d", &n, &m);
printf("%d\n", (LL)fact[n] * infact[m] % P * infact[n - m] % P);
}
return 0;
}
AcWing887. 求组合数 III
传送门
#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
int T, P;
int qmi(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (LL)ans * a % P;
a = (LL)a * a % P;
b >>= 1;
}
return ans;
}
// 递推求解朴素的C(a,b)
int C(int n, int m) {
if (m > n) return 0;
int ans = 1;
// i控制的是分母的循环,对于b!，从1到b总共有b个数
// j控制的是分子的循环,从a到a-b+1总共有b个数
// 因此可以发现，分子和分母循环的次数是相同的
for (int i = 1, j = n; i <= m; ++ i, -- j) {
ans = (LL)ans * j % P;
ans = (LL)ans * qmi(i, P - 2) % P;
}
return ans;
}
// 用Lucas定理递归求解
int Lucas(LL n, LL m) {
if (n < P && m < P ) return C(n, m);
return (LL)C(n % P, m % P) * Lucas(n / P, m / P) % P;
}
int main()
{
scanf("%d", &T);
while (T -- ) {
LL n, m;
scanf("%lld%lld%d", &n, &m, &P);
printf("%d\n", Lucas(n, m));
}
return 0;
}
AcWing888. 求组合数 IV
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int s[N], primes[N], cnt;
bool st[N];
void get_primes(int n) {
for (int i = 2; i <= n; ++ i) {
if (!st[i] ) primes[cnt ++ ] = i;
for (int j = 0; j < cnt && primes[j] <= n / i; ++ j) {
st[i * primes[j]] = true;
if (i % primes[j] == 0 ) break;
}
}
}
int get(int n, int p) {
int ans = 0;
while (n) {
ans += n / p;
n /= p;
}
return ans;
}
vector<int> mul(vector<int> &A, int b) {
vector<int> C;
for (int i = 0, t = 0; i < () || t; ++ i) {
if (i < ()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (() > 1 && () == 0) C.pop_back();
return C;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
get_primes(n);
for (int i = 0; i < cnt; ++ i) {
int p = primes[i];
s[i] = get(n, p) - get(m, p) - get(n - m, p);
}
vector<int> ans;
ans.push_back(1);
for (int i = 0; i < cnt; ++ i)
for (int j = 0; j < s[i]; ++ j)
ans = mul(ans, primes[i]);
for (int i = () - 1; i >= 0; -- i)
printf("%d", ans[i]);
puts("");
return 0;
}
AcWing889. 满足条件的01序列
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
using LL = long long ;
int n;
int qmi(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (LL)ans * a % P;
a = (LL)a * a % P;
b >>= 1;
}
return ans;
}
int main() {
scanf("%d", &n);
int a = 2 * n, b = n, ans = 1;
for (int i = 1, j = a; i <= n; ++ i, -- j) {
ans = (LL)ans * j % P;
ans = (LL)ans * qmi(i, P - 2) % P;
}
ans = (LL)ans * qmi(n + 1, P - 2) % P;
printf("%lld\n", ans);
return 0;
}
// 写法2
#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
const int N = 2e5 + 10, P = 1e9 + 7;
int fact[N], infact[N], n;
int qmi(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (LL)ans * a % P;
a = (LL)a * a % P;
b >>= 1;
}
return ans;
}
void init() {
fact[0] = infact[0] = 1;
for (int i = 1; i < N; ++ i) {
fact[i] = (LL)fact[i - 1] * i % P;
infact[i] = (LL)infact[i - 1] * qmi(i, P - 2) % P;
}
}
int main()
{
init();
scanf("%d", &n);
int ans = (LL)fact[2 * n] * infact[n] % P * infact[n] % P * qmi(n + 1, P - 2) % P;
printf("%d\n", ans);
return 0;
}
容斥原理
AcWing890. 能被整除的数
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
using LL = long long ;
int p[N], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i ++ ) scanf("%d", &p[i]);
int ans = 0;
for (int i = 1; i < 1 << m; i ++ ) {
int t = 1, cnt = 0;
for (int j = 0; j < m; j ++ ) {
if (i >> j & 1) {
if ((LL)t * p[j] > n) {
t = -1;
break;
}
cnt ++ ;
t *= p[j];
}
}
if (t == -1) continue;
cnt & 1 ? ans += n / t : ans -= n / t;
}
printf("%d\n", ans);
return 0;
}
博弈论
AcWing891. Nim游戏
传送门
#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
int main()
{
int n, x;
scanf("%d", &n);
LL ans = 0;
while (n -- )
{
scanf("%d", &x);
ans ^= x;
}
puts(ans ? "Yes" : "No");
return 0;
}
AcWing892. 台阶-Nim游戏
传送门
#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
int main()
{
int n, x;
scanf("%d", &n);
LL ans = 0;
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &x);
if (i & 1) ans ^= x;
}
puts(ans ? "Yes" : "No");
return 0;
}
AcWing893. 集合-Nim游戏
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 10010;
int s[N], f[M], n, m;
int SG(int x) {
if (~f[x]) return f[x];
unordered_set<int> S;
for (int i = 0; i < m; ++ i)
if (x >= s[i])
(SG(x - s[i]));
for (int i = 0; ; ++ i)
if (!(i))
return f[x] = i;
}
int main()
{
memset(f, -1, sizeof f);
scanf("%d", &m);
for (int i = 0; i < m; ++ i) scanf("%d", &s[i]);
scanf("%d", &n);
int ans = 0;
while (n -- ) {
int x;
scanf("%d", &x);
ans ^= SG(x);
}
puts(ans ? "Yes" : "No");
return 0;
}
AcWing894. 拆分-Nim游戏
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N], n;
int SG(int x) {
if (~f[x]) return f[x];
unordered_set<int> S;
for (int i = 0; i < x; ++ i)
for (int j = 0; j <= i; ++ j)
(SG(i) ^ SG(j));
for (int i = 0; ; ++ i)
if (!(i))
return f[x] = i;
}
int main()
{
memset(f, -1, sizeof f);
scanf("%d", &n);
int ans = 0;
while (n -- ) {
int x;
scanf("%d", &x);
ans ^= SG(x);
}
puts(ans ? "Yes" : "No");
return 0;
}
第五讲 动态规划
背包问题
AcWing2. 01背包问题
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
int w, v;
scanf("%d%d", &w, &v);
for (int j = m; j >= w; j -- )
f[j] = max(f[j], f[j - w] + v);
}
printf("%d\n", f[m]);
return 0;
}
AcWing3. 完全背包问题
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
int w, v;
scanf("%d%d", &w, &v);
for (int j = w; j <= m; j ++ )
f[j] = max(f[j], f[j - w] + v);
}
printf("%d\n", f[m]);
return 0;
}
AcWing4. 多重背包问题 I
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
int w, v, c;
scanf("%d%d%d", &w, &v, &c);
for (int j = m; j >= w; j -- )
for (int k = 0; k <= c && k * w <= j; k ++ )
f[j] = max(f[j], f[j - k * w] + k * v);
}
printf("%d\n", f[m]);
return 0;
}
AcWing5. 多重背包问题 II
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
// 物品总个数 = N*logs = 1000*log200 = 24000
const int N = 24010, M = 2010;
int w[N], v[N], f[M], n, m, cnt;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
int wi, vi, c;
scanf("%d%d%d", &wi, &vi, &c);
for (int k = 1; k <= c; k <<= 1) {
w[ ++ cnt] = k * wi;
v[cnt] = k * vi;
c -= k;
}
if (c > 0) {
w[ ++ cnt] = c * wi;
v[cnt] = c * vi;
}
}
n = cnt;
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= w[i]; j -- )
f[j] = max(f[j], f[j - w[i]] + v[i]);
printf("%d\n", f[m]);
return 0;
}
// 写法二
#include <bits/stdc++.h>
using namespace std;
const int N = 24010, M = 2010;
int f[M], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
int w, v, c;
scanf("%d%d%d", &w, &v, &c);
if (c * w >= m) { // 转化完全背包
for (int j = w; j <= m; j ++ )
f[j] = max(f[j], f[j - w] + v);
} else {
for (int k = 1; c; k <<= 1) { // 进行二进制拆分 转化01背包
int x = min(k, c);
for (int j = m; j >= x * w; j -- )
f[j] = max(f[j], f[j - x * w] + x * v);
c -= x;
}
}
}
printf("%d\n", f[m]);
return 0;
}
AcWing9. 分组背包问题
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int w[N], v[N], f[N], n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) { // 物品组
int c;
scanf("%d", &c);
for (int j = 1; j <= c; j ++ )
scanf("%d%d", &w[j], &v[j]);
for (int j = m; j >= 1; j -- ) // 体积 也可以写成j >= 0
for (int k = 0; k <= c; k ++ ) // 决策 选择第i组中的第k件物品
if (j >= w[k])
f[j] = max(f[j], f[j - w[k]] + v[k]);
}
printf("%d\n", f[m]);
return 0;
}
线性DP
AcWing898. 数字三角形
传送门
// 写法1
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int f[N][N], w[N][N], n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
scanf("%d", &w[i][j]);
// 初始化所有状态为负无穷(因为求最大值),即都是非法状态
memset(f, -0x3f, sizeof f);
// 因为起点(1,1)只能从点(0,0)或(0,1)到达,所以这两个状态是合法的,赋值为0
f[0][0] = f[0][1] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + w[i][j];
int ans = -INF;
for (int j = 1; j <= n; j ++ )
ans = max(ans, f[n][j]);
printf("%d\n", ans);
return 0;
}
// 写法2：自顶向下
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int f[N][N], w[N][N], n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
scanf("%d", &w[i][j]);
// for (int i = 0; i <= n; i ++ )
// for (int j = 0; j <= i + 1; j ++ )
// f[i][j] = -INF;
memset(f, -0x3f, sizeof f);
// 对第一层做特殊处理,金字塔顶端就只有一个数,那么这个数本身就是最大值
f[1][1] = w[1][1];
for (int i = 2; i <= n; i ++ ) // 从金字塔第二层开始枚举到第n层
for (int j = 1; j <= i; j ++ )
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + w[i][j];
int ans = -INF;
for (int j = 1; j <= n; j ++ )
ans = max(ans, f[n][j]);
printf("%d\n", ans);
return 0;
}
// 写法2：自顶向下，空间优化
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int f[N], w[N][N], n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
scanf("%d", &w[i][j]);
memset(f, -0x3f, sizeof f);
f[1] = w[1][1];
for (int i = 2; i <= n; i ++ ) // 类比 01背包的优化
for (int j = i; j >= 1; j -- )
f[j] = max(f[j - 1], f[j]) + w[i][j];
int ans = -INF;
for (int j = 1; j <= n; j ++ )
ans = max(ans, f[j]);
printf("%d\n", ans);
return 0;
}
// 写法3：自底向上
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int f[N][N], w[N][N], n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
scanf("%d", &w[i][j]);
for (int i = n; i >= 1; i -- )
for (int j = i; j >= 1; j -- )
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + w[i][j];
printf("%d\n", f[1][1]);
return 0;
}
// 写法3：自底向上，空间优化
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int f[N], w[N][N], n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
scanf("%d", &w[i][j]);
for (int i = n; i >= 1; i -- )
for (int j = 1; j <= i; j ++ )
f[j] = max(f[j], f[j + 1]) + w[i][j];
printf("%d\n", f[1]);
return 0;
}
AcWing895. 最长上升子序列
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], f[N], n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
int ans = 0;
for (int i = 1; i <= n; i ++ ) {
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
ans = max(ans, f[i]);
}
printf("%d\n", ans);
return 0;
}
AcWing896. 最长上升子序列 II
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
// d[]数组记录最长上升子序列 len表示最长上升子序列的长度
int a[N], d[N], n, len;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) {
// 直接把它接在最长上升子序列的后面
if (!len || a[i] > d[len]) d[ ++ len] = a[i];
// 题目说了严格递增 因此当a[i]等于d[]中的最后一个元素 则跳过 保证严格单调递增
else if (a[i] == d[len]) continue;
else {
int l = 1, r = len;
// 二分找到d数组中第一个>=a[i]的数d[l]
while (l < r) {
int mid = l + r >> 1;
if (d[mid] >= a[i]) r = mid;
else l = mid + 1;
}
d[l] = a[i]; // 替换
}
}
printf("%d\n", len);
return 0;
}
AcWing897. 最长公共子序列
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N], n, m;
int main()
{
scanf("%d%d%s%s", &n, &m, a + 1, b + 1);
// 边界条件
for (int j = 0; j <= m; j ++ ) f[0][j] = 0;
for (int i = 0; i <= n; i ++ ) f[i][0] = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
printf("%d\n", f[n][m]);
return 0;
}
AcWing902. 最短编辑距离
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N], n, m;
int main()
{
scanf("%d%s%d%s", &n, a + 1, &m, b + 1);
// 边界条件
for (int j = 0; j <= m; j ++ ) f[0][j] = j;
for (int i = 0; i <= n; i ++ ) f[i][0] = i;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
else f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
}
}
printf("%d\n", f[n][m]);
return 0;
}
AcWing899. 编辑距离
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 1010;
char s[M][N];
int f[N][N];
int solve(char a[], char b[]) {
int n = strlen(a + 1), m = strlen(b + 1);
for (int j = 0; j <= m; j ++ ) f[0][j] = j;
for (int i = 0; i <= n; i ++ ) f[i][0] = i;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
else f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
}
}
return f[n][m];
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%s", s[i] + 1);
while (m -- ) {
char t[N];
int k, ans = 0;
scanf("%s%d", t + 1, &k);
for (int i = 1; i <= n; i ++ )
if (solve(s[i], t) <= k)
ans ++ ;
printf("%d\n", ans);
}
return 0;
}
区间dp
AcWing282. 石子合并
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int s[N], f[N][N], n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &s[i]);
s[i] += s[i - 1];
}
// 边界条件 初始化
memset(f, 127, sizeof f); // 其他状态都是非法的 由于是求最小值 所以初始化为无穷大
// 只有一堆 自身并不需要合并 最小花费为0
for (int i = 1; i <= n; i ++ ) f[i][i] = 0;
for (int len = 2; len <= n; len ++ ) { // 枚举区间长度
for (int l = 1; l + len - 1 <= n; l ++ ) { // 枚举左端点l
int r = l + len - 1; // 右端点r
for (int k = l; k < r; k ++ ) // 枚举分界点k
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
}
printf("%d\n", f[1][n]);
return 0;
}
计数类DP
AcWing900. 整数划分
传送门
// 写法1：完全背包 二维
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
// f[i][j]表示从前i个数中选，总和恰好为j的划分方法的方案数
int f[N][N], n;
int main()
{
scanf("%d", &n);
for (int i = 0; i <= n; i ++ ) f[i][0] = 1;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
else f[i][j] = f[i - 1][j] % mod;
}
}
printf("%d\n", f[n][n]);
return 0;
}
// 完全背包，一维
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N], n;
int main()
{
scanf("%d", &n);
f[0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = i; j <= n; j ++ )
f[j] = (f[j] + f[j - i]) % mod;
printf("%d\n", f[n]);
return 0;
}
// 计数dp
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N], n; // f[i][j]表示 总和是i，并且由j个数组成的方案数
int main()
{
scanf("%d", &n);
f[0][0] = 1;
for (int i = 1; i <= n; i ++ ) // 枚举总和i 让总和从1枚举到n
for (int j = 1; j <= i; j ++ ) // 枚举整数的个数 从1枚举到n个数
f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
int ans = 0;
for (int i = 1; i <= n; i ++ )
ans = (ans + f[n][i]) % mod;
printf("%d\n", ans);
return 0;
}
数位dp
AcWing338. 计数问题
传送门
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int nums[N], f[N][N];
int dfs(int pos, int cnt, int x, bool lead, bool limit) {
if (!pos) return cnt;
if (!limit && !lead && ~f[pos][cnt]) return f[pos][cnt];
int up = limit ? nums[pos] : 9, ans = 0;
for (int i = 0, t; i <= up; i ++) {
if (x != i ) t = cnt;
else {
if (lead && !x ) t = 0;
else t = cnt + 1;
}
ans += dfs(pos - 1, t, x, lead && i == 0, limit && i == up);
}
if (!limit && !lead) f[pos][cnt] = ans;
return ans;
}
int solve(int x, int num) {
memset(f, -1, sizeof f);
int n = 0;
while (x) {
nums[++ n] = x % 10;
x /= 10;
}
return dfs(n, 0, num, true, true);
}
int main()
{
int l, r;
while (cin >> l >> r, l || r) {
if (l > r) swap(l, r);
for (int i = 0; i <= 9; i ++) {
int ans = solve(r, i) - solve(l - 1, i);
cout << ans << " ";
}
puts("");
}
}
状压dp
AcWing291. 蒙德里安的梦想
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 12, M = 1 << N;
using LL = long long ;
LL f[N][M];
bool st[M];
int n, m;
int main()
{
while (~scanf("%d%d", &n, &m), n || m) {
for (int i = 0; i < 1 << n; i ++ ) {
st[i] = true;
int cnt = 0;
for (int j = 0; j < n; j ++ ) {
if (i >> j & 1) {
if (cnt & 1) {
st[i] = false;
break;
}
} else cnt ++ ;
}
if (cnt & 1) st[i] = false;
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= m; i ++ ) {
for (int j = 0; j < 1 << n; j ++ ) {
for (int k = 0; k < 1 << n; k ++ ) {
if (!(j & k) && st[j | k])
f[i][j] += f[i - 1][k];
}
}
}
printf("%lld\n", f[m][0]);
}
return 0;
}
AcWing91. 最短Hamilton路径
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
// f[i][j]表示“点被经过的状态”对应的二进制数是i，且目前处于点j时的最短路径
int dist[N][N], f[1 << N][N], n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &dist[i][j]);
memset(f, 127, sizeof f);
f[1][0] = 0; // 边界条件
// i代表着是一个方案集合，其中每一个位置1和0，代表着这个点经过还是没有经过
for (int i = 0; i < 1 << n; i ++ ) {
for (int j = 0; j < n; j ++ ) { // 枚举当前到了哪一个点
if (i >> j & 1) { // 如果i集合中第j位是1，也就是当前经过了j点
for (int k = 0; k < n; k ++ ) { // 枚举从哪个点k走到点j
// 如果k和j是同一个点,则跳过
if (k == j) continue;
// 写法1：(i ^ 1 << j) >> k & 1
// 写法2：(i & (~ (1 << j))) >> k & 1
// 写法3：(i - (1 << j)) >> k & 1
if ((i ^ 1 << j) >> k & 1)
f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + dist[k][j]);
}
}
}
}
// 表示所有点都走过了,且终点是n-1的最短距离
printf("%d\n", f[(1 << n) - 1][n - 1]);
return 0;
}
树形dp
AcWing285. 没有上司的舞会
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 6010, M = N;
int h[N], e[M], ne[M], idx;
int happy[N], d[N], f[N][2], n;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u) {
f[u][0] = 0, f[u][1] = happy[u];
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
dfs(v);
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += f[v][0];
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]);
for (int i = 0; i < n - 1; i ++ ) {
int a, b;
scanf("%d%d", &b, &a);
d[b] ++ ;
add(a, b);
}
int rt = 0;
for (int i = 1; i <= n; i ++ )
if (!d[i]) {
rt = i;
break;
}
dfs(rt);
printf("%d\n", max(f[rt][0], f[rt][1]));
return 0;
}
记忆化搜索
AcWing901. 滑雪
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int f[N][N], w[N][N], n, m;
int dfs(int x, int y) {
int &v = f[x][y];
if (v != -1) return v;
v = 1;
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a < 1 || a > n || b < 1 || b > m || w[a][b] >= w[x][y]) continue;
v = max(v, dfs(a, b) + 1);
}
return v;
}
int main()
{
memset(f, -1, sizeof f);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &w[i][j]);
int ans = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
ans = max(ans, dfs(i, j));
printf("%d\n", ans);
return 0;
}
第六讲 贪心
区间问题
AcWing905. 区间选点
传送门
// 闭区间，按右端点从小到大排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator < (const Range &t) const {
return r < ; // 按右端点从小到大排序
}
} range[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
sort(range, range + n);
int ans = 0, lastR = -2e9; // lastR 记录上一次已经选中的最右端点
for (int i = 0; i < n; i ++ )
{
if (lastR < range[i].l)
{
ans ++ ;
lastR = range[i].r;
}
}
printf("%d\n", ans);
return 0;
}
// 开区间，按左端点从大到小排序（其实就是上面写法的对称操作）
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator < (const Range& t) const {
return l > ; // 按左端点从大到小排序
}
} range[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
sort(range, range + n);
// lastL记录上次已经选中的最左端点
int res = 0, lastL = 2e9;
for (int i = 0; i < n; i ++ )
{
if (lastL > range[i].r)
{
res ++ ;
lastL = range[i].l;
}
}
printf("%d\n", res);
return 0;
}
AcWing908. 最大不相交区间数量
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator < (const Range &t) const {
return r < ; // 按右端点从小到大排序
}
} range[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
sort(range, range + n);
int ans = 0, lastR = -2e9; // lastR 记录上一次已经选中的最右端点
for (int i = 0; i < n; i ++ )
{
if (lastR < range[i].l)
{
ans ++ ;
lastR = range[i].r;
}
}
printf("%d\n", ans);
return 0;
}
AcWing906. 区间分组
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator < (const Range &t) const {
return l < ;
}
} range[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
sort(range, range + n);
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0; i < n; i ++ )
{
if (() || range[i].l <= ())
(range[i].r);
else
{
();
(range[i].r);
}
}
printf("%d\n", ());
return 0;
}
AcWing907. 区间覆盖
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator < (const Range &t) const {
return l < ;
}
} range[N];
int n, S, T;
int main()
{
scanf("%d%d%d", &S, &T, &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
sort(range, range + n);
bool ok = false;
int ans = 0;
for (int i = 0; i < n; i ++ )
{
int j = i, r = -2e9;
while (j < n && range[j].l <= S)
{
r = max(r, range[j].r);
j ++ ;
}
if (r < S)
{
ans = -1;
break;
}
ans ++ ;
if (r >= T)
{
ok = true;
break;
}
S = r, i = j - 1;
}
if (ok) printf("%d\n", ans);
else puts("-1");
return 0;
}
Huffman树
AcWing148. 合并果子
传送门
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
scanf("%d", &n);
priority_queue<int, vector<int>, greater<int>> q;
while (n -- ) {
int x;
scanf("%d", &x);
(x);
}
int ans = 0;
while (() > 1) {
int x = (); ();
int y = (); ();
ans += x + y;
(x + y);
}
printf("%d\n", ans);
return 0;
}
排序不等式
AcWing913. 排队打水
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using LL = long long;
int t[N], n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &t[i]);
sort(t + 1, t + 1 + n);
LL ans = 0;
for (int i = 1; i <= n; i ++ ) ans += t[i] * (n - i);
printf("%lld\n", ans);
return 0;
}
绝对值不等式
AcWing104. 货仓选址
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
sort(a, a + n);
int ans = 0;
for (int i = 0; i < n; i ++ ) ans += abs(a[i] - a[n / 2]);
printf("%d\n", ans);
return 0;
}
推公式
AcWing125. 耍杂技的牛
传送门
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
using PII = pair<int, int> ;
PII cows[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++) {
int w, s;
scanf("%d%d", &w, &s);
cows[i] = {w + s, w};
}
sort(cows, cows + n);
int sum = 0, ans = -2e9;
for (int i = 0; i < n; i ++ ) {
int w = cows[i].second, s = cows[i].first - w;
ans = max(ans, sum - s);
sum += w;
}
printf("%d\n", ans);
return 0;
}