跃迁引擎启动

发表于 分类于 阅读次数：

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int getmin(char* s){
    int n = strlen(s), i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n){
        int t = s[(i + k) % n] - s[(j + k) % n];
        if (!t) k++;
        else {
            if (t > 0) i += k + 1;
            else j += k + 1;
            if (i == j) j++;
            k = 0;
        }
    }
    return min(i, j) + 1;
}

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

模板

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
const int maxn = 5000 + 5;
const int maxm = 100000 + 5;

int head[maxn], tot = 1;
struct edge{
    int to, nxt, flow, cost;
}g[maxm];
void add(int x, int y, int f, int c){
    g[++tot] = edge{y, head[x], f, c};
    head[x] = tot;
    g[++tot] = edge{x, head[y], 0, -c};
    head[y] = tot;
}
void init() {
    ms(head, 0); tot = 1;
}

int vis[maxn], cost[maxn], pre[maxn], flow[maxn], last[maxn], mf, mc;
bool spfa(int s, int t){
    ms(cost, 0x7f); ms(flow, 0x7f); ms(vis, 0);
    queue<int> q; q.push(s); vis[s] = 1; cost[s] = 0; pre[t] = -1;
    while (!q.empty()){
        int now = q.front(); q.pop(); vis[now] = 0;
        for (int i = head[now]; i; i = g[i].nxt){
            int v = g[i].to;
            if (g[i].flow > 0 && cost[v] > cost[now] + g[i].cost){
                cost[v] = cost[now] + g[i].cost;
                pre[v] = now; last[v] = i;
                flow[v] = min(flow[now], g[i].flow);
                if (!vis[v]){
                    vis[v] = 1; q.push(v);
                }
            }
        }
    }
    return pre[t] != -1;
}

int s, t;
void mcmf(){
    mc = mf = 0;
    while (spfa(s, t)){
        int now = t;
        mf += flow[t]; mc += flow[t] * cost[t];
        while (now != s){
            g[last[now]].flow -= flow[t];
            g[last[now] ^ 1].flow += flow[t];
            now = pre[now];
        }
    }
}

dijkstra 优化

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
struct MCMF {
    struct edge {
        int to, flow, cost, rev;
        edge() { }
        edge(int to, int f, int cost, int r): to(to), flow(f), cost(cost), rev(r) { }
    };
    int V, H[maxn + 5], dis[maxn + 5], preV[maxn + 5], preE[maxn + 5];
    vector<edge> G[maxn + 5];
    void init(int n) {
        V = n;
        for (int i = 0; i <= V; ++i) G[i].clear();
    }
    void add(int from, int to, int cap, int cost) {
        G[from].push_back(edge(to, cap, cost, (int)G[to].size()));
        G[to].push_back(edge(from, 0, -cost, (int)G[from].size() - 1));
    }
    int getmin(int s, int t, int f, int& flow) {
        int ans = 0; 
        fill(H, H + 1 + V, 0);
        while (f) {
            priority_queue<PII,vector<PII>,greater<PII> > q;
            fill(dis, dis + 1 + V, inf);
            dis[s] = 0; q.push({0, s});
            while (!q.empty()) {
                PII now = q.top(); q.pop();
                int v = now.second;
                if (dis[v] < now.first) continue;
                for (int i = 0; i < G[v].size(); ++i) {
                    edge& e = G[v][i];
                    if (e.flow > 0 && dis[e.to] > dis[v] + e.cost + H[v] - H[e.to]) {
                        dis[e.to] = dis[v] + e.cost + H[v] - H[e.to];
                        preV[e.to] = v;
                        preE[e.to] = i;
                        q.push({dis[e.to], e.to});
                    }
                }
            }
            if (dis[t] == inf) break;
            for (int i = 0; i <= V; ++i) H[i] += dis[i];
            int d = f;
            for (int v = t; v != s; v = preV[v]) d = min(d, G[preV[v]][preE[v]].flow);
            f -= d; flow += d; ans += d * H[t];
            for (int v = t; v != s; v = preV[v]) {
                edge& e = G[preV[v]][preE[v]];
                e.flow -= d;
                G[v][e.rev].flow += d;
            }
        }
        return ans;
    }
} f;

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

显然如果要把序列弄成 $1,2,3, \dots, n$ 的操作数就是逆序对的数量。

然后我们可以 $O(1)$ 将原答案转移为 $n,1,2,3,\dots,n-1$ ，即其余数操作不变，将最后一个数放到最后的操作数改成放到第一个。

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

阅读全文 »

发表于 分类于 阅读次数：

JSOI2004 平衡点

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
const double delta = 0.998;
const double eps = 1e-15;

int n, x[maxn], y[maxn], w[maxn];
double ansx, ansy, ans = 1e18;

