常用技巧&写法

Za

1. 将满足某一性质的边长设为1，不满足的设为0，通过求最短路或者维护一个双端队列可以得到两点之间的满足该性质的边的最小值或最大值。
2. 最大值最小/尽可能大/具有二段性的问题可以想想能否用二分。
3. 具有结合律(1 + 1 + 1 + 1 == 1 + 3 == 2 + 2 -> 1 2 4 8)的性质，可以考虑倍增。
4. 使用前缀和的时候，若用到-1，（j - i-1）考虑把所有的下标向后移一位
5. 用Hash直接记不了pair 采用 LL 然后 x * 1e6 + y （看数据大小） 求这个hash值的时候1e6要转LL
6. unsign int scanf("%u", &a), ull -> scanf("%llu", &b)

二分

1. 小数点保留2位一般去4位(即比保留多两位即可)
2. 实数二分[0, 1000], l 取不到 右端点, r 取不到 左端点, 虽然输出保留小数因为精度问题可能看不出来,还是要注意 是取不到的, 有时会有大问题.

卡常

#include <ctime>

int start = clock();

if(clock() - start >= CLOCKS_PER_SEC * 0.9)
{
    cout << ... << endl;
    exit(0);
}

注意

clock()函数很慢， 为了减少clock()的次数（控制在几百次可能），前面加上某个条件减少次数 如 i % 1000000 == 0

使用常量CLOCKS_PER_SEC，因为不同系统下可能常量不同

并查集

不要忘了压缩路径 fa[x] = t;

int get_fa(int x)
{
    if(fa[x] == x) return fa[x];
    int t = get_fa(fa[x]);
    return fa[x] = t;
}

手写循环队列

用到的是[0, N - 1];

int hh = 0, tt = 0;

// 加入
q[tt ++ ] = i;
if (tt == N) tt = 0;
// 弹出
int t = q[hh ++ ];
if (hh == N) hh = 0;

高精度

先写非高精，再改为高精。

void add(LL a[], LL b[])
{
    static LL c[M];
    memset(c, 0, sizeof c);
    for(int i = 0, t = 0; i < M; i ++)
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}
void mul(LL a[], LL b)
{
    static LL c[M];
    memset(c, 0, sizeof c);
    LL t = 0;
    for(int i = 0; i < M; i ++)
    {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}
int cmp(LL a[], LL b[])
{
    for(int i = M - 1; i >= 0; i --)
        if(a[i] > b[i]) return 1;
        else if(a[i] < b[i]) return -1;
    return 0;
}
void print(LL a[])
{
    int k = M - 1;
    while(k && !a[k]) k --;
    while(k >= 0) printf("%lld", a[k --]);
    puts("");
}

图论

1. 符合拓扑序，不管边权正负。
2. 一个的和/另一个的和 max -> 01分数规划 -> 二分一个定值 将不等式整理一下 重新定义点权或边权 再做一遍图论算法
3. 正环（相当于最长路）spfa更新dist方式改变一下即可.

常用技巧&写法

原文：https://www.cnblogs.com/RemnantDreammm/p/14827639.html