Dijkstra

s : 起点
c[i] : s 到 i 的最短距离(初始化a[s][i])
a[i][j] : i 到 j 的边长度(初始化MAXN)
b[i] : i 是否为白点(初始化false)
k : 记录可更新点的编号
minn : 记录可更新点的距离

c[s] = 0;                                     // s到s距离为0

for (int i = 1; i < n; ++i) {
    int minn = MAXN;
    int k = 0;
    for (int j = 1; j <= n; ++j) {  //寻找可更新的点
        if ((!b[j]) && (c[j] < minn)) {
            minn = c[j];
            k = j;
        }
    }
    if (!k) break;    //均为白点，退出循环
    b[k] = true;  //标记为白点
    for (int j = 1; j <= n; ++j) {
        if (a[k][j] != MAXN && c[k] + a[k][j] < c[j])  //更新路径
            c[j] = c[k] + a[k][j];
    }
}

SPFA

s : 起点
dis[i] : s 到 i 的最短路径(初始化MAXN)
a[i][j] : i 到 j 之间的边(初始化MAXN)
used[i] : i 是否在队列里(初始化false)
MAXN : INT_MAX

queue<int> q;
q.push(s);
dis[s] = 0;
used[s] = true; 

while (!q.empty()) {
    int x = q.front();	q.pop();

    for (int i = 1; i <= n; ++i) {
        if (a[x][i] != MAXN && dis[x] + a[x][i] < dis[i]) {
            dis[i] = dis[x] + a[x][i];
            if (!used[i]) {
            	q.push(i);
            	used[i] = true;
            }
        }
    }
    
    used[x] = false;
}

③打代码易犯的错误

1.名称
	a)示例: 
		-输入输出文件后缀/文件名写错，如"angle"/"angle.txt"
		-输入输出方式写错("r"、stdin等)
		-文件夹/文件名错误（如"angel/angel.cpp"(正确的是angle/angle.cpp))
		-函数名错误(但可以通过编译解决)
        -叫你输出impossible写成impossilbe
	b)解决:
		-赛前花五分钟写好每个题的框架
		-结束前5分钟检查

2.scanf/printf/cin/cout
	a)示例:
		-格式控制符漏写/错写/多写(如使用#define int long long后,忘记使用%lld);
		-使用ios::sync_with_stdio(false);后还使用printf/scanf;
		-用printf/cout调试时忘记修改
		 如未注释printf("ans = %d\n", ans);
		 如忘删/错删 cout << ans << endl << f[n][m];忘记删除f[n][m]; 
		 如printf("%lld %lld", ans, f[n][m]); 忘记删除%lld和f[n][m];
	b)解决:
		-结束前5分钟每个程序都输一遍样例对一遍 
		-写一个专门用于Debug的函数，写完后删掉/注释掉 
		 （即使忘记删掉函数调用，结束前检查编译时也会报错提醒你） 
3.数据范围
	a)示例:
		-1 <= n <= 1e5;的范围写成f[10000];(这是1e4)
		-打擦边球，256 MB的限制数组开到250 MB左右 (如f[23000][23000]共252MB)
		-二维数组两个维度的边界大小写反了(比如f[1e2][1e5]写成f[1e5][1e2]);
		-未用long long / unsigned long long
	b)解决:
		-结束时检查数据范围
		-做大数据的时候用边界数据(比如1<=n<=100的题测试数据用n=100甚至更多)
		-#define int long long | #define uint unsigned long long | signed main()
4.其它
	a)示例
		-#include错误(所以建议用bits/stdc++.h) 
		-不能使用c++11甚至更高标准的特性(如auto);
		-运算符重载错误(如bool operator<(Node x))没有加const/&修饰
		-下标负数/指针乱指，比如sort传参数的时候前后指针不对
		-STL乱用，比如find/erase等
        -位运算乱用(如<<搞成>>)
	b)解决
		-静态差错(俗称人工检查) 
		-修改本地Dev-C++编译器设置(编译选项>代码生成/优化>代码生成>语言标准(-std)) 
5.提示	
	struct Edge {
		int u, v;
		Edge() {}
		Edge(int x, int y) : u(x), v(y) {}
	}e[10000];
	-结构体尽量使用构造函数初始化，不要用{}初始化，如上面的结构体应该用Edge(u, v)而不是Edge{u, v}
	-函数尽量用inline
    -x % 2 用 x & 1;x /= 2 用 x >>= 1

④快速幂/取余

//递归式
long long binpow(long long a, long long b) {
  if (b == 0) return 1;
  long long res = binpow(a, b / 2);
  if (b % 2)
    return res * res * a;
  else
    return res * res;
}
//非递归式
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
//快速幂取余
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}

⑤GCD/LCM

