|
（文章框架来自学长，内容来源于自我想象，不足之处dd）
入门篇
在入门篇我们会学习很多有用的知识，下面给出一份比较推荐的学习的路径，大家可以根据自己的情况去查缺补漏。
1. 枚举
2. 模拟
3. 递归
4. 前缀和和差分
5. 尺取法
6. 排序算法原理的理解
7. 二分，三分
1> STL自带的二分函数
在库#include <algorithm中有两个函数：upper_bound和lower_bound。
这两个函数的作用是二分查找一个数在数组中出现的位置。区别是upper返回第一个大于搜索数的位置，而lower是第一个大于等于搜索数的位置。
函数的用法：lower_bound(a.begin(),a.end(),x) – 返回第一个大于等于 x 的数的地址。而由于是地址，在最后要加上?a（也就是减去地址）。
//vector数组中
int index = lower_bound(vec.begin(), vec.end(), t) - vec.begin();
//普通数组中
int index = lower_bound(a + 1, a + n + 1, x) - a;
2> 手写二分
int binarySearch(std::vector<int> &nums, int left, int right, int target)
{
//找不到，返回-1
if (left > right)
return -1;
//防止(left + right)溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target)
{
//找到target，返回下标
return mid;
}
else if (nums[mid] < target)
{
//中间的值小于target，说明target在右边
return binarySearch(nums, mid + 1, right, target);
}
else
{
//中间的值大于target，说明target在左边
return binarySearch(nums, left, mid - 1, target);
}
}
//重载binarySearch方法，便于调用
int binarySearch(std::vector<int> &nums, int target)
{
//nums为空则直接返回-1，否则递归查找
return nums.size() == 0 ? -1 : binarySearch(nums, 0, nums.size() - 1, target);
}
int binarySearch(std::vector<int> &nums, int target)
{
//nums为空时直接返回-1
if (nums.size() == 0)
return -1;
int left = 0;
int right = nums.size() - 1;
while (left <= right)
{
//防止(left + right)溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target)
{
//找到target，返回下标
return mid;
}
else if (nums[mid] < target)
{
//中间的值小于target，说明target在右边
left = mid + 1;
}
else
{
//中间的值大于target，说明target在左边
right = mid - 1;
}
}
//找不到，返回-1
return -1;
}
8. 分治
- **划分问题：**把问题的实例划分成子问题。
- **递归求解：**递归解决子问题。
- **合并问题：**合并子问题的解得到原问题的解。
- 例：归并排序 (merge_sort) –
O(n*logn)
void merge_sort(int *A, int x, int y, int *T){
if(y - x > 1){
int m = x + (y - x) / 2; //划分
int p = x, q = m, i = x;
merge_sort(A, x, m, T);
merge_sort(A, m, y, T); //递归求解
while(p < m || q < y){
if(q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++]; //从左半数组复制到临时空间
else T[i++] = A[q++]; //从右半数组复制到临时空间
}
for(i = x; i < y; i++) A[i] = T[i]; //从辅助空间复制回A数组
}
}
9. 贪心
10. 简单搜索
11. 读入优化
inline int read_int()//快读整数
{
char c;
int sign = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-') sign = -1;
int res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
return res * sign;
}
inline double read_double()//快读实数
{
char c;
int sign = 1;
while((c = getchar()) < '0' || c > '9')
if(c == '-') sign = -1;
double res = c - '0';
while((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
if(c != '.') return res * sign;
double ll = 0.1;
while((c = getchar()) >= '0' && c <= '9')
res += (c - '0') * ll, ll *= 0.1;
return res * sign;
}
#include <iostream>
#include <cstdio>
#include <sstream>//stringstream的头文件
using namespace std;
int main()
{
string line, word;
while(getline(cin, line))
{
stringstream stream(line);
cout << stream.str() << endl;
while(stream >> word) { cout << word << endl; }
}
// 输入: shanghai no1 school 1989
// 输出: shanghai no1 school 1989
// shanghai
// no1
// school
// 1989
printf("\n");
int val1 = 512, val2 = 1024;
stringstream ss;
ss << "val1: " << val1 << endl << "val2: " << val2 << endl;
// "val1: "此处有空格,字符串流是通过空格判断一个字符串的结束
// 将int类型读入ss,变为string类型
cout << ss.str();
// 输出为: val1: 512
// val2: 1024
printf("\n");
string dump;
int a, b;
ss >> dump >> a >> dump >> b;
// 提取512,1024保存为int类型.当然,如果a,b声明为string类型,那么这两个字面值常量相应保存为string类型
cout << a << " " << b << endl;
// 输出为: 512 1024
printf("\n");
// stringstream不会主动释放内存(或许是为了提高效率),但如果在程序中用同一个流,反复读写大量的数据,将会造成大量的内存消耗,所以此时,需要用stream.str("")适时地清除一下缓冲
stringstream sss;
string s;
sss << "shanghai no1 school";
sss >> s;
cout << "size of stream = " << sss.str().length() << endl;
cout << "s: " << s << endl;
sss.str("");
cout << "size of stream = " << sss.str().length() << endl;
// 输出: size of stream = 19
// s: shanghai
// size of stream = 0
return 0;
}
something
浮点数
浮点型比较大小时，不能用a == b表示，要用|a - b| < 0.0000001（或其他精确度）。
float：2^23 = 8388608，一共七位，这意味着最多能有7位有效数字，但绝对能保证的为6位，也即float的精度为6~7位有效数字。
double：2^52 = 4503599627370496，一共16位，同理，double的精度为15~16位。
Memset函数
0的二进制是00000000 00000000 00000000 00000000，取后8位00000000，初始化后00000000 00000000 00000000 00000000结果还是0
负数在计算机中以补码存储，-1的二进制是11111111 11111111 11111111 11111111，取后8位11111111，则是11111111 11111111 11111111 11111111结果也是-1
memset(a, 0, sizeof(a)); //初始化为0
memset(a, 255, sizeof(a)); //初始化为-1
不能初始化为1
0x8f的含义：
0x是指16进制，所以16进制的2位可以表示2进制的8位
8则对应1000，f则对应1111；所以每个字节的值就是10001111
众所周知 int 的最高位即32位是表示正负的，第32位为1则为负数，反之为整数
很明显10001111100011111000111110001111这个数是个大负数 (-1886417009)
memset(a, 0x7f, sizeof(a)); //初始化为很大的数（略小于0x7fffffff）
memset(a, 0xaf, sizeof(a)); //初始化为很小的数
memset(a, 0x8f, sizeof(a)); //初始化为很大的负数
基础篇
学会了上面的算法后。我们就有了很好的基础帮我们去理解学习下一步的各种算法。在此我一共把算法大概划分成了4个大类，
- 数据结构
- 动态规划
- 图论
- 数学
其中计算几何和博弈论归为数学部分，字符串相关算法归为数据结构。接下来我们对每个部分的基础算法进行了解。
一、基础数据结构
对与基础数据结构，很多都是借助STL实现的，所以希望大家都能熟练掌握STL的用法。
1. 栈
2. 队列
3. 链表
4. 堆
5. 优先队列
6. HASH表
7. 二叉树
8. Trie树
字典树可以看作一棵26叉树。
请看以下题目：
给出n个单词构成的词典，再给出m个字符串。统计有多少个字符串为词典中的单词。
（单词与字符串均为小写字母构成）
以下为用字典树实现的标准程序
#include<bits/stdc++.h>
using namespace std;
int ch[1000000][26];
//ch[i][j]的定义：i号结点的某字母子树的根结点编号。j = int('该字母' - 'a')。当编号为0时，结点不存在。
int main()
{
int n, m;
cin >> n >> m;
//以下为字典树的构造
int i, j, ls, c, tot = 1, u, sum = 0;
char s[1000000];
memset(ch, 0, sizeof(ch));
for(i = 0; i < n; i++)
{
u = 0;
scanf("%s", s);
ls = strlen(s);
for(j = 0; j < ls; j++)
{
c = s[j] - 'a';
if(ch[u][c] == 0)
{
tot++;//tot记录结点总数，用于分配编号
ch[u][c] = tot;
}
u = ch[u][c];//将本次修改的结点用于下次操作，相当于在树上深入了一层
}
}
//以下为在字典树上进行的查找操作
bool b;
for(i = 0; i < m; i++)
{
scanf("%s", s);
ls = strlen(s);
b = true;
u = 0;
for(j = 0; j < ls; j++)
{
c = s[j] - 'a';
if(ch[u][c] != 0)
{
u = ch[u][c];
continue;
}
b = false;
break;
}
for(i = 0; i < 26; i++)//判断字符串是否为完整的单词
{
if(ch[u][i] != 0)
{
b = false;
break;
}
}
if(b)
sum++;
}
cout << sum;
return 0;
}
/*
给定n个长度不超过10的数字串，问其中是否存在两个数字串S,T，使得S是T的前缀。有多组数据，数组组数不超过40，n<=10000
*/
/*
思路->在构建过程中：
若当前串插入后没有新建任何结点，则当前串一定是之前插入的某个串的前缀
若当前串插入过程中经过某个带有串结尾标记的结点，则之前插入的某个串一定是当前串的前缀
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int t, n, ans, cnt;
char a[15];
int ch[maxn][15];
bool f[maxn];
inline int read()
{
char c;
int f = 1;
while((c = getchar()) < '0' || c > '9')
if(c == '-') f = -1;
int res = c - '0';
while((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + c - '0';
// res = res * 10 + c - '0';
return res * f;
}
bool insert(char *s)
{
int len = strlen(s);
int u = 1;
bool
int main()
{
t = read();
for(int i = 1; i <= t; i++)
{
cnt = 1;//新的Trie树
ans = false;
memset(ch, 0, sizeof(ch));
memset(f, false, sizeof(f));
n = read();
for(int j = 1; j <= n; j++)
{
scanf("%s", a);
if(insert(a)) ans = true;
}
if(ans) printf("YES");
else printf("NO");
}
return 0;
}
9. set和map的用法
10. 并查集
并查集合并与查询
n个元素，m次操作
p1 = 1时，将p2与p3所在集合合并
p1 = 2时，输出p2与p3是（Y）否（N）在同一集合内
#include<bits/stdc++.h>
using namespace std;
int k, n, m, s, ans, p1, p2, p3;
int fa[10010];
int find(int k)//路径压缩
{
if(fa[k] == k) return k;
return fa[k] = find(fa[k]);
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) fa[i] = i;//初始化
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &p1, &p2, &p3);
if(p1 == 1) fa[find(p2)] = find(p3);
else if(find(p2) == find(p3)) printf("Y\n");
else printf("N\n");
}
return 0;
}
11. KMP算法
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
//i + 1 - m + 1
int n, m;
char a[maxn], b[maxn];
int p[maxn];
int ans[maxn], cnt;
inline int read()
{
char c;
int f = 1;
while((c = getchar()) < '0' || c > '9')
if(c == '-') f = -1;
int res = c - '0';
while((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
return res * f;
}
void pre()
{
p[1] = 0;
int j = 0;
for(int i = 1; i < m; i++)
{
while(j && b[i + 1] != b[j + 1]) j = p[j];
if(b[i + 1] == b[j + 1]) j++;
p[i + 1] = j;
}
}
void kmp()
{
int j = 0;
for(int i = 0; i < n; i++)//!!!!!!!!从0开始枚举
{
while(j && a[i + 1] != b[j + 1]) j = p[j];
if(a[i + 1] == b[j + 1]) j++;
if(j == m)
{
printf("%d\n", i + 1 - m + 1);
j = p[j];
}
}
}
int main()
{
scanf("%s", a + 1);
scanf("%s", b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
pre();
kmp();
for(int i = 1; i <= m; i++) printf("%d ", p[i]);//前缀
printf("\n");
return 0;
}
12. 单调栈
13. 树状数组
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int dp[100001];
inline int read_int()
{
char c;
int sign = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-') sign = -1;
int res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
return res * sign;
}
int lowbit(int x) { return x & (-x); }//取二进制中最低位的1
void add(int x, int d, int n)//单点加法
{
while(x <= n)
{
dp[x] += d;
x += lowbit(x);
}
}
int sum(int q)//区间[1, q]求和
{
int ans = 0;
while(q > 0)
{
ans += dp[q];
q -= lowbit(q);
}
return ans;
}
int main()
{
int t, cnt = 0;
char word[20];
t = read_int();
while(t--)
{
memset(dp, 0, sizeof(dp));
n = read_int();
int m;
for(int i = 1; i <= n; i++)
{
m = read_int();
add(i, m, n);
}
printf("Case %d:\n", ++cnt);
while(scanf("%s", word) && word[0] != 'E')
{
int a = read_int();
int b = read_int();
if(word[0] == 'A') add(a, b, n);//a点加b
else if(word[0] == 'S') add(a, -b, n);//a点减b
else printf("%d\n", sum(b) - sum(a - 1));//询问区间和[a, b]
}
}
return 0;
}
14. 线段树
//线段树
struct SegmentTree {
static const int MAXN = 50005; //最大节点数
//static const int MOD = 1e9 + 7;
LL a[MAXN];
LL addLazy[MAXN * 4], mulLazy[MAXN * 4]; //加法lazy标记、乘法lazy标记
LL sum[MAXN * 4]; //区间和
void update(int k) {
//sum[k] = (sum[k << 1] + sum[k << 1 | 1]) % MOD;
sum[k] = sum[k << 1] + sum[k << 1 | 1];
}
//建树
void build(int k, int l, int r) {
addLazy[k] = 0;
mulLazy[k] = 1;
if(l == r) {
//sum[k] = a[l] % MOD;
sum[k] = a[l];
return ;
}
//int mid = (l + ((r - l) >> 1)) % MOD;
int mid = l + ((r - l) >> 1);
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
update(k);
}
void pushdown(int k, int l, int r) {
//int mid = (l + ((r - l) >> 1)) % MOD;
int mid = l + ((r - l) >> 1);
//维护区间和
//子节点的值 = 此刻子节点的值 * 父结点的乘法lazy标记 + 父结点的加法lazy标记 * 子节点的区间长度
//sum[k << 1] = (sum[k << 1] * mulLazy[k] + addLazy[k] * (mid - l + 1)) % MOD;
sum[k << 1] = sum[k << 1] * mulLazy[k] + addLazy[k] * (mid - l + 1);
//sum[k << 1 | 1] = (sum[k << 1 | 1] * mulLazy[k] + addLazy[k] * (r - mid)) % MOD;
sum[k << 1 | 1] = sum[k << 1 | 1] * mulLazy[k] + addLazy[k] * (r - mid);
//维护lazy标记，修改加法lazy标记时 要遵循乘法优先
//mulLazy[k << 1] = (mulLazy[k << 1] * mulLazy[k]) % MOD;
mulLazy[k << 1] = mulLazy[k << 1] * mulLazy[k];
//mulLazy[k << 1 | 1] = (mulLazy[k << 1 | 1] * mulLazy[k]) % MOD;
mulLazy[k << 1 | 1] = mulLazy[k << 1 | 1] * mulLazy[k];
//addLazy[k << 1] = (addLazy[k << 1] * mulLazy[k] + addLazy[k]) % MOD;
addLazy[k << 1] = addLazy[k << 1] * mulLazy[k] + addLazy[k];
//addLazy[k << 1 | 1] = (addLazy[k << 1 | 1] * mulLazy[k] + addLazy[k]) % MOD;
addLazy[k << 1 | 1] = addLazy[k << 1 | 1] * mulLazy[k] + addLazy[k];
//父结点标记初始化
addLazy[k] = 0;
mulLazy[k] = 1;
}
void Mul(int k, int v) {
//sum[k] = (sum[k] * v) % MOD;
sum[k] = sum[k] * v;
//mulLazy[k] = (mulLazy[k] * v) % MOD;
mulLazy[k] = mulLazy[k] * v;
//addLazy[k] = (addLazy[k] * v) % MOD;
addLazy[k] = addLazy[k] * v;
}
void modify_mul(int k, int l, int r, int x, int y, int v) {
if(l >= x && r <= y) {
Mul(k, v);
return ;
}
pushdown(k, l, r);
//int mid = (l + ((r - l) >> 1)) % MOD;
int mid = l + ((r - l) >> 1);
if(x <= mid) modify_mul(k << 1, l, mid, x, y, v);
if(mid < y) modify_mul(k << 1 | 1, mid + 1, r, x, y, v);
update(k);
}
void Add(int k, int l, int r, int v) {
//addLazy[k] = (addLazy[k] + v) % MOD;
addLazy[k] = addLazy[k] + v;
//sum[k] = (sum[k] + v * (r - l + 1)) % MOD;
sum[k] = sum[k] + v * (r - l + 1);
}
void modify_add(int k, int l, int r, int x, int y, int v) {
if(l >= x && r <= y) {
Add(k, l, r, v);
return ;
}
pushdown(k, l, r);
//int mid = (l + ((r - l) >> 1)) % MOD;
int mid = l + ((r - l) >> 1);
if(x <= mid) modify_add(k << 1, l, mid, x, y, v);
if(mid < y) modify_add(k << 1 | 1, mid + 1, r, x, y, v);
update(k);
}
//询问区间和
LL query_sum(int k, int l, int r, int x, int y) {
if(l >= x && r <= y) return sum[k];
pushdown(k, l, r);
//int mid = (l + ((r - l) >> 1)) % MOD;
int mid = l + ((r - l) >> 1);
LL res = 0;
//if(x <= mid) res = (res + query_sum(k << 1, l, mid, x, y)) % MOD;
if(x <= mid) res = res + query_sum(k << 1, l, mid, x, y);
//if(mid < y) res = (res + query_sum(k << 1 | 1, mid + 1, r, x, y)) % MOD;
if(mid < y) res = res + query_sum(k << 1 | 1, mid + 1, r, x, y);
//return res % MOD;
return res;
}
//询问区间最大值
}tet;
上述十二种数据结构都能帮助大家更清晰的学习算法并且锻炼代码能力。并且在后续学习中也会继续用到
二、基础动态规划
对于动态规划。很多人都感到头疼。所以在基础动态规划部分我们只给出几个基础的DP让大家学习
1. 路径搜索dp
2. 背包dp
#include<bits/stdc++.h>
using namespace std;
int m, n;//m表示背包容量, n表示物品数量
int w[500], c[500];//w[i]表示费用，c[i]表示价值
int f[2010];//f[v]表示费用不超过v的最大价值
int main()
{
scanf("%d%d", &m, &n);
for(int i = 1; i <= n; i++) scanf("%d%d", &w[i], &c[i]);
for(int i = 1; i <= n; i++)
for(int v = m; v >= w[i]; v--)
if(f[v - w[i]] + c[i] > f[v]) f[v] = f[v - w[i]] + c[i];
printf("%d\n", f[m]);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 205, maxx = 0x7fffffff / 2;
int f1[maxn][maxn];
int f2[maxn][maxn];
int s[maxn][maxn];
int a[maxn], sum[maxn], n, ans1, ans2;
inline int read()
{
char c;
int f = 1;
while((c = getchar()) < '0' || c > '9')
if(c == '-') f = -1;
int res = c - '0';
while((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
return res * f;
}
int main()
{
n = read();
for(int i = 1; i <= n; i++)
{
a[i] = read();
a[i + n] = a[i];
}
for(int i = 1; i <= n * 2; i++)
{
sum[i] = sum[i - 1] + a[i];//前缀和
f1[i][i] = 0;
f2[i][i] = 0;
}
for(int g = 2; g <= n; g++)//以合并堆数为阶段
for(int i = 1; i <= n * 2 - g + 1; i++)//合并的起始位置
{
int j = i + g - 1;
f1[i][j] = maxx;
f2[i][j] = 0;
for(int k = i; k < j; k++)
{
f1[i][j] = min(f1[i][j], f1[i][k] + f1[k + 1][j]);
f2[i][j] = max(f2[i][j], f2[i][k] + f2[k + 1][j]);
}
f1[i][j] += sum[j] - sum[i - 1];
f2[i][j] += sum[j] - sum[i - 1];
}
ans1 = maxx;
ans2 = 0;
for(int i = 1; i <= n; i++)
ans1 = min(ans1, f1[i][i + n - 1]);
for(int i = 1; i <= n; i++)
ans2 = max(ans2, f2[i][i + n - 1]);
printf("%d\n%d\n", ans1, ans2);
return 0;
}
3. 区间dp
区间dp的精华 – 将问题划分为“两两合并”的形式
for(int t = 1; t <= n - 1; t++)//阶段（枚举合并次数）
for(int i = 1; i <= 2 * n - t; i++)//状态（枚举起始位置）
{
int j = i + t;//终止位置
for(int k = i; k <= j - 1; k++)//决策（枚举划分点）
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + 决策）
}
区间dp–高精度
#include<bits/stdc++.h>
using namespace std;
long long f[110][110][110], a[110];
long long s1[110], s2[110], s3[110];
int n;
void mark(long long c[])//进位，只可意会
{
for(int i = 1; i <= c[0]; i++)
{
c[i + 1] += c[i] / 10000;
c[i] %= 10000;
}
while(c[c[0] + 1])
{
c[0]++;
c[c[0] + 1] += c[c[0]] / 10000;
c[c[0]] %= 10000;
}
}
void mul(long long a1, long long a2, long long a3, long long c[])//乘法: c = a1 * a2 * a3
{
c[0] = c[1] = 1;
for(int i = 1; i <= c[0]; i++) c[i] *= a1;
mark(c);
for(int i = 1; i <= c[0]; i++) c[i] *= a2;
mark(c);
for(int i = 1; i <= c[0]; i++) c[i] *= a3;
mark(c);
}
void add(long long a[], long long b[], long long c[])//加法: c = a + b
{
c[0] = a[0] > b[0] ? a[0] : b[0];
for(int i = 1; i <= c[0]; i++)
c[i] = a[i] + b[i];
mark(c);
}
int compare(long long a[], long long b[])//大于return 1，小于return 0;
{
//位数多的大
if(a[0] < b[0]) return 0;
if(a[0] > b[0]) return 1;
//位数相同->从高位开始比较
for(int i = a[0]; i >= 1; i--)
if(a[i] < b[i]) return 0;
else if(a[i] > b[i]) return 1;
return 0;
}
void print()
{
cout << f[1][n][f[1][n][0]];
for(int i = f[1][n][0] - 1; i >= 1; i--)//万进制输出
{
cout << f[1][n][i] / 1000;
cout << (f[1][n][i] / 100) % 10;
cout << (f[1][n][i] / 10) % 10;
cout << f[1][n][i] % 10;
}
cout << endl;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
f[i][j][0] = 0;
for(int t = 2; t <= n - 1; t++)//枚举分割次数
for(int i = 1; i <= n - t; i++)//枚举起始位置
{
int j = i + t;//终止位置
f[i][j][0] = 60;//极大值（因为n <= 50）
for(int k = i + 1; k <= j - 1; k++)
{
memset(s1, 0, sizeof(s1));
memset(s2, 0, sizeof(s2));
memset(s3, 0, sizeof(s3));
mul(a[i], a[k], a[j], s1);
add(f[i][k], f[k][j], s2);
add(s1, s2, s3);
if(compare(f[i][j], s3))
memcpy(f[i][j], s3, sizeof(s3));
}
}
print();
return 0;
}
4. 树形dp
5. 状态压缩dp
6. 概率dp
三、基础图论
关于图论的学习，也不用操之过急，从基础入手，锻炼对图论的理解就好
1. 建图方法
2. 用DFS和BFS遍历整个图
3. 欧拉回路
- 如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。
- 如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。
- 具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。
- 无向图存在欧拉回路的充要条件：
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图是连通图。 - 有向图存在欧拉回路的充要条件：
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。 - 哈密尔顿环是指不重复地走过所有点且最终能回到起点的回路。
4. 拓扑排序
用邻接矩阵 + dfs 实现拓扑排序的方法如下：
int G[MAX_V][MAX_V]; // 邻接矩阵
int V, E; // V为结点数，E为边数
int vis[MAX_V]; // 访问标志，-1表示正在访问，0表示从未访问过，1表示已经访问过
int topo[MAX_V]; // 拓扑序储存数组
int cnt; // 用于给topo数组计数
bool dfs(int i)
{
vis[i] = -1;
for (int j = 0; j < V; ++j)
if (G[i][j]) // 若存在顶点i指向顶点j的边
{
if (vis[j] == -1) // 该结点正在访问，说明存在环，失败退出
return false;
else if (!vis[j])
dfs(j); // 搜索后续结点看是否存在环
}
vis[i] = 1;
topo[--cnt] = i; // 因dfs是递归实现的，所以返回的是最底层的顶点
return true;
}
bool toposort()
{
cnt = V;
memset(vis, 0, sizeof(vis));
for (int i = 0; i < V; ++i)
if (!vis[i]) // 若该结点还未访问过，则进行深搜
if (!dfs(i))
return false;
return true;
}
用邻接表 + bfs 实现的方法如下：
vector<int> G[MAX_V]; // 邻接表
int V, E; // V为结点数，E为边数
int in[MAX_V]; // 记录每个结点的入度
vector<int> topo; // 储存拓扑序的数组
bool toposort()
{
queue<int> que;
for (int i = 0; i < V; ++i)
if (in[i] == 0)
que.push(i);
while (!que.empty())
{
int u = que.front();
que.pop();
topo.push_back(u); // 将剔除的结点加到当前拓扑序的末尾
for (int i = 0; i < G[u].size(); ++i) // 将顶点u指向的顶点的入度都减1
{
int vv = G[u][i];
if (--in[vv] == 0) // 若出现入度为0的结点，则加入队列
que.push(vv);
}
}
if (topo.size() != V)
return false;
return true;
}
5. 三种最短路算法（Floyd，Dijkstra，SPFA）
Floyd
/*
时间复杂度 O(n ^ 3)
可以解决多源最短路问题
*/
void Floyd() {
//初始化dis[]数组
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dis[i][j] = graph[i][j];
}
}
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
Dijkstra
/*
统计图(G)中"顶点vs"到其它各个顶点的最短路径。
时间复杂度正比于 节点个数和边的个数的乘积
参数说明：
G -- 图
vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路 径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
*/
void dijkstra(Graph G, int vs, int prev[], int dist[])
{
int i,j,k;
int min;
int tmp;
int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
// 初始化
for (i = 0; i < G.vexnum; i++){
flag[i] = 0; // 顶点i的最短路径还没获取到。
prev[i] = 0; // 顶点i的前驱顶点为0。
dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
}
// 对"顶点vs"自身进行初始化
flag[vs] = 1;
dist[vs] = 0;
// 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
for (i = 1; i < G.vexnum; i++){
// 寻找当前最小的路径；
// 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
min = INF;
for (j = 0; j < G.vexnum; j++){
if (flag[j]==0 && dist[j]<min){
min = dist[j];
k = j;
}
}
// 标记"顶点k"为已经获取到最短路径
flag[k] = 1;
// 修正当前最短路径和前驱顶点
// 即当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
for (j = 0; j < G.vexnum; j++){
tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出
if (flag[j] == 0 && (tmp < dist[j]) ){
dist[j] = tmp;
prev[j] = k;
}
}
}
}
Bellman
bool Bellman_Ford()
{
for(int i = 1; i <= nodenum; ++i) //初始化
dis[i] = (i == original ? 0 : MAX);
for(int i = 1; i <= nodenum - 1; ++i)
for(int j = 1; j <= edgenum; ++j)
if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛
{
dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
pre[edge[j].v] = edge[j].u;
}
bool flag = 1; //判断是否含有负权回路
for(int i = 1; i <= edgenum; ++i)
if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
{
flag = 0;
break;
}
return flag;
}
SPFA
/*
SPFA可以处理负权边和负权环
时间复杂度为 O(k?E)
*/
int SPFA(int s) {
queue<int> q;
bool inq[maxn] = {false};
for(int i = 1; i <= N; i++) dis[i] = 2147483647;
dis[s] = 0;
q.push(s); inq[s] = true;
while(!q.empty()) {
int x = q.front(); q.pop();
inq[x] = false;
for(int i = front[x]; i !=0 ; i = e[i].next) {
int k = e[i].v;
if(dis[k] > dis[x] + e[i].w) {
dis[k] = dis[x] + e[i].w;
if(!inq[k]) {
inq[k] = true;
q.push(k);
}
}
}
}
for(int i = 1; i <= N; i++) cout << dis[i] << ' ';
cout << endl;
return 0;
}
6. 两种最小生成树（Prim，Kruskal）
Prim
复杂度：O(n^2)
void prim(Graph G, int start)
{
int min,i,j,k,m,n,sum;
int index=0; // prim最小树的索引，即prims数组的索引
char prims[MAX]; // prim最小树的结果数组
int weights[MAX]; // 顶点间边的权值
// prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。
prims[index++] = G.vexs[start];
// 初始化"顶点的权值数组"，将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
for (i = 0; i < G.vexnum; i++ )
weights[i] = G.matrix[start][i];
// 将第start个顶点的权值初始化为0。可以理解为"第start个顶点到它自身的距离为0"。
weights[start] = 0;
for (i = 0; i < G.vexnum; i++){
// 由于从start开始的，因此不需要再对第start个顶点进行处理。
if(start == i)
continue;
j = 0;
k = 0;
min = INF;
// 在未被加入到最小生成树的顶点中，找出权值最小的顶点。
while (j < G.vexnum){
// 若weights[j]=0，意味着"第j个节点已经被排序过"(或者说已经加入了最小生成树中)。
if (weights[j] != 0 && weights[j] < min){
min = weights[j];
k = j;
}
j++;
}
// 经过上面的处理后，在未被加入到最小生成树的顶点中，权值最小的顶点是第k个顶点。
// 将第k个顶点加入到最小生成树的结果数组中
prims[index++] = G.vexs[k];
// 将"第k个顶点的权值"标记为0，意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。
weights[k] = 0;
// 当第k个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。
for (j = 0 ; j < G.vexnum; j++){
// 当第j个节点没有被处理，并且需要更新时才被更新。
if (weights[j] != 0 && G.matrix[k][j] < weights[j])
weights[j] = G.matrix[k][j];
}
}
// 计算最小生成树的权值
sum = 0;
for (i = 1; i < index; i++){
min = INF;
// 获取prims[i]在G中的位置
n = get_position(G, prims[i]);
// 在vexs[0...i]中，找出到j的权值最小的顶点。
for (j = 0; j < i; j++){
m = get_position(G, prims[j]);
if (G.matrix[m][n]<min)
min = G.matrix[m][n];
}
sum += min;
}
// 打印最小生成树
printf("PRIM(%c)=%d: ", G.vexs[start], sum);
for (i = 0; i < index; i++)
printf("%c ", prims[i]);
printf("\n");
}
Kruskal
复杂度：O(E*logE)
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int from, to, dis;
}edge[10005];//用结构体存储各边
int fa[105];
int fin(int x)//找祖宗的漫漫长路
{
while(x != fa[x]) x = fa[x];
return x;
}
void unionn(int x,int y)//集合的合并
{
int fx = fin(x);
int fy = fin(y);
if(fx != fy) fa[fx] = fy;
//fa[father(y)] = father(x);
}
bool cmp(const node &i, const node &j)
{
return i.dis < j.dis;
}//按照权值从小到大排序各边
int main()
{
int m, n, k = 0, tot = 0;//k为边的计数，tot为最小权值的计数
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].dis);
for(int i = 1; i <= n; i++) fa[i] = i;//将所有点的父结点都初始化为自身
sort(edge + 1, edge + n + 1, cmp);//对边进行排序
int f = 0;
for(int i = 1; i <= m; i++)
{
if(k == n - 1)//n个点则需要n-1条边，当边数为n-1时，树生成完毕
{
f = 1;
break;
}
if(fin(edge[i].from) != fin(edge[i].to))
{
unionn(edge[i].from, edge[i].to);
k++;
tot += edge[i].dis;
}
}
if(f) printf("%d\n", tot);//输出最小生成树对应的权值
else printf("Failed\n");
return 0;
}
// 邻接矩阵
typedef struct _graph
{
char vexs[MAX]; // 顶点集合
int vexnum; // 顶点数
int edgnum; // 边数
int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;
// 边的结构体
typedef struct _EdgeData
{
char start; // 边的起点
char end; // 边的终点
int weight; // 边的权重
}EData;
void kruskal(Graph G)
{
int i,m,n,p1,p2;
int length;
int index = 0; // rets数组的索引
int vends[MAX]={0}; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
EData rets[MAX]; // 结果数组，保存kruskal最小生成树的边
EData *edges; // 图对应的所有边
// 获取"图中所有的边"
edges = get_edges(G);
// 将边按照"权"的大小进行排序(从小到大)
sorted_edges(edges, G.edgnum);
for (i=0; i<G.edgnum; i++){
p1 = get_position(G, edges[i].start); // 获取第i条边的"起点"的序号
p2 = get_position(G, edges[i].end); // 获取第i条边的"终点"的序号
m = get_end(vends, p1); // 获取p1在"已有的最小生成树"中的终点
n = get_end(vends, p2); // 获取p2在"已有的最小生成树"中的终点
// 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
if (m != n){
vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n
rets[index++] = edges[i]; // 保存结果
}
}
free(edges);
// 统计并打印"kruskal最小生成树"的信息
length = 0;
for (i = 0; i < index; i++)
length += rets[i].weight;
printf("Kruskal=%d: ", length);
for (i = 0; i < index; i++)
printf("(%c,%c) ", rets[i].start, rets[i].end);
printf("\n");
}
四、基础数学
在本次集训中，我们其实没有涉及任何一个数学问题，因为数学的学习不是能直接一步到位的，它更多的要依靠大家的积累。
1. 位运算
typedef long long LL;
LL fastPower(LL base, LL power, LL MOD) {
LL res = 1;
while (power > 0) {
if (power & 1) { //此处等价于 if(power % 2 == 1)
res = res * base % MOD;
}
power >>= 1; //此处等价于 power = power / 2
base = (base * base) % MOD;
}
return res;
}
3. 线性素数筛（埃式筛，欧拉筛）
void primes()
{
for(int i = 2; i <= 1e6; i++)
{
if(!st[i]) prime[cnt++] = i;
for(int j = 0; j <= cnt && prime[j] <= 1e6 / i; j++)
{
st[prime[j] * i] = true;
if(!(i % prime[j])) break;
}
}
}
4. 高精度加减乘除
//用高精度求gcd（最大公约数）
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[1000], b[1000], c[1000], s[100], f[1000], s0=0, T;
const int base = 10000;//高精度中用“万进制”存储，常量base是其基数
void Print(int a[])
{
int i, j;
cout << a[a[0]];
for(i = a[0] - 1; i > 0; i--)
for(j = base / 10; j > 0; j /= 10)
cout << a[i] / j % 10;
cout << endl;
}
void Init(int a[])//用“万进制”将数组初始化
{
string s;
cin >> s;
int len = s.length();
for(int i = 0; i < len; i++)
{
int j = (len - i + 3) / 4;
a[j] = a[j] * 10 + s[i] - '0';
}
a[0] = (len + 3) / 4;//记录“万进制”下有几位数
}
//例如:12345678 --> a[0] = 2, a[1] = 5678, a[2] = 1234;
int Comp(int a[], int b[])//高精度数字的大小比较
{
if(a[0] > b[0]) return 1;
if(a[0] < b[0]) return -1;//比较长度
for(int i = a[0]; i >= 1; i--)//从高位开始比较
if(a[i] > b[i]) return 1;
else if(a[i] < b[i]) return -1;
return 0;
}
void Div(int a[], int k)//高精度除以单精度
{
int t = 0;
for(int i = a[0]; i >= 1; i--)
{
t = t * base + a[i];
a[i] = t / k;
t %= k;
}
while(a[a[0]] == 0 && a[0] > 0) a[0]--;//若最高位为零&&还有数
}
void Minus(int a[], int b[])//高精度减法
{
for(int i = 1; i <= a[0]; i++)
{
a[i] -= b[i];
if(a[i] < 0) { a[i + 1]--; a[i] += base; }
}
while(a[a[0]] == 0 && a[0] > 0) a[0]--;
}
void Gcd(int a[], int b[], int t)//利用二进制求大整数的最大公约数
{
if(Comp(a, b) == 0) { T = t; return; }
if(Comp(a, b) < 0) { Gcd(b, a, t); return; }
int ta, tb;
if(a[1] % 2 == 0) { Div(a, 2); ta = 1; }
else ta = 0;
if(b[1] % 2 == 0) { Div(b, 2); tb = 1; }
else tb = 0;
if(ta && tb) Gcd(a, b, t + 1);
else if(! ta && ! tb) { Minus(a, b); Gcd(a, b, t); }
else Gcd(a, b, t);
}
void MulHigh(int a[], int b[])//高精度乘以高精度
{
memset(c, 0, sizeof(c));
for(int i = 1; i <= a[0]; i++)
for(int j = 1; j <= b[0]; j++)
{
c[i + j - 1] += a[i] * b[j];
c[i + j] += c[i + j - 1] / base;
c[i + j - 1] %= base;
}
c[0] = a[0] + b[0];
while(c[c[0]] == 0 && c[0] > 0) c[0]--;
for(int i = 0; i <= c[0]; i++) a[i] = c[i];
}
void MulLow(int a[], int k)//高精度乘以单精度
{
for(int i = 1; i <= a[0]; i++) a[i] *= k;
for(int i = 1; i <= a[0]; i++)
{
a[i + 1] += a[i] / base;
a[i] %= base;
}
while(a[a[0] + 1] > 0)
{
a[0]++;
a[a[0] + 1] = a[a[0]] / base;
a[a[0]] %= base;
}
}
int main()
{
Init(a);
Init(b);
Gcd(a, b, 0);
if(T == 0) Print(a);
else
{
f[0] = f[1] = 1;
for(int i = 1; i <= T; i++) MulLow(f, 2);
MulHigh(f, a);//求出2^T*a[]的值
Print(f);//输出结果
}
return 0;
}
5. 组合数学（鸽巢原理，容斥原理等）
6. 矩阵快速幂
//矩阵
struct Matrix {
static const int N = 15;
static const int MOD = 10000;
static const int n = 2;
LL a[N][N];
//初始化
Matrix(LL e = 0) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
a[i][j] = e * (i == j);
}
}
}
//矩阵乘法
Matrix Multiply(Matrix A, Matrix B) {
Matrix ans(0);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int k = 1; k <= n; k++) {
ans.a[i][j] = (ans.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
}
}
}
return ans;
}
//快速幂
Matrix fastPower(Matrix A, LL power) {
Matrix res(1); //初始化为单位矩阵，任何矩阵与它相乘都等于矩阵本身
while(power > 0) {
if(power & 1) { //此处等价于 if(power % 2 == 1)
res = Multiply(res, A);
}
power >>= 1; //此处等价于 power = power / 2
A = Multiply(A, A);
}
return res;
}
}tet;
7. gcd和lcm和exgcd（扩展欧几里得算法）
gcd和lcm
//计算最大公约数
long long gcd(long long b,long long c) {
return c == 0 ? b : gcd(c, b % c);
}
//计算最小公倍数
long long lcm(long long b,long long c) {
return b * c / gcd(b, c);
}
扩展欧几里得
ax+by=c, d=gcd(a,b), c%d==0则有解，通过gcd求出特解x1,y1。
根据朴素的欧几里德原理有
gcd(a,b)=gcd(b,a mod b);
则: ax1+by1=bx2+(a mod b)y2;
即: ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得： x1=y2; y1=x2-(a/b)*y2;
通解为：
x=c/d*x1+b/d*k
y=c/d*y1-a/d*k
(k为任意整数)
typedef long long LL;
LL ExGCD(LL a, LL b, LL &x, LL &y)
{
// x, y 为引用传参，故最终程序结束后，x,y会被赋值为可行解
if(b == 0)
{
// 递归终点，ax+by=GCD(a,b)的b为0，故方程变为
// ax=a，则可行解可以是 x=1, y=0
x = 1, y = 0;
return a;
}
LL d = ExGCD(b, a % b, x, y), t = x;
x = y, y = t - a / b * x;
return d; // 这里返回值是GCD(a,b)的结果，即最大公约数
}
扩展欧几里得求逆元
了解了扩展欧几里得，我们来看它与乘法逆元的关系。
- 逆元：a 关于 模b 的逆元 整数d 满足
ad mod b ≡ 1 。 - 扩展欧几里得：求方程
ax + by = GCD(a, b)的一组可行解。
逆元的ad mod b ≡ 1，等价于ad - kb = 1，其中 k 为未知整数。
设 d为x，-k为y，则ad - kb = 1转换为ax + by = 1。
求出x就得到了a关于 模b 的逆元。
typedef long long LL;
LL ExGCD(LL a, LL b, LL &x, LL &y)
{
// x, y 为引用传参，故最终程序结束后，x,y会被赋值为可行解
if(b == 0)
{
// 递归终点，ax+by=GCD(a,b)的b为0，故方程变为
// ax=a，则可行解可以是 x=1, y=0
x = 1, y = 0;
return a;
}
LL d = ExGCD(b, a % b, x, y), t = x;
x = y, y = t - a / b * x;
return d; // 这里返回值是GCD(a,b)的结果，即最大公约数
}
int ExGcdInv(int a, int b)
{
int x, y;
ExGCD(a, b, x, y);
return x;
}
8. 费马小定理
如果 p 是一个质数，而整数 a 不是 p 的倍数，则有a ^ (p - 1) ≡ 1(mod p)。
费马小定理求逆元
9. 乘法逆元
如果上面的算法你都掌握，理解并且能够熟练运用，那么恭喜你，你已经完成了基础组部分算法的学习。之后你就可以愉快的进入进阶组学习更有趣的算法了。
进阶篇
进阶篇的算法没有设置任何限制。所以可能涉及算法都会尽量提及。大家也可以按自己的情况来进行学习和练习
一、进阶数据结构
1. 点分治
2. 二叉查找树（Treap，spaly）
3. AC自动机
4. 后缀数组
5. 后缀树和后缀自动机
6. 扩展KMP
7. 回文树
8. A算法和IDA算法
9. 双向BFS
10. AVL树和替罪羊树
11. 红黑树
12. 树链剖分
13. 最近公共祖先（LCA）
14. 树上启发式合并（dsu on tree）
15. 哈夫曼树
16. ST表
17. 主席树
18. 划分树
19. 莫队算法
20. 树套树（线段树套线段树，平衡树套线段树，线段树套平衡树，树状数组套主席树，分块套树状数组）
上面的数据结构几乎囊括了所有竞赛会涉及的数据结构，不管是难度还是数量，都没非常多。大家可以一步步慢慢学习这些数据结构的使用方式
二、进阶动态规划
1. DAG上dp
2. 数位dp
3. 计数dp
4. 动态dp
5. 插头dp
6. 用单调队列或单调栈优化的dp、
7. 斜率优化dp
8. 四边形不等式优化dp
9. 树上dp
三、进阶图论
1. k短路
k短路 = 单源点最短路跑反向边 + 高级搜索A*
A*算法 结合了启发式方法和形式化方法;
启发式方法通过充分利用图给出的信息来动态地做出决定而使搜索次数大大降低;
形式化方法不利用图给出的信息,而仅通过数学的形式分析;
算法思路：
算法通过一个估价函数f(h)来估计图中的当前点p到终点的距离,并由此决定它的搜索方向;
当这条路径失败时,它会尝试其他路径;
对于A*,估价函数=当前值+当前位置到终点的距离,即f(p)=g(p)+h(p),每次扩展估价函数值最小的一个;
对于K短路算法来说,g§为当前从s到p所走的路径的长度;h§为点p到t的最短路的长度;
f§的意义为从s按照当前路径走到p后再走到终点t一共至少要走多远;
为了加速计算,h§需要在A*搜索之前进行预处理，从终点t做一次单源点最短路径就能得到每个点的h§了;
算法步骤：
- 以原终点t为源点,求解t到所有点的最短距离(即：跑一遍最短路);
- 新建一个优先队列,将源点s加入到队列中;
- 从优先级队列中弹出f§距离最小的点p,如果点p就是t,则计算t出队的次数;
如果当前为t的第k次出队,则当前路径的长度就是s到t的第k短路的长度,算法结束;
否则遍历与p相连的所有的边,将扩展出的到p的邻接点信息加入到优先级队列;
模板题
题意
给出一个图和起点、终点、K、时间限制。求第K最短路。模板题，可以用来入门。（注：这个图是单向的）
思路
- 先用SPFA跑一下最短路(反向跑)。
A*的思想用优先队列(限制不跑偏)，跑到第K条路。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int M=1000005;
int pre1[M],pre2[M],cent1,cent2;//链式前向星
ll dis[M],vis[M];//SPFA
int s,e,k,t;//起点、终点、第k条、时间限制
struct A{
int y,len,next;
}a1[M*2],a2[M*2];//链式前向星
struct B{
ll x,t;
B(ll x,ll t):x(x),t(t){}
friend bool operator < (B aa,B bb){
return aa.t+dis[aa.x]>bb.t+dis[bb.x];
//优先队列，限制最小的，且防止跑偏
}
};
void add1(int x,int y,int z)//链式前向星反向记录边
{
a1[cent1].y=y;
a1[cent1].len=z;
a1[cent1].next=pre1[x];
pre1[x]=cent1++;
}
void add2(int x,int y,int z)//链式前向星正向记录边
{
a2[cent2].y=y;
a2[cent2].len=z;
a2[cent2].next=pre2[x];
pre2[x]=cent2++;
}
void SPFA()//SPFS 反向求最短路
{
memset(dis,inf,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int>q;
q.push(e);
dis[e]=0,vis[e]=1;
while(!q.empty())
{
int x=q.front();
q.pop(),vis[x]=0;
for(int i=pre1[x];~i;i=a1[i].next)
{
int y=a1[i].y,len=a1[i].len;
if(dis[y]>dis[x]+len)
{
dis[y]=dis[x]+len;
if(!vis[y])
{
q.push(y);
vis[y]=1;
}
}
}
}
}
ll ASTAR()//A*求第k条边
{
if(dis[s]>=inf)
return -1;
priority_queue <B> q;
B re(s,0);
int num=0;
q.push(re);
while(!q.empty())
{
re=q.top();
q.pop();
if(re.x==e)
{
num++;
if(num==k)//找到第k条路
return re.t;
}
for(int i=pre2[re.x];~i;i=a2[i].next)//进队
{
q.push(B(a2[i].y,a2[i].len+re.t));
}
}
return -1;
}
int main()
{
int m,n;
while(cin>>n>>m)
{
cin>>s>>e>>k>>t;
memset(pre1,-1,sizeof(pre1));
memset(pre2,-1,sizeof(pre2));
cent1=0,cent2=0;
for(int i=0;i<m;i++)//储存图
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add2(x,y,z);//正向
add1(y,x,z);//反向
}
SPFA();
ll ans=ASTAR();
if(ans==-1||ans>t){
puts("Whitesnake!");
}else{
puts("yareyaredawa");
}
}
return 0;
}
2. 强连通分量
- 定义
在有向图G中，如果两个顶点u，ｖ间有一条从ｕ到ｖ的有向路径，同时还有一条从ｖ到ｕ的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OT9hIB8q-1656045369386)(C:\Users\焦智慧\Desktop\1.png)]
图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。
四条边：
树枝边：DFS时经过的边，即DFS搜索树上的边。
前向边：与DFS方向一致，从某个结点指向其某个子孙的边。
后向边：与DFS方向相反，从某个结点指向其某个祖先的边。（返祖边）
横叉边：从某个结点指向搜索树中的另一子树中的某结点的边。
Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。 定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。 由定义可以得出，Low(u)=Min {Low(u), Low(v) } (u,v)为树枝边，u为v的父节点 . Low(u)=Min {Low(u), DFN(v) } DFN(v),(u,v)为指向栈中节点的后向边(指向栈中结点的横叉边) } 当结点u搜索结束后，若DFN(u)=Low(u)时，则以u为根的搜索子树上所有还在栈中的节点是一个强连通分量。
算法过程：
从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wLn11kTg-1656045369388)(C:\Users\焦智慧\Desktop\2.png)]
初始化时Low[u]=DFN[u]=++index
返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JkoT0Gap-1656045369390)(C:\Users\焦智慧\Desktop\3.png)]
返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SwJrRmgb-1656045369391)(C:\Users\焦智慧\Desktop\4.png)]
Low(u)=Min {Low(u), DFN(v) } DFN(v),(u,v)为指向栈中节点的后向边
继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GqrN45gf-1656045369391)(C:\Users\焦智慧\Desktop\5.png)]
至此，算法结束。求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。
void tarjan(int u) //tarjan缩点
{
dfn[u] = low[u] = ++num;
st[++top] = u;
for(int i = fir[u]; i; i = nex[i])
{
int v = to[i];
if(!dfn[v]) //深度优先
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(!co[v]) //判断是否在栈中
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) //退栈
{
co[u] = ++col; //记录第几个集合
++si[col]; //记录集合数量
while(st[top] != u)
{
++si[col];
co[st[top]] = col;
--top;
}
--top;
}
}
- tarjan算法用途
1、有向图的缩点
将同一个强连通分量中的点缩成同一个新结点，对于两个新结点a,b之间有边相连，当且仅当存在两个点u属于a，v属于b。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-APhLZQkg-1656045369392)(C:\Users\焦智慧\Desktop\6.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OBqIYl8z-1656045369392)(C:\Users\焦智慧\Desktop\7.png)]
2、求割点和桥
受欢迎的牛（信息学奥赛一本通 1513）
【题目描述】
每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
【输入】
第一行两个数 N,M；
接下来 M 行，每行两个数 A,B，意思是 A 认为 B 是受欢迎的（给出的信息有可能重复，即有可能出现多个 A,B）。
【输出】
输出被除自己之外的所有牛认为是受欢迎的牛的数量。
【输入样例】
3 3
1 2
2 1
2 3
【输出样例】
1
【提示】
样例说明
只有第三头牛被除自己之外的所有牛认为是受欢迎的。
数据范围：
对于全部数据，1≤N≤104,1≤M≤5×104
#include<bits/stdc++.h>
using namespace std;
const int maxN = 1e4 + 5, maxM = 5e4 + 5;
int to[maxM], nex[maxM], fir[maxN];
int col, num, dfn[maxN], low[maxN], de[maxN], si[maxN];
int tot = 0, co[maxN], n, m, top, st[maxN];
void tarjan(int u) //tarjan缩点
{
dfn[u] = low[u] = ++num;
st[++top] = u;
for(int i = fir[u]; i; i = nex[i])
{
int v = to[i];
if(!dfn[v]) //深度优先
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(!co[v]) //判断是否在栈中
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) //退栈
{
co[u] = ++col; //记录第几个集合
++si[col]; //记录集合数量
while(st[top] != u)
{
++si[col];
co[st[top]] = col;
--top;
}
--top;
}
}
void ins(int x, int y) //添加x到y的边
{
to[++tot] = y;
nex[tot] = fir[x];
fir[x] = tot;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1, x, y; i <= m; i++)
{
scanf("%d%d", &x, &y);
ins(y, x); //反向，题中的统计入读就变成统计出度
}
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i); //缩点
for(int i = 1; i <= n; i++)
for(int j = fir[i]; j; j = nex[j]) //统计入度
if(co[i] != co[to[j]]) de[co[to[j]]]++; //不在一个集合，就统计入度
int ans = 0, u = 0;
for(int i = 1; i <= col; i++)
if(!de[i]) ans = si[i], u++; //记录入度为零的点，有多个则输出0
if(u == 1) printf("%d\n", ans);
else printf("0\n");
return 0;
}
3. 割点和桥
4. 二分图匹配
1） 匈牙利算法
#include <iostream>
using namespace std;
int N, K;
bool edge[501][501], vis[501];
int match[501];
bool path(int u) {
for (int i = 1; i <= N; ++i) {
if (edge[u][i] && !vis[i]) {
vis[i] = true; //i没有匹配后者可以找到另一个与之匹配的点
if (match[i] == -1 || path(match[i])) {
match[i] = u;
return true;
}
}
}
return false;
}
int maxMatch() {
int res = 0;
memset(match, -1, sizeof(match));
for (int i = 1; i <= N; ++i) {
memset(vis, 0, sizeof(vis));
if (path(i))
res++;
}
return res;
}
2） km算法
题目大意：
a[i]表示对手的每个队伍战斗力
p[i]表示打败对手后获得的分数
b[i]表示我方第一种人的战斗力
c[i]表示我方第二种人的战斗力
定义我方一组选手的战斗力为b[i]+c[j]，第一种选手与第二种选手某种顺序两两组队后，与对方进行pk，共有n!种pk顺序，求最大期望×n
题解：
显然求我方b[i]+c[j]的方案，使得期望最大。
考虑两两组队会和对方n个队各pk一场，故贡献即为对方战斗力小于己方的价值
n3预处理b[i]+c[j]的贡献，然后KM求最大带权匹配即可
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
const int maxn = 550;
const int INF = 0x3f3f3f3f;
int n;
long long w[maxn][maxn], fl[maxn], fr[maxn];
long long net[maxn], s[maxn], pre[maxn];
bool vis[maxn];
long long a[maxn], b[maxn], c[maxn], p[maxn];
void bfs(long long k)
{
long long x, y = 0, ty = 0, de;
for(int i = 1; i <= n; i++) pre[i] = 0;
for(int i = 1; i <= n; i++) s[i] = INF;
net[y] = k;
while(1)
{
vis[y] = true;
x = net[y];
de = INF;
for(int i = 1; i <= n; i++)
{
if(!vis[i])
{
if(s[i] > fl[x] + fr[i] - w[x][i])
{
s[i] = fl[x] + fr[i] - w[x][i];
pre[i] = y;
}
if(s[i] < de)
{
de = s[i];
ty = i;
}
}
}
for(int i = 0; i <= n; i++)
{
if(!vis[i]) s[i] -= de;
else
{
fl[net[i]] -= de;
fr[i] += de;
}
}
y = ty;
if(net[y] == -1) break;
}
while(y)
{
net[y] = net[pre[y]];
y = pre[y];
}
}
long long Km()
{
for(int i = 1; i <= n; i++)
{
fl[i] = 0;
fr[i] = 0;
net[i] = -1;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++) vis[j] = false;
bfs(i);
}
long long res = 0;
for(int i = 1; i <= n; i++)
if(net[i] != -1) res += w[net[i]][i];
return res;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1; i <= n; i++) scanf("%lld", &p[i]);
for(int i = 1; i <= n; i++) scanf("%lld", &b[i]);
for(int i = 1; i <= n; i++) scanf("%lld", &c[i]);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
long long sum = 0;
for(int k = 1; k <= n; k++)
if(b[i] + c[j] > a[k]) sum += p[k];
w[i][j] = sum;
}
}
printf("%lld\n", Km());
return 0;
}
5. 2-SAT
6. 基环树
7. 图的着色
图着色问题（Graph Coloring Problem, GCP）又称着色问题，是最著名的NP-完全问题之一。
图的m可着色判定问题
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。
图的m可着色优化问题
若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。
- 图的m可着色判定问题
判定问题采用暴力dfs处理，对于当前的节点cur，其前面的节点已经着色过了，判断cur节点可以使用的颜色即可。如何判断cur节点可以使用的颜色呢？遍历所有颜色，判断当前颜色i和cur周围节点的颜色是不是不一样，如果是的话，那么可行；否则，不可行。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100, M = N * 2;
struct Edge {
int to, next;
} edge[M];
int head[N], color[N], idx = -1;
int n, m, k;// n表示节点个数， m表示颜色个数，k表示数据个数
bool res = false;
void add(int u, int v) {
edge[++idx].to = v;
edge[idx].next = head[u];
head[u] = idx;
}
//判断位置cur是否可以放入颜色i
bool check(int cur, int i) {
for (int j = head[cur]; ~j; j = edge[j].next) {
int son = edge[j].to;
if (color[son] == i) return false;
}
return true;
}
void dfs(int cur) { //cur从0开始计算
if (cur >= n) {
res = true;
return;
}
for (int i = 1; i <= m; i++) {
if (check(cur, i)) {
color[cur] = i;
dfs(cur + 1);
}
}
}
另外上述代码稍加修改就可以计算方案个数。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100, M = N * 2;
struct Edge {
int to, next;
} edge[M];
int head[N], color[N], idx = -1;
int n, m, k;
int res;
void add(int u, int v) {
edge[++idx].to = v;
edge[idx].next = head[u];
head[u] = idx;
}
bool check(int cur, int i) {
for (int j = head[cur]; ~j; j = edge[j].next) {
int son = edge[j].to;
if (color[son] == i) return false;
}
return true;
}
void dfs(int cur) {
if (cur >= n) {
res++;
return;
}
for (int i = 1; i <= m; i++) {
if (check(cur, i)) {
color[cur] = i;
dfs(cur + 1);
color[cur] = 0;
}
}
}
元素=[1,2,3,4,5,6,7,8,9] 互斥=[(1,4),(2,5),(1,5),(5,6),(7,8),(3,9),(2,8),(4,5)]
把元素组成 N 个组, 保证互斥元素不在同一个组里, 并且 N 最小
这个问题实际上就是图的m可着色优化问题。
图的m可着色优化问题首先不难想到通过二分法（加上上述的方法）来做，但是这么做的话时间复杂度过高。可以直接采用dfs来处理。（为了处理简单，使用矩阵存储图）
每次判断当前数cur能不能放入之前的集合中，如果不能放入，那么新开辟一个集合；否则，放入即可。那么关键问题就是判定能否放入之前的集合中？将集合中的每个数存储，然后判断当前数cur和这些数是不是互斥即可。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100;
int cnt[N], num[N][N], g[N][N];//cnt表示每个集合中元素个数，num表示第i个集合中的第j个元素是谁，g表示关系图。
int n, k;// n表示节点个数，k表示数据个数
int res;
//判断第i个集合是不是可以放入cur（也就是i中的元素都不和cur互斥）
bool check(int cur, int i) {
for (int j = cnt[i]; j > 0; --j) {
if (g[num[i][j]][cur]) return false;
}
return true;
}
//将cur放入第s个集合中
void dfs(int cur, int s) { //cur从1开始计算
if (s >= res) return;
if (cur > n) {
res = s;
return ;
}
for (int i = 1; i <= s; i++) {
if (check(cur, i)) {
num[i][++cnt[i]] = cur;
dfs(cur + 1, s);
num[i][cnt[i]--] = 0;
}
}
s++;
num[s][++cnt[s]] = cur;
dfs(cur + 1, s);
num[s][cnt[s]--] = 0;
}
8. 最大流
9. 最小割
10. 费用流
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 200010
using namespace std;
bool vis[MAXN];
int n, m, s, t;
int u, v, c, w;
int cost[MAXN], pre[MAXN], last[MAXN], flow[MAXN];
int maxFlow, minCost;
struct Edge {
int from, to, flow, cost;
}edge[MAXN];
int head[MAXN], num_edge;
queue <int> q;
void addEdge(int from, int to, int flow, int cost) {
edge[++num_edge].from = head[from];
edge[num_edge].to = to;
edge[num_edge].flow = flow;
edge[num_edge].cost = cost;
head[from] = num_edge;
edge[++num_edge].from = head[to];
edge[num_edge].to = from;
edge[num_edge].flow = 0;
edge[num_edge].cost = -cost;
head[to] = num_edge;
}
bool SPFA(int s, int t) {
memset(cost, 0x7f, sizeof(cost));
memset(flow, 0x7f, sizeof(flow));
memset(vis, 0, sizeof(vis));
q.push(s);
vis[s] = 1;
cost[s] = 0;
pre[t] = -1;
while(!q.empty()) {
int now = q.front();
q.pop();
vis[now] = 0;
for(int i = head[now]; i != -1; i = edge[i].from) {
if(edge[i].flow > 0 && cost[edge[i].to] > cost[now] + edge[i].cost) {
cost[edge[i].to] = cost[now] + edge[i].cost;
pre[edge[i].to] = now;
last[edge[i].to] = i;
flow[edge[i].to] = min(flow[now], edge[i].flow);
if(!vis[edge[i].to]) {
vis[edge[i].to] = 1;
q.push(edge[i].to);
}
}
}
}
return pre[t] != -1;
}
void MCMF() {
while(SPFA(s, t)) {
int now = t;
maxFlow += flow[t];
minCost += flow[t] * cost[t];
while(now != s) {
edge[last[now]].flow -= flow[t];
edge[last[now] ^ 1].flow += flow[t];
now = pre[now];
}
}
}
int main() {
int Case = 1;
while(scanf("%d%d", &n, &m) != EOF) {
memset(head, -1, sizeof(head));
num_edge = -1;
maxFlow = 0, minCost = 0;
for(int i = 0; i < m; i++) {
int u, v, d, a;
scanf("%d%d%d%d", &u, &v, &d, &a);
addEdge(u, v, 1, d);
addEdge(u, v, 1, d + a);
}
s = 0, t = n + 1;
addEdge(s, 1, 2, 0);
addEdge(n, t, 2, 0);
MCMF();
printf("Case %d: %d\n", Case++, minCost);
}
return 0;
}
11. 哈密顿图和哈密顿回路
12. 弦图
13. 舞蹈链（Dancing Links X）
精确覆盖模板
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 505;
const int M = MAXN * MAXN; //最大节点数
struct DLX {
int n, m, s; //n行m列，s表示节点数
//Left[]指向左边的元素、Right[]指向右边的元素、Up[]指向上边的元素、Down[]指向下边的元素
//Col[]指向列标元素、Row[]表示当前元素所在的行
int Up[M], Down[M], Left[M], Right[M], Col[M], Row[M];
int Head[MAXN]; //Head[]表示行首指针，当Head[0] = 0时，链表为空
int S[MAXN]; //S[i]表示第i列中的节点数
int ansR, ans[MAXN];//ansR表示答案所包含的行数，ans[]记录答案
//初始化,构建空的十字链表
void pre(int _n, int _m) {
n = _n, m = _m;
for(int i = 0; i <= m; i++) {
//其实对于列首元素而言，并不需要Up、Down指向，这里为了方便就一起写了
Up[i] = i;
Down[i] = i;
Left[i] = i - 1;
Right[i] = i + 1;
Col[i] = i;
Row[i] = 0; //列首元素统一放在第0行
S[i] = 0; //初始时每列节点数清零
}
Left[0] = m;
Right[m] = 0;
s = m; //从m号元素后就表示普通元素
for(int i = 0; i <= n; i++) {
Head[i] = -1;
ans[i] = 0;
}
//memset(Head, -1, sizeof(Head));
//memset(ans, 0, sizeof(ans));
ansR = 0;
}
//在第r行，第c列的位置添加新的节点(注意这里是向下插入、行是前插法)
void Insert(int r, int c) {
s++; //节点数+1
Down[s] = Down[c]; //新节点的下侧指针指向列标元素下边的节点
Up[s] = c; //新节点的上侧指针指向列标元素
Up[Down[c]] = s; //原来在列标元素下边的节点的上侧指针指向新节点
Down[c] = s; //列标元素的下侧指针指向新节点
//新节点位于第r行，第c列
Row[s] = r;
Col[s] = c;
S[c]++; //第c列的节点数+1
//如果插入成该行第一个元素
if(Head[r] < 0) {
Head[r] = s; //该行第一个元素为新节点
//它的Right、Left均没有节点
Right[s] = s;
Left[s] = s;
}
else {
Left[s] = Head[r]; //新节点的左侧指针指向这一行的第一个节点
Right[s] = Right[Head[r]]; //新节点的右侧指针指向这一行第一个节点右边的节点
Left[Right[Head[r]]] = s; //这一行第一个节点右边的节点的左侧指针指向新节点
Right[Head[r]] = s; //这一行的第一个节点的右侧指针指向新节点
}
}
//将某一列及该列上节点所在的行从链表中暂时删掉
void Remove(int c) {
Left[Right[c]] = Left[c]; //第c列右边一列的左侧指针指向第c列的左边一列
Right[Left[c]] = Right[c]; //第c列左边一列的右侧指针指向第c列的右边一列
//对于这一列的每个节点
for(int i = Down[c]; i != c; i = Down[i]) {
//遍历该节点所在行上的所有节点
for(int j = Right[i]; j != i; j = Right[j]) {
//逐一删除节点j
Up[Down[j]] = Up[j]; //在节点j下边的那个节点的上侧指针指向节点j上边的节点
Down[Up[j]] = Down[j]; //在节点j上边的那个节点的下侧指针指向节点j下边的节点
--S[Col[j]]; //节点j所在的那一列的节点数-1
}
}
}
//将 第c列及该列上节点所在的行 重新加入链表
void Resume(int c) {
//对于第c列上的每个节点i
for(int i = Up[c]; i != c; i = Up[i]) {
//遍历节点i所在行的每个节点j
for(int j = Left[i]; j != i; j = Left[j]) {
Down[Up[j]] = j; //节点j上边节点的下侧指针 指向节点j
Up[Down[j]] = j; //节点j下边节点的上侧指针 也指向节点j
++S[Col[j]];
}
}
Right[Left[c]] = c; //第c列左边一列的列标元素 的右侧指针 指向第c列
Left[Right[c]] = c; //第c列右边一列的列标元素 的左侧指针 指向第c列
}
//核心代码，本质是dfs，Deep表示搜索深度
bool Dance(int Deep) {
//当Head.Right == Head本身时 结束
if(Right[0] == 0) {
ansR = Deep;
return true;
}
int c = Right[0]; //获取Head.Right指向的列标元素，作为搜索起点
//下面这个for循环是用来找到当前状态中节点数最少的那一列
for(int i = Right[0]; i != 0; i = Right[i]) //链表常规操作，不断读取当前元素的右侧指向
if(S[i] < S[c]) c = i;
Remove(c); //将选定的这一列从十字双向链表中删掉
//对于这一列的每个节点
for(int i = Down[c]; i != c; i = Down[i]) {
ans[Deep] = Row[i]; //将节点i所在的行记录进答案
//移除所有 与节点i在同一行的节点j们 所在的那一列
for(int j = Right[i]; j != i; j = Right[j])
Remove(Col[j]);
//找到答案，退出
if(Dance(Deep + 1)) return true;
//否则，回溯
for(int j = Left[i]; j != i; j = Left[j])
Resume(Col[j]);
}
Resume(c); //退出搜索前别忘了回溯c的状态
return false;
}
}dlx;
void deal(int n, int m) {
dlx.pre(n, m); //初始化
//读入原矩阵，只存储1的信息
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int x;
scanf("%d", &x);
if(x) dlx.Insert(i, j); //将每个位于(i, j)的1 加到矩阵、链表中
}
}
if(!dlx.Dance(0)) printf("No\n");
else printf("Yes\n");
//要求输出具体答案时：
/*else {
//printf("%d\n", dlx.ansR); //答案包含的行数
int f = 1;
for(int i = 0; i < dlx.ansR; i++) {
if(f) {
f = 0;
printf("%d",dlx.ans[i]);
}
else printf(" %d",dlx.ans[i]);
}
printf("\n");
}*/
}
int main() {
int n, m;
while(scanf("%d%d", &n, &m) != EOF)
deal(n, m);
return 0;
}
重复覆盖模板
//将某一列及该列上所有节点从链表中暂时删掉
void Remove(int c) {
for(int i = Down[c]; i != c; i = Down[i]) {
Left[Right[i]] = Left[i];
Right[Left[i]] = Right[i];
}
}
//将 第c列及该列上所有节点 重新加入链表
void Resume(int c) {
for(int i = Up[c]; i != c; i = Up[i]) {
Left[Right[i]] = Right[Left[i]] = i;
}
}
四、进阶数学
对于进阶数学我们把他分成数学，计算几何，和博弈论
1> 数学部分
1. 线性同余方程
2. 中国剩余定理
要求的数为n， n%x=a， n%y=b， n%z=c，那么，设m, p, q分别为(y,z),(x,z),(x,y)的公倍数，令m%x=1, p%y=1, q%z=1，那么m*a+p*b+q*c就满足n的要求。
POJ 1006
while(scanf("%d%d%d%d", &a, &b, &c, &k), a != -1)
{
i = (5544 * a + 14421 * b + 1288 * c + 21252 - 1 - k) % 21252 + 1;
printf("Case %d: the next triple peak occurs in %d days.\n", ++ ca, i);
}
3. 二次剩余
4. 卢卡斯定理
5. 杜教筛
6. 莫比乌斯反演
8. 原根
9. 拉格朗日插值
10. 快速傅里叶变换
11. 快速数论变换
12. 多项式变化
13. 牛顿迭代
14. 高斯消元
15. 调和
16. 构造
17. 线性规划
18. 多项式求根
19. 母函数
20. 群论
21. 定积分的求解
2> 计算几何部分
1. 点积、叉积
<1.1> 叉积的定义：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k8Ca5XS7-1656045369393)(E:\ACM算法学习笔记\ACM算法汇总\计算几何3.png)]
<1.2> 叉积与有向面积：
2. 坐标离散化
3. 求线段交点
??.1> 两条线段相交的定义：
- 规范相交：两条线段恰有唯一一个不是端点的公共点。
- **非规范相交：**一条线段的一个端点恰在另一条线段上或两条线段部分重合。
??.2> 解析几何求线段规范相交的思路：
- 用两点式写出一般式方程：
Ax + By + C = 0； - 判断方程解的情况：
- 若无解，则为平行（或者三维的异面直线）；
- 若有无穷多解，则两线段共线——非规范相交；
- 若有唯一解，则判断这个交点是否分别在两条线段的内部（非端点），若是则相交，否则不相交。
- 特点：需要进行除法和开根运算，存在较大的浮点误差。
??.3> 计算几何初步：
- 特点：算法简洁，仅限于加、减、乘和比较运算，容易推广到三维甚至高维情形，并将浮点误差降到了最低限度。
- 问题转化——从交点到左右：
- 不难发现，当两条线段规范相交时，每条线段的两个端点都在另一条线段的异侧。
- 将线段的一个端点规定为起点，另一个端点规定为终点，就得到了一条有向线段（向量），从起点向终点看，这条线段就将平面分成了左、右两部分。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RNDb8PDE-1656045369394)(E:\ACM算法学习笔记\ACM算法汇总\计算几何1.png)]
4. 欧式距离，曼哈顿距离，和切比雪夫距离
5. 皮克定理
6. 凸包
7. 扫描线算法
8. 旋转卡壳
9. 平面最近点对
10. 平面几何知识
11. 判断点在线上
bool onSegment(Point Pi, Point Pj, Point Q)
{
if((Q.x - Pi.x) * (Pj.y - Pi.y) == (Pj.x - Pi.x) * (Q.y - Pi.y) //叉乘,保证Q点坐标在pi,pj之间
&& min(Pi.x , Pj.x) <= Q.x && Q.x <= max(Pi.x , Pj.x)
&& min(Pi.y , Pj.y) <= Q.y && Q.y <= max(Pi.y , Pj.y))
return true;
return false;
}
3> 博弈论部分
1. 巴什博奕（Bash Game）：
A和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30。比如第一次报数，A报k个数，那么B报5-k个数，那么B报数之后问题就变为，A和B一块报数，看谁先报到25了，进而变为20,15,10,5，当到5的时候，不管A怎么报数，最后一个数肯定是B报的，可以看出，作为后手的B在个游戏中是不会输的。
原理：如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。也就是把全部数以m+1个为一组分开。我们可以找到这么一个整数x和r，使n=x*（m+1）+r，当(m+1) | n时，也就是r=0时，后手会赢。
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m)
if(n%(m+1)==0) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
return 0;
}
2. 尼姆博弈（Nimm Game）：
尼姆博弈指的是这样一个博弈游戏：有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。取完最后一个为胜！
我们假设有三堆物品用(a,b,c)来表示。我们用（a，b，c）表示某种局势，其中a,b,c分别表示当你选择时每一堆剩余的物品数。
.无论谁面对某种局势时，都必败的话，我们称这种局势为奇异局势。我们先来看奇异局势：
①首先（0，0，0）显然是奇异局势。
②第二种奇异局势是（0，n，n）。因为在这种情况下无论你拿走多少件物品，对方都可以拿走和你一样多的物品，这样你必败
③其次（1，2，3）也是奇异局势。因为无论你怎么拿，对手都可以将它变为（0，n，n）格式。
任何奇异局势(a,b,c)都有a xor b xor c =0。该结论可以推广至若干堆，都是成立的。
如果我们面对的是一个非奇异局势(a,b,c),要如何变为奇异局势呢？假设a < b< c,我们只要将c 变为a xor b,即可,因为有如下的运算结果: a xor b xor (a xor b)=(a xor a) xor (b xor b)=0 xor 0=0.要将c 变为a xor b,只要从c中减去c-(a xor b)即可.
也就是判断a xor b xor c 是否为0，如果为零，则先手必败，否则先手 必胜
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
int n,ans,temp;
while(cin>>n)
{
temp=0;
for(int i=0;i<n;i++)
{
cin>>ans;
temp^=ans;
}
if(temp==0) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
}
return 0;
}
取完最后一个为败！
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int ans=0;
int flag=0;
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
ans^=x;
if(x>1)
flag++;
}
cout<<"ans:"<<ans<<' '<<flag<<endl;
if((ans&&!flag)||(!ans&&flag))//当奇数个1 或 有多个相同的偶数 时先手一定输
printf("Brother\n");
else
printf("John\n");
}
return 0;
}
给出n堆石子，每堆都有相应个数，最后问先手一开始有多少种取子方式能够取得最终的胜利。
其实把异或和算出来，然后用异或和去异或每个堆(因为偶数次异或，相当于抹去了这个值，比如 1^2==3,1^2^2=1，相当于抹去了2)，也就是看这个堆对最终的异或和有没有贡献，若有贡献，则这是一种走法
#include<iostream>
using namespace std;
int a[1005];
int main()
{
int n;
while(cin>>n&&n)
{
int ans=0;
int Count=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
ans^=a[i];
}
for(int i=0;i<n;i++)
{
if((ans^a[i])<a[i])//如果对ans是有贡献
Count++;//如果有 则方法数+1
}
cout<<Count<<endl;
}
}
3. Nim Staircase博奕:
这个问题是尼姆博弈的拓展：游戏开始时有许多硬币任意分布在楼梯上，共n阶楼梯从地面由下向上编号为0到n。游戏者在每次操作时可以将楼梯j(1<=j<=n)上的任意多但至少一个硬币移动到楼梯j-1上。游戏者轮流操作，将最后一枚硬币移至地上（0号）的人获胜。
其实阶梯博弈经过转换可以变为Nim，把所有奇数阶梯看成N堆石子，做nim把石子从奇数堆移动到偶数堆可以理解为拿走石子，就相当于几个奇数堆的石子在做Nim 。假设我们是先手，所给的阶梯石子状态的奇数堆，做Nim先手能必胜，我就按照能赢的步骤将奇数堆的石子移动到偶数堆。如果对手也是移动奇数堆，我们继续移动奇数堆。如果对手将偶数堆的石子移动到了奇数堆，那么我们紧接着将对手所移动的这么多石子从那个奇数堆移动到下面的偶数堆。两次操作后，相当于偶数堆的石子向下移动了几个，而奇数堆依然是原来的样子，即为必胜的状态。就算后手一直在移动偶数堆的石子到奇数堆，我们就一直跟着他将石子继续往下移，保持奇数堆不变。如此做下去，我可以跟着后手把偶数堆的石子移动到0，然后你就不能移动这些石子了。所以整个过程，将偶数堆移动到奇数堆不会影响奇数堆做Nim博弈的过程，整个过程可以抽象为奇数堆的Nim博弈。
结论：将奇数楼层的状态异或，和为0则先手必败，否则先手必胜。
#include<iostream>
#include<cmath>
using namespace std;
int num[100];
int main()
{
int n;
cin>>n;
int temp=0;
for(int i=0;i<n;i++)
{
cin>>num[i];
if(i&1)//奇数堆
temp^=num[i];
}
if(temp)
cout<<"先手必胜"<<endl;
else
cout<<"先手必败"<<endl;
}
4. 威佐夫博弈（Wythoff Game）：
有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜.
直接说结论了，若两堆物品的初始值为(x，y)，且x<y，则另z=y-x；记w=（int)[ ( (sqrt(5)+1) /2 )*z ]；若w=x，则先手必败，否则先手必胜。
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int x,y;
cin>>x>>y;
int z=abs(y-x);
if((int)(((sqrt(5)+1)/2)*z)==min(x,y))
cout<<"后手必胜"<<endl;
else
cout<<"先手必胜"<<endl;
}
5. 斐波那契博弈：
有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。
结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）
#include<iostream>
#include<cmath>
using namespace std;
int f[100];
void Init()//斐波那契数列
{
f[0]=f[1]=1;
for(int i=2;i<=100;i++)
{
f[i]=f[i-1]+f[i-2];
}
}
int main()
{
int n;
cin>>n;
Init();
bool flag=false;
for(int i=0;f[i];i++)
{
if(f[i]==n)
{
flag=true;
break;
}
}
if(flag)
cout<<"后手必胜"<<endl;
else
cout<<"先手必胜"<<endl;
6. k倍动态减法
1.定义： 有一堆物品，共n个，两人轮流取物，先手可取任意件，但不能不取，也不能把物品取完，之后每次取的物品数不能超过上一次的k倍，且至少为1件，取走最后一件物品的人获胜。
和斐波那契博弈一样，只不过拿的不是2倍了，而是一个任意的k倍，当k为2时就是完全的斐波那契博弈了。
2.结论： 我们手动构建一个a数列，若n是该数列中的数时，先手必败，否则后手必败。即该数列是必败态。
#include
#define N 20000005
int a[N], b[N]; // a为数列,b保存a[0...i]能构造出的最大的数
int main()
{
int n, k;
int loop = 0, casei = 1;
scanf("%d",&loop);
while(loop --){
scanf("%d%d",&n,&k);
a[0] = b[0] = 1;
int i = 0, j = 0;
while(n > a[i]){ // 构建数列
i ++;
a[i] = b[i - 1] + 1;
while(a[j + 1] * k < a[i])
j ++;
if(k * a[j] < a[i])
b[i] = b[j] + a[i];
else
b[i] = a[i];
}
printf("Case %d: ", casei ++);
if(n == a[i])
printf("lose\n");
else{
int ans;
while(n){
if(n >= a[i]){ // 构成n的最小的数列中的数字，即为第一次要取的数字
n -= a[i];
ans = a[i];
}
i --;
}
printf("%d\n",ans);
}
}
return 0;
}
7. 公平组合博弈
8. SG函数
在谈SG函数之前，我们先看一下关于有向图游戏的定义。
给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。
事实上我们可以发现任何一个ICG(公平组合游戏)都可以转化成有向图游戏。具体方法为，把每个局面看成图的一个节点，并且从每个局面向能到达的局面连有向边。
然后我们再来了解一下Mex(minimal excludant)运算
Mex wiki
In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name “mex” is shorthand for “minimum excluded” value.
我们这里可以简单点理解，给一个非负整数集合S，mex(S)为求出不属于集合S的最小非负整数的运算。例如mex(0,1,2,4,5)=3、 mex(2,3,5)=0、mex()=0
接着就到了本文的核心，SG函数
SG函数
对于一个给定的有向无环图，定义关于图的每个顶点的SG函数SG如下，SG(x)= mex({ SG(y1) ,SG(y2),…,SG(yk)}) (y是x的后继) 。
我们怎么理解这个函数呢？在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1,y2,…,yk，SG(x)为x的后继节点的SG函数值构成的集合再执行mex运算的结果为该节点x的SG函数值
整个有向图游戏G的SG函数值被定义为有向图游戏起点的SG函数值
有向图游戏的和
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或值
定理
有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0
个人理解：
1.在一个没有出边的节点s上，棋子不能移动，SG(s) = 0 ,对应P局面
2.一个节点k的SG函数值大于0，则其后继节点必有一个节点s的SG函数值等于0，由1得节点s对应P局面，则当前节点k对应的局面为N局面
3.一个节点的后继节点SG函数值均不为0，则该节点的SG函数值为0。可推出若一个局面的后继局面全部为N局面，则当前局面为P局面。
SG函数模板
define MAX 1005
/* 计算从1-n范围内的SG值。
Array(存储可以走的步数，Array[0]表示可以有多少种走法)
Array[]需要从小到大排序 */
/*HDU1847博弈SG函数
1.可选步数为1-m的连续整数，直接取模即可，SG(x) = x % (m+1);
2.可选步数为任意步，SG(x) = x;
3.可选步数为一系列不连续的数，用GetSG(计算) */
int SG[MAX], hash[MAX];
void GetSG(int Array[],int n = MAX-1)
{
memset(SG, 0, sizeof(SG));
for(int i = 0; i <= n; ++i)
{
memset(hash, 0, sizeof(hash));
for(int j = 1; j <= Array[0]; ++j)
{
if(i < Array[j])
break;
hash[SG[i - Array[j]]] = 1;
}
for(int j = 0; j <= n; ++j)
if(!hash[j])
{
SG[i] = j;
break;
}
}
}
上面提到了很多算法，他们基本包括个各种各样的算法，但是在算法竞赛中，不只有这些算法题目要掌握，我们还要学习做一些思维题和构造题。如果大家能全部掌握上面所有算法，相信大家也能取得自己想要的成绩了。希望大家不要停下脚步。加油努力的继续在算法学习的道路上越走越远吧！
|