跃迁引擎启动

发表于 分类于 阅读次数：

判断条件

无向图

因为欧拉路径中，起点与终点度数为奇数，其它点的度数均为偶数。

如果是欧拉回路，奇点的个数应该为 0。

有向图

欧拉路径中，最多只有两个点的入度不等于出度。起点出度比入度大 1，终点入度比出度大 1。

如果是欧拉回路，所有点的 入度 = 出度 。

Hierholzer算法

1
2
3
4
5
6
7
8
9
void dfs(int u){
    for (int i = 0; i < edge[u].size(); i++){
        int v = edge[u][i];
        if (vis[u][i]) continue;
        vis[u][i] = 1;
        dfs(v);
    }
    ans.push_back(u);
}
阅读全文 »

发表于 更新于 分类于 阅读次数：

倍增LCA

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
int head[maxn], to[maxn * 2], nxt[maxn * 2], d[maxn * 2], tot;
void add(int x, int y, int w){
    to[++tot] = y; nxt[tot] = head[x]; d[tot] = w; head[x] = tot;
}

int n, m;

int dp[maxn][20], dep[maxn], dis[maxn];
void dfs(int u, int fa){
    dp[u][0] = fa; dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if (v == fa) continue;
        dis[v] = dis[u] + d[i];
        dfs(v, u);
    }
}
void init(){
    ms(dp, 0); dep[0] = dis[0] = 0;
    dfs(1, 0); 
    for (int j = 1; j < 20; j++) 
        for (int i = 1; i <= n; i++) 
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int lca(int x, int y){
    if (dep[x] < dep[y]) swap(x, y);
    int tmp = dep[x] - dep[y];
    for (int i = 0; tmp; i++, tmp >>= 1)
        if (tmp & 1) x = dp[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--){
        if (dp[x][i] != dp[y][i]){
            x = dp[x][i]; y = dp[y][i];
        }
    }
    return dp[x][0];
}

树链剖分LCA

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
namespace hld {
    int siz[maxn], dep[maxn], fa[maxn], son[maxn], top[maxn];
    void dfs(int u, int f) {
        dep[u] = dep[f] + 1; fa[u] = f; siz[u] = 1; son[u] = 0;
        int m = -1;
        for (auto& v: edge[u]) {
            if (v == f) continue;
            dfs(v, u);
            siz[u] += siz[v];
            if (siz[v] > m) son[u] = v, m = siz[v];
        }
    }
    void dfs(int u, int f, int tp) {
        top[u] = tp;
        if (!son[u]) return;
        dfs(son[u], u, tp); // !
        for (auto& v: edge[u]) {
            if (v == f || v == son[u]) continue; // !
            dfs(v, u, v);
        }
    }
    void build() {
        dfs(1, 0); dfs(1, 0, 1);
    }
    int qlca(int u, int v) {
        while (top[u] != top[v]){
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            u = fa[top[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }
}

发表于 更新于 分类于 阅读次数：

A In Search of an Easy Problem

模拟。

B Vasya and Cornfield

当 $(x,y)$ 满足 $ d \le x+y \le 2n-d$ 并且 $-d \le y-x\le d$ 时，$(x,y)$ 在矩形内。

C Vasya and Golden Ticket

直接枚举分成了几段，计算每段的值，模拟一下即可。

D Vasya and Triangle

数论构造。

求解方程 $ x \times y = \frac{2nm}{k} $ 的整数解 $(x,y)$ 。

如果 k 模 2 为 0，令 $k = \frac k2$, $ g=\gcd(n,k)$，则 $x=\frac ng$，$y=\frac{m}{\frac kg}$。

如果 k 模 2 为 1，令 $g=\gcd(n,k)$, 则 $x=\frac ng$, $y=\frac{m}{\frac kg}$, 注意到 $x = n$ 或者 $x < \frac n2$, 则可以令 $x = 2x$ 或 $y = 2y$。

E Vasya and Good Sequences

对于原问题，将输入 $a_i$ 转换成一串表示该数二进制表示多少个1，实际上我们要求区间 $[l,r]$ 满足 $2|sum(a[l \dots r])$ 且 $\max(a[l \dots r]) <= \frac 12 sum(a[l \dots r])$ 的方案数。

对于 $a_i \ge 1$，则每个数至少有一位是 1，而位数最多只有60位，那么如果序列长度大于 60，则必然满足第二个条件。

因此对于每个位置，我们预处理他的后缀和为奇数和偶数的数量，那么不考虑第二个条件，左端点为 $l$ 对答案的贡献为 $cnt[i+1][sufSum_i \% 2]$，对于长度小于 60 的后缀，暴力查询即可。

阅读全文 »

发表于 更新于 分类于 阅读次数：

A Little C Loves 3 I

对 $n$ 模 $3$ 分类。

B Cover Points

$ans = \max(x_i+y_i)$。

C Enlarge GCD

线性筛预处理 $1$ ~ $1.5e7$ 所有数的最小因子。

预处理 $a_i/=gcd$，因此答案就是从所有数中取出最多数，使得他们的 $\gcd$ 大于 $1$，也就是某个最小素因子出现次数最多。

阅读全文 »

发表于 更新于 分类于 ， 阅读次数：

A Vasya And Password

统计一下三种字符的个数。

如果每种有多于 $1$ 个字符，将其替换为没出现过的字符。

B Relatively Prime Pairs

显然 $\gcd(i,i+1)=1$，直接输出即可。

C Vasya and Multisets

统计只出现 $1$ 次的数字有哪些，如果有偶数个，对半分配即可。

出现两次的数字要么一人拿一个，要么一个人全拿，不影响答案。

出现次数大于 $2$ 的数字，如果已经可以分配了就全部给一个人即可；如果第一种是奇数个，那么分配一个出现次数大于 $2$ 的。

D Bicolorings

自闭题T^T。

考虑 $dp[i][j][state]$ 表示遍历到第 $i$ 列，有 $j$ 个联通块，第 $i$ 列状态为 $state$ 的方案数。

时间复杂度 $O(nk)=O(n^2)$。

阅读全文 »

发表于 分类于 阅读次数： 
1
2
3
4
5
6
7
8
#ifdef XLor
  #define dbg(args...) do {cout << "debug -> "; err(args);} while (0)
#else
  #define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}

发表于 更新于 分类于 阅读次数： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
namespace sieve{
    const int maxp = 1000000 + 5;
    int vis[maxp], prime[maxp], tot;
    void init(){
        ms(vis, 0);
        for (int i = 2; i < maxp; i++){
            if (!vis[i]) prime[tot++] = i;
            for (int j = 0; j < tot && prime[j] * i < maxp; j++){
                vis[i * prime[j]] = 1;
                if (i % prime[j] == 0) break;
            }
        }
    }
}

发表于 更新于 分类于 阅读次数：

询问最值

1
2
3
4
5
6
7
8
9
10
11
12
int dp[20][maxn];
void build(){
    for (int i = 1; i <= n; i++) dp[0][i] = s[i];
    for (int j = 1; j < 20; j++)
        for (int i = 1; i + (1 << j) <= n + 1; i++)
            dp[j][i] = max(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
}
int rmq(int l, int r){
    // int k = 0; while ((1 << (k + 1)) <= r - l + 1) k++;
    int k = __lg(r - l + 1);
    return max(dp[k][l], dp[k][r - (1 << k) + 1]);
}

询问最值下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dp[20][maxn];
void build() {
    for (int i = 1; i <= n; i++) dp[0][i] = i;
    for (int j = 1; j < 20; j++)
        for (int i = 1; i + (1 << j) <= n + 1; i++) {
            int l = dp[j - 1][i];
            int r = dp[j - 1][i + (1 << (j - 1))];
            if (a[l] > a[r]) dp[j][i] = l;
            else dp[j][i] = r;
        }
}
int qmax(int l, int r) {
    int k = __lg(r - l + 1);
    int x = dp[k][l], y = dp[k][r - (1 << k) + 1];
    if (a[x] > a[y]) return x;
    else return y;
}

发表于 更新于 分类于 ， 阅读次数：

后缀自动机求母串不包含给定串子串的不同子串数量

首先，需要知道求两个串最长公共子串，即维护第二个串的每个前缀与第一个串的最长公共后缀。

对母串建一个 $sam$，所有串在 $sam$ 上面跑，并维护每个 $sam$ 上每个状态与所有的最长公共后缀长度，因此每个状态对答案的贡献为 $len(s) - dep(s)$。

可以理解原来状态的对子串数量的贡献为 $len(s) - len(link(s))$，$s$ 代表的子串长度区间中每个后缀都对答案有贡献，现在我们将这个区间拆成两块更新答案。

具体来讲，在获取所有点的 $dep$ 值后，基数排序获得 $sam$ 的状态的逆序拓扑排序。

因为需要对于每个状态更新他父亲节点的 $dep$ 值，所以遍历逆序拓扑排序。

这里需要同时从自动机和后缀树两个角度同时思考，当前节点的父亲也是当前节点的后缀，但是计算 $dep$ 时是自动机视角，所以当前节点和他的父亲计算的 $dep$ 没有影响，但实际上当前节点 $dep$ 值对他的父亲是有影响的，例如当前 $dep$ 超过了父亲节点的 $len$，父亲节点对答案是没有贡献的。

阅读全文 »

发表于 更新于 分类于 ， 阅读次数：

后缀自动机

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
namespace sam {
    int tot, last, cnt[maxn << 1];
    int len[maxn << 1], link[maxn << 1], ch[maxn << 1][26];
    void clear() { 
        tot = last = 1; ms(ch[1], 0);
    }
    void insert(int c) {
        int cur = ++tot, p = last; 
        ms(ch[cur], 0);
        len[cur] = len[last] + 1; 
        cnt[cur] = 1;
        for (; p && !ch[p][c]; p = link[p]) ch[p][c] = cur;
        if (!p) link[cur] = 1;
        else {
            int q = ch[p][c];
            if (len[p] + 1 == len[q]) link[cur] = q;
            else {
                int nq = ++tot; 
                len[nq] = len[p] + 1; 
                cnt[nq] = 0;
                link[nq] = link[q]; 
                link[q] = link[cur] = nq;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                for (; ch[p][c] == q; p = link[p]) ch[p][c] = nq;
            }
        }
        last = cur;
    }
    int c[maxn << 1], a[maxn << 1];
    void rsort() {
        for (int i = 1; i <= tot; i++) c[i] = 0;
        for (int i = 1; i <= tot; i++) c[len[i]]++;
        for (int i = 1; i <= tot; i++) c[i] += c[i - 1];
        for (int i = 1; i <= tot; i++) a[c[len[i]]--] = i;
    }
}

广义后缀自动机

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
namespace gsam {
    int tot, last, cnt[maxn << 1];
    int len[maxn << 1], link[maxn << 1], ch[maxn << 1][2];
    int insert(int last, int c) {
        int cur = ++tot, p = last; 
        ms(ch[cur], 0);
        len[cur] = len[last] + 1; 
        cnt[cur] = 1;
        for (; p && !ch[p][c]; p = link[p]) ch[p][c] = cur;
        if (!p) link[cur] = 1;
        else {
            int q = ch[p][c];
            if (len[p] + 1 == len[q]) link[cur] = q;
            else {
                int nq = ++tot; 
                len[nq] = len[p] + 1; 
                cnt[nq] = 0;
                link[nq] = link[q]; 
                link[q] = link[cur] = nq;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                for (; ch[p][c] == q; p = link[p]) ch[p][c] = nq;
            }
        } 
        return cur;
    }
    namespace Trie {
        int tot, ch[maxn][2], pos[maxn];
        void clear() {
            tot = 1; ms(ch[1], 0);
        }
        void insert(char* s) {
            int u = 1;
            for (int i = 0; s[i]; i++) {
                int c = s[i] - '0';
                if (!ch[u][c]) {
                    ch[u][c] = ++tot;
                    ms(ch[tot], 0);
                }
                u = ch[u][c];
            }
        }
        void build() {
            queue<int> q; q.push(1);
            pos[1] = 1;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int i = 0; i < 2; i++) {
                    if (!ch[u][i]) continue;
                    int v = ch[u][i];
                    pos[v] = gsam::insert(pos[u], i);
                    q.push(v);
                }
            }
        }
    }
    using Trie::insert;
    using Trie::build;
    void clear() { 
        Trie::clear();
        tot = last = 1;
        ms(ch[1], 0);
    }
}
阅读全文 »