C++常用便捷技巧
前言
基于平衡二叉树（红黑树）的存储方式，set, map, multiset, multimap 甚至vector等等容器他们都用一些共同的操作，哈希表实现的有unordered_map, unorder_set
size()
empty()
clear()
begin()/end()
lower_bound/upper_bound
这两个二分查找操作可以在set，数组，vector，map中使用；
数组 或者 vector 中的语法：
序列是升序的（从小到大）
lower_bound(begin(),end(),x) //返回序列中第一个大于等于x的元素的地址
upper_bound(begin(),end(),x) //返回序列中第一个大于x的元素的地址
序列是降序的（从大到小）
lower_bound(begin(),end(),x,greater<tpye>()) //返回序列中第一个小于等于x的元素的地址
upper_bound(begin(),end(),x,greater<type>()) //返回序列中第一个小于x的元素的地址
set 或者 map 中的语法：
和数组差不多，只不过返回的是迭代器：
s.lower_bound(x) //返回序列中第一个大于等于x的元素的地址
s.upper_bound(x) //返回序列中第一个大于x的元素的地址
重点注意：如果当前序列中找不到符合条件的元素，那么返回end(),对于数组来说，返回查询区间的尾地址位置，对于set来讲，返回end()-1后面元素的迭代器，也就是end();
set
set/multiset
前者去重后者不去重
intsert() 插入一个数
find() 查找一个数
count() 返回一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
map
map/multimap
(它们都是关联容器，增删效率为log级别，并且依据key能自动排序，默认小于，前者key不允许重复，后者允许)
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
迭代器的使用
vector<type>::iterator iter;
map<type,type>::iterator iter;
set<type>::iterator iter;
等等.....
迭代器可以像指针一样，遍历STL时可以直接对迭代器 ++ -- ；
访问迭代器的值的形式：
*iter
iter->first iter->second
auto 访问map：
for(auto &iter:mp){
int x=iter->first,y=iter->second;
}
auto 访问set：
for(auto &iter:mp){
int x=iter;
}
map和set都是根据key值从小到大排好序的，带ordered的都不会排序，因为是基于哈希表实现的，但是查找效率非常高是O(1)
unordered....
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset
bitset, 圧位（存放一个十进制数的二进制，可以像数组一样来使用）
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
String
string 是一个很强大的字符串类
size()/length() 返回字符串的长度
reverse(s.begin(),s.end()); 将字符串的反转
s.append(str) 在字符串后面加上字符串str
支持对两个字符串的 ’ + ‘ 操作，实现字符串的拼接（s.append(str)比 + 要慢）
s.erase(0,s.find_first_not_of('0')); //利用string函数去除前导0
s1=s2.substr(起始下标，拷贝长度) //string的截取
pos = s.find('x') //返回string里面字符x的下标；
字符串转化为数字的库函数：
string str = "16";
int a = atoi(str.c_str());//能转换整数和小数，能报异常
int b = strtol(str.c_str(), nullptr, 10);//能指定进制
数字转化为字符串的函数：
int val=123456;
string s=to_string(val);
iterator erase(iterator p)：删除字符串中p所指的字符
iterator erase(iterator first, iterator last)：删除字符串中迭代器区间 [first, last) 上所有字符
string& erase(size_t pos, size_t len)：删除字符串中从索引位置 pos 开始的 len 个字符
编译优化
// 开启O2优化
#pragma GCC optimize(2)
#pragma GCC optimize(“O2”)
// 开启O3优化
#pragma GCC optimize(3,"Ofast","inline")
取消同步流
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
算法基础课
第一讲 基础算法
快速排序
算法基础课版本
void quick_sort(int a[], int l, int r)
{
if (l >= r) return;
int x = a[l + r >> 1];
int i = l - 1;
int j = r + 1;
while (i < j)
{
while (a[++i] < x);
while (a[--j] > x);
if (i < j) swap(a[i], a[j]);
}
quick_sort(a, l, j); quick_sort(a, j + 1, r);
}
基于划分思想：蓝白混合 + pivot + 红(不能AC)
//对于元素进行比较,只有三种结果:
// 1.<
// 2.=
// 3.>
//
//现在我们可以根据元素与pivot的大小关系进行分色:
// 1.< 蓝色
// 2.= 白色
// 3.> 红色
//
//当数组划分完之后.数组各部分的颜色应该是:蓝/蓝白 --- pivot --- 红/红白,详细分类如下:
// 1.蓝白混合 + pivot + 红
// 2.蓝 + pivot + 红白混合
// 3.蓝白混合 + pivot + 红白混合
// 4.蓝白混合 + pivot + 红白混合
// 5.蓝 + 白 + 红
//单指针从左向右扫描,跳过蓝白
//最终划分结果: 蓝白混合 + pivot + 红
int partition(int w[], int l, int r)
{
// 随机取枢轴值的方法
// int pivot_pos = (rand() % (r - l + 1) + (r - l + 1)) % (r - l + 1) + l;
// int pivot = w[pivot_pos];
// swap(w[l], w[pivot_pos]);
// pivot_pos = l;
int pivot = w[l]; //最左元素选为pivot
int pivot_pos = l;//先记录位置
while (l <= r) // 当左右指针交错时退出循环
{
//当l == r时不能退出,因为还没有扫描w[l],不知道其大小,没法对其进行划分
if (w[l] <= pivot) ++l;//遇到大于pivot的元素(红色),就停下
else
{
swap(w[l], w[r]); // 否则左右指针内容交换
--r; // 右指针减一
//最后一次循环,当l == r时, w[l] > pivot,右指针减一,表示r后边的元素全都大于pivot,而w[r] <= pivot
}
}
swap(w[pivot_pos], w[r]); // 退出循环时最后把pivot与r交换,此时l与r交错，l指向右部分第一元素，r指向左部分最后元素
return r;//返回当前pivot位置
}
void quick_sort(int w[], int l, int r)
{
if (l >= r) return;
int mid = partition(w, l, r);
quick_sort(w, l, mid - 1);
quick_sort(w, mid + 1, r);
}
以平均值作为枢轴划分
int partition(int w[], int l, int r)
{
if (l >= r) return l;
double average = 0;
for (int i = l; i <= r; i++) average += w[i];
average /= (r - l + 1);
while (l < r)
{
//如果一下两行交换顺序后,算法会MLE,目前不清楚原因
while (l < r && w[r] >= average) r--;
while (l < r && w[l] <= average) l++;
swap(w[l], w[r]);
}
return l;
}
void quick_sort(int w[], int l, int r)
{
//目前不清楚为什么这样划分是对的
if (l >= r) return;
int mid = partition(w, l, r);
quick_sort(w, l, mid);
quick_sort(w, mid + 1, r);
}
第k个数
int quick_select(int a[], int l, int r, int k)
{
if(l >= r) return a[l];
int x = a[l + r >> 1];
int i = l - 1, j = r + 1;
while(i < j)
{
while(a[++i] < x);
while(a[--j] > x);
if(i < j) swap(a[i], a[j]);
}
int sl = j - l + 1;
if(k <= sl) return quick_select(a, l, j, k);
return quick_select(a, j + 1, r, k - sl);
}
归并排序
void merge_sort(int a[], int l, int r)
{
if(l >= r) return ;
int mid = l + r >> 1;
merge_sort(a, l, mid);merge_sort(a, mid + 1, r);
int i = l, j = mid + 1;
int st = l;
while(i <= mid && j <= r)
{
if(a[i] <= a[j]) temp[st++] = a[i++];
else temp[st++] = a[j++];
}
while(i <= mid) temp[st++] = a[i++];
while(j <= r) temp[st++] = a[j++];
for(int i = l; i <= r; i++) a[i] = temp[i];
}
二分
整数二分模板
//区间划分成什么取决于check()
bool check(int x);
//区间[l,r]被划分成[l,mid]和[mid+1,r]时使用
int bsearch(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
return l;
}
}
//区间[l,r]被划分成[l,mid-1】和[mid,r]时使用
int bsearch(int l, int r)
{
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
return l;
}
}
浮点数二分模板
// eps是一个正数误差值
int bsearch(double l, double r) {
while (1 - r > eps) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;//r = mid;//根据check的策略决定
else r = mid; //l=mid;
return l;
}
}
高精度
高精度加法
// 低位在前,高位在后
vector<int> add(vector<int> &A, vector<int> &B)
{
vector<int> C;
int t = 0;
for(int i = 0; i <= A.size() - 1; i++)
{
t += A[i];
if(i <= B.size() - 1) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if(t) C.push_back(t);
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
高精度减法
vector<int> sub(vector<int> &A, vector<int> &B)
{
int t = 0;
for(int i = 0; i <= A.size() - 1; i++)
{
t = A[i] - t;
if(i <= B.size() - 1) t -= B[i];
C.push_back((t + 10) % 10);
if(t < 0) t = 1;
else t = 0;
}
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
高精度乘法
vector<int> mul(vector<int> &A, int b)
{
int t = 0;
for(int i = 0; i <= A.size() - 1 | t; i++)
{
if(i <= A.size() - 1) t += A[i] * b;
C.push_back( t % 10);
t /= 10;
}
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
高精度除法
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
for(int i = A.size() - 1; i >= 0; i--)
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
前缀和
一维前缀和
for(int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];
二维前缀和
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> s[i][j], s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
差分
一维差分
void insert(int b[], int l, int r, int c)
{
b[l] += c, b[r + 1] -= c;
}
for(int i = 1; i <= n; i++) cin >> c, insert(b, i, i, c);
二维差分
void insert(int b[][N], int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c, b[x1][y2 + 1] -= c, b[x2 + 1][y1] -= c, b[x2 + 1][y2 + 1] += c;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> c, insert(b, i, j, i, j, c);
lowbit位运算
含义：lowbit(x)是x的二进制表达式中最低位的1所对应的值。对于任意一个整数x，lowbit(x) = x & (~x)，其中&表示按位与运算，~x表示x的相反数。
int lowbit(int x)
{
//return x & (~x + 1);//二进制x与x的补码(取反加一)的与运算
//由于-x = (~x + 1),所以可简写为下方形式
return x & -x;
}
第二讲 数据结构
单链表
int head, e[N], ne[N], idx;
void init()
{
head = -1;
idx = 0;
}
void add_to_head(int x)
{
e[idx] = x, ne[idx] = head, head = idx++;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
void add(int k, int x)
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
双链表
int e[N], l[N], r[N], idx;
void init()
{
idx = 2;
r[0] = 1;
l[1] = 0;
}
void add(int k, int x)
{
e[idx] = x, l[idx] = k, r[idx] = r[k];
l[r[k]] = idx, r[k] = idx++;
}
void remove(int k)
{
l[r[k]] = l[k], r[l[k]] = r[k];
}
单调栈
int stk[N], tt;
cin >> x;
while(tt && stk[tt] >= x) tt--;
单调队列(滑动窗口例题)
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k;
int a[N];
int q[N], hh, tt = -1;
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++)
{
while(hh <= tt && i - q[hh] + 1 > k) hh++;
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
if(i + 1 >= k) cout << a[q[hh]] << ' ';
}
hh = 0, tt = -1;
cout << endl;
for(int i = 0; i < n; i++)
{
while(hh <= tt && i - q[hh] + 1 > k) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if(i + 1 >= k) cout << a[q[hh]] << ' ';
}
}
KMP算法(KMP例题)
#include<iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
char p[N], s[M];
int ne[N];
//kmp算法的思路是根据两个字符串 已经部分匹配的匹配串 来进行模式串位移匹配，如果我们根据 匹配串中的最长公共前后缀长度 来进行位移匹配的话，我们就能减小位移次数，缩减时间
//模式串的next数组，ne[i] = j 的含义：p[1 ~ i]中的最长公共前后缀的长度，最长公共前后缀 不能是 原串
//该式具体含义为p[1 ~ j] == p[(i - j + 1) ~ i],即 1 ~ j 的字符串 与 (i - j + 1) ~ i的字符串相同
int main()
{
cin >> n >> p + 1;//字符串从 下标1 开始读入
cin >> m >> s + 1;
ne[1] = 0;//由于只含 一个字符 的字符串没有公共前后缀，故其最长公共前后缀的长度为0
//求next数组过程也是模式串自匹配过程，为什么？
//下方求next数组程序中的指针i为什么从2开始,指针j为什么从0开始？？
//下方匹配过程可看作 p[2 ~ n] 与 p [1 ~ n]进行匹配,循环体中每个i都对应一个j,这表示的是p[(i - j + 1) ~ i] == p[1 ~ j],从这里仔细思考便可得到 p[1 ~ i] 的最长公共前后缀长度正是 j,所以求next数组过程可看作 p[2 ~ n] 与 p[1 ~ n]的自匹配过程
//求next数组过程:由于我们需要将模式串中的 每个下标字符 对应的 1 ~ i 的最长公共前后缀长度求出来，所以我们需要枚举 指针i
//如果这里的 指针i 初始化为 1，然后 按照下述方法求next数组的话，会求的ne[1] = 1与实际情况不符,如果不对ne[1] = 0 进行赋值(设置边界条件),那么我们得到next数组也不会满足我们现实中的实际含义
//指针j 含义:已经部分匹配的匹配串的长度
for(int i = 2, j = 0; i <= n; i++)
{
while(j && p[i] != p[j + 1]) j = ne[j]; //当j == 0 时, 指针j就不能回滚了
if(p[i] == p[j + 1]) j++;
ne[i] = j;
}
//指针j 含义:已经部分匹配的匹配串的长度
for(int i = 1, j = 0; i <= m; i++)
{
while(j && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j++;
if(j == n)
{
cout << i - n << ' ';
j = ne[j];
}
}
}
Trie字符串树
const int N = 1e5 + 10;
int son[N][26], cnt[N], idx;
void insert(char str[])
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
并查集(例题:合并集合)
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) p[i] = i;
char op;
int a,b;
while(m--)
{
cin >> op >> a >> b;
if(op == 'M') p[find(a)] = find(b);
else cout << (find(a) == find(b) ? "Yes" : "No") << endl;
}
}
堆排序(例题:堆排序)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], cnt;
void down(int u)
{
int t = u;
if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(u != t) swap(h[u], h[t]), down(t);
}
void up(int u)
{
if(u / 2 && h[u / 2] > h[u]) swap(h[u / 2], h[u]), up(u / 2);
}
// void down(int u)
// {
// while(2 * u <= cnt && h[2 * u] < h[u] || 2 * u + 1 <= cnt && h[2 * u + 1] < h[u])
// {
// int t = u;
// if(2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u;
// if(2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
// swap(h[u], h[t]);
// u = t;
// }
// }
// void up(int u)
// {
// while(u / 2 && h[u / 2] > h[u]) swap(h[u / 2], h[u]), u = u / 2;
// }
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> h[i];
cnt = n;
for(int i = n / 2; i >= 1; i--) down(i);
//for(int i = 1; i <= n ; i++) up(i);
while(m--)
{
cout << h[1] << ' ';
h[1] = h[cnt--];
down(1);
}
}
模拟散列表(例题:模拟散列表)
开放寻址法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003, INF = 0x3f3f3f3f;
int h[N];
int n;
int find(int x)
{
int k = (x % N + N) % N;
while(h[k] != INF && h[k] != x)
{
k++;
if(k == N) k = 0;
}
return k;
}
int main()
{
cin >> n;
memset(h, 0x3f, sizeof h);
string op;
int x;
while(n--)
{
cin >> op >> x;
int k = find(x);
if(op == "I") h[k] = x;
else cout << (h[k] != INF ? "Yes" : "No") << endl;
}
}
拉链法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;
int n;
int h[N], e[N], ne[N], idx;
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}
bool find(int x)
{
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i])
{
if(e[i] == x) return true;
}
return false;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
string op;
int x;
while(n--)
{
cin >> op >> x;
if(op == "I") insert(x);
else cout << (find(x) ? "Yes" : "No") << endl;
}
}
字符串哈希(例题:字符串哈希)
#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int N = 1e5 + 10, P = 131;
//每个字符都对应一个数值,每个字符所处的位置都有对应的位权(P的几次方),这样就能将一个字符串转换为一个数值形式,这样就能将不同字符串对应不同数值
//哈希函数:字符串对应的P进制数对2^64取模,代码没有显示给出,是隐式取模的(字符串的哈希值的类型是ull,对应64位,如果字符串的P进制数超过范围会自动取模的),P = 131 是一个经验值,能减小哈希冲突(该题是在哈希不冲突的假设前提下完成的)
int n, m;
ull h[N], p[N];
char str[N];
ull get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
cin >> n >> m;
cin >> (str + 1);
h[0] = 0,p[0] = 1;
for(int i = 1; i <= n; i++)
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
int l1, r1, l2, r2;
while(m--)
{
cin >> l1 >> r1 >> l2 >> r2;
if(get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
第三讲 搜索与图论
DFS搜索具体方案(例题:排列数字)
#include<iostream>
using namespace std;
const int N = 10;
int n;
int path[N], st[N];
//path[i]:表示第i位数字是几(1 <= i <= n)
//st[i]:表示数字i是否可用(1 <= i <= n)
void dfs(int u)//枚举第u位数字可填的方案,当u >= n + 1时,数字已全部填写完,开始回溯
{
if(u >= n + 1)
{
for(int i = 1; i <= n; i++) cout << path[i] << ' ';
cout << endl;
return ;
}
for(int i = 1; i <= n; i++)
{
if(!st[i])
{
path[u] = i;
st[i] = true;
dfs(u + 1);
st[i] = false;
}
}
}
int main()
{
cin >> n;
dfs(1);
}
BFS搜索目标最短步长(例题:八数码)
#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<cstring>
using namespace std;
int bfs(string start)
{
string end = "12345678x";
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
queue<string> q;
unordered_map<string, int> dist;
q.push(start);
dist[start] = 0;
while(q.size())
{
string t = q.front();
q.pop();
int distance = dist[t];
if(t == end) return distance;
int tk = t.find('x');
int tx = tk / 3, ty = tk % 3;
for(int i = 0; i < 4; i++)
{
int x = tx + dx[i], y = ty + dy[i];
if(x >= 0 && x < 3 && y >= 0 && y < 3)
{
int k = x * 3 + y;
swap(t[tk], t[k]);
if(!dist.count(t))//只需要对没有搜到过的状态进行搜索
{
q.push(t);
dist[t] = distance + 1;
}
swap(t[tk], t[k]);
}
}
}
return -1;
}
int main()
{
string start;
char ch;
for(int i = 1; i <= 9; i++)
{
cin >> ch;
start += ch;
}
cout << bfs(start);
}
BFS遍历图
int h[N], e[N], ne[N], idx;
int d[N];
int q[N], hh, tt;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs()
{
memset(d, -1, sizeof d);
hh = 0, tt = 0;
q[0] = 1;
d[1] = 0;
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t]; i!= -1 ; i = ne[i])
{
int j = e[i];
if(d[j] == -1)
{
d[j] = d[t] + 1;
q[++tt] = j;
}
}
}
return d[n];
}
拓扑序列
int h[N], e[N], ne[N], idx;
int q[N], hh, tt;
int d[N];//d[i]:表示点i的入度
bool topsort()
{
hh = 0, tt = -1;
for(int i = 1; i <= n; i++)//将入度为0的点加入到队列中
{
if(d[i] == 0) q[++tt] = i;
}
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j]--;
if(d[j] == 0) q[++tt] = j;
}
}
return tt == n - 1;//如果所有点都进入了队列,那么存在拓扑序,否则不存在
}
Dijkstra求最短路(普通版)
int g[N][N];
bool st[N];
int dist[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1; i <= n; i++)
{
int t = -1;
for(int j = 1; j <= n; j++)
{
if(!st[j] && (t == -1 || dist[t] > dist[j])) 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] == 0x3f3f3f3f) return -1;
return dist[n];
}
Dijkstra求最短路(优先队列版)
typedef pair<int, int> PII;
int h[N], e[N], w[N], ne[N], idx;
bool st[N];
int dist[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
while(heap.size())//堆中有一些信息是冗余的,需要将堆中的每个信息进行辨认后,才能对搜索最短路有帮助
{
PII t = heap.top();
heap.pop();
int x = t.x;//x表示结点编号
int y = t.y;//y表示距离
if(st[x]) continue;
st[x] = true;
for(int i = h[x]; i != -1; i = ne[i])
{
//之前的疑问:只有这种情况才能加入堆中,不然加了太冗余,可能会导致死循环
//解答:取等号也没关系,因为通过某一个点来更新到其他点距离,加入其他点进入队列之前,都会判断当前点是否已经加入最短路集合(也即是否已经用当前点更新了其他点)
//如果所有点都已经加入了最短路集合,但队列不为空,当从队列拿出结点时,在更新距离,扩展队列前都会判断该点是否已经加入最短路集合,此时因为所有点都已加入最短路集合,队列中的点都会一一弹出,不会继续扩展队列
//if(dist[e[i]] >= dist[x] + w[i])
if(dist[e[i]] > dist[x] + w[i])
{
dist[e[i]] = dist[x] + w[i];
heap.push({dist[e[i]], e[i]});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
bellman-ford算法
struct
{
int a, b, w;
}Edge[M];
int dist[N], backup[N];
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1; i <= k; i++)//迭代k次,表示不经过k条边,到达某点的最短距离为dist[b]
{
memcpy(backup, dist, sizeof dist);
for(int j = 1; j <= m; j++)//枚举各边
{
int a = Edge[j].a, b = Edge[j].b, w = Edge[j].w;
if(dist[b] > backup[a] + w && backup[a] != 0x3f3f3f3f) dist[b] = backup[a] + w;//更新距离的时候必须用上一次迭代的结果,如果用本次迭代的结果去更新,那就与"不超过k条到达某点的最短距离"的实际意义不符
}
}
if(dist[n] == 0x3f3f3f3f) return 0x3f3f3f3f;
return dist[n];
}
spfa算法
spfa求最短路
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
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;
queue<int> q;
q.push(1);
st[1] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
//问题:为什么这里if(dist[j] >= dist[t] + w[i])可以取等号
//原因:题中数据没有特殊情况
//自身理解:这里严格的来说,应写成dist[j] > dist[t] + w[i]
//spfa算法有一个特点,更新起点到其他点距离的过程中,是遵循了一个拓扑序的,所以这里不能取等号
//如果这里取到等号,并构造一份数据,使其满足一下情况,就会陷入死循环
//一个结点更新满足上述条件的后继邻接点后,将其邻接点放入队列中,之后用其后继结点更新该结点时,如果上述条件又成立,就又会将该结点重新加入队列中,始终队列不为空,无法结束循环
//上述条件的成立情形为:两结点存在负权回路或两点之间存在边长为0的边,即存在负权回路或0回路
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return 0x3f3f3f3f;
//疑惑:为什么这里的判断条件为什么变成了dist[n] == 0x3f3f3f3f,而不是dist[n] > 0x3f3f3f3f /2 呢
//因为队列里都是由起点更新到的点,不存在bellman-ford算法中未更新的点去更新其他点情况。
//队列中的点都是距离变小过的点,到起点的距离不为无穷大
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = spfa();
if(t == 0x3f3f3f3f) cout << "impossible";
else cout << t;
}
spfa判断负环
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 2010, M = 1e4 + 10;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N];//超级源点到各个点的最短距离和经过的边数
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()
{
queue<int> q;
for(int i = 1; i <= n; i++)
{
q.push(i);
st[i] = true;
}
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if(spfa()) cout << "Yes";
else cout << "No";
}
//在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为0的有向边。
//那么原图有负环等价于新图有负环。此时在新图上做spfa，将虚拟源点加入队列中。
Prim算法求最小生成树
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
int res = 0;
for(int i = 1; i <= n; i++)
{
int t = -1;
for(int j = 1; j <= n; j++)
{
if(!st[j] &&(t == -1 || dist[t] > dist[j])) t = j;
}
if(dist[t] == INF) return INF;//如果某个点到集合的距离为无穷大,说明这是一个非连通图,不存最小生成树
st[t] = true;
res += dist[t];
for(int j = h[t]; ~j; j = ne[j])
{
int u = e[j];
dist[u] = min(dist[u], w[j]);//与dijkstra更新方式不同之处
}
}
return res;
}
Kruskal算法求最小生成树
int n, m;
int p[N];
struct edge
{
int a, b, w;
bool operator < (const edge x) const
{
return w < x.w;
}
}Edges[M];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
for(int i = 1; i <= n; i++) p[i] = i;//初始化集合
sort(Edges + 1, Edges + 1 + m);//为边集排序
int res = 0, cnt = 0;
for(int i = 1; i <= m; i++)
{
int a = Edges[i].a, b = Edges[i].b, w = Edges[i].w;
int pa = find(a), pb = find(b);
if(pa != pb)//完美规避自环问题
{
p[pa] = pb;
res += w;
cnt++;
}
}
if(cnt < n - 1) return INF;
return res;
}
染色法判定二分图
int h[N], e[M], ne[M], idx;
int color[N];
//0:未染色
//1:1号颜色
//2:2号颜色
bool dfs(int u, int c)//遍历以u结点为根的树,进行染色,将根结点染成编号为c的颜色
{
color[u] = c;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!color[j])
{
if(!dfs(j, 3 - c)) return false;//3 - c 小技巧
}else if(color[j] == c) return false;
}
return true;
}
二分图的最大匹配
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 1e5 + 10;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[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 != -1; i = ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
if(match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}
return false;
}
int main()
{
cin >> n1 >> n2 >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
//匈牙利算法,基于贪心的思维,原理目前不太懂
for(int i = 1; i <= n1 ; i++)//依次为左半部分点集的每个点找对象
{
memset(st, false, sizeof st);//为第i个点重置预定数组,防止陷入递归的时候,为另一个点找对象时重复选择同一个人
if(find(i)) res++;
}
cout << res;
}
第四讲 数学知识
质数
分解质因数
void divide(int x)//x >= 2
{
//为什么从i = 2枚举,因为2是最小的质因子,只有这样做才具有实际意义
for(int i = 2; i <= x / i; i++)//枚举小于等于sqrt(x)的质因子
{
if(x % i == 0)//枚举到i时,说明x中已经没有2 ~ i - 1的质因子了,但i能整除x,说明i是质数
{
int s = 0;
while(x % i == 0)
{
x /= i;
s++;
}
cout << i << ' ' << s << endl;
}
}
//x最多有一个大于sqrt(x)的质因子,如果有两个大于sqrt(x)的质因子,那么他们的乘积就已经大于x了
if(x > 1) cout << x << ' ' << 1 << endl;//判断那个大于sqrt(x)的质因子
//当x == 1时表示,x已经被其质因子除干净了,已经没有质因子了
}
筛质数(线性筛法)
int n, cnt;
bool st[N];//st[i]:表示数i是否被筛过,是否是质数
int primes[N];
void get_primes(int n)
{
for(int i = 2; i <= n; i++)//枚举2 ~ n的所有数
{
if(!st[i]) primes[cnt++] = i;//如果i没被筛过,就是质数,加入到质数组中去
for(int j = 0; primes[j] <= n / i; j++)//枚举质数数组,筛选当前质数的倍数
{
st[primes[j] * i] = true;//i也可充当倍数来筛相关数,倍数是从2 ~ n的,能保证每个质因子的所有倍数的数被筛过
if(i % primes[j] == 0) break;
//我们是从小到大枚举的质数数组
//如果 i % primes[j] == 0说明,当前的primes[j]是i的最小质因数,如果此时循环不停止,会导致primes[j + 1] * i被筛掉,但primes[j + 1] * i既是primes[j]的倍数,又是primes[j + 1]的倍数,我们想要的情况是primes[j + 1] * i被最小质因数primes[j]筛掉,所以这里必须及时停止,等当i足够大时,primes[j] * i会将其筛掉
//为什么循环条件为:primes[j] <= n / i ？
//观察筛选语句:st[primes[j] * i] = true;这里保证了筛选的数是<= n的
//为什么循环语句不添加当前质数数组的长度限制,为什么这能保证质数数组访问合法
//当i是合数时,一定存在其最小质因数加入到指数数组中去了,在指针j的循环体中有if(i % primes[j] == 0) break;保证了循环体的安全结束
//当i时质数时,i会被加入到指数数组中去,当指针j枚举到质数i时,if(i % primes[j] == 0) break;也保证了循环体的安全结束
}
}
}
约数
试除法求约数
vector<int> get_divisor(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(res.begin(), res.end());
return res;
}
约数个数
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int n;
int main()
{
cin >> n;
unordered_map<int, int> primes;
while(n--)
{
int x;
cin >> x;
for(int i = 2; i <= x / i; i++)//依次求每个数的质数指数,若一次性求其乘积的质数指数,会爆int
{
while(x % i == 0)
{
primes[i]++;
x /= i;
}
}
if(x > 1) primes[x]++;
}
ll ans = 1;//对mod取模,需用ll类型
for(auto t : primes) ans = ans * (t.second + 1) % mod;
cout << ans;
}
约数之和
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int n;
int main()
{
cin >> n;
unordered_map<int, int> primes;
while(n--)
{
int x;
cin >> x;
for(int i = 2; i <= x / i; i++)
{
while(x % i == 0)
{
primes[i]++;
x /= i;
}
}
if(x > 1) primes[x]++;
}
ll res = 1;//需用ll类型
for(auto t : primes)
{
int p = t.first, a = t.second;
ll sum = 1;//需用ll类型
while(a--) sum = (sum * p + 1) % mod;
res = res * sum % mod;
}
cout << res;
}
最大公约数(欧几里得算法)
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
快速幂
int qmi(int a, int k, int p)
{
int res = 1;
while(k)//枚举k的二进制形式的每一位
{
if(k & 1) res = (ll)res * a % p;//k的最后一位为1才进行运算
k >>= 1;
a = (ll)a * a % p;
}
return res;
}
扩展欧几里得算法
#include<iostream>
using namespace std;
int n;
int exgcd(int a, int b, int &x, int &y)
{
if(!b)
{
x = 1, y = 0;//构造一组满足条件的解即可
return a;
//由于需要构造 a * x + b * y = (a, b)
//递归到这一层时b = 0,即需要构造一组解满足 a * x + 0 * y = (a, 0),即 a * x = a,则x = 1, y = 任意值
}
int d = exgcd(b, a % b, y, x);//已经从下层递归回来后,即找了一组解使得 b * y + (a % b) * x = (b, a % b) = (a, b);
//由于在这层,我们需要找到一组解使得 a * x + b * y = (a, b),我需要根据下层的计算结果来进行构造
//将下层结果公示转换后,得b * y + [a - (a / b下取整) * b] * x = (a, b)
//a * x + [y - (a / b下取整) * x] * b = (a, b);
//所以x = x, y = y - (a / b下取整) * x
y -= a / b * x;
return d;
}
int main()
{
cin >> n;
while(n--)
{
int a, b, x, y;
cin >> a >> b;
exgcd(a, b, x, y);
cout << x << ' '<< y << endl;
}
}
高斯消元解线性方程组
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110;
const double eps = 1e-8;
int n;
double a[N][N];
int gauss() // 高斯消元，答案存于a[i][n]中，0 <= i < n
{
int c, r;
for (c = 0, r = 0; c < n; c ++ )
{
int t = r;
for (int i = r; i < n; i ++ ) // 找绝对值最大的行
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if (fabs(a[t][c]) < eps) continue;
for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成1
for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];
r ++ ;
}
if (r < n)
{
for (int i = r; i < n; i ++ )//注意是从r开始枚举,因为在上述代码结束后,r是落在了未扫描行上
if (fabs(a[i][n]) > eps)
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("%lf", &a[i][j]);
int t = gauss();
if (t == 2) puts("No solution");
else if (t == 1) puts("Infinite group solutions");
else
{
for (int i = 0; i < n; i ++ )
{
if (fabs(a[i][n]) < eps) a[i][n] = 0; // 去掉输出 -0.00 的情况
printf("%.2lf\n", a[i][n]);
}
}
return 0;
}
求组合数
二维数组迭代版
int c[N][N];
void init()
{
for(int i = 0; i < N; i++)//N是数组边界,不能取到N
for(int j = 0; j <= i; j++)
if(!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
快速幂+lucas定理
#include<iostream>
using namespace std;
typedef long long ll;
int n, p;
int qmi(int a, int k, int p)
{
int res = 1;
while(k)
{
if(k & 1) res = (ll)res * a % p;
k >>= 1;
a = (ll) a * a % p;
}
return res;
}
int C(int a, int b)
{
int res = 1;
for(int i = 1, j = a; i <= b; i++, j--)
{
res = (ll)res * j % p;
res = (ll)res * qmi(i, p - 2, p) % p;
}
return res;
}
int lucas(ll a, ll b)
{
if(a < p && b < p) return C(a, b);
return (ll)C(a % p, b % p) * lucas(a / p, b / p) % p;
}
int main()
{
cin >> n;
while(n--)
{
ll a, b;
cin >> a >> b >> p;
cout << lucas(a, b) << endl;
}
}
C(m,n)中m,n数值较大且需要高精度
#include<iostream>
#include<vector>
using namespace std;
const int N = 5010;
int primes[N], cnt;
int sum[N];
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; primes[j] <= n / i; j++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
int get(int n, int p)//求n!中p的指数
{
int res = 0;
while(n)
{
res += n / p;
n /= p;
}
return res;
}
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for(int i = 0; i <= A.size() - 1; i++)
{
t = t + A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while(t)
{
C.push_back(t % 10);
t /= 10;
}
while(C.size() && C.back() == 0) C.pop_back();
return C;
}
int main()
{
int a, b;
cin >> a >> b;
get_primes(a);
for(int i = 0; i < cnt; i++)
{
int p = primes[i];
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
vector<int> res;
res.push_back(1);
for(int i = 0; i < cnt; i++)
{
for(int j = 1; j <= sum[i]; j++)
{
res = mul(res, primes[i]);
}
}
for(int i = res.size() - 1; i >= 0; i--) cout << res[i];
}
卡特兰数
int catalan(int n)//卡特兰数:catalan(n) = C(2 * n, n) - C(2 * n, n - 1) = C(2 * n, n) / (n + 1)
{
int res = 1;
int x, y;
for(int i = 1, j = 2 * n; i <= n; i++, j--)
{
res = (ll) res * j % mod;
exgcd(i, mod, x, y);
res = (ll) res * x % mod;
}
exgcd(n + 1, mod, x, y);
res = ((ll)res * x % mod + mod) % mod;
return res;
}
第五讲 动态规划
背包问题
01背包问题
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m];
}
完全背包问题
暴力版
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k <= j / v[i]; k++)
{
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
cout << f[n][m];
}
优化版(寻找f[i] [j] 与 f[i] [j - v]的计算公式的性质,发现f[i][j] = max(f[i - 1] [j], f[i] [j - v])
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
cout << f[n][m];
}
多重背包问题
暴力版
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
cout << f[n][m];
}
二进制优化for循环写法
#include<iostream>
#include<algorithm>
using namespace std;
const int M = 2e3 + 10;
int n, m;
int f[M];
int main()
{
cin >> n >> m;
//二进制优化,将第i的物品的取法进行打包,然后再做一次01背包问题
for(int i = 1; i <= n; i++)
{
int a, b, c;
cin >> a >> b >> c;
for(int k = 1; k <= c; c -= k, k *= 2)
{
int v = k * a, w = k * b;
for(int j = m; j >= v; j--)
f[j] = max(f[j], f[j - v] + w);
}
if(c)
{
int v = c * a, w = c * b;
for(int j = m; j >= v; j--)
f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[m];
}
单调队列优化版
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10, M = 2e3 + 10;
int n, m;
int v[N], w[N], s[N];
int f[N][M];
int q[M], hh, tt;//因为s最大值为2000,单调队列里可能会装这么多
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
for(int i = 1; i <= n; i++)
for(int r = 0; r < v[i]; r++)//枚举v[i]的余数
{
hh = 0, tt = -1;
for(int j = r; j <= m; j += v[i])//枚举背包容量
{
while(hh <= tt && j - q[hh] > s[i] * v[i]) hh++;//判断是否滑出窗口
while(hh <= tt && f[i - 1][q[tt]] - (q[tt] - r) / v[i] * w[i] <= f[i - 1][j] - (j - r) / v[i] * w[i]) tt--;
//f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w...f[i - 1][j - s * v] + s * w)
//关于式子内各个状态的横向对比,因为对于f[i][r],f[i][r + v]...f[i][j]中状态方程中的加的权重是不一样的,有不同的偏移量,不好对每个f[i][r],f[i][r + v]...f[i][j]中的状态方程中的各个f[i - 1]层状态不好比较,然后我们观察式子找到规律以当前方案做对比
q[++tt] = j;
f[i][j] = max(f[i][j], f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i]);
}
}
cout << f[n][m];
}
线性DP
最长上升子序列
记录方案的普通版
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e3 + 10;
int n;
int a[N];
int f[N], g[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++)
{
f[i] = 1;
for(int j = 1; j < i; j++)
if(a[j] < a[i])
if(f[i] < f[j] + 1)
{
f[i] = f[j] + 1;
g[i] = j;
}
}
int res = 0, tt = 0;
for(int i = 1; i <= n; i++)
if(res < f[i])
{
res = f[i];
tt = i;
}
vector<int> q;
while(tt)
{
q.push_back(a[tt]);
tt = g[tt];
}
//for(int i = q.size() - 1; i >= 0; i--) cout << q[i] << ' ';
cout << res;
}
二分优化版
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int q[N], len = 1;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
q[1] = - 2e9;//增加一个最小的数,保证能在区间内找到一个小于a[i]的数
for(int i = 1; i <= n; i++)
{
int l = 1, r = len;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] < a[i]) l = mid;//找到最后一个小于a[i]的数,然后在其尾巴上加上a[i]变成一个数量加一的上升子序列
else r = mid - 1;
}
q[r + 1] = a[i];//找到最后一个小于a[i]的数,其对应的下标是r,但我们需要更新的是q[r + 1],因为q[r + 1]表示的是长度为r + 1的上升子序列末尾的那个数,该数一定大于等于a[i],我们需要让其变小,用a[i]去更新
len = max(len, r + 1);//(1 ~ r + 1)的数列就是对于当前数a[i]的最长上升子序列,len既是队列长度,又是各个上升子序列的最大长度
}
cout << (len - 1);//除去初始最小的那个数
}
最长公共子序列
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int j = 1; j <= m; j++) cin >> b[j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
//f[i][j] = max(f[i - 1][j - 1], max(f[i - 1][j], f[i][j - 1]));
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m];
}
最短编辑距离
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
cin >> n >> a + 1;
cin >> m >> b + 1;
for(int i = 1; i <= m; i++) f[0][i] = i;
for(int i = 1; i <= n; i++) f[i][0] = i;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = min(f[i][j - 1] + 1, f[i - 1][j] + 1);//增,删
if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);//改
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m];
}
区间DP
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 310, INF = 1e9;
int n;
int s[N];//前缀和
int f[N][N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> s[i];
s[i] += s[i - 1];
}
for(int len = 2; len <= n; len++)//长度从2开始枚举,长度为1的状态f[l][r] = 0
for(int i = 1; i + len - 1 <= n; i++)
{
int l = i, r = i + len - 1;
f[l][r] = INF;//只初始化了长度为2以上的状态,长度为1的状态f[l][r] = 0,默认为0
for(int k = l; k < r; k++)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
cout << f[1][n];
}
数位统计DP
计数问题
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll N = 10;
ll power10[N];//位权数组
struct
{
ll s[10];
//f[i][j].s[k]:表示该数字集合中,数字k的出现次数
}f[N][10];//f[i][j]:表示位数为i,最高位数字为j的数字集合(包含前导零)
void init(ll n)
{
power10[0] = 1;
for (ll i = 1; i < n; i++) power10[i] = power10[i - 1] * 10;
//初始化一位数字
for (ll i = 0; i < 10; i++) f[1][i].s[i]++;
for (ll i = 2; i < n; i++)
for (ll j = 0; j < 10; j++)
{
f[i][j].s[j] = power10[i - 1];//数字j在最高位的出现次数(其余位置数字任意选择)
for (ll k = 0; k < 10; k++)//枚举次高位数字
for (ll p = 0; p < 10; p++)//枚举出现数字
f[i][j].s[p] += f[i - 1][k].s[p];
}
}
//数位dp
vector<ll> dp(ll n)
{
vector<ll> ans(10, 0);
if (n == 0) return ans;
vector<ll> nums;
while (n) nums.push_back(n % 10), n /= 10;
//循环体内枚举的都是与n相同位数的数字(不包含前导零)
ll last = 0;//前缀数字
for (ll i = nums.size() - 1; i >= 0; i--)
{
ll x = nums[i];//次高位数字
//当i == nums.size() - 1时,枚举次高位数字范围(1 ~ x - 1),不能包含前导零
//枚举次高位数字范围(0 ~ x - 1),这样的话其余后面位置的数字可以任选
for (ll j = (i == nums.size() - 1 ? 1 : 0); j < x; j++)
{
ll temp = last;
while (temp) ans[temp % 10] += power10[i], temp /= 10;//计算该分支情况前缀各个数字出现次数
for (ll k = 0; k < 10; k++) ans[k] += f[i + 1][j].s[k];
}
last = last * 10 + x;
if (i == 0)//计算末尾分支结点
{
ll temp = last;
while (temp) ans[temp % 10] += 1, temp /= 10;
}
}
//枚举数字位数(小于最高位数)
for (ll i = 1; i <= nums.size() - 1; i++)
for (ll j = 1; j < 10; j++)//不包含前导零
for (ll k = 0; k < 10; k++) ans[k] += f[i][j].s[k];
return ans;
}
int main()
{
init(10);
int a, b;
while (cin >> a >> b, a || b)
{
if(a > b) swap(a, b);
vector<ll> ans1 = dp(a - 1);
vector<ll> ans2 = dp(b);
for (ll i = 0; i < 10; i++) cout << ans2[i] - ans1[i] << ' ';
cout << endl;
}
return 0;
}
状态压缩DP
蒙德里安的梦想
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 12, M = 1 << N;
//n:行数
//m:列数
int n, m;
//说明:长条横着摆放叫做横条,长条竖着摆放叫竖条
//思路:只枚举横条摆放位置,若剩余位置能容纳竖条,则为一个合法方案
//f[i][j]:
//前i列枚举横条摆放方案(横条摆放状态并非完全能使棋盘充满,其余位置还需排放竖条才能使期盼充满)
//第i列空位置摆放横条,且使第i+1列格子状态为j的合法方案数(即第i列横条摆放状态为j)
//状态转移:
//枚举第i - 1列横条的摆放状态k,即使第i列格子状态为k,判断状态k能否与f[i][j]所代表状态进行转移
//若(k & j) == 0,则说明第i - 1列横条摆放后,第i列格子状态为k,能够使第i列摆放横条时,将横条摆放成状态j(人话:第i - 1列横条不会与第i列摆放的横条冲突)
//从第i - 1列向第i列进行状态转移后,第i列格子状态变为(k | j),若st[k | j] == true,即第i列格子状态不存在连续奇数个空格子(人话:第i列格子状态能够摆放竖条,使第i列格子充满)
ll f[N][M];
//st[i]:某一列格子状态为i时,是否存在连续奇数个空格子,即是否能够容纳竖条使该列格子充满
bool st[M];
//state[j]:第i列格子状态为j,第i - 1列格子状态为k,若第i - 1列能够向第i列进行状态转移,则state[j]存储的是能够进行状态转移的状态
vector<int> state[M];
void init()
{
//初始化st数组,处理能够容纳竖条的状态
for (int i = 0; i < 1 << n; i++)
{
st[i] = true;
for (int j = 0, k = 0; j < n; j = k)
{
//双指针算法处理奇数个空格子
while (k < n && (i >> k & 1) == (i >> j & 1)) k++;
// if (!(i >> j & 1) && (k - j) & 1)
if (!(i >> j & 1) && (k - j) % 2 == 1)
{
st[i] = false;
break;
}
}
}
//初始化state数组,存储能够进行状态转移的前一列格子状态
for (int i = 0; i < 1 << n; i++)
{
state[i].clear();
for (int j = 0; j < 1 << n; j++)
if (((i & j) == 0) && st[i | j]) state[i].push_back(j);//注意&的优先级很低,需加括号
}
}
ll dp()
{
// 暴力版dp方式
// memset(f, 0, sizeof f);//初始化f数组,若f[i][j] == 0,则说明该状态不合法,枚举横条后,竖条不能充满棋盘
// f[0][0] = 1;//第0列横条摆放状态为0,使第1列格子状态为0的方案数,第0列只有该状态合法
// for (int i = 1; i <= m; i++)//枚举第i列(1 ~ m)
// for (int j = 0; j < 1 << n; j++)//枚举第i列横条摆放状态
// for (int k = 0; k < 1 << n; k++)
// if((j & k) == 0 && st[j | k]) f[i][j] += f[i - 1][k];
// return f[m][0];//第m列摆放横条状态为0,第m + 1列格子状态为0的合法方案数,因为第m列是最后一列,不能摆放横条,只有该状态才会最终合法状态
// 预处理版dp方式
memset(f, 0, sizeof f);//初始化f数组,若f[i][j] == 0,则说明该状态不合法,枚举横条后,竖条不能充满棋盘
f[0][0] = 1;//第0列横条摆放状态为0,使第1列格子状态为0的方案数,第0列只有该状态合法
for (int i = 1; i <= m; i++)//枚举第i列(1 ~ m)
for (int j = 0; j < 1 << n; j++)//枚举第i列横条摆放状态
for (auto k : state[j]) f[i][j] += f[i - 1][k];//寻找能够进行状态转移,前一列格子的合法状态
return f[m][0];//第m列摆放横条状态为0,第m + 1列格子状态为0的合法方案数,因为第m列是最后一列,不能摆放横条,只有该状态才会最终合法状态
}
int main()
{
while (cin >> n >> m, n || m)
{
init();
cout << dp() << endl;
}
}
最短Hamilton路径
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];//f[i][j]:表示从0走到j,路径点集状态为i,终点为j的路径最小值
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) cin >> w[i][j];
memset(f, 0x3f, sizeof f);//因为求最小值,初始化距离为无穷大
f[1][0] = 0;//从0走到0,路径状态为1(00..001),终点为0的路径最小值为0
//顺序:先枚举线路状态,后枚举终点状态
//这样才能使DP计算当前状态时,能确保依赖的前一个状态被计算过
for(int i = 0; i < 1 << n; i++)
for(int j = 0; j < n; j++)//枚举终点j
if((i & 1) && (i >> j & 1))//如果路径状态不包含0点,且不包含终点j点,则状态不合法
for(int k = 0; k < n; k++)//枚举倒数第二个终点k
if((i - (1 << j)) >> k & 1)//如果路径状态不包含k点,则状态不合法
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
cout << f[(1 << n) - 1][n - 1];//从0走到n - 1,路径状态为11...11,终点为n - 1的路径最小值
}
树形DP
没有上司的舞会
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 6010;
int n;
int happy[N];
int h[N], e[N], ne[N], idx;
bool has_father[N];
int f[N][2];
//f[i][0]:表示以i结点为根的树,不选i结点,整个树的最大高兴度
//f[i][1]:表示以i结点为根的树,选i结点,整个树的最大高兴度
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
f[u][1] = happy[u];//不初始化f[u][0]的原因是f[u][0]默认为0
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
dfs(j);
f[u][0] += max(f[j][0], f[j][1]);
f[u][1] += f[j][0];
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> happy[i];
memset(h, -1, sizeof h);
for(int i = 1; i <= n - 1; i++)
{
int a, b;
cin >> a >> b;
add(b, a);
has_father[a] = true;
}
int root = 1;
for(int i = 1; i <= n; i++)
if(!has_father[i])
{
root = i;
break;
}
dfs(root);
cout << max(f[root][0], f[root][1]);
}
记忆化搜索
滑雪
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 310;
int n, m;
int w[N][N];
int f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y)
{
int &v = f[x][y];
if(v != -1) return v;
v = 1;
for(int i = 0; i < 4; i++)
{
int tx = x + dx[i], ty = y + dy[i];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && w[x][y] > w[tx][ty]) v = max(v, dp(tx, ty) + 1);
}
return v;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> w[i][j];
int res = 0;
memset(f, -1, sizeof f);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
res = max(res, dp(i, j));
cout << res;
}
算法提高课
第三章 图论
最近公共祖先
祖孙询问
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 4e4 + 10, M = 8e4 + 10, INF = 0x3f3f3f3f;
int n, m;
//邻接表
int h[N], e[M], ne[M], idx;
//depth[i]:表示第i号结点所在的深度,根节点root的depth[root] = 1
//father[i][j]:表示第i号结点向根节点方向移动,即向上移动2^j步的祖先结点编号,father[i][0]:表示第i号的直接父节点
//由题目中结点总数为4e4可得,father数组的第二维大小为[log2(4e4) + 1] = 16,即2^16 > 4e4
int depth[N], father[N][17];
//bfs队列
int q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
//由于根节点root没有祖先,这里我们把根节点的所有祖先编号都设置为0,当作哨兵,用于检测是否访问越界
//for(int k = 0; k <= 16; k++) father[root][k] = 0;//默认设置
depth[0] = 0;//边界深度设置为0
int hh = 0, tt = 0;
depth[root] = 1, q[0] = root;
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(depth[j] == INF)//如果没有访问过,则更新
{
depth[j] = depth[t] + 1;
q[++tt] = j;
//DP思想,从根向下扩展
father[j][0] = t;//初始化当前结点j的直接父节点
//如果当前结点j经过2^k步达到的祖先结点为high,则当前结点j可以先走2^(k-1)步到路径中间某个结点mid,然后在从mid结点走2^(k-1)再到high
//即j -> 2^(k - 1) -> mid -> 2^(k - 1) -> high
//根据上述思想进行如下DP
for(int k = 1; k <= 16; k++) father[j][k] = father[father[j][k - 1]][k - 1];
}
}
}
}
//LCA-最近公共祖先LCA(Least Common Ancestors)
int lca(int a, int b)
{
//在以root为根的树中,如果a结点在b结点的上方,则交换a,b方便处理
if(depth[a] < depth[b]) swap(a, b);
//处理depth[a] >= depth[b]的情况
for(int k = 16; k >= 0; k--)//从大到小枚举的原因:因为我们需要将a,b结点移动到同一层,根据二进制化拼凑移动步数,我们需要移动最大且合适的步数,然后再重复该操作直至拼凑得到最终移动步数
if(depth[father[a][k]] >= depth[b]) a = father[a][k];
//a,b同层之后,判断两个结点是否相等,如果相等则b是初始a的最近祖先结点
if(a == b) return a;
//a,b同层之后,则a,b每次移动都是移动相同层数
for(int k = 16; k >= 0; k--)//从大到小枚举的原因同上,但问题是从小到大枚举得到的答案也是正确的
if(father[a][k] != father[b][k])//我们需要将a,b移动至最近公共祖先的下一层,如果移动到公共祖先层,即移动到father[a][k] == father[b][k]时,一是我们无法判断该层是否是!!!最近!!!祖先,二是我们这样做会走到哨兵0,得不到我们想要的答案
{
a = father[a][k];
b = father[b][k];
}
//此时a,b已经移动至最近公共祖先的下一层
return father[a][0];
}
int main()
{
cin >> n;
int root;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
if(b == -1) root = a;
else
{
add(a, b);
add(b, a);
}
}
//预处理depth数组和father数组
bfs(root);
cin >> m;
for(int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
int p = lca(a, b);
if(p == a) cout << 1 << endl;
else if(p == b) cout << 2 << endl;
else cout << 0 << endl;
}
}
有向图的强连通分量
受欢迎的牛
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e4 + 10, M = 5e4 + 10;
int n, m;
//原始数据邻接表
int h[N], e[M], ne[M], idx;
//tarjan算法所需的一些变量与数组
//timestamp:时间戳
//dfn[u]:表示dfs遍历到当前结点u的时间
//low[u]:在图的dfs过程中,如果要求某个结点u与其相关的强连通分量的话,那么u结点必须在dfs中搜到其祖宗结点构成一条回路(回路是构成强连通分量的必要条件),low[u]:表示的是通过该结点u及其子树在dfs过程中所能搜到某些祖宗结点的最小时间戳
//stk数组:存储结点的栈,在图的dfs过程中,是靠栈完成的,我们也可以用栈在dfs过程中保存某条路径的一些结点,但在tarjan算法中我们通过时间戳与存储结点的栈可找出某个强连通分量
//top:栈顶下标
//in_stk[u]:判断u结点是否在结点栈中
//scc_id[u]:表示u结点所属的强连通分量的编号
//scc_size[i]:表示编号为i的强连通分量所含结点的个数
//dout[i]:表示编号为i的强连通分量的出度
//scc_cnt:强连通分量的个数
int timestamp;
int dfn[N], low[N];
int stk[N], top;
bool in_stk[N];
int scc_id[N], scc_size[N], dout[N], scc_cnt;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++timestamp;//更新当前结点u的时间戳数组
stk[++top] = u, in_stk[u] = true;//保存dfs路径,将当前结点u加入栈中
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])//如果子结点j没有被搜过
{
tarjan(j);
low[u] = min(low[u], low[j]);//子结点更新父结点,更新low[u]
}
else if(in_stk[j])//该判断语句好像可以省略
{
//搜到某个直连祖宗结点,用祖宗结点的时间戳dfn[j]去更新low[u]
low[u] = min(low[u], dfn[j]);
}
}
//如果该判断语句成立,那就说明当前结点u是某个强连通分量的最高点(在强连通分量中第一次被搜到的点)
//由于stk保存的是一段dfs路径,我们可以将其中属于该强连通分量的结打上标记,更新相关数组
if(dfn[u] == low[u])
{
++scc_cnt;
int y;
do
{
y = stk[top--];
in_stk[y] = false;
scc_id[y] = scc_cnt;
scc_size[scc_cnt]++;
}while(y != u);
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
add(a, b);
}
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; i++)
for(int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
int a = scc_id[i], b = scc_id[k];
if(a != b) dout[a]++;
}
//zeros:表示出度为0的强连通分量个数
//sum:表示答案
int zeros = 0, sum = 0;
for(int i = 1; i <= scc_cnt; i++)
if(!dout[i])
{
zeros++;
sum += scc_size[i];
if(zeros > 1)//如果有多个强连通分量,那就说明答案情况不成立,为0
{
sum = 0;
break;
}
}
cout << sum;
}
第四章 高级数据结构
树状数组(作用:单点修改,单点查询;区间修改,单点查询;区间查询,区间修改)
一个简单的整数问题
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
//n:数据个数
//m:操作个数
int n, m;
//原始数组
int a[N];
//树状数组用作差分数组
//树状数组对应的原始序列每个数存储的是原始数组中相邻两个数的差分值,其前缀和表示的是第多少个数
int tr[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int sum(int x)
{
int res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++)
{
add(i, a[i] - a[i - 1]);
//add(i, a[i]), add(i + 1, -a[i]);
}
for(int i = 1; i <= m; i++)
{
char ch;
cin >> ch;
if(ch == 'C')
{
int l, r, c;
cin >> l >> r >> c;
add(l, c), add(r + 1, -c);
}
else
{
int x;
cin >> x;
cout << sum(x) << endl;
}
}
}
线段树(作用:解决区间上统一增加、区间上统一修改、区间上统一查询累加和等问题)
最大数
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
//n:代表当前序列中已添加数的个数
//m:操作个数
//p:模运算取模量
int n, m, p;
//需求:我们需要维护一段数字序列,需要对该数字序列的各个区间或者某个位置上的值作修改,我们就需要用到线段树
//线段树结点
struct node
{
int l, r;//维护数字序列中下标为(l ~ r)这一段
int v;//所维护区间中数字序列的最大值(只是该题的需求是这样,因题而已)
}tr[N * 4];//线段树结点编号类似于堆,但不并不一定是完全二叉树,线段树结点数量是所维护数字序列的长度的四倍
//在数字序列某个位置的数进行修改时,实际过程是在线段树的叶子节点进行修改的,因为叶子结点所维护区间只有1个数,便是所代表数
//对叶子结点修改后,我们需要更新父结点的相关信息,就需要用到pushup操作
//修改函数见modify递归修改
void pushup(int u)
{
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
//因为为线段树动态增加结点是很困难的,我们可以先构建一棵大小合适(数字序列的长度)的线段树
//每个结点中只有区间值设置了,但没有设置代表值v,就相当于只是把位置预留出来,等待添加数时,将对应位置上的数进行变更即可
//u:线段树结点编号(线段树结点编号为(1 ~ n),这样设置取值范围的原因类似于堆,易计算结点编号,所以根节点编号为1,所维护区间为(1 ~ 数字序列的长度)
//l:为当前线段树结点设置区间左边界
//r:为当前线段树结点设置区间右边界
void build(int u, int l, int r)
{
tr[u] = {l, r};//设置区间
if(l == r) return ;//区间内只有一个数,代表当前结点是叶子结点,直接返回
int mid = l + r >> 1;//以mid为边界,为左右儿子结点设置对应维护区间,保证左右儿子所维护的数字序列不重不漏
build(u << 1, l, mid);//左儿子:编号为u * 2 = u << 1, 所维护区间为(l, mid)
build(u << 1 | 1, mid + 1, r);//右儿子:编号为u * 2 + 1 = u << 1 | 1, 所维护区间为(mid + 1, r)
}
//u:线段树结点编号
//(l ~ r):对应查询区间
int query(int u, int l, int r)
{
//如果当前线段树结点所维护区间 ⊂ 查询区间,即(tr[u].l, tr[u].r) ⊂ (l, r)时,代表查询区间包含当前线段树结点所维护区间
//因为我们是要求(l, r)这段区间的最大值,由于当前情况下该线段树结点所维护区间被包含与此,只能求出重叠部分的最大值,不能求出其他部分的最大值,已不能作出贡献,直接返回即可
if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
int mid = tr[u].l + tr[u].r >> 1;//左右儿子所维护区间分割的边界
int v = 0;//所求查询区间的数字最大值,即查询答案,可初始化也可不初始化,数字序列中的数字大小 > 0
//当左儿子所维护区间与查询区间有交集时,我们需要进入左儿子结点,求出重叠部分的最大值
if(l <= mid) v = max(v, query(u << 1, l, r));
//当右儿子所维护区间与查询区间有交集时,我们需要进入右儿子结点,求出重叠部分的最大值
if(r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
//u:线段树结点编号
//x:我们需要将原始数字数列的第x个数进行修改,其对应叶子结点所维护的区间为(x, x)
//v:更新的值
void modify(int u, int x, int v)
{
if(tr[u].l == x && tr[u].r == x) tr[u].v = v;//找到叶子结点
else
{
int mid = tr[u].l + tr[u].r >> 1;//左右儿子所维护区间分割的边界
if(x <= mid) modify(u << 1, x, v);//修改位置x在左儿子所维护区间时,进入左儿子结点
else modify(u << 1 | 1, x, v);//修改位置x在右儿子所维护区间时,进入右儿子结点
pushup(u);//子结点更新父节点
}
}
int main()
{
cin >> m >> p;
build(1, 1, m);//操作个数 -> 数字序列的长度最大值,初始化线段树,所维护区间最大为(1 ~ m)
int last = 0;//上一次查询的值
for(int i = 1; i <= m; i++)
{
char ch;
int x;
cin >> ch >> x;
if(ch == 'Q')
{
last = query(1, n - x + 1, n);
cout << last << endl;
}
else
{
modify(1, n + 1, ((ll)x + last) % p);//在第n + 1个数位置上进行修改
n++;//数字序列的长度加一
}
}
}
第六章 基础算法
RMQ
天才的记忆
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2e5 + 10, M = 18;
int n, m;
int w[N], f[N][M];
//f[i][j]:表示的是以第i个数为起点,长度为2^j的区间内的最大数
void init()
{
for(int j = 0; j < M; j++)//先枚举长度
for(int i = 1; i + (1 << j) - 1 <= n; i++)
if(!j) f[i][j] = w[i];
else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return max(f[l][k], f[r - (1 << k) + 1][k]);//当2^k != len时,区间(l, r)的最大数的计算方法:由两个小区间进行计算
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> w[i];
init();
cin >> m;
for(int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
cout << query(a, b) << endl;
}
}
大佬，666