跃迁引擎启动

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

线段树区间加，区间开根号，区间和查询。

根据吉老师的直播，我们可以感性的认识到在可以接受的时间内，区间开根号会使得区间逐渐相同。

对于一些线段树问题，我们不能一开始就把他当成是线段树，需要首先从全局修改查询的方式去思考。

我们维护区间最大值和区间最小值，在区间开根号操作上如果两者差距小于等于 1，我们进行更新。

此时，区间开根号的问题被转换成区间加和区间覆盖的双标记问题。

阅读全文 »

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

线段树区间取模，区间查询。

维护区间最大值，更新时进行剪枝，如果 $max[l…r] < mod$，那么剪枝不进行更新。

复杂度分析

一个数一旦被修改，那么它的大小至少除以了2。

总的修改次数不超过 nlogn 次。

阅读全文 »

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

A k-Factorization

对 $n$ 质因数分解。

B Odd sum

将所有正偶数加在一起。

排序后从后往前加奇数，判断和是否为奇数，更新最大值。

C Minimal string

预处理 s 串的每个后缀最小值和后缀最小值出现的位置。

遍历 s 串，找到后缀最小值，如果当前中间栈顶小于等于后缀最小值，则压入答案中。

之后将当前位置到后缀最小值全部压入中间栈内。

时间复杂度：$O(n)$。

D Broken BST

对于一棵排序二叉树，每一个节点都有一条从根到当前节点的路径，这条路径决定了一个节点的最大值和最小值，如果这个节点在这个范围内，那么代表他可以通过这颗排序二叉树找到。

dfs遍历这棵树，维护路径上的最大值和最小值即可，用 set 记录可以到达的节点。

时间复杂度：$O(n+n\log(n))$。

E Array Queries

首先注意到一种时间复杂度 $O(n^2)$ 暴力的方法。

第二，注意一种 dp 的方法，时空复杂度均为 $O(n^2)$ 。

但是发现如果 $k > \sqrt{n}$ ，那么第一种暴力的方法只需要 $O(\sqrt{n})$ 的时间。

而对于 $k \le \sqrt{n}$ ，使用第二种 dp 的方法，时空复杂度将为 $O(n\sqrt{n})$。

总体时间复杂度为 $O(n\sqrt{n} + q\sqrt{n})$ 。

阅读全文 »

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

判断条件

无向图

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

如果是欧拉回路，奇点的个数应该为 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;
            }
        }
    }
}