跃迁引擎启动

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

询问最值

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);
    }
}
阅读全文 »

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

A Heist

排序得到左右边界，即为原编号的左右边界，减去序列的长度即可。

B Buying a TV Set

求满足 $x_0 \le a, y_0 \le b$ 且 $\frac{x_0}{y_0}=\frac{x}{y}$ 的 $(x_0, y_0)$ 方案数，将 $\frac{x}{y}$ 约分， 答案为 $max(\frac{a}{x}, \frac{b}{y})$。

C Coffee Break

自闭题T^T。

维护一个 set 存放所有咖啡时间点和在原序列中的下标，每次选 set 的第一个元素 $x$ 放在某一天的第一个，之后二分第一个大于等于 $x+d+1$ 的元素放在同一天并将他从 set 中删除，直到没有元素可以放在这一天。

D Glider

注意到这样一个结论：如果我们从 $x+1$ 处下落，当 $x+1$ 位于上升气流外，假如 $x+1$ 处下落经过的气流和 $x$ 处经过的气流相同，那么他们滑翔的距离也相同，但是对于x轴的一个位置，$x+1$ 下落总比 $x$ 下落高一个单位，因此有可能经过 $x$ 未经过的气流，所以 $ans(x+1) \ge ans(x)$ ；同样的，如果 $x+1$ 位于上升气流内，$ans(x+1) \le ans(x)$。因此可以得出，最长距离一定会在某个上升气流的左端点出取到。

考虑枚举每个左端点的答案，如果直接计算显然这是 $O(n^2)$ 。

我们还发现，高度下降只会发生在上升气流之间，落地前必定高度下降 $h$ ，在上升气流之间水平移动 $h$ ，加上在经过的所有上升气流的长度和。因此，预处理上升气流长度的后缀和，上升气流之间距离的后缀和。

假设枚举到第 $i$ 个位置，如果当前高度大于当前间隔后缀和，那么表示可以滑翔到最后一个上升气流之后，那么答案就是 $len(i) + h$；如果当前高度小于等于当前间隔后缀和，我们需要找到从 $i$ 开始多少个连续间隔距离加起来大于等于 $h$，也就是后缀和小于等于 $h-delta(i)$，因为是后缀和所以满足单调性，二分即可。

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

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： 
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
struct Edge {
    int from, to; ll cap, flow;
    Edge(int u, int v, ll c, ll f): from(u), to(v), cap(c), flow(f) {}
};

