跳转至

JOISC2016 做题记录

感谢 lgswdn 的推荐。

据说 JOISC2016 相对要阳间一点，有部分分，难度也挺合适。

一年 JOISC 十二个题，先做着，ABC F 确实有点没啥营养了，但是 LOJ 上似乎只有十一道。

LOJ2729「JOISC 2016 Day 1」俄罗斯套娃ψ(｀∇´)ψ

最初思路

首先不难想到使用图论关系来代表嵌套。

换句话说考虑连边，具体方式是两维度都严格偏序才能连边，为了方便理解放到直角坐标系上。

单次询问实际上是求 DAG 上的最小链划分，暴力的话直接求独立集就可以 \(O(n^3)\) 做。

然后考虑到 Dilworth 定理，偏序集上的最小链划分等价于最长反链，这个最长反链就是向右向下的一条最长路径（左上到右下，因为正常边是左下到忧上），于是这个就是一个类 LIS 问题。

于是要处理一堆询问，考虑离线批量处理贡献。

然后一个询问的答案就是这个询问内的反链最大值，但这里注意是 \(\ge A, \le B\)，我开始以为是 \(\le A, \le B\) 变成区间 LIS 了，海草，哈哈。

于是我们可以直接从大往小扫描 \(x\)，每次加入一堆新点，这个反链相当于二维数点，我们扫描线已经维护了一维，另一维树状数组维护即可，询问的贡献直接挂在树状数组维护那一维上面就好，当然也可以直接二分。

题解

上面已经说了

Code 
 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
// author : black_trees
// make yourself an idiot.

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define Enonya
#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

const int si = 2e5 + 10;

struct Node {
    int x, y, id;
    friend bool operator < (Node a, Node b) {
        if(a.x != b.x) return a.x > b.x;
        return a.y < b.y;
    }
} a[si], b[si];

int n, q;
int las, top, ans[si], stk[si];

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i].x >> a[i].y;
    }
    for(int i = 1; i <= q; ++i) {
        cin >> b[i].x >> b[i].y, b[i].id = i;
    }

    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    las = 1;
    for(int i = 1; i <= n; ++i) {
        int id = upper_bound(stk + 1, stk + top + 1, a[i].y) - stk;
        top = max(top, id), stk[id] = a[i].y;
        while(b[las].x > a[i].x) ++las;
        while(b[las].x > a[i + 1].x) {
            ans[b[las].id] = upper_bound(stk + 1, stk + top + 1, b[las].y) - stk - 1, ++las;
        }
    }

    for(int i = 1; i <= q; ++i) cout << ans[i] << endl;

    return 0;
}

算是一个 Dilworth 定理的经典应用吧。

LOJ2730「JOISC 2016 Day 1」神经衰弱ψ(｀∇´)ψ

最初思路

这什么够吧提，第一眼是一点思路都没有。

先考虑一下前两个 subtask 吧，这样才比较符合 OI 的感觉。

\(P_i = i\) 的话，那么返回的一定是实际数字小的那一个。

所以我从 \(1\) 开始，每次问后面的，我可以知道 \(1\) 应该在哪个位置（个数）

问 \(2N - 1\) 次，可以知道 \(1\) 的值（就是所有 Flip 返回值的众数，如果所有都一样那么说明是 \(n - 1\)），并知道比它大的那些数的值。

于是我会最坏 \(O(n^2)\) 做完这个过程，只能拿到 subtask1。

题解

不妨考虑比较简单的情况，如果说有两次不同的 \(\texttt{Flip}(i, j)\) 操作。

它们的结果是一样的，那么这说明这四个位置当中一定有两个是相同的。

我们尝试把这两个找出来，具体做法是这里还有三对关系没问，全部问了，就能找到这两个位置。

我们考察这种情况会怎么出现，考虑最小的那一对元素，如果它们没被归到一起，那么一定存在这样的一个位置。

否则我们递归找次小的，如果还是没有说明早就已经配对好了。

于是这说明不管什么情况下按照这样做都是能够继续下去的，于是每次确定完之后给剩下两个重新配对，重复一次寻找这个的过程。

可以发现询问次数不超过 \(5n\)，可以通过本题。

Code 
 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
// author : black_trees

#include "Memory2_lib.h"
#include "bits/stdc++.h"

using namespace std;

const int si = 1e2 + 10;

