跃迁引擎启动

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

模板

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
namespace manacher{
    char s[maxn << 1] = "##";
    int n, hw[maxn << 1];
    void init(){
        int len = strlen(a);
        for (int i = 0; i < len; i++){
            s[i * 2 + 2] = a[i];
            s[i * 2 + 3] = '#';
        }
        n = len * 2 + 2; s[n] = 0;
    }
    void manacher(){
        int maxr = 0, m = 0;
        for (int i = 1; i < n; i++){
            if (i < maxr) hw[i] = min(hw[m * 2 - i], hw[m] + m - i);
            else hw[i] = 1;
            while (s[i + hw[i]] == s[i - hw[i]]) hw[i]++;
            if (hw[i] + i > maxr){
                m = i; maxr = hw[i] + i;
            }
        }
    }
    int getMax(){
        init(); manacher(); int ans = 1;
        for (int i = 0; i < n; i++) ans = max(ans, hw[i]);
        return ans - 1;
    }
}
阅读全文 »

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

A Golden Plate

随便数数。

B Curiosity Has No Limits

给定两个长度为 $n-1$ 的序列 $a,b$，要求构造一个长度为 $n$ 序列 $t$ 满足一定条件。

显然可以注意到，对于大部分组合解实际上是唯一的，但是会存在一个情况解有多个并且实际上这种情况不会连续出现，因此考虑直接搜。

C Cram Time

将 ${1 \dots t}$ 划分进两个大小分别为 $a,b$ 的集合中。

二分找到最大的 $t$ ，从大到小塞进 $a,b$ 内，显然是肯定可以全部放进去的。

阅读全文 »

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

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$：暴力递归。
阅读全文 »