int gcd(int a, int b) {return b == 0 ? a :gcd(b, a % b);}
int lcm(int a, int b) {return a * b / gcd(a, b);}

⑥欧拉函数

// 小于等于n和n互质的数的个数。
int euler_phi(int n) {
  int m = int(sqrt(n + 0.5));
  int ans = n;
  for (int i = 2; i <= m; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

⑦STL算法

find ：顺序查找。 find(v.begin(), v.end(), value) ，其中 value 为需要查找的值。
find_end ：逆序查找。 find_end(v.begin(), v.end(), value) 。
reverse ：翻转数组、字符串。 reverse(v.begin(), v.end()) 或 reverse(a + begin, a + end) 。
unique ：去除容器中相邻的重复元素。 unique(ForwardIterator first, ForwardIterator last) ，返回值为指向 去重后 容器结尾的迭代器，原容器大小不变。与 sort 结合使用可以实现完整容器去重。
random_shuffle ：随机地打乱数组。 random_shuffle(v.begin(), v.end()) 或 random_shuffle(v + begin, v + end) 。
sort ：排序。 sort(v.begin(), v.end(), cmp) 或 sort(a + begin, a + end, cmp) ，其中 end 是排序的数组最后一个元素的后一位， cmp 为自定义的比较函数。
stable_sort ：稳定排序，用法同 sort() 。
nth_element ：按指定范围进行分类，即找出序列中第 n 大的元素，使其左边均为小于它的数，右边均为大于它的数。 nth_element(v.begin(), v.begin() + mid, v.end(), cmp) 或 nth_element(a + begin, a + begin + mid, a + end, cmp) 。
binary_search ：二分查找。 binary_search(v.begin(), v.end(), value) ，其中 value 为需要查找的值。
merge ：将两个（已排序的）序列合并。 merge(v1.begin(), v1.end(), v2.begin(), v2.end()) 。
lower_bound ：在一个有序序列中进行二分查找，返回指向第一个 大于等于x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。 lower_bound(v.begin(),v.end(),x)。
upper_bound ：在一个有序序列中进行二分查找，返回指向第一个 大于x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。 upper_bound(v.begin(),v.end(),x) 。
next_permutation ：将当前排列更改为 全排列中的下一个排列 。如果当前排列已经是 全排列中的最后一个排列 （元素完全从大到小排列），函数返回 false 并将排列更改为 全排列中的第一个排列 （元素完全从小到大排列）；否则，函数返回 true 。 next_permutation(v.begin(), v.end()) 或 next_permutation(v + begin, v + end) 。
partial_sum ：求前缀和。设源容器为 x ，目标容器为 y ，则令。 partial_sum(src.begin(), src.end(), back_inserter(dst)) 。

⑧迭代器

vector<int> data(10);

for (int i = 0; i < data.size(); i++)
  cout << data[i] << endl;  // 使用下标访问元素

for (vector<int>::iterator iter = data.begin(); iter != data.end(); iter++)
  cout << *iter << endl;  // 使用迭代器访问元素

⑨Vector

resize() 改变 vector 的长度，多退少补。补充元素可以由参数指定。
insert() 支持在某个迭代器位置插入元素、可以插入多个。 复杂度与 pos 距离末尾长度成线性而非常数的
erase() 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。复杂度与 insert 一致。
push_back/pop_back添加/删除元素

⑨Queue

push/pop添加/删除元素

⑩Stack

11 Priority Queue

12 Map

可以直接通过下标访问来进行查询或插入操作。例如 mp["Alan"]=100 。
通过向 map 中插入一个类型为 pair<Key, T> 的值可以达到插入元素的目的，例如 mp.insert(pair<string,int>("Alan",100)); ；
erase(key) 函数会删除键为 key 的所有元素。返回值为删除元素的数量。
erase(pos) : 删除迭代器为 pos 的元素，要求迭代器必须合法。
erase(first,last) : 删除迭代器在范围内的所有元素。
clear() 函数会清空整个容器。

13 Set

insert添加元素
erase(x)删除value = x的元素erase(pos)删除pos迭代器所指元素erase(first, last)删除范围内元素
rbeing()末尾
count(x) 返回 set 内键为 x 的元素数量。
find(x) 在 set 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 end() 。
lower_bound(x) 返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回 end() 。
upper_bound(x) 返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回 end() 。
empty() 返回容器是否为空。
size() 返回容器内元素个数。

笔记

Dijkstra

SPFA

③打代码易犯的错误

④快速幂/取余

⑤GCD/LCM

⑥欧拉函数

⑦STL算法

⑧迭代器

⑨Vector

⑨Queue

⑩Stack

11 Priority Queue

12 Map

13 Set

共 5 条回复