int vis[si], a[si];
int f[si][si], ans[si], del[si];
std::pair<int, int> p[si], g[si], h[si];

int ask(int i, int j) {
    if(i > j) swap(i, j);
    if(~f[i][j]) return f[i][j];
    return f[i][j] = Flip(i, j);
}

void Solve(int T, int N) {
    int n = N;
    memset(f, -1, sizeof f);

    for(int i = 0; i < n; ++i) p[i] = make_pair(i, i + n);
    for(int t = 0; t < n; ++t) {
        for(int i = 0; i < n; ++i) vis[i] = -1;
        bool ff = false;
        for(int i = 0; i < n; ++i) {
            if(del[i]) continue;
            int x = ask(p[i].first, p[i].second);
            if(~vis[x]) {
                auto [xa, ya] = g[x];
                auto [xb, yb] = p[i];
                if(ask(xa, xb) != x) ans[ya] = ans[yb] = x, p[i] = make_pair(xa, xb);
                else if(ask(ya, yb) != x) ans[xa] = ans[xb] = x, p[i] = make_pair(ya, yb);
                else if(ask(xa, yb) != x) ans[ya] = ans[xb] = x, p[i] = make_pair(xa, yb);
                else ans[xa] = ans[yb] = x, p[i] = make_pair(ya, xb);
                del[vis[x]] = 1, ff = true;
                break;
            }
            g[x] = p[i], vis[x] = i;
        }
        if(!ff) {
            for(int i = 0; i < n; ++i) {
                if(del[i]) continue;
                auto [x, y] = p[i];
                ans[x] = ans[y] = ask(x, y);
            }
            break;
        }
    }

    for(int i = 0; i < n * 2; ++i) {
        if(!h[ans[i]].first) h[ans[i]].first = i;
        else h[ans[i]].second = i;
    }

    for(int i = 0; i < n; ++i) Answer(h[i].first, h[i].second, i);

    return;
}

这种考虑某种较小局面，尝试说明决策（去掉）该局面后，整体局面仍然能找出这种较小局面进行决策。

也是一种考虑问题的好办法；也说不上是阶段，但是有点“思考的阶段”的感觉，也不太好形容，反正要记住这种感觉，因为之前觉得不自然。

LOJ2731「JOISC 2016 Day 1」棋盘游戏ψ(｀∇´)ψ

最初思路
题解
Code

LOJ2732「JOISC 2016 Day 2」雇佣计划ψ(｀∇´)ψ

最初思路

先考虑一下静态版本的问题怎么做吧。

就是只有 \(T_j = 1\) 的操作。

这个数连通块看起来很不可做啊，感觉上个数级别是 \(O(n)\) 的。

不会，g 了。

题解

很巧妙的思路啊……

考虑其实可以转化为数 \(a_{i - 1} \le B \le a_{i}\) 的 \(i\) 的个数。

1

就是如果没能构成连通块，我们把中间的 gap 称作沟壑（这个说法来自link）

开头和结尾也算上，于是答案就是沟壑的数量 -1，这是显然的，于是问题转化为求这些个沟壑的数量，那么就转化为了求上面那个东西个数的一半，满足条件的位置已经画出来了。

静态问题就是考虑直接扫一遍所有 \(i\)，给可以更新的 \(ans\) 做一个加法，这相当于是直接对于值域上的每个位置，直接维护这个位置的答案，然后单点修改就是一个值域上的区间加。

那么就是一个区间加单点查值，BIT 维护即可，这种直接“维护答案”的东西在做 Ds 题的时候一定不要考虑漏了。

Code 
  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
// author : black_trees
// make yourself an idiot.

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define Enonya
#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

const int si = 2e5 + 10;

class Fenwick {
    private:
        int t[si << 2], V;
        int lowbit(int x) { return x & -x; }
    public:
        void init(int n) {
            for(int i = 0; i <= n; ++i) 
                t[i] = 0;
            V = n;
        }
        void add(int x, int v) {
            while(x <= V) {
                t[x] += v;
                x += lowbit(x);
            }
        }
        int ask(int x) {
            int ret = 0;
            while(x) {
                ret += t[x];
                x -= lowbit(x);
            }
            return ret;
        }
} tc, te; // init, modify

