跃迁引擎启动

发表于 分类于 阅读次数：

A Elevator or Stairs?

读错题，自闭，还被人插了？

比较一下两种方法的用时，注意开门用时。

B Appending Mex

定义每次操作为选取某些已有元素，添加他们的 $mex$ 到集合最后，判断到第几步发生错误。

每次添加的 $mex$ 值不会超过最大值+1，否则都能构造出来，记录一下最大值即可。

C Candies Distribution

$n$ 个人排成一列，给每个人发糖，已知每个人得到的数量，前缀中有 $l_i$ 个大于它，后缀中有 $r_i$ 个大于它。

实际上，可以发现第 $i$ 个人的糖数是第 $l_i+r_i$ 大，通过 $n-(l_i+r_i)$ 构造出每个人的糖数，$O(n^2)$ 判断是否可行即可。

D Changing Array

给出 $n$ 个 $k$ 位二进制数，允许将其中一些数取反，求最多区间 $[l,r]$ 的数量，使得区间内异或和不为 $0$。

首先，不考虑修改操作，记录每个前缀异或和 $pre_i$，如果有 $m$ 个位置异或和相同，那么这 $\frac{m(m-1)}{2}$ 个端点两两可以组成一个异或和为 $0$ 的段，时间复杂度 $O(n\log n)$。

对于修改操作，考虑一个贪心的算法，我们要尽量让每个前缀异或和的值出现次数尽量少，根据出现次数比较一下是否翻转，记录出一个 $map$ ，按照上方法进行计算。

注意一个细节，长度为 $0$ 的前缀和为 $0$，因为如果 $pre_i=pre_j$，区间 $(i,j]$ 异或和为 0。

阅读全文 »

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

Hash

模板

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
typedef long long ll;
typedef unsigned long long ull;
const int seed = 135;
const int maxn = 1000000 + 10;
const int p1 = 1e9 + 7, p2 = 1e9 + 9;

ull xp1[maxn], xp2[maxn], xp[maxn];
void init() {
    xp1[0] = xp2[0] = xp[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        xp1[i] = xp1[i - 1] * seed % p1;
        xp2[i] = xp2[i - 1] * seed % p2;
        xp[i] = xp[i - 1] * seed;
    }
}

#define ENABLE_DOUBLE_HASH

// index start at 0
ull h[maxn], hl[maxn];
ull Hash(char* s) { 
    int length = strlen(s);
    ull res1 = 0, res2 = 0;
    h[length] = 0;  // ATTENTION!
    for (int j = length - 1; j >= 0; j--) {
    #ifdef ENABLE_DOUBLE_HASH
        res1 = (res1 * seed + s[j]) % p1;
        res2 = (res2 * seed + s[j]) % p2;
        h[j] = (res1 << 32) | res2;
    #else
        res1 = res1 * seed + s[j];
        h[j] = res1;
    #endif
    }
    return h[0];
}

// get hash of s[left...right-1]
ull get(int left, int right) {
    int len = right - left;
#ifdef ENABLE_DOUBLE_HASH
    unsigned int mask32 = ~(0u);
    ull left1 = h[left] >> 32, right1 = h[right] >> 32;
    ull left2 = h[left] & mask32, right2 = h[right] & mask32;
    return (((left1 - right1 * xp1[len] % p1 + p1) % p1) << 32) |
           (((left2 - right2 * xp2[len] % p2 + p2) % p2));
#else
    return h[left] - h[right] * xp[len];
#endif
}

注意：

  1. 第 $n$ 位哈希值置 0，从 $n-1$ 开始逆序计算哈希值。

  2. 获取子串 $[l,r)$ 的哈希值，注意预处理和取模细节。

  3. 注意不要将字符映射到 $0$ 上。

阅读全文 »

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

模板

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
vector<int> edge[maxn], st;
int n, id, dfn[maxn], low[maxn], vis[maxn];
int cnt, bel[maxn], ind[maxn], oud[maxn];

void dfs(int u){
    dfn[u] = low[u] = ++id;
    vis[u] = 1; st.push_back(u);
    for (int i = 0; i < edge[u].size(); i++){
        int v = edge[u][i];
        if (!dfn[v]){
            dfs(v); low[u] = min(low[u], low[v]);
        }
        else if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]){
        cnt++; int t = 0;
        do{
            t = st.back(); st.pop_back();
            bel[t] = cnt;
            vis[t] = 0;
        } while(t != u);
    }
}

void init(){ ms(dfn, 0); ms(vis, 0); st.clear(); cnt = id = 0; }

发表于 分类于 阅读次数：

模板

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
namespace kdt{
    int rt, cmpd;
    struct node{
        int d[2], mx[2], mn[2], l, r, id;
        bool operator<(const node& b)const{
            return d[kdt::cmpd] < b.d[kdt::cmpd];
        }
    }tree[maxn];

    inline void pushup(int u, int v){
        node& a = tree[u], & b = tree[v];
        for (int i = 0; i < 2; i++){
            a.mx[i] = max(a.mx[i], b.mx[i]);
            a.mn[i] = min(a.mn[i], b.mn[i]);
        }
    }
    inline int build(int l, int r, int k){
        int m = l + r >> 1; cmpd = k;
        nth_element(tree + l, tree + m, tree + r + 1);
        node& t = tree[m]; t.l = t.r = 0;
        for (int i = 0; i < 2; i++) t.mx[i] = t.mn[i] = t.d[i];
        if (l != m){
            t.l = build(l, m - 1, k ^ 1);
            pushup(m, t.l);
        }
        if (r != m){
            t.r = build(m + 1, r, k ^ 1);
            pushup(m, t.r);
        }
        return m;
    }

