首页 模拟赛

贪心 + 对顶堆, AC自动机 + 树状数组, Tarjan缩点 + 拓扑排序

# A. 「APIO2015」巴邻旁之桥 Palembang Bridges

刚开始的时候没啥思路，然后看到数据范围 k=1k = 1 或 k=2k = 2？！

首先把不需要过河的人都排除掉，然后考虑 k=1k = 1 的情况，那么每一组点对都要经过这个桥，所以就是所有点到这个桥的距离之和，显然中位数是最优的，于是把所有点都存下来求个中位数即可。

再来看 k=2k = 2 的情况，我们可以枚举一个断点，强制令左边的点都从左边的桥走，右边的点都从右边的桥走，所以整个对顶堆快速维护中位数即可。

关于对顶堆维护中位数P1168 中位数

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
88
89
90
#include <bits/stdc++.h>
#define ll long long

using namespace std;

namespace IO{
    inline ll read(){
        ll x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const ll N = 3e5 + 10;
const ll INF = 1e18;
ll m, n;
char op1[5], op2[5];
struct node{
    ll x, y;
    inline bool operator < (const node &b) const{
        return x + y < b.x + b.y;
    }
}per[N];
ll p[N];
ll tot, cnt, ans;
priority_queue <ll> q1, q2;
ll sum1, sum2, s[N];

inline void Push(ll x){
    if(q1.empty() || x <= q1.top()) q1.push(x), sum1 += x;
    else q2.push(-x), sum2 += x;
    if(q2.size() + 1 < q1.size()){
        ll now = q1.top();
        q1.pop(), q2.push(-now);
        sum1 -= now, sum2 += now;
    }
    if(q1.size() + 1 < q2.size()){
        ll now = q2.top();
        q2.pop(), q1.push(-now);
        sum1 -= now, sum2 += now;
    }
}

inline void solve1(){
    sort(p + 1, p + 1 + tot);
    for(ll i = 1; i <= tot; ++i) ans += abs(p[i] - p[cnt]);
    write(ans), puts("");
}

inline void solve2(){
    sort(per + 1, per + 1 + cnt);
    for(ll i = 1; i <= cnt; ++i){
        Push(per[i].x), Push(per[i].y);
        s[i] = sum2 - sum1;
    }
    while(!q1.empty()) q1.pop();
    while(!q2.empty()) q2.pop();
    sum1 = sum2 = 0;
    for(ll i = cnt; i > 0; --i){
        s[i] += sum2 - sum1;
        Push(per[i].x), Push(per[i].y);
    }
    ll mins = INF;
    for(ll i = 1; i <= cnt; ++i) mins = min(mins, s[i]);
    write(ans + mins), puts("");
}

signed main(){
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    m = read(), n = read();
    for(ll i = 1, x, y; i <= n; ++i){
        scanf("%s%lld%s%lld", op1, &x, op2, &y);
        if(op1[0] == op2[0]) {ans += abs(x - y); continue;}
        per[++cnt] = (node){x, y};
        p[++tot] = x, p[++tot] = y, ans++;
    }
    if(!cnt) return write(ans), puts(""), 0;
    if(m == 1) solve1();
    else solve2();
    return 0;
}

# B. 「NOI2011」阿狸的打字机

虽然之前做过一遍，但是不会了 QwQ

# 40pts 暴力

暴力建出 ACAC 自动机，对于每组询问暴力在自动机上跑。

# 60pts 暴力

  • 观察到有许多重复的询问，所以把询问离线下来，按 yy 排序，开个桶一块询问。

  • 建出 ACAC 自动机后，把 failfail 指针倒过来，此时问题就变成了查询 xx 在从根到 yy 这条链中出现了多少次，所以找出 dfsdfs 序，把根到 yy 这条链全都标记为 1（这个操作可以用树状数组解决），然后 xx 暴力往下跳。

# 100pts

感觉上面这种做法已经很优了，为什么还是过不了呢？

很简单，因为有很多串多次插入树状数组，所以同样把询问离线下来，按 yy 排个序，统一处理即可。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x =(x << 3) +(x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
struct node{
    int v, nxt;
} edge[N];
int head[N], cnt;
struct Query{
    int x, y, id, ans;
    inline bool operator < (const Query &b) const{
        return y < b.y;
    }
} q[N << 1];
char s[N];
int n, m;
int trie[N][27], tot;
int fa[N], fail[N], End[N], num[N];
int vis[N][27];
int in[N], out[N], tim;
int c[N], ans[N];
int ql[N], qr[N];

void add(int x, int y){
    edge[++cnt] =(node){y, head[x]};
    head[x] = cnt;
}

void init(){
    scanf("%s", s + 1);
    int now = 0;
    int len = strlen(s + 1);
    for(int i = 1; i <= len; i++){
        if(s[i] >= 'a' && s[i] <= 'z'){
            if(!trie[now][s[i] - 'a']) trie[now][s[i] - 'a'] = ++tot, fa[tot] = now;
            now = trie[now][s[i] - 'a'];
        }
        if(s[i] == 'B') now = fa[now];
        if(s[i] == 'P') End[++n] = now, num[now] = n;
    }
}

void build(){
    queue<int> q;
    for(int i = 0; i < 26; i++)
        if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i = 0; i < 26; i++){
            if(trie[now][i])
                fail[trie[now][i]] = trie[fail[now]][i], q.push(trie[now][i]);
            else trie[now][i] = trie[fail[now]][i];
        }
    }
}

void dfs(int x){
    in[x] = ++tim;
    for(int i = head[x]; i; i = edge[i].nxt) dfs(edge[i].v);
    out[x] = tim;
}

void update(int x, int y){
    for(; x <= tim; x +=(x &(-x))) c[x] += y;
}

int query(int x){
    int res = 0;
    for(; x > 0; x -=(x &(-x))) res += c[x];
    return res;
}

void solve(int x){
    update(in[x], 1);
    if(num[x])
        for(int i = ql[num[x]]; i <= qr[num[x]]; i++)
            q[i].ans = query(out[End[q[i].x]]) - query(in[End[q[i].x]] - 1);
    for(int i = 0; i < 26; i++)
        if(vis[x][i]) solve(vis[x][i]);
    update(in[x], -1);
}

int main(){
    init();
    for(int i = 0; i <= tot; i++)
        for(int j = 0; j < 26; j++)
            vis[i][j] = trie[i][j];
    build();
    for(int i = 1; i <= tot; i++) add(fail[i], i);
    dfs(0);
    scanf("%d", &m);
    for(int i = 1; i <= m; i++) q[i] = (Query){read(), read(), i, 0};
    sort(q + 1, q + 1 + m);
    for(int i = 1, pos = 1; i <= m; i = pos){
        ql[q[i].y] = i;
        while(q[i].y == q[pos].y) pos++;
        qr[q[i].y] = pos - 1;
    }
    solve(0);
    for(int i = 1; i <= m; i++) ans[q[i].id] = q[i].ans;
    for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

# C. 「CEOI2011」Traffic

观察到这么一句话：保证边在交点以外的任何地方不相交。

qwq

（图源自：ppp204巨佬的题解）

然后把中间到不了的点都删掉，剩下的点就是右边一段连续的区间。

因此我们只需要 dfsdfs 一遍跑出它能到达的最高点与最低点，就计算出了答案。

由于会有环，所以 TarjanTarjan 缩点一下。

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
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 3e5 + 10;
const int M = 9e5 + 10;
const int INF = 2e9;
int n, m, A, B;
struct node{
    int x, y, id;
    inline bool operator < (const node &b) const{
        return y > b.y;
    }
}p[N];
vector <int> g[N], G[N];
vector <node> L, R;
int ans[N];
int mx[N], mn[N];

int dfn[N], low[N], tim;
int stk[N], vis[N], top;
int scc[N], cnt;

inline void tarjan(int x){
    dfn[x] = low[x] = ++tim;
    stk[++top] = x, vis[x] = 1;
    if(p[x].x == A) R.push_back(p[x]);
    for(auto y : g[x]){
        if(!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
        else if(vis[y]) low[x] = min(low[x], dfn[y]);
    }
    if(dfn[x] == low[x]){
        int k; cnt++;
        do{
            k = stk[top--];
            vis[k] = 0;
            scc[k] = cnt;
        }while(x != k);
    }
}

inline void dfs(int x){
    if(vis[x]) return;
    vis[x] = 1;
    for(auto y : G[x]){
        dfs(y);
        mx[x] = max(mx[x], mx[y]), mn[x] = min(mn[x], mn[y]);
    }
}

int main(){
    n = read(), m = read(), A = read(), B = read();
    for(int i = 1; i <= n; ++i) p[i] = (node){read(), read(), i};
    for(int i = 1; i <= m; ++i){
        int x = read(), y = read(), k = read();
        g[x].push_back(y);
        if(k == 2) g[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i){
        mx[i] = 0, mn[i] = INF;
        if(!p[i].x){
            L.push_back(p[i]);
            if(!dfn[i]) tarjan(i);
        }
    }
    for(int x = 1; x <= n; ++x)
        for(auto y : g[x])
            if(scc[x] != scc[y]) G[scc[x]].push_back(scc[y]);
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());
    for(auto x : R){
        int now = scc[x.id], res = lower_bound(R.begin(), R.end(), x) - R.begin() + 1;
        mx[now] = max(mx[now], res);
        mn[now] = min(mn[now], res);
    }
    memset(vis, 0, sizeof(vis));
    for(auto u : L){
        dfs(scc[u.id]);
        write(max(mx[scc[u.id]] - mn[scc[u.id]] + 1, 0)), puts("");
    }
    return 0;
}

阅读次数 次