int n, m;
int op[si], a[si], b[si], c[si];
std::vector<int> v;

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m;  
    for(int i = 1; i <= n; ++i) {
        cin >> c[i], v.push_back(c[i]);
    }
    for(int i = 1; i <= m; ++i) {
        cin >> op[i];
        if(op[i] == 1) {
            cin >> a[i];
            v.push_back(a[i]);
        }
        else {
            cin >> a[i] >> b[i];
            v.push_back(b[i]);
        }
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    int k = (int)v.size();
    tc.init(k), te.init(k);

    for(int i = 1; i <= n; ++i)  {
        c[i] = lower_bound(v.begin(), v.end(), c[i]) - v.begin() + 1;
    }

    for(int i = 1; i <= m; ++i) {
        if(op[i] == 1) a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        if(op[i] == 2) b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin() + 1;
    }

    auto upd = [&](int x, int v) -> void {
        te.add(min(c[x], c[x + 1]), v);
    };

    for(int i = 1; i <= n; ++i) tc.add(c[i], 1);
    for(int i = 1; i <= n - 1; ++i) upd(i, 1);

    for(int i = 1; i <= m; ++i) {
        if(op[i] == 1) {
            int ans = 0;
            ans += tc.ask(k) - tc.ask(a[i] - 1);
            ans -= te.ask(k) - te.ask(a[i] - 1);
            cout << ans << endl;
        }
        else {
            if(a[i] < n) upd(a[i], -1);
            if(a[i] > 1) upd(a[i] - 1, -1);
            tc.add(c[a[i]], -1), c[a[i]] = b[i], tc.add(c[a[i]], 1);
            if(a[i] < n) upd(a[i], 1);
            if(a[i] > 1) upd(a[i] - 1, 1);
        }
    }

    return 0;
}

比较值得总结的就是这个维护 gap 的想法，对于连续段来说是不是会比较有用。

LOJ2733「JOISC 2016 Day 2」三明治ψ(｀∇´)ψ

最初思路

看起来很吓人，不过没关系，先想一想。

手玩了一下，整个矩阵主对角线上两个端点被副对角线切割，或者是副对角线上两个端点被主对角线切割才行。

然后求的是每个位置最小，并不是问某种方案下最小。

所以肯定有多个起始点。

并且输出除了 -1 都应当是一个偶数，你吃了一半显然会尝试把另一半也吃了，这样一定不劣。

是不是可能要一层一层剥掉这样的？

因为外面一层没被吃显然被包裹的里层是没法被吃的。

然后考虑最外面这层，发现从一个端点开始，能够扩展的一定是和端点切割方式相同的。

然后 argue 一下里面这层的端点什么时候裸露出来可以开吃。

如果被同一个切割情况围住两个直角边，并且这里裸露的时候可以吃，那么应该是这样的：

1
2
2 4
4 x

x 这个位置被吃需要至少 8 步。

因为实际吃法是：

1
2
2 4
6 8

所以按照这种方式向内扩展就是 +4.

如果是分割情况不一样的？

1
2
2  4
10 x

其中 10 是从下面来的。

那么一种实际操作就是，先吃完 2 4。

然后从下面再多走 10 步，再 +2

那么就是 16 步。

这么做应该是没问题的，这两个也可以归类为，两边之和 +- 2，如果是重合起点就-2，否则+2

于是从四个端点向里面扩展，每个端点我只扩展当前层，O(n) 个。

复杂度就是 \(O(n^2)\) 的。

这给 400？？真的吗！？？？

算了还是不看代码题解当口胡了，先写一下。

这样一定最优吗。

哦还有种情况：

1
2
NZ
Zx

哦哦没事，这个实际上也只能是同起点。

写完了。

诶诶，好像还是不太对，每次扩展完可能出现的新的端点是不是没处理到啊啊。

晕了。

题解

我的最初思路里面是正着做的，错了的原因是，我实际上只考虑了正方形的那种情况。

如果不是正方形，那么在我的做法里没有被标记为四个顶点的点也可能成为顶点，但是这么来看还是可以做，不过会很麻烦。

更常见一点的做法是考虑反着做，其实也很自然，但是在我陷进上面那个最初思路的时候很难想到，近期会对这类思维上的问题做个总结。

首先最初思路里说的每次一定连着吃完大块里的两个小块这个是没问题的，我们可以发现，在实际操作的时候，两个小块被吃掉的先后顺序是确定的。