struct Dinic {
    int n, m, s, t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int dep[maxn], cur[maxn];
    void init(int n) {
        this->n = n;
        for (int i = 0; i <= n; i++) G[i].clear();
        edges.clear();
    }
    void adde(int from, int to, ll cap) {
        edges.emplace_back(from, to, cap, 0);
        edges.emplace_back(to, from, 0, 0);
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    bool bfs() {
        ms(vis, 0); ms(dep, 0);
        queue<int> q; q.push(s);
        dep[s] = 0; vis[s] = 1;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i = 0; i < G[x].size(); i++) {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    dep[e.to] = dep[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    ll dfs(int x, ll a) {
        if (x == t || a == 0) return a;
        ll flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); i++) { 
            //从上次考虑的弧
            Edge& e = edges[G[x][i]];
            if (dep[x] + 1 == dep[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }
    ll get(int s, int t) {
        this->s = s, this->t = t;
        ll flow = 0;
        while (bfs()) {
            ms(cur, 0);
            flow += dfs(s, inf);
        }
        return flow;
    }
} f;
阅读全文 »

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

A Packets

将n枚硬币分成几块，要求能够每次拿出几块组成任意1到n的整数，块数最小。

考虑多重背包的二进制优化，计算n的二进制位数即可。

B Reach Median

给一个序列，每次对一个数加1或减1，求使得中位数等于x的最小操作数。

将原序列排序，二分找到第一个大于x的位置，如果在中位数后则这一部分全部加成中位数，反之亦然。

C Equalize

给两个01串，对第一个串操作，交换两个位置，花费是下标之差的绝对值，翻转一个位置，花费是1。

显然除非两个错误位置时相邻的不同数，否则都使用翻转操作。

将原序列处理成一个012序列，0表示位置正确，12表示错误，1表示错位的是0，2表示错位的是1。

第一遍扫一下这个序列，把相邻的12取出来，第二遍扫一下这个序列加上剩余的12个数。

D Valid BFS?

给一棵树，判断给的序列是否为合法的BFS序列。

合法BFS序列第一个一定是1，然后直接遍历给定的序列。

记录一下每次遍历的一个点时，他的子节点的位置应该在哪。

使用set对比真正的子节点和序列中的子节点。

更新子节点位置，也就是加上当前点的子节点个数。

E Trips

n个人，m天，每天加一条边，询问一次，当天加边之后，在图中选取一个子图，这些点度数都大于k，输出这个子图的最大大小。

先考虑一个静态的问题，m条边全部给定，那么考虑迭代，直到图上剩余点度数都大于等于k，每次迭代将所有度数小于k的点删除，连接他的边也删除。

优化一下迭代过程，考虑维护一个队列，记录所有度数小于k的点，遍历这个队列，每次遍历到一个点时进行删点和删边，如果使得一个点度数恰好小于k就入队（防止重复入队）。

回到原题，可以反过来处理，变加边为删边，建好整个图之后，每次当天加的边没有删除，就把他删除。

算法复杂度来源于第一次遍历原图。

阅读全文 »

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

原题：codeforces867E

不考虑每天实际是否持有股票。

使用一个最小堆，维护每天可能会买进的股票价格，扫一遍整个序列，如果当前的股票价格大于堆顶的价格，那么我们可以买入这个股票，相当于更新最终答案ans，弹出堆顶。

再将新的价格入两次堆，第一次入堆代表卖出的是当前可以买入的，如果后面在购买这支股票，考虑股价之间的差值，使当前股票变为一个中转站，并不会影响最终答案。第二次入堆代表的是购买当前的股票，前一次入堆实际上只是一次中转，并没有实际在此处购买。

两次入堆之间不会相互影响，如果当前入堆的两个后来被卖出了，那么第一次相当于在这个位置做了中转，第二次又买了这个位置则是忽略了那次中转进行再次卖出。

对于记录操作的次数，对于每次买进操作都会对应一个卖出操作，为节点增加一个维度，表示是否是中转站，对于每次真实的买进都会更新操作数量。

阅读全文 »

发表于 更新于 分类于 阅读次数： 
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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ms(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;

int n;

int a[maxn], cnt = 1;
void mul(int k){
    int g = 0, tmp = 0;
    for (int j = 0; j < cnt; j++){
        tmp = a[j] * k + g;
        a[j] = tmp % 10000;
        g = tmp / 10000;
    }
    while (g){
        a[cnt++] = g % 10000;
        g /= 10000;
    }
}
void print(){
    printf("%d", a[cnt - 1]);
    for (int i = cnt - 2; i >= 0; i--){
        printf("%04d", a[i]);
    }
    puts("");
}

int main(){
    int T; scanf("%d", &T);
    while (T--){
        scanf("%d", &n);
        a[0] = 1; cnt = 1; // init
        for (int i = 1; i <= n; i++){
            mul(2);
        }
        print();
    }
    return 0;
}

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

HDu6435 CSGO

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
const ll inf = 1ll << 62;
const int maxn = 100000 + 5;

int n, m, k;
ll x[maxn][5], y[maxn][5], a[maxn], b[maxn];

int main(){
    int T; scanf("%d", &T);
    while (T--){
        scanf("%d%d%d", &n, &m, &k);
        int ss = 1 << k;
        for (int i = 0; i < n; i++){
            scanf("%lld", &a[i]);
            for (int j = 0; j < k; j++){
                scanf("%lld", &x[i][j]);
            }
        }
        for (int i = 0; i < m; i++){
            scanf("%lld", &b[i]);
            for (int j = 0; j < k; j++){
                scanf("%lld", &y[i][j]);
            }
        }

        ll ans = -inf;
        for (int s = 0; s < ss; s++){
            ll ma = -inf, mi = inf;
            for (int i = 0; i < n; i++){
                ll t = 0;
                for (int j = 0; j < k; j++){
                    if (s & (1 << j)) t += x[i][j];
                    else t -= x[i][j];
                }
                ma = max(1ll * a[i] + t, ma);
            }
            for (int i = 0; i < m; i++){
                ll t = 0;
                for (int j = 0; j < k; j++){
                    if (s & (1 << j)) t += y[i][j];
                    else t -= y[i][j];
                }
                mi = min(-1ll * b[i] + t, mi);
            }
            ans = max(ans, ma - mi);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

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

维护一串线段树 + 线段树合并。

首先，注意到小于1e5的整数最多只有100多个因子。

那么我们先预处理小于1e5的所有整数的因子。

对于每个输入的权值，将他的所有因子插入到第i颗线段树上，线段树本身里面没有维护任何值，只是维护了左右儿子的存在性。

之后，我们从后往前扫描整个数组，因为从后面开始的由于输入格式一定是叶子结点，对于每个节点将以他为根的线段树合并到父亲节点上。

合并时，将当前父节点的答案更新为最大值。

合并的意义在于，以他为lca的节点的所有因子合并在一起，并找到最大相同因子。

阅读全文 »