    inline ll sqr(ll x){return x * x;}
    inline ll distance(const node& a, ll x, ll y){
        x -= a.d[0]; y -= a.d[1]; return x * x + y * y;
    }
    inline ll cal(int p, ll x, ll y){ // cut
        ll ans = 0; node& a = tree[p];
        if (x < a.mn[0]) ans += sqr(a.mn[0] - x);
        if (x > a.mx[0]) ans += sqr(a.mx[0] - x);
        if (y < a.mn[1]) ans += sqr(a.mn[1] - y);
        if (y > a.mx[1]) ans += sqr(a.mx[1] - y);
        return ans;
    }
		
  	ll ans, x, y;
    inline void query(int p){
        node& t = tree[p];
        ll d0 = distance(t, x, y), dl = inf, dr = inf;
        if (x == t.d[0] && y == t.d[1]) d0 = inf; //cut
        ans = min(ans, d0);
        if (t.l) dl = cal(t.l, x, y);
        if (t.r) dr = cal(t.r, x, y);
        if (dl < dr){
            if (dl < ans) query(t.l);
            if (dr < ans) query(t.r);
        }
        else {
            if (dr < ans) query(t.r);
            if (dl < ans) query(t.l);
        }
    }
    inline int query(int a, int b){
        x = a; y = b; ans = inf;
        query(rt); return ans;
    }
    
    inline int insert(int x, int y, int p){
        node& t = tree[p]; t.l = t.r = 0;
        t.mx[0] = t.mn[0] = t.d[0] = x;
        t.mx[1] = t.mn[1] = t.d[1] = y;
        int now = rt, k = 0;
        while (true){
            pushup(now, p);
            if (tree[now].d[k] <= tree[p].d[k]){
                if (!tree[now].l) return tree[now].l = p;
                now = tree[now].l;
            }
            else {
                if (!tree[now].r) return tree[now].r = p;
                now = tree[now].r;
            }
            k ^= 1;
        }
        return 0;
    }
}
阅读全文 »

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

A Cashier

给出 $n$ 个顾客的到达时间和服务他需要的时长，保证没有时间没有重叠，要求在总时间 $L$ 中能休息多少次，每次时长为 $a$。

A题就出了一个大锅，有点没睡醒？忘记在第一个顾客之前的时间也可以休息。

B Forgery

判断给定的矩形图形是否可以用一个剪掉中心的 $3\times3$ 图形可重叠的覆盖。

直接对于每个可以进行覆盖的位置覆盖，最后判断是否覆盖完全即可。

C Sequence Transformation

数论乱搞？

给定序列 $1,2,3 \dots n$ ，每次从中间删除一个，并向答案序列中添加原序列中剩余数字的 $\gcd$，要求字典序最大的答案序列。

首先，对于 $n\le3$，样例已经给出。如果 $n>3$，我们注意到由于 $\gcd(i,i+1)=1$，因此一开始会添加很多 $1$，那么要字典序最大显然 $1$ 的个数要最少，所以我们可以保留一个最小的因子，将不包含这个因子的数全部删除，可以发现我们选 $2$ 可以删除最少的数，这时剩下的数字是 $2,4,6 \dots$，且 $\gcd=2$，对于剩下的数字实际上可以除以 $2$，即转化为了原问题。因此，我们可以递归的重复这个过程，直到递归边界 $n\le3$，特判输出即可。

D Nature Reserve

计算几何 + 二分 = 好题。

给定二维平面上的 $n$ 个点，要求一个与x轴相切的最小圆的半径，使得该圆能覆盖所有的点。

显然可以二分半径。

判断条件为是否能够构造出这样一个半径为 $r$ 圆，即是否存在 $a$，使得 $(x_i-a)^2+(y_i-r)^2 \le r^2$ 恒成立。化简得到，不等式对 $a$ 有解满足$\Delta=8ry_i-4y_i^2 \ge 0$ 且 $\max(x_i-\sqrt{2ry_i-y_i^2}) \le \min(x_i+\sqrt{2ry_i-y_i^2})$。

本题还需注意实数上二分的写法。

E Split the Tree

树上二分好题。

给一棵以 $1$ 为根的有根树，现在要求你将树剖分成一些路径，满足每条路径上的点数小于等于 $L$，权值和小于等于 $S$，且路径上的点以此满足父子关系。

显然，每个叶子都必须分别划分进路径内，考虑一个贪心的做法，对任何一个点尽量在满足限制条件下往上爬，如果不尽量往上肯定不如当前的优。

对于每个点，在从根（$L$ 级祖先）到这个节点的路径的前缀和上二分，找到最浅的顶点满足这条路径权值和小于等于 $S$。

计算答案时，因为向上爬的路径是可以重合的，如果一个顶点的所有儿子的剖分路径都不能到达这个顶点，那么这个顶点必须作为一个新的剖分路径。否则，这个顶点在某个儿子的剖分路径内，贪心地取向上爬的最小深度顶点即可。

阅读全文 »

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

对于一类区间最值更新问题，我们可以维护最大值，最大值个数和次大值。

对于最小值更新 x：

  1. $max[l \dots r] \le x$ ：无需更新
  2. $ secondMax[l \dots r] < x < max[l \dots r]$ ：将 $max[l \dots r]$ 覆盖为 x，打标记。
  3. $secondMax[l \dots r] \ge x$：暴力递归。
阅读全文 »

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

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

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

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

我们维护区间最大值和区间最小值，在区间开根号操作上如果两者差距小于等于 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})$ 。

阅读全文 »