double cal(double a, double b){
    double ans = 0;
    for (int i = 0; i < n; i++){
        double dx = a - x[i], dy = b - y[i];
        ans += sqrt(dx * dx + dy * dy) * w[i];
    }
    return ans;
}

void get(){
    double x = ansx, y = ansy, t = 2000;
    while (t > eps){
        double tx = x + ((rand() << 1) - RAND_MAX) * t;
        double ty = y + ((rand() << 1) - RAND_MAX) * t;
        double now = cal(tx, ty), d = now - ans;
        if (d < 0){
            x = tx; y = ty;
            ansx = tx; ansy = ty; ans = now;
        }
        else if (exp(-d / t) * RAND_MAX > rand()) x = tx, y = ty;
        t *= delta;
    }
}
阅读全文 »

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

模板

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
namespace SA {
    int n, m, sa[maxn], h[maxn], c[maxn], x[maxn], y[maxn];
    void rsort() {
        for (int i = 1; i <= m; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) c[x[i]]++;
        for (int i = 1; i <= m; i++) c[i] += c[i - 1];
        for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
    }
    int cmp(int i, int j, int k) {
        int a = i + k > n ? -1 : y[i + k];
        int b = j + k > n ? -1 : y[j + k];
        return y[i] == y[j] && a == b;
    }
    void build(int nn, char* s) {
        n = nn; m = 255; // important
        for (int i = 1; i <= n; i++) x[i] = s[i], y[i] = i;
        rsort();
        for (int k = 1, p; k <= n; k += k, m = p) {
            p = 0;
            for (int i = n; i > n - k; i--) y[++p] = i;
            for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k;
            rsort(); 
            for (int i = 1; i <= n; i++) swap(x[i], y[i]);
            x[sa[1]] = p = 1;
            for (int i = 2; i <= n; i++) x[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
        }
        for (int i = 1; i <= n; i++) x[sa[i]] = i;
        for (int i = 1, k = 0; i <= n; i++) {
            if (k) k--;
            int j = sa[x[i] - 1];
            while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
            h[x[i]] = k;
        }
    }
}
阅读全文 »

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

KMP

模板1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char s[maxn], p[maxn];
int nxt[maxn];

void getnxt(char *p){
    int len = strlen(p), k = -1, i = 0; nxt[0] = -1;
    while (i < len){
        if (k == -1 || p[k] == p[i]) i++, k++, nxt[i] = k;
        else k = nxt[k];
    }
}
int kmp(char *s, char *p){
    getnxt(p);
    int slen = strlen(s), plen = strlen(p), i = 0, j = 0;
    while (i < slen && j < plen){
        if (j == -1 || s[i] == p[j]) i++, j++;
        else j = nxt[j];
    }
    if (j == plen) return i - j;
    return -1;
}

模板2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void getfail(int len, char* s, int fail[]) {
    fail[1] = 0;
    for (int i = 2; i <= len; i++) {
        int cur = fail[i - 1];
        while (cur > 0 && s[cur + 1] != s[i])
            cur = fail[cur];
        if (s[cur + 1] == s[i])
            ++cur;
        fail[i] = cur;
    }
}
void kmp(char *s, char *p) {
    int slen = strlen(s + 1), plen = strlen(p + 1), cur = 0;
    getfail(plen, p, nxt);
    for (int i = 1; i <= slen; i++) {
        while (cur > 0 && s[i] != p[cur + 1]) cur = nxt[cur];
        if (p[cur + 1] == s[i]) cur++;
        if (cur == plen) {
            printf("%d\n", i - cur + 1);
            cur = nxt[cur];
        }
    }
}

扩展KMP

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
char s[maxn], t[maxn];
int nxt[maxn], extend[maxn];

void getnxt(char *s){
    int n = strlen(s), p = 0, k = 1; nxt[0] = n;
    while (p + 1 < n && s[p] == s[p + 1]) p++;
    nxt[1] = p;
    for (int i = 2; i < n; i++){
        p = k + nxt[k] - 1;
        if (i + nxt[i - k] <= p) nxt[i] = nxt[i - k];
        else {
            int j = max(p - i + 1, 0);
            while (i + j < n && s[i + j] == s[j]) j++;
            nxt[i] = j; k = i;
        }
    }
}
void exkmp(char *t, char *s){ 
    getnxt(s); int tlen = strlen(t), slen = strlen(s), p = 0, k = 0;
    while (p < tlen && p < slen && t[p] == s[p]) p++;
    extend[0] = p;
    for (int i = 1; i < tlen; i++){
        p = k + extend[k] - 1;
        if (i + nxt[i - k] <= p) extend[i] = nxt[i - k];
        else {
            int j = max(p - i + 1, 0);
            while (i + j < tlen && j < slen && t[i + j] == s[j]) j++;
            extend[i] = j; k = 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
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$ 内，显然是肯定可以全部放进去的。

阅读全文 »