因为并且前一个被吃掉的一定是依赖于第一个条件的失效而吃的，所以我们可以考虑，钦定一下哪一个小块先被吃。

然后 dfs 两个直角边挨着的方向，假定出发位置为实际的“终止位置”，然后往回求一下哪一些是必要的就行，复杂度 \(O(n^4)\)。

从最初思路里那个剥洋葱的想法能看出，如果某一个位置的左边被吃掉了，然后再吃的它，那么一定会是从最左边连续吃过来的。

于是我们可以考虑对行记一个状态，直接记录好左边被吃完的答案，然后从当前位置向另一个直角边方向 dfs 求答案，左右各做一次（实际上就是钦定哪一边先吃了）。

然后复杂度就是 \(O(n^3)\) 了，挺好玩的一个 dfs 题。

Code 
  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
// author : black_trees
// make yourself an idiot.

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define Enonya
#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

const int si = 5e2 + 10;
const int inf = 1e8 + 10;

int n, m;
char s[si][si];
int vis[si][si];
int dpl[si][si], dpr[si][si];

int dfs(int x, int y, int tp) {
    if(vis[x][y] == -1) return inf;
    else if(vis[x][y] == 1) return 0;

    int ret = 2;
    vis[x][y] = -1;
    if(s[x][y] == 'N') {
        if(tp == 1) {
            if(x > 1) {
                ret += dfs(x - 1, y, s[x - 1][y] == 'N');
            }
            if(y < m) {
                ret += dfs(x, y + 1, 1);
            }
        }
        else {
            if(x < n) {
                ret += dfs(x + 1, y, s[x + 1][y] == 'Z');
            }
            if(y > 1) {
                ret += dfs(x, y - 1, 0);
            }
        }
    }
    else {
        if(tp == 1) {
            if(x < n) {
                ret += dfs(x + 1, y, s[x + 1][y] == 'Z');
            }
            if(y < m) {
                ret += dfs(x, y + 1, 1);
            }
        }
        else {
            if(x > 1) {
                ret += dfs(x - 1, y, s[x - 1][y] == 'N');
            }
            if(y > 1) {
                ret += dfs(x, y - 1, 0);
            }
        }
    }

    if(ret < inf) {
        vis[x][y] = 1;
    }
    else {
        ret = inf;
    }

    return ret;
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            cin >> s[i][j];
        }
    }

    for(int i = 1; i <= n; ++i) {
        memset(vis, false, sizeof vis);
        for(int j = 1; j <= m; ++j) {
            dpl[i][j] = min(dpl[i][j - 1] + dfs(i, j, 0), inf);
        }

        memset(vis, false, sizeof vis);
        for(int j = m; j >= 1; --j) {
            dpr[i][j] = min(dpr[i][j + 1] + dfs(i, j, 1), inf);
        }

        for(int j = 1; j <= m; ++j) {
            int ans = min(dpl[i][j], dpr[i][j]);
            if(ans >= inf) cout << -1 << " ";
            else cout << ans << " ";
        }
        cout << endl;
    }

    return 0;
}

LOJ2734「JOISC 2016 Day 2」女装大佬ψ(｀∇´)ψ

最初思路

题意可能有需要再加一句，就是说选择的那个过程其实是不耗时间的，也就是说 [M, F], [M, void] 这两种摊位的状态都会消耗 1min。

注意到首先 F 的个数应当大于等于 M 的个数，不然总会出现至少一个 [M, void] 的状态，就不可能完成。

然后 MF 这样的子序列显然可以消掉。我们希望 MM 这样的子串后面永远能有 F 来抵消掉，也就是说，只需要让 M 的问题解决就好，F 可以通配。

怎么保证 Dark 度（逆序对）最大最小呢，我猜是只用交换一种，但似乎不太对，不过可以想到，交换一个 F 到后面，对这个 F 前面的 M 并没有影响，因为它后面的 F 个数不变嘛。

二分？搞笑呢，这数据范围 \(10^{18}\)

题解

其实上面说出了一些性质。

  1. 显然，如果把 M 看作 +1，F 看作 -1，任意后缀和必须 \(\le 1\)，不然无解。
  2. 如果要改变，肯定是把最后一个 M 拉到最前面。

所以求的就是全局最大后缀。

Code 
 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
// author : black_trees
// make yourself an idiot.

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define Enonya
#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

const int si = 2e5 + 10;

