呵呵,一时兴起,就想写一篇笔记
Part 1
排序
排序就是把一个无序的序列变成有序的
以下主要讲解一下快速排序&归并排序
快速排序
注意奥,这是一个纯纯的双指针算法
代码:
#include<iostream>
using namespace std;
const int N = 1e9 + 9;
int n, q[N];
void func1(int q[], int l, int r){
if (l >= r) return;
int x = q[l], i = l - 1, j = r + 1;
while (i < j){
do i ++; while (q[i] < x);
do j --; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
func1(q, l, j);
func1(q, j + 1, r);
}
int main(){
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
func1(q, 0, n - 1);
for (int i = 0; i < n; i ++) printf("%d ", q[i]);
return 0;
}
当然也有不用do-while的方法,别记
归并排序
本质是先份,递归时再合并
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e8;
int n, a[N], temp[N];
void func(int l, int r){
if (l >= r) return;
int mid = (l + r) >> 1;
func(l, mid);
func(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r){
if (a[i] <= a[j]) temp[k ++ ] = a[i ++ ];
else temp[k ++ ] = a[j ++ ];
}
while (i <= mid) temp[k ++ ] = a[i ++ ];
while (j <= r) temp[k ++ ] = a[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) a[i] = temp[j];
}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
func(1, n);
for (int i = 1; i <= n; i ++) printf("%d ", a[i]);
return 0;
}
总结
以上两个算法都是用双指针&递归所实现的
归并用到了回溯
延申(求逆序对)(归并)
…
二分
二分的几个要点:
- 有序
- 有check( )函数
- 可分成两段
整数二分
bool check(int x){...}
// [l, r] -> [l, mid] + [mid + 1, r]
int bitS(){
// 本质是可以通过一个函数(check),去将一个范围的数分成两部分,并只搜索某一部分
int l, r, mid; // 自行调范围
while (l < r){
mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
// [l, r] -> [l, mid - 1] + [mid, r]
int bitS(){
int l, r, mid;
while (l < r){
mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
浮点二分
和整数二分差不多但是有一点要注意
高精度
其实无非就是四则运算,一个个看吧
加
(这个很简单,就不讲了)
#include<bits/stdc++.h>
using namespace std;
string a, b;
vector<int> av, bv;
vector<int> add(vector<int> av, vector<int> bv){
vector<int> cv;
int t = 0; // 进位, 后面做和
for (int i = 0; i < av.size() || i < bv.size(); i ++){
if (i < av.size()) t += av[i];
if (i < bv.size()) t += bv[i];
cv.push_back(t % 10);
t = t / 10;
}
if (t == 1) cv.push_back(1);
return cv;
}
int main(){
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i --) av.push_back(a[i] - '0'); // 变整数
for (int i = b.size() - 1; i >= 0; i --) bv.push_back(b[i] - '0');
// for (int i = 0; i <= av.size() - 1; i ++) cout << av[i] << ' ';
// cout << endl;
// for (int i = 0; i <= bv.size() - 1; i ++) cout << bv[i] << ' ';
auto c1 = add(av, bv);
for (int i = c1.size() - 1; i >= 0; i --) cout << c1[i]; // 输出
system("pause");
return 0;
}
减
如果a > b
那么直接a - b
否则-(b - a)
定理: |a - b|
= |b - a|
#include<bits/stdc++.h>
using namespace std;
string a, b;
vector<int> av, bv, cv;
bool flag;
bool com(vector<int> av, vector<int> bv){
// len
if (av.size() > bv.size()){
return true;
}else if (bv.size() > av.size()){
return false;
}else{
for (int i = av.size(); i >= 0; i --){
if (av[i] > bv[i]) return true;
else if (av[i] < bv[i]) return false;
}
return true;
}
}
vector<int> sub(vector<int> av, vector<int> bv){
vector<int> cv;
int t = 0;
for(int i = 0; i < av.size(); i ++){
t = av[i] - t;
if(i < bv.size()) t -= bv[i];
cv.push_back((t + 10) % 10 );
if(t < 0) t = 1;
else t = 0;
}
while(cv.size() > 1 && cv.back() == 0) cv.pop_back();
return cv;
}
int main(){
cin >> a >> b;
for(int i = a.size() - 1; i >= 0; i --) av.push_back(a[i] - '0');
for(int i = b.size() - 1; i >= 0; i --) bv.push_back(b[i] - '0');
flag = com(av, bv);
if (flag == true){
// A - B
cv = sub(av, bv);
for(int i = cv.size() - 1; i >= 0; i --) cout << cv[i];
}else{
// -(B - A)
cv = sub(bv, av);
if (cv[0] != 0) cout << '-';
for(int i = cv.size() - 1; i >= 0; i --) cout << cv[i];
}
system("pause");
return 0;
}
乘
这里只把a拆开了,一位一位的算(因为a比较大,b偏小)
#include<bits/stdc++.h>
using namespace std;
int b;
string a;
vector<int> av, cv;
vector<int> mul(vector<int> av, int b){
int t = 0;
vector<int> cv;
for (int i = 0; i < av.size(); i ++){
cv.push_back((av[i] * b + t) % 10);
t = (av[i] * b + t) / 10;
}
if (t != 0) cv.push_back(t);
return cv;
}
int main(){
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i --) av.push_back(a[i] - '0');
if (b == 0){
cout << 0;
return 0;
}
cv = mul(av, b);
for (int i = cv.size() - 1; i >= 0; i --) cout << cv[i];
system("pause");
return 0;
}
除
#include<bits/stdc++.h>
using namespace std;
string a;
long long b, r;
vector<long long> av, bv, cv;
vector<long long> div(vector<long long> av, long long b){
long long temp = 0;
vector<long long> cv;
for (long long i = 0; i < av.size(); i ++){
temp = temp * 10 + av[i];
cv.push_back(temp / b);
temp = temp % b;
}
r = temp;
for (long long i = 0; i < cv.size(); i ++){
if (cv[0] != 0) break;
cv.erase(cv.begin());
}
return cv;
}
int main(){
cin >> a >> b;
for (long long i = 0; i < a.size(); i ++) av.push_back(a[i] - '0');
cv = div(av, b);
if (cv.empty() == true) cout << 0;
for (long long i = 0; i < cv.size(); i ++) cout << cv[i];
cout << endl << r;
system("pause");
return 0;
}
前缀和&差分
一维前差
前缀和
#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int n, m, l, r;
int a[N];
void funC(){
for (int i = 1; i <= n; i ++)
a[i] = a[i] + a[i - 1];
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i];
funC();
for (int i = 1; i <= m; i ++){
cin >> l >> r;
cout << a[r] - a[l - 1] << endl;
}
system("pause");
return 0;
}
差分
#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int a[N], b[N];
int l, r, c;
void func1(){ for (int i = 1; i <= n; i ++) b[i] = a[i] - a[i - 1];}
void func2(){ for (int i = 1; i <= n; i ++) a[i] = b[i] + a[i - 1];}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i];
func1();
for (int i = 1; i <= m; i ++){
cin >> l >> r >> c;
b[l] += c;
b[r + 1] -= c;
}
func2();
for (int i = 1; i <= n; i ++) cout << a[i] << ' ';
system("pause");
return 0;
}
二维前差
前缀和
#include<iostream>
using namespace std;
const int N = 1e3 + 3;
int n, m, q;
int a[N][N];
int x1, x2, y1, y2;
void func(){
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
int main(){
cin >> n >> m >> q;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
cin >> a[i][j];
func();
// for (int i = 1; i <= n; i ++){
// for (int j = 1; j <= m; j ++)
// cout << a[i][j] << ' ';
// cout << endl;
// }
for (int i = 1; i <= q; i ++){
cin >> x1 >> y1 >> x2 >> y2;
cout << a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1] << endl;
}
system("pause");
return 0;
}
差分
#include<iostream>
using namespace std;
const int N = 1e3 + 3;
int n, m, q;
int a[N][N], b[N][N];
int x1, x2, y1, y2, c;
void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
void func2(){
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++){
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
}
}
}
int main(){
cin >> n >> m >> q;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
cin >> a[i][j];
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
insert(i, j, i, j, a[i][j]);
}
}
for (int i = 1; i <= q; i ++){
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, c);
}
func2();
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++)
cout << b[i][j] << ' ';
cout << endl;
}
system("pause");
return 0;
}
双指针
这个算法的核心就是先写出一个朴素算法 ->O(n ^ 2)
再找一些奇妙的性质(单调,优先......)
变成O(n)
或O(nlogn)
的时间复杂度
主要是一个思路
题的话可以看看洛谷或ac上的题
位运算
(很简单)
这里有四个符号要掌握:
四个符号
& 位与 -> 两位同时为1,结果才为1,否则为0
运算规则:0&0=0; 0&1=0; 1&0=0; 1&1=1;
| 位或 -> 两位同时为0,结果才为0,否则为1
运算规则:0|0=0; 0|1=1; 1|0=1; 1|1=1;
^ 异或 -> 一样为1,不同为0
运算规则:0^0=0; 0^1=1; 1^0=1; 1^1=0;
~ 取反
离散化(没更)
区间合并
其实挺简单的,只不过有几个要掌握
cmp
里的代码,(背过就行)ans
从一开始r = max(r, a[i].second);
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, ans = 1;
int l, r;
pair<int, int> a[N];
bool cmp(pair<int, int> x, pair<int, int> y){
return x.first <= y.first;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i].first >> a[i].second;
sort(a + 1, a + 1 + n, cmp);
l = a[1].first;
r = a[1].second;
for (int i = 2; i <= n; i ++){
if (a[i].first <= r){
r = max(r, a[i].second);
}else{
ans ++;
l = a[i].first;
r = a[i].second;
}
}
cout << ans;
return 0;
}
Part 2
别问我为什么,Part 1没写完
单链表
首先,我们使用数组来模拟链表,要开以下几个变量(数组):
-
int e[]
表示当前点的值是e[i]
-
int en[]
表示当前点指向的下一个点ne[i]
-
int head
表示头指针的坐标 -
int idx
表示当前用的点的数量
然后有一下几个操作:
H x
,表示向链表头插入一个数 xD k
,表示删除第 k 个插入的数后面的数(当 k 为 0 时,表示删除头结点)。I k x
,表示在第 k 个插入的数后面插入一个数 x(此操作中 k 均大于 0)。
每个函数的代码
add_to_head()
:
C++
// 将x插到头结点
void add_to_head(int x)
{
e[idx] = x, ne[idx] = head, head = idx ++ ;
}
add()
C++
void add(int k, int x)
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
remove()
C++
// 将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];
}
代码:
#include <iostream>
using namespace std;
const int N = 100010;
// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 将x插到头结点
void add_to_head(int x)
{
e[idx] = x, ne[idx] = head, head = idx ++ ;
}
// 将x插到下标是k的点后面
void add(int k, int x)
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
// 将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
int m;
cin >> m;
init();
while (m -- )
{
int k, x;
char op;
cin >> op;
if (op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
if (!k) head = ne[head];
else remove(k - 1);
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
双链表
其实和单链表差不多,只是有点麻烦,有两个指针
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int m;
int l[N], r[N], e[N], idx;
void insert(int a, int x){
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++;
}
void remove(int a){
r[l[a]] = r[a];
l[r[a]] = l[a];
}
int main(){
cin >> m;
r[0] = 1, l[1] = 0, idx = 2;
while (m -- )
{
string op;
cin >> op;
int k, x;
if (op == "L")
{
cin >> x;
insert(0, x);
}
else if (op == "R")
{
cin >> x;
insert(l[1], x);
}
else if (op == "D")
{
cin >> k;
remove(k + 1);
}
else if (op == "IL")
{
cin >> k >> x;
insert(l[k + 1], x);
}
else
{
cin >> k >> x;
insert(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
栈&队列
这个在C++的库里有,include<stack>
include<queue>
Part 3
dfs
呵呵🙂 这是一个很大的话题,但是我们在这里只给几道例题
全排列
#include<iostream>
using namespace std;
const int N = 9;
int n, a[N], st[N], cnt;
void func(int u){
if (u == n + 1){
for (int i = 1; i <= n; i ++) cout << a[i] << ' ';
cout << endl;
return;
}
for (int i = 1; i <= n; i ++){
if (st[i] != true){
st[i] = true;
a[++ cnt] = i;
func(u + 1);
st[i] = false;
cnt --;
}
}
}
int main(){
cin >> n;
func(1);
}
这是一道很经典的问题,主要注意加和撤 标记
n皇后
#include<iostream>
using namespace std;
const int N = 11, M = 22;
int n;
bool row[N], col[N], dg[M], udg[M], ans[N][N];// row -> -, col -> |, dg -> /, udg -> \;
void dfs(int u){
if (u > n){
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= n; j ++){
if (ans[i][j]) cout << "Q";
else cout << ".";
}
cout << endl;
}
cout << endl;
}
for (int j = 1; j <= n; j ++){ // every col
if (row[u] || col[j] || dg[u + j - 1] || udg[u - j + n]) continue;
ans[u][j] = true;
row[u] = true, col[j] = true, dg[u + j - 1] = true, udg[u - j + n] = true;
dfs(u + 1);
ans[u][j] = false;
row[u] = false, col[j] = false, dg[u + j - 1] = false, udg[u - j + n] = false;
}
}
int main(){
cin >> n;
dfs(1);
system("pause");
return 0;
}