写题小技巧 -- 持续更新

vector数组存图

当边权为1的图可以用vector数组存图

vector<int>	e[100010];
int xx,yy;
for (int i=1;i<=m;++i)//	总共m条边
{
	scanf("%d%d", &xx,&yy);
    a[xx].push_back(yy);
    a[yy].push_back(xx);
}//	图的读入

for (int i=0;i<a[x].size;++i)//对于m节点相连的边的遍历。
{
	int t = a[x][i];
    if (!vis[t])
    	...
}

register 的优化

当在使用循环时，定义循环变量为register int，可以优化常数。

例如:

1
2
3

for (register int i=1; i<=n; ++i) {
    ...
}

lower_bound() 和 upper_bound() 的使用

当寻找数组中一段单调的数列中的某一个数q的位置时，可以直接使用

1	int T = lower_bound(a+1, a+n+1, q) - a;

来寻找或者来使用lower_bound()来寻找第一个大于等于的数的位置，upper_bound() 是寻找第一个大于这个数的位置。

next_permutation() 的使用

这个函数是生成数组中的字典序的下一个序列，会直接在序列上更新。返回一个bool值，如果还有排名更靠后的排列，返回true，否则返回false。使用方法如下：

1
2
3

do {
...
}while (next_permutation(a+1, a+n+1));

unique()

这个函数是用来进行数组的去重，不过好像数组必须是有序的。返回值是一个去重完成后元素的指针。该函数常用来离散化。

比如:

1	int m = unique(a+1, a+n+1) - (a+1);// m值为去重之后数组的个数

距离

关于 OI 中题目中的距离大概有3种 ;

欧氏距离 (两点之间的直线距离)
曼哈顿距离(两个点在标准坐标系上的绝对轴距总和)
切比雪夫距离(各坐标数值差绝对值的最大值)

公式:

dis = sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );//欧氏距离
    
dis = abs (x1 - x2) + abs (y1 - y2);//曼哈顿距离
    
dis = max(abs (x1 - x2), abs (y1 - y2));//切比雪夫距离

注意题中所用的距离是什么.

字符判断函数

一些函数可以判断字符的类型
在C++的STL中有一些可以直接用的字符函数:

isdigit(char ch) // 判断该字符是否为数字
isalpha(char ch) // 判断该字符是否为英文字母（小写字母为2，大写字母为1）。若不是字母，返回0。
isupper(char ch) // 判断该字符是否为大写字母
islower(char ch) // 判断该字符是否为小写字母

大概就是这些.
这些函数来自于\头文件中

greater( ) 函数的使用

关于 greater<int>() 这个函数，它存在于 C++ 的 functional 库中，是一个内置的比较函数，在定义小根堆的时候和在使用sort函数的时候可以见到这个函数的使用：

#include<functional>
using namespace std;
int main() {
    int a[maxn];
    sort(a+1, a+1+n, greater<int>());
    ...
}

以上的代码就是 greater\( ) 的使用，如果在从大到小排序时，就不用再写一个 cmp 函数了

优先队列的使用：

关于优先队列的函数和容器在 C++ 的 \ 库中

有关于小根堆的定义：

1	priority_queue< int, vector< int >, greater< int > >q;

这样就可以完成小根堆的定义。

关于 Struct 的小技巧 <运算符的重载>

在使用 Struct 的时候，可以在结构体中定义一些成员函数，或者重载运算符。
例如：

struct node {
    int id, v1, v2;
    //定义 sum 这个成员函数
    inline int sum() {
        return v1 + v2;
    }
    //重载 < 运算符
    friend bool operator < (node a, node b) {
        return a.v1 < b.v1;
    }//一定注意在 operator 前面加上重载后的类型
}
int main() {
    ...
    sort(a+1, a+n+1);
    int sum = a[1].sum();
    ...
}

关于 max 函数的使用

在题目中有时候会出现要求两值最大的情况，但是如果单纯使用 < 等判断的话会出现一些不可预料的情况。建议直接写 a = max(a, b) 这种形式。而不是if(a > b) a =b 这种形式。避免蜜汁错误。

关于出现数环的情况

一般情况下，对于数成环的情况，我们都不对环上的指针进行特殊处理。而是将数环拆成一个链，在尾部复制一份完全相同的链，这样就避免了环上指针的麻烦的操作了。