string s[si];
int n, m, ans, cnt[si];

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> s[i] >> cnt[i];
    }

    int sum[2] = {0, 0};
    for(int i = m; i >= 1; --i) {
        int tot = 0, all = sum[0];
        for_each(s[i].begin(), s[i].end(), 
                [&](char ch) -> void { if(ch == 'F') ++tot; }); 
        for(int j = (int)s[i].size() - 1; ~j; --j) {
            if(s[i][j] == 'F') {
                ++all;
                ans = max(ans, sum[0] + sum[1] + ((int)s[i].size() - j) - 2ll * all);
                ans = max(ans, sum[0] + sum[1] + (cnt[i] - 1) * ((int)s[i].size()) + ((int)s[i].size() - j) - 2ll * (all + (cnt[i] - 1) * tot));
            }
        }
        sum[0] += tot * cnt[i];
        sum[1] += ((int)s[i].size() - tot) * cnt[i];
    }

    if(sum[0] < n) cout << "-1" << endl;
    else cout << ans << endl;

    return 0;
}

LOJ2735「JOISC 2016 Day 3」地牢 2ψ(｀∇´)ψ

最初思路
题解
Code

LOJ2736「JOISC 2016 Day 3」回转寿司ψ(｀∇´)ψ

最初思路

首先观察一下这个操作的意义是什么。

初步的感觉是，把这一段里面 \(\ge A\) 的 \(\max\) 拉出来。

中间所有会被交换的位置提出来，放入 A，向前位移舍掉最前的一位（就是 max）

能被交换的位置组成的显然是一个单调递增的子序列。

这些位置满足很多的限制，不过交换限制的叙述顺序是不会改变的，这也许能简化思路，首先他们都是 \(> A\) 的并且为前缀的第一个 max。

所以两个方向，一个先处理出 \(> A\) 的，一个先找到所有前缀 max。

后者看起来要简单的多，然后注意到这里还是区间，先想想这个怎么弄。

前缀 max 就是单调栈，可能和粉兔线段树有关？但是这里要维护所有位置，吗？

只需要知道每次完了 A 是多少就行，那 A' 然就是这个区间 >A 里的 Max。

思考一下，我们是不是真的要维护序列本身的形态（ds 套路感觉是）。

是不是只需要维护区间内的值域就行了，但是区间咋维护，我只会全局的 subtask。

那个单调递增子序列也许会有用，不过维护起来特别麻烦，也是因为区间的缘故。

题解

为啥我啥都想不到，我们发现这个数据范围 \(N \le 4 \times 10^5\)。

并且 TL = 9000ms，我们想一下，既然我们会做全局，换句话说，考虑分块，那么我们如果会做整块的，小块可以就暴力处理。

对于一个整块，我们可以维护一个大根堆，每次有操作的时候我们判一下这个块的 Max 是不是比 \(A\) 大，不然就不交换，因为这里是一个整块，我们只关心它的值域，不关心数到底是怎么排的。

然后考虑一个小块，我们只维护了一个值域上的大根堆，我们并不知道经历过一些操作后，小块被当前询问覆盖的元素有哪些，所以我们需要保留原序列，这部分暴力就直接在原序列上做就行了。

但是这样的话整块又有问题了，我们上面的操作只维护了值域，没有在下标维度上维护这个数列，当整块成为小块被扫到的时候就 gg 了。

所以我们不妨再维护一个集合，表示新插入进去的数的集合（ 不关心它是不是原来在，被换出来又换进去的，我们只关心插入了哪些）。

然后考虑用这个集合对大块重构，并且只在它作为小块的时候重构。

可以发现对于多个被插入的数 \(\{t\}\)，假设有 \(t_x < t_y\)，那么 \(t_x\) 能换出来的 Max 一定也是 \(t_y\) 能换出来的 Max，如果 \(t_x\) 先操作，这个位置会被换成 \(t_x\)，如果 \(t_y\) 先操作，它还是会变成 \(t_x\)，所以实际上顺序是无关紧要的，我们只关心值域上的大小关系。

于是我们维护一个小根堆，暴力的扫一下整个块，如果能交换就把堆里的交换出去，被交换的插入小根堆里面，可以发现不管原来插入的顺序如何，这样维护之后最后的结果都是一样的。

那么重构的复杂度就是 \(O(B \log B)\) 了，整体复杂度可以做到 \(O(q\sqrt n \log n)\)。

