处理细节

Posted on In

历来不确定的东西

  • ST表

注意细节:

1
2
3
4
5
int t = log(n) / log(2) + 1;
for (j = 1; j <= t; ++ j) for (i = 1; i <= n - (1 << j) + 1; ++ i)
    f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

return max(f[l][k], f[r - (1 << k) + 1][k]);
  • unsigned long long 与 long long

unsigned long long

min: 0

max: \(2^{64} - 1\)

long long

min: \(-2^{63}\)

max: \(2^{63} - 1\)

  • 逆元
1
2
3
4
5
6
7
8
9
10
ifac[1] = 1;
for (i = 2; i < p; ++ i)
    ifac[i] = (p - p / i) * inv[p % i] % p;
四字口诀:减除乘膜

对于阶乘的最常用的:
fac[0] = 1;
for (i = 1; i <= n; ++ i) fac[i] = fac[i - 1] * i % mod;
ifac[n] = ksm(fac[i], mod - 2);
for (i = n - 1; i >= 0; -- i) ifac[i] = ifac[i + 1] * (i + 1) % mod;
  • 直径

树上最长的一段距离.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
inline void bfs(int s)
{
    memset(dis, -1, sizeof dis);
    queue<int>q; int i, x, y;
    dis[s] = 0, q.push(s);
    while (! q.empty())
    {
        x = q.front(); q.pop();
        for (i = head[x]; i; i = nex[i])
        {
            y = ver[i];
            if (dis[y] == -1) continue;
            dis[y] = dis[x] + len[i];
            //树上路径唯一确定
            q.push(y);
        }
    }
    return;
}

bfs(1);
for (i = 1; i <= n; ++ i) if (dis[i] > dis[From]) From = i;
bfs(From);
for (i = 1; i <= n; ++ i) if (dis[i] > dis[To]) To = i;
此时直径的端点就为:From与To
  • 重心

定义:对于树上的每一个点,计算其所有子树中最大的子树节点数,这个值最小的点就是这棵树的重心

性质:以树的重心为根时，所有子树的大小都不超过整棵树大小的一半

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void getroot(int x, int fa)
{
    int i, y;
    f[x] = 0, siz[x] = 1;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (v[y] || y == fa) continue;
        getroot(y, x);
        f[x] = max(f[x], siz[y]);
        siz[x] += siz[y];        
    }
    f[x] = max(f[x], yhm_size - f[x]); //yhm_size为指定大小.
    if (f[x] < f[rt]) rt = x;
    return;
}

getroot(1, 0);
  • 树剖求lca

主要就是少处理dfn.别的和树剖一模一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
inline void dfs1(int x)
{
    int i, y; siz[x] = 1;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (y == fa[x]) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs1(y);
        siz[x] += siz[y];
        if (siz[y] > siz[son[x]]) son[x] = y;
    }
    return;
}

inline void dfs2(int x, int yhm_top)
{
    int i, y; top[x] = yhm_top;
    if (! son[x]) return;
    dfs2(son[x], yhm_top);
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (y == fa[x] || y == son[x]) continue;
        dfs2(y, y);
    }
    return;
}

inline int lca(int x, int y)
{
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;	
}
  • exgcd

式子自己推推就好,主要是这里值的一步步代入.

1
2
3
4
5
6
7
8
9
inline void calc(int a, int b)
{
    if (! b) return (void)(x = 1, y = 0);
    calc(b, a % b);
    int tx = x;
    x = y;
    y = tx - a / b * x;
    return;
}
  • 差分约束与负环

好像有两种建边方式都可以.

我只写一种:

如果\(a - b >= c\),意味着\(a >= b + c\)

所以由b出发连一条向a边,边权为c

然后跑最长路就可以了

判断负环两个细节:

必须在判断vis里面判断

必须判断次数是否大于n

以小k的农场一题为例,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
inline void spfa()
{
    int i, x, y; memset(dis, 0xcf, sizeof dis);
    dis[0] = 0, vis[0] = cishu[0] = 1, q.push(0);

    while (! q.empty())
    {
        x = q.front(); q.pop();
        vis[x] = 0;
        for (i = head[x]; i; i = nex[i])
        {
            y = ver[i];
            if (dis[y] < dis[x] + len[i])
            {
                dis[y] = dis[x] + len[i];
                if (! vis[y])
                {
                    if (++ cishu[y] > n) return (void)(pd = 1);
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
    return;
}

signed main()
{
    int i, a, b, c, opt;
    n = read(), m = read();

    while (m --)
    {
        opt = read(), a = read(), b = read();
        if (opt == 1) c = read(), add_edge(b, a, c);
        if (opt == 2) c = read(), add_edge(a, b, -c);
        if (opt == 3) add_edge(a, b, 0), add_edge(b, a, 0);
    }
    for (i = 1; i <= n; ++ i) add_edge(0, i, 0);

    spfa();

    pd == 1 ? puts("No") : puts("Yes");
    return 0;
}
  • 筛各种东西

首先是筛\(\phi\)

定义:

\[ \phi(i) = \sum_{i=1}^n\gcd(i,n)==1 \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void pres_dou()
{
    int i, j;
    
    v[1] = 1, phi[1] = 1;
    
    for (i = 2; i < N; ++ i)
    {
        if (! v[i]) pri[++ cnt] = i, phi[i] = i - 1;
        for (j = 1; j <= cnt && i * pri[j] < N; ++ j)
        {
            v[i * pri[j]] = 1;
            if (! (i % pri[j]))
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
}

其次是筛\(\mu\)

定义:

\[ \mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void pres_dou()
{
    int i, j; v[1] = 1, mu[1] = 1;
    for (i = 2; i < N; ++ i)
    {
        if (! v[i]) pri[++ cnt] = i, mu[i] = -1;
        for (j = 1; j <= cnt && i * pri[j] < N; ++ j)
        {
            v[i * pri[j]] = 1;
            if (! (i % pri[j]))
            {
                mu[i * pri[j]] = 0;
                break;
            }
            else mu[i * pri[j]] = -mu[i];
        }
    }
}