Code 
 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
// author : black_trees
// make yourself an idiot.

#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define Enonya
#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

const int si = 4e5 + 10;
const int sib = 1e3 + 10;

int n, m, a[si];
int bel[si], unit;

inline int lb(int p) { return unit * (p - 1) + 1; }
inline int rb(int p) { return unit * p >= n ? n : unit * p; }

std::priority_queue<int> num[sib];
std::priority_queue<int, std::vector<int>, std::greater<int>> tag[sib];

void reset(int p) {
    while(!num[p].empty()) num[p].pop();
    for(int i = lb(p); i <= rb(p); ++i) {
        num[p].push(a[i]);
    }
}
void pushdown(int p) {
    if(tag[p].empty()) return;
    for(int i = lb(p); i <= rb(p); ++i) {
        int v = tag[p].top();
        if(v < a[i]) swap(a[i], v), tag[p].pop(), tag[p].push(v);
    }
    while(!tag[p].empty()) tag[p].pop();
    reset(p);
}
int modify(int l, int r, int A) {
    pushdown(bel[l]);
    for(int i = l; i <= min(rb(bel[l]), r); ++i) {
        if(a[i] > A) swap(A, a[i]);
    }
    reset(bel[l]);

    for(int i = bel[l] + 1; i < bel[r]; ++i) {
        int v = num[i].top();
        if(v > A) num[i].pop(), num[i].push(A), tag[i].push(A), swap(v, A);
    }

    if(bel[l] != bel[r]) {
        pushdown(bel[r]);
        for(int i = lb(bel[r]); i <= r; ++i) {
            if(a[i] > A) swap(A, a[i]);
        }
        reset(bel[r]);
    }

    return A;
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m, unit = sqrt(n);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for(int i = 1; i <= n; ++i) {
        bel[i] = (i - 1) / unit + 1;
        num[bel[i]].push(a[i]);
    }

    for(int i = 1; i <= m; ++i) {
        int l, r, A;
        cin >> l >> r >> A;
        if(l <= r) A = modify(l, r, A);
        else A = modify(l, n, A), A = modify(1, r, A);
        cout << A << endl;
    }
    return 0;
}

感觉分块思想从这道题应该重新总结一下。

“小段暴力，大段维护”，这是之前的，现在应该加上一句：

“维护标记，适时重构”，具体来说对于大段的整体处理，如果会导致小段维护信息失效，需要在扫描小段之前对标记进行重构。

LOJ2737「JOISC 2016 Day 3」电报ψ(｀∇´)ψ

最初思路

考虑缩点，考虑没有大小 \(> 1\) 的 SCC 的情况。

此时最优的策略一定是将它们连接成一个环，这是显然的。

因为如果我们不连成环，必然是一个大环上几个小环的形式。

而本题保证了出度为 \(1\)，这是不可能存在的。

考虑怎么计算代价，实际上我们不关心某一条被改变的边到底到哪里去了，我们只关心一条边是否改变了。

所以考虑一个点，将它的所有入边中最大的留下，其它的修改，然后你发现这样做可能会变成几个独立的环。

所以我们还需要断开这些环，这个对于环上的点和不在环上的边贪心考虑即可，需要特判一下本来就是环的情况。

题解

上面说了，不过这个贪心思想似乎还挺常见的。

尝试构造答案的下界，说明每一步都是必要的，或者类似多限制模型里一样，尝试说明某个最优局面的等价唯一性。

Code 
 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
// author : black_trees
// make yourself an idiot.

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define Enonya
#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

const int si = 2e5 + 10;
const int inf = 1e9 + 10;

int n, l, r;
int d[si], a[si], c[si];
int q[si], a1[si], a2[si];

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    i64 ans = 0;
    cin >> n, l = 1, r = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i] >> c[i];
        a1[a[i]] = max(a1[a[i]], c[i]);
        ans += c[i], d[a[i]]++;
    }

    for(int i = 1; i <= n; ++i) {
        if(!d[i]) q[++r] = i;
        ans -= a1[i];
    }

    while(l <= r) {
        int x = q[l++], y = a[x];
        a2[y] = max(a2[y], c[x]);
        if(!--d[y]) q[++r] = y;
    }

    int x = 1;
    int mi = inf, num = 0;
    for(int i = 1; i <= n; ++i) {
        if(d[i]) {
            do {
                ++num, d[x] = 0;
                mi = min(mi, a1[x] - a2[x]), x = a[x];
            } while(x != i);
            ans += mi;
            if(num == n) break;
        }
        x = i + 1, mi = inf, num = 0;
    }

    if(num == n) cout << "0" << endl;
    else cout << ans << endl;

    return 0;
}

LOJ2738「JOISC 2016 Day 4」危险的滑冰ψ(｀∇´)ψ

最初思路

模拟赛做过这题，这里是模拟赛时候的思路：

并没有，就超级暴力直接乱搜，但是感觉很容易 g 啊。

题解

只需要注意到，走到相邻两个点的步数，如果它们都没有冰块（一开始）。

那么花费是 \(2\)，并且走过了不能再走，然后能直接撞墙的，花费就是 \(1\)。

于是我们可以 \(O(n^2 \log n)\) 建图，跑一个 Dijkstra，这就是最短路了。

需要想一想这个做法为什么会比较自然但是我没想到。

Code 
 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
// loj.ac/s/1062255
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int N = 1e3 + 5, inf = 0x3f3f3f3f, dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };

int n, m, sx, sy, tx, ty, L[N][N], R[N][N], U[N][N], D[N][N], dis[N][N];
char s[N][N];
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;

void relax(int x, int y, int d) {
    if(s[x][y] == '#' || d >= dis[x][y]) {
        return;
    }
    pq.push(make_pair(dis[x][y] = d, make_pair(x, y)));
}

void dijkstra() {
    memset(dis, inf, sizeof(dis));
    pq.push(make_pair(dis[sx][sy] = 0, make_pair(sx, sy)));
    while(pq.size()) {
        auto u = pq.top();
        pq.pop();
        int x = u.se.fi, y = u.se.se;
        if(x == tx && y == ty) {
            return;
        }
        if(u.fi > dis[x][y]) {
            continue;
        }
        for(int i = 0; i < 4; ++i) {
            relax(x + dx[i], y + dy[i], u.fi + 2);
        }
        relax(U[x][y] + 1, y, u.fi + 1);
        relax(D[x][y] - 1, y, u.fi + 1);
        relax(x, L[x][y] + 1, u.fi + 1);
        relax(x, R[x][y] - 1, u.fi + 1);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        cin >> (s[i] + 1);
    }
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) {
            L[i][j] = (s[i][j] == '#' ? j : L[i][j - 1]), U[i][j] = (s[i][j] == '#' ? i : U[i - 1][j]);
        }
    for(int i = n; i; --i) for(int j = m; j; --j) {
            R[i][j] = (s[i][j] == '#' ? j : R[i][j + 1]), D[i][j] = (s[i][j] == '#' ? i : D[i + 1][j]);
        }
    cin >> sx >> sy >> tx >> ty;
    dijkstra();
    cout << (dis[tx][ty] == inf ? -1 : dis[tx][ty]) << "\n";
    return 0;
}

这种，有障碍的搜索，很多时候也可以考虑一下建边之类的。

LOJ2740「JOISC 2016 Day 4」最差记者 2ψ(｀∇´)ψ

最初思路

感觉上来说是一个二分图状物，首先把 B 可行的 D 连一条 B -> D 边。

如果把同 \(A_i, C_i\) 的放到一层，那么就是修改尽量少的 \(A_i, C_i\)，使得整张图存在一个：

1
2
3
--->
--->
--->

一样的匹配。

思考一下怎么做。

题解

按照 \(b, d\) 放在一起排序，显然对于一个 \(d\) 一定选离它最近的 \(b\)。

但是如果就这么贪心，有可能出现不合法的情况，比如你后一个 \(d\) 占用了前面的 \(d\) 唯一可以匹配的 \(b\), 那绝对无解。

你注意到这个图，从 \(d\) 这边来看显然是对着 \(b\) 的一个前缀连边（排序过后），并且 \(N(d)\) 显然是随着 \(d\) 变大而越来越大的。

所以很容易想到，可以使用 Hall 定理判断某一步贪心是否合法，换句话说判断某个前缀能否形成完美匹配。

然后这个，把 \(d\) 权值赋为 \(-1\)，\(b\) 赋为 \(1\)，只需要用一个线段树 Check 一下就行了。

Code

咕咕咕。

最后更新: November 19, 2023