跳转至

ATC & CF 选做(23Mar,23Apr)

CFR #857ψ(｀∇´)ψ

Contest Id: 1801/1802

久违的 div1 2 分开的场。

Vp 打了 5 题，很开心，有点思考的迹象了。

2A - Likesψ(｀∇´)ψ

有一些人，他们会 add likes 或者 remove likes。

同一个人的操作用 \(x, -x\) 来记录，表示 add 或者 remove。

给定一个操作序列，你可以 rearrange 一下，要你求每个时刻，最大的 likes 和最小的 likes 数。

考虑记录一下有几个 remove likes。

然后最大化显然是把 remove likes 丢到后面。

然后最小化就是尽量早的 add remove, add remove 这样交替。

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

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

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int T, n, a[si];

int main() {

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

    cin >> T;
    while(T--) {
        cin >> n;
        int cnt = 0;
        for(int i = 1; i <= n; ++i)
            cin >> a[i], cnt += (a[i] < 0);
        for(int i = 1; i <= n - cnt; ++i) {
            cout << i << " ";
        }
        for(int i = 1; i <= cnt; ++i) {
            cout << n - cnt - i << " ";
        }
        cout << endl;
        for(int i = 1; i <= cnt; ++i) {
            cout << 1 << " ";
            cout << "0" << " ";
        }
        for(int i = cnt * 2 + 1; i <= n; ++i) {
            cout << (i - (cnt * 2)) << " ";
        }
        cout << endl;
    }

    return 0;
}

2B - Settlement of Guinea Pigsψ(｀∇´)ψ

Dasha 很喜欢豚鼠，她在 \(n\) 天内要不是买豚鼠，要不是请医生来看豚鼠。

Dasha 和宠物店都无法分辨豚鼠的性别（思考人生），只能在医生来查看豚鼠的时候为这些豚鼠做性别鉴定。

为了豚鼠，Dasha 打算给它们买一些笼子，但宠物店里卖的笼子只能放最多 \(2\) 只豚鼠。由于她不想让她的豚鼠遭受道德伤害，一个笼子里只能放同一种性别的豚鼠。

求 Dasha 最少需要买多少个笼子。

这个翻译由 @ztrztr 提供

感觉，没啥好说的，就兽医来了最优分配，其他一个一个放。

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

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

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

using namespace std;
using i64 = long long;

signed main() {

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

    int T; cin >> T; 
    while(T--) {
        int n; cin >> n;
        int ans = 0, u = 0, v = 0;
        for(int i = 1, x; i <= n; ++i) {
            cin >> x;
            if(u == 0 && x == 2) continue;
            if(x == 1) u++, v++;
            else u = v / 2 + 1;
            ans = max(ans, u);
        }
        cout << ans << endl;
    }

    return 0;
}

1A - The Very Beautiful Blanketψ(｀∇´)ψ

你需要对一个 \(n\times m\) 的矩阵 \(B\) 填数，要求你满足，对于 \(B\) 的任意一个 \(4 \times 4\) 的子矩阵，满足以下两个条件：

  • \(A_{11} \oplus A_{12} \oplus A_{21} \oplus A_{22} = A_{33} \oplus A_{34} \oplus A_{43} \oplus A_{44}\)

  • \(A_{13} \oplus A_{14} \oplus A_{23} \oplus A_{24} = A_{31} \oplus A_{32} \oplus A_{41} \oplus A_{42}\)

\(\oplus\) 表示按位或，\(4 \le n,m \le 200\)，要求 \(B_{ij} \in [0, 2^{63})\)。

首先一个显然的结论是，不同的数的数量一定是 \(n \times m\)。

因为 \(n,m \le 200\) 嘛。

然后我们就随便构造一下，不难发现 \(a(i, j) = 2^9 + j\) 是一种满足条件的构造。

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

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

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

using namespace std;
using i64 = long long;

signed main() {

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

    int T; cin >> T; 
    while(T--) {
        int n; cin >> n;
        int ans = 0, u = 0, v = 0;
        for(int i = 1, x; i <= n; ++i) {
            cin >> x;
            if(u == 0 && x == 2) continue;
            if(x == 1) u++, v++;
            else u = v / 2 + 1;
            ans = max(ans, u);
        }
        cout << ans << endl;
    }

    return 0;
}

1B - Buying giftsψ(｀∇´)ψ

有 \(n\) 个商店，在第 \(i\) 个商店会进行下面两个操作之一：

  • 为朋友 A 买礼物，花费 \(a_i\) 元。
  • 为朋友 B 买礼物，花费 \(b_i\) 元。

求在每个商店进行过以上操作后，朋友 A 和 B 获得的礼物中的最大价值之差的最小值。

有 \(t\) 组测试数据。

数据范围：\(1\le t\le1000\)，\(2\le n\le5\times 10^5\)，\(0\le a_i, b_i\le 10^9\)。

也比较容易，就是我们可以先观察一下，看看有没有什么性质。

但是其实也没有什么，也就是说，我们没法通过 \(O(1)\) 或者是 \(O(\log n)\) 之类的方式来固定一些选项（排除一些冗杂状态）。

于是我们只能考虑 \(O(n)\) 枚举每一个位置，然后考虑它的最优决策是什么。

发现，如果我们钦定一个位置 \(i\) 是 \(a\) 中的 \(\max\)，那么显然，所有满足 \(a(j) > a(i)\) 的 \(j\) 我们都不选 \(a\) 而是选 \(b\)。

然后满足 \(a(k) \le a(i)\) 的 \(k\) 可以选择性的选一些作为 \(b\) 中的选项（两边都只要各选一个就行）。

于是 \(b\) 这边的 \(\max\) 就可以从 \(\{b(j)\}\) 或者 \(\max\{b(k)\}\) 当中来，我们考虑一下，后者必须取，前者在 \(b(k) < \max\{b(j)\}\) 的条件下可能更靠近 \(a(i)\)。

所以我们可以用一个线段树维护，一边 qmax，一边线段树二分，但是这太复杂了，注意到其实这里是可以不管顺序的，所以我们可以先排序，用两个 set 或者一个 set 维护一下就行（两个就是直接维护两部分，一个就是先从最大的考虑，就能省去一个 set。）

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

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

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 5e5 + 10;
const int inf = 0x3f3f3f3f;

int n;
std::multiset<int> s;
std::vector<std::pair<int, int>> v;

int main() {

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

    int T; cin >> T;
    while(T--) {
        cin >> n;
        int mi = -inf, ans = inf;
        s.clear(), v.clear();
        for(int i = 1; i <= n; ++i) {
            int x, y;
            cin >> x >> y;
            s.insert(y), v.emplace_back(make_pair(x, y));
        }
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        for(auto &[x, y] : v) {
            s.erase(s.lower_bound(y));
            if(x <= mi) ans = min(ans, mi - x);
            else {
                ans = min(ans, x - mi);
                auto it = s.upper_bound(x);
                if(it != s.end()) ans = min(ans, *it - x);
                if(it != s.begin() && *(std::prev(it)) > mi)
                    ans = min(ans, x - *(std::prev(it)));
            }
            mi = max(mi, y);
        }
        cout << ans << endl;
    }

    return 0;
}

1C - Music Festivalψ(｀∇´)ψ

  • 给你 \(n\) 个数列，你要把它们按任意顺序首尾连接起来。
  • 最大化连接后能成为严格前缀最大值的数的数量。
  • 多组测试数据，\(1 \leq n \leq 2 \times 10^5\)。

我们对于这种拼起来的问题，可以考虑对于每段先处理一下，思想类似 NOIOnline2022 sort 那个题，显然一个段里面能做贡献的一定是在这个段当中就满足条件的位置。

于是我们可以对于每个段把不满足的位置去掉，然后就是一堆严格单调递增的序列拼在一起，要做出贡献的点最多。

这个显然就直接 dp 一下，设 \(dp_i\) 表示第 \(i\) 个位置的最大值。

然后转移是类似这样的形式：

img

于是随便怎么转移一下就好。

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

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

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

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3fll;

int n, dp[si], k[si];
std::vector<int> a[si];
std::pair<int, int> b[si];

void init(int n) {
    dp[0] = 0;
    for(int i = 1; i <= n; ++i)
        a[i].clear();
}

signed main() {

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

    int T; cin >> T;
    while(T--) {
        cin >> n, init(n);
        for(int i = 1; i <= n; ++i) {
            std::vector<int> tmp;
            cin >> k[i]; tmp.push_back(0ll);
            for(int j = 1; j <= k[i]; ++j) {
                int x; cin >> x;
                tmp.push_back(x);
            }
            a[i].resize(k[i] + 3);
            int mx = -inf, cur = 0;
            for(int j = 1; j <= k[i]; ++j) {
                if(tmp[j] > mx)
                    mx = tmp[j], ++cur, a[i][cur] = mx;
            }
            k[i] = cur;
        }

        for(int i = 1; i <= n; ++i)
            b[i] = make_pair(a[i][k[i]], i);
        sort(b + 1, b + n + 1);

        for(int i = 1; i <= n; ++i) {
            auto [fr, sc] = b[i];
            dp[i] = dp[i - 1];
            for(int j = 1; j <= k[sc]; ++j)
                dp[i] = max(dp[i], dp[lower_bound(b + 1, b + n + 1, make_pair(a[sc][j], 0ll)) - b - 1] + k[sc] - j + 1);
        }
        cout << dp[n] << endl;
    }

    return 0;
}

1D - The way homeψ(｀∇´)ψ

一个人在一张有向图的 \(1\) 号结点，他要去到 \(n\) 结点。每条边 \((a_i,b_i)\) 有边权 \(s_i\)，表示走过这条边需要花 \(s_i\) 元。这个人一开始有 \(p\) 元，到了一个点 \(u\)，他可以进行若干次演出，每次演出收获 \(w_u\) 元。问到达 \(n\) 的最小演出次数，若无解输出 -1。

这题很好玩，属于是 div2/ABC 特别喜欢出的一种，状态复杂的最短路题。

这里要用到一个类似反悔？的 "postpone" 思想。

我们有一个观察，如果我们走到某一个节点，钱不够了的时候，显然我们只需要在之前打工过的最优位置疯狂打工直到钱够用。

然后我们可以设一个 dp 状态，设 \(dp(i,j) = \{x, y\}\) 表示，走到 \(i\)，并且最优点是 \(j\)，当前最小打工次数为 \(x\)，在此前提下最大剩余钱数为 \(y\).

这个显然就 Dijkstra 转移一下就行，正确性可以通过 Exchange Argument 证明这个结论：如果 \(x\) 更小，哪怕 \(y\) 更小，这个状态依旧是优秀的，来得到。

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

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

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

using namespace std;
using i64 = long long;
using pii = std::pair<int, int>;

const int si_n = 8e2 + 10;
const int si_m = 3e3 + 10;
const int inf = 0x3f3f3f3f3f3f3f3fll;

int n, m, p;
pii dp[si_n][si_n];
int tot = 0, head[si_n];
struct Edge { int ver, Next, w; } e[si_m << 1];
inline void add(int u, int v, int w) { e[tot] = (Edge){v, head[u], w}, head[u] = tot++; }

int ww[si_n];
std::priority_queue<std::pair<pii, pii>> q;
void dijkstra() {
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= n; ++j) {
            dp[i][j] = make_pair(-inf, -inf);
        }
    }
    dp[1][0] = make_pair(0, p), q.push(make_pair(make_pair(0, p), make_pair(1, 0)));
    while(!q.empty()) {
        auto fr = q.top().first;
        auto sc = q.top().second;
        q.pop();
        int u = sc.first, o = sc.second;
        if(dp[u][o] > fr) continue;
        if(ww[u] > ww[o]) o = u;
        for(int i = head[u]; ~i; i = e[i].Next) {
            int v = e[i].ver, w = e[i].w;
            auto nfr = fr;
            if(nfr.second < w) {
                int rest = w - nfr.second;
                int tim = ceil((rest * 1.0) / (1.0 * ww[o]));
                nfr.first -= tim, nfr.second += tim * ww[o];
            }   
            nfr.second -= w;
            if(dp[v][o] < nfr) q.push(make_pair(dp[v][o] = nfr, make_pair(v, o)));
        }
    }
}

signed main() {

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

    int T; cin >> T;
    while(T--) {
        cin >> n >> m >> p;
        for(int i = 0; i <= n; ++i)
            head[i] = -1;
        while(!q.empty()) q.pop();
        for(int i = 1; i <= n; ++i)
            cin >> ww[i];
        for(int i = 1; i <= m; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            add(u, v, w);
        }
        dijkstra();
        pii ans = make_pair(-inf, -inf);
        for(int i = 1; i <= n; ++i)
            ans = max(ans, dp[n][i]);
        if(ans.first <= -inf) cout << "-1" << endl;
        else cout << -ans.first << endl;
    }

    return 0;
}

CFR #858ψ(｀∇´)ψ

Contest Id: 1806

Aψ(｀∇´)ψ

题面暂略。

把给定的 \((c, d)\) 分到四个区域。

如果在 \((a, b)\) 的下面显然不可行（\(b > d\)）

然后如果在 \(a\) 的右侧，考虑 \(c - a\) 是否大于 \(d - b\)，如果成立也无解，这个显然。

然后剩下的两种情况就给 \(y\) 凑一下就行了。

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

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

#define endl '\n'

using namespace std;
using i64 = long long;

int main() {

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

    int T; cin >> T;
    while(T--) {
        i64 a, b, c, d;
        cin >> a >> b >> c >> d;
        if(b > d) { cout << "-1" << endl; continue; }
        i64 ansy = d - b;
        i64 ansx = c - a;
        if(ansx > ansy) { cout << "-1" << endl; continue; }
        i64 ans = (ansy - ansx) + ansy;
        cout << ans << endl;
    }

    return 0;
}

Bψ(｀∇´)ψ

题面暂略。

显然答案为 \(x\in \{0, 1, 2\}\)。

然后就数一下 \(0\) 的个数，数一下是不是存在大于 \(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
// author : black_trees

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

#define endl '\n'

using namespace std;
using i64 = long long;

int main() {

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

    int T; cin >> T;
    while(T--) {
        int n; cin >> n;
        std::vector<int> a(n + 1);
        std::bitset<400010> b; b.reset();
        int cnt0 = 0, f = 0;
        for(int i = 1; i <= n; ++i)
            cin >> a[i], cnt0 += (a[i] == 0), f += (a[i] > 1);
        if(cnt0 - 1 <= n - cnt0) { cout << "0" << endl; continue; }
        if(f || cnt0 == n) { cout << "1" << endl; continue; };  
        cout << "2" << endl;
    }

    return 0;
}

Cψ(｀∇´)ψ

题面暂略。

注意到满足条件的 \(q\) 只能是两种情况

  1. 全部是 \(0\)。
  2. 如果 \(n \equiv 0 \pmod 2\)，那么 \(2n - 1\) 个 \(-1\)，一个 \(n\) 就满足条件。

然后 \(n = 1, n = 2\) 的时候还有特殊情况（题目解释里就只给了这两种，YunQian 你好恶毒。）

于是四种可能分别判断一下就行了。

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

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

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

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n, a[si << 1];

signed main() {

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

    int T; cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 1; i <= n * 2; ++i)
            cin >> a[i];
        sort(a + 1, a + 1 + n + n);
        int ans = 0;
        for(int i = 1; i <= n * 2; ++i)
            ans += abs(a[i]);
        if(n == 1) ans = min(ans, abs(a[1] - a[2]));
        if(n == 2) ans = min(ans, min(abs(a[1] - 2) + abs(a[2] - 2) + abs(a[3] - 2) + abs(a[4] - 2),
                   abs(a[1] + 1) + abs(a[2] + 1) + abs(a[3] + 1) + abs(a[4] - 2)));
        if(n % 2 == 0) {
            int ret = 0;    
            for(int i = 1; i < n * 2; ++i) {
                ret += abs(a[i] + 1);
            }
            ret += abs(a[n * 2] - n);
            ans = min(ans, ret);
        }
        cout << ans << endl;
    }   

    return 0;
}

Dψ(｀∇´)ψ

题面说的有点抽象，找别人的翻译估计一时半会也看不懂，还是自己写题面好了。

给定你一个长度为 \(n\) 的 0/1 序列 \(a\)，假定有一个 \(1 \sim m - 1\) 的排列 \(p\)，定义排列 \(p\) 的贡献为一张由 \(a, p\) 生成的有向图 \(G\) 中，节点 \(1\) 的入度。

\(G\) 的生成方式如下：

Step1: 在图 \(G\) 上初始化一个有 \(m\) 个节点的并查集。

Step2: 对于 \(\forall i \in 1 \sim m - 1\)，选择 \(p_i, p_i + 1\) 所在的两个联通块 \(U, V\)，合并他们。

Step3: 并且，如果 \(a_{p_i} = 0\)，那么令 \(V\) 的 root 指向 \(U\) 的 root，否则反之。（这里的指向就是连一条有向边）

给定 \(N\)，令 \(n = N - 1\)，对于 \(\forall k \in [1, N)\)，你需要求出长度为 \(k\) 的所有排列的贡献之和，对 \(998244353\) 取模。

\(2\le N \le 5 \times 10^5\)，多组数据。

感觉是送分题，不知道为啥赛时没几个人做，思想和之前那个，ABC290F - Maximum Diameter 很像。

显然我们可以讨论任意一种排列，然后算方案数，为了方便，我们假设，每次加入的点对都是 \((i - 1, i)\) 的形式，这样的排列显然存在。

我们考虑新加入一个点对 \((i - 1, i)\) 之后，对于答案的贡献是什么。

显然如果能对答案有贡献，需要此时的 \(1\) 为并查集的树根。

我们记 \(g(i)\) 表示 \(1 \sim i\) 已经加入并查集时的答案，显然有 \(g(i) = g(i - 1) \times i + val\)，其中 \(val\) 为当前这个点对 \((i - 1, i)\) 的贡献。

那么，如果 \(a_i = 0\)，这个点对显然会做出贡献 \(1\)，我们乘上方案数就行，反之它不会做出贡献。

这个方案数应当是，以 \(1 \sim i\) 组成的并查集，且 \(1\) 为根的方案数，我们记这个值为 \(f(i)\)，考虑加入 \(i\) 的时候是不是指向 \(i - 1\) 的根即可得到 \(f\) 的计算式：\(f(i) = f(i - 1) \times (i - [a_i = 1])\)。

最终 \(g\) 的递推式是：\(g(i) = g(i - 1) \times i + f(i) \times [a_i = 0]\)，边界 \(f(0) = 1, g(0) = 0\)。

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

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

constexpr i64 safe_mod(i64 x, i64 m) { return x %= m, x < 0 ? x + m : x; }
constexpr i64 pow_mod_constexpr(i64 x, i64 n, int m) {
    if(m == 1) return 0;
    unsigned _m = m; uint64_t r = 1, _x = safe_mod(x, m);
    for(; n; n >>= 1, _x = _x * _x % _m) if(n & 1) r = r * _x % m;
    return r;
}
constexpr bool is_prime_constexpr(int n) {
    if(n <= 1) return false;
    if(n == 2 || n == 7 || n == 61) return true;
    if(n % 2 == 0) return false;
    i64 d = n - 1; while(~d & 1) d /= 2;
    for(i64 a : {2, 7, 61}) {
        i64 t = d, y = pow_mod_constexpr(a, t, n);
        while(t != n - 1 && y != 1 && y != n - 1) y = y * y % n, t <<= 1;
        if(y != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
constexpr pair<i64, i64> inv_gcd(i64 a, i64 b) {
    a = safe_mod(a, b);
    if(a == 0) return {b, 0};
    i64 s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        i64 u = s / t; s -= t * u, m0 -= m1 * u;
        i64 tmp = s; s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}
struct Barrett_Reduction {
    unsigned m; uint64_t im;
    Barrett_Reduction(unsigned m) :m(m), im(~0ull / m + 1) {}
    unsigned mul(unsigned a, unsigned b) const {
        uint64_t z = (uint64_t)a * b, x = (__uint128_t)z * im >> 64; unsigned v = z - x * m;
        return m <= v ? v + m : v;
    }
};
template<int m> struct static_modint {
    using _mint = static_modint;
  public:
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    static_modint() :_v(0) {}
    template<class __Tp> static_modint(__Tp v) { i64 x = v % m; _v = x < 0 ? x + m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= m) _v -= m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v -= rhs._v; if(_v >= m) _v += m; return *this; }
    _mint& operator *= (const _mint& rhs) { uint64_t z = _v; z *= rhs._v, _v = z % m; return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const{ if(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static constexpr bool prime = is_prime_constexpr(m);
};
struct dynamic_modint {
    using _mint = dynamic_modint;
  public:
    static void set_mod(int m) { assert(1 <= m), bt = Barrett_Reduction(m); }
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    dynamic_modint() :_v(0) {}
    template<class __Tp> dynamic_modint(__Tp v) { i64 x = v % (int)bt.m; _v = x < 0 ? x + bt.m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == bt.m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = bt.m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v += bt.m - rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
    _mint& operator *= (const _mint& rhs) { _v = bt.mul(_v, rhs._v); return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const { auto eg = inv_gcd(_v, bt.m); assert(eg.first == 1); return eg.second; }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static Barrett_Reduction bt;
};
using modint = dynamic_modint;
using barrett = Barrett_Reduction;

barrett modint::bt = 998244353;

const int si = 5e5 + 10;

int n, a[si];

int main() {

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

    int T; cin >> T;
    while(T--) {
        cin >> n;
        modint f = 1, g = 0;
        for(int i = 1; i < n; ++i)
            cin >> a[i];
        for(int i = 1; i < n; ++i) {
            g = i * g + (a[i] == 0) * f;
            cout << g.val() << " \n"[i == n]; 
            f = f * (i - a[i]);
        }   
    }

    return 0;
}

Eψ(｀∇´)ψ

题面暂略。

不会。

ABC293G Triple Indexψ(｀∇´)ψ

题面暂略

注意到其实只需要维护区间中每个数出现的 \(cnt\)，然后答案是 \(\sum\dbinom{cnt}{3}\)。

那么就是莫队板子了。

没有放代码的必要。

ABC294G Distance Queries on a Treeψ(｀∇´)ψ

题面暂略。

呃呃，树剖的板子。

没有放代码的必要。

ABC295E Kth Numberψ(｀∇´)ψ

题面暂略。

神秘题，没看懂咋想到的。

注意到对于 \(E(X) = \sum i \times p_i\)，其中 \(p_i\) 是这个位置取到 \(i\) 的概率，有一个转化：

\(E(X) = \sum pp_i\)，其中 \(pp_i\) 表示 \(X \ge i\) 的概率。

为啥呢，比如对于 \(m = 3\)：

\(E(X) = 1 \times \dfrac{1}{3} + 2 \times \dfrac{1}{3} + 3 \times \dfrac{1}{3} = \dfrac{3}{3} + \dfrac{2}{3} + \dfrac{1}{3}\)。

不仅规避了取值还降低了难度，好牛逼的做法。

转化过后，分类讨论算贡献即可，这个是 trivial 的。

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
// author : black_trees

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

#define endl '\n'

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

constexpr i64 safe_mod(i64 x, i64 m) { return x %= m, x < 0 ? x + m : x; }
constexpr i64 pow_mod_constexpr(i64 x, i64 n, int m) {
    if(m == 1) return 0;
    unsigned _m = m; uint64_t r = 1, _x = safe_mod(x, m);
    for(; n; n >>= 1, _x = _x * _x % _m) if(n & 1) r = r * _x % m;
    return r;
}
constexpr bool is_prime_constexpr(int n) {
    if(n <= 1) return false;
    if(n == 2 || n == 7 || n == 61) return true;
    if(n % 2 == 0) return false;
    i64 d = n - 1; while(~d & 1) d /= 2;
    for(i64 a : {2, 7, 61}) {
        i64 t = d, y = pow_mod_constexpr(a, t, n);
        while(t != n - 1 && y != 1 && y != n - 1) y = y * y % n, t <<= 1;
        if(y != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
constexpr pair<i64, i64> inv_gcd(i64 a, i64 b) {
    a = safe_mod(a, b);
    if(a == 0) return {b, 0};
    i64 s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        i64 u = s / t; s -= t * u, m0 -= m1 * u;
        i64 tmp = s; s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}
struct Barrett_Reduction {
    unsigned m; uint64_t im;
    Barrett_Reduction(unsigned m) :m(m), im(~0ull / m + 1) {}
    unsigned mul(unsigned a, unsigned b) const {
        uint64_t z = (uint64_t)a * b, x = (__uint128_t)z * im >> 64; unsigned v = z - x * m;
        return m <= v ? v + m : v;
    }
};
template<int m> struct static_modint {
    using _mint = static_modint;
  public:
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    static_modint() :_v(0) {}
    template<class __Tp> static_modint(__Tp v) { i64 x = v % m; _v = x < 0 ? x + m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= m) _v -= m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v -= rhs._v; if(_v >= m) _v += m; return *this; }
    _mint& operator *= (const _mint& rhs) { uint64_t z = _v; z *= rhs._v, _v = z % m; return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const{ if(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static constexpr bool prime = is_prime_constexpr(m);
};
struct dynamic_modint {
    using _mint = dynamic_modint;
  public:
    static void set_mod(int m) { assert(1 <= m), bt = Barrett_Reduction(m); }
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    dynamic_modint() :_v(0) {}
    template<class __Tp> dynamic_modint(__Tp v) { i64 x = v % (int)bt.m; _v = x < 0 ? x + bt.m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == bt.m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = bt.m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v += bt.m - rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
    _mint& operator *= (const _mint& rhs) { _v = bt.mul(_v, rhs._v); return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const { auto eg = inv_gcd(_v, bt.m); assert(eg.first == 1); return eg.second; }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static Barrett_Reduction bt;
};
using modint = dynamic_modint;
using barrett = Barrett_Reduction;

barrett modint::bt = 998244353;

const int si = 1e5 + 10;

modint fac[si];
void init() {
    fac[0] = 1;
    for(int i = 1; i <= si - 10; ++i) {
        fac[i] = fac[i - 1] * i;
    }
}
modint C(int n, int m) {
    return fac[n] / (fac[n - m] * fac[m]);
}


int main() {

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

    init(); 
    int n, m, k;
    cin >> n >> m >> k;

    std::vector<int> a(n);
    for(int i = 0; i < n; ++i)
        cin >> a[i];

    modint ans = 0;
    for(int i = 1; i <= m; i++) {
        int r = n + 1 - k, tmp = 0;
        for(int j : a) {
            if(j >= i) --r;
            if(j == 0) ++tmp;
        }
        if(r < 0 or r > tmp) {
            ans += (r < 0 ? 1 : 0);
            continue;
        }
        modint p = modint(m + 1 - i) / m;
        std::vector<modint> pw1(tmp + 1, 1);
        std::vector<modint> pw2(tmp + 1, 1);
        for(int j = 0; j < tmp; j++) {
            pw1[j + 1] = pw1[j] * p;
            pw2[j + 1] = pw2[j] * (1 - p);
        }
        for(int j = r; j <= tmp; j++) {
            ans += C(tmp, j) * pw1[j] * pw2[tmp - j];
        }
    }
    cout << ans.val() << endl;

    return 0;
}

ABC295G Minimum Reachable Cityψ(｀∇´)ψ

题面暂略。

其实题目就是对于每个点要维护两个集合，它能去向的，它能到达的。

或者换句话说要对有向图动态维护连通性，可以想到并查集，但是并查集只能维护无向关系。

我们不妨考虑阅读题面，注意到每次加边一定会加出一个环（可以看作无向边了）

那么我们钦定，一开始所有反向边都连上了，然后加边我们就等于加出了无向边，此时使用并查集维护即可。

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

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

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n, m;
int p[si], pa[si];
int root(int x) { 
    if(pa[x] != x) 
        return pa[x] = root(pa[x]);
    return pa[x];
}
void Merge(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx == ry) return;
    pa[rx] = ry;
}
bool same(int x, int y) {
    return root(x) == root(y);
}

int main() {

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

    cin >> n, p[1] = 1;
    for(int i = 2; i <= n; ++i)
        cin >> p[i];
    for(int i = 1; i <= n; ++i) 
        pa[i] = i;

    cin >> m;
    while(m--) {
        int opt; cin >> opt;
        if(opt == 1) {
            int x, y; cin >> x >> y;
            while(!same(x, y)) x = root(x), Merge(x, p[x]);
        }
        if(opt == 2) {
            int x; cin >> x;
            cout << root(x) << endl;
        }
    }

    return 0;
}

ABC296F Simultaneous Swapψ(｀∇´)ψ

题面暂略

三句话题解：

  • 注意到如果值域不是对应显然无解。
  • 注意到，如果存在一个数出现了两次，必然可以不改变这个数组去交换（交换完了利用这个元素再换回去即可）。
  • 如果逆序对奇偶性不相同，因为不存在可以只更改一边的操作，所以无解，剩下的都是有解。
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
// author : black_trees

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

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

class Fenwick {
    private:
        int t[si << 1], V;
        inline int lowbit(int x) { return x & -x; }
    public:
        void init(int n) { memset(t, 0, sizeof t), V = n + 1; }
        void add(int x, int v) { while(x <= V) t[x] += v, x += lowbit(x); }
        int que(int x) { int ret = 0; while(x) ret += t[x], x -= lowbit(x); return ret; } 
} tr;

int main() {

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

    int n; cin >> n;
    std::vector<int> a(n), b(n);
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    for(int i = 0; i < n; ++i)
        cin >> b[i];

    int inv[2] = {0, 0};
    tr.init(n);
    for(int i = 0; i < n; ++i) {
        inv[0] += tr.que(n - a[i]);
        tr.add(n - a[i] + 1, 1);
    }
    tr.init(n);
    for(int i = 0; i < n; ++i) {
        inv[1] += tr.que(n - b[i]);
        tr.add(n - b[i] + 1, 1);
    }

    sort(a.begin(), a.end()), sort(b.begin(), b.end());
    for(int i = 0; i < n; ++i) {
        if(a[i] != b[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    for(int i = 1; i < n; ++i) {
        if(a[i] == a[i - 1]) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    if((inv[0] - inv[1]) % 2 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

ABC296G Polygon and Pointsψ(｀∇´)ψ

题面暂略。

是计算几何板子，之前寒假模拟赛的时候讨论过的 PIP 问题。

然后就是，直接用回转数算法是 \(O(n)\) 单次的。

因为你就算使用了叉积，你也只能对于一条直线判断点的位置。

但是我们可以以多边形的重心为极点建极坐标系。

设询问点为 \((\theta, d)\)，我们只需要在凸包上二分一条极角相近的边，看一下叉积的大小即可。

因为这样等于人为给点划分了一个“区域”，方便找到一个边进行判定。

复杂度 \(O(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
// author : black_trees

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

#define endl '\n'

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

const int si = 2e5 + 10;

int n, p, x[si << 1], y[si << 1];
ldb fx, fy;
ldb ang[si << 1];

int main() {

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

    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
        x[i + n] = x[i], y[i + n] = y[i];
        fx += x[i], fy += y[i];
    }
    fx /= (1.0 * n), fy /= (1.0 * n);
    for(int i = 1; i <= n; ++i) {
        ldb val = atan2(y[i] - fy, x[i] - fx);
        if(val < ang[p]) p = i;
        ang[i] = ang[i + n] = val;
    }

    int q; cin >> q;
    while(q--) {
        int dx, dy; cin >> dx >> dy;
        int it = lower_bound(ang + p, ang + p + n, atan2(dy - fy, dx - fx)) - ang;
        i64 outer_product = 1ll * (x[it] - x[it - 1]) * (dy - y[it - 1]) - 
                            1ll * (y[it] - y[it - 1]) * (dx - x[it - 1]) ;
        if(outer_product == 0) cout << "ON" << endl;
        if(outer_product >  0) cout << "IN" << endl;
        if(outer_product <  0) cout << "OUT" << endl;
    }

    return 0;
}

ABC297F Minimum Bounding Box 2ψ(｀∇´)ψ

题面暂略。

有两种计算方式，不过计算起来都差不多。

考虑最暴力的枚举点：设 \(S\) 表示枚举的点集，有 \(|S| = k\)。

则有：\(ans = \dfrac{\sum\limits_{S} f(S)}{\dbinom{H\cdot W}{k}}\)，其中 \(f(S)\) 为包含点集 \(S\) 的所有点的最小矩形 \(R\) 的大小。

考虑拆开：\(ans = \sum\limits_{S}\sum\limits_{(x, y) \in R} 1\)，这样不好算，所以我们 交换 Sigma，这里不是简单的交换，要考虑实际意义，下标里面的 \(\in R\) 不好考虑，我们丢出来就能直接交换了

可以得到 \(ans = \sum\limits_{S} \sum\limits_{(x, y)}1 [(x, y) \in R]\)，交换之后：\(ans = \sum\limits_{(x,y)}\sum\limits_{S} 1 [(x, y) \in R]\)，此时式子是正确的。

为啥交换 Sigma 呢？我们考虑交换后的式子的意义，本质上是，枚举每一个点 \((x, y)\)，考虑有多少个点集，使得这个点集构成的 \(R\) 包含了 \((x, y)\)，此时计算起来就容易多了。

这里可以容斥算，不过还是有点麻烦？

另一种更直接的方式是，我们设 \(f(h, w)\) 表示在 \(h \cdot w\) 的矩形当中放 \(k\) 个点，且这个矩形恰好是包含这 \(k\) 个点的最小矩形。

这个乍一看不好算，但是可以考虑更本质的问题，要求最小，就是考虑四条边上都有点。

这里要考虑边上，点上，不太好搞对吧？

但是一看就是容斥，就，抽象成四个条件，\(2^4\) 容斥一下就好了。

容斥的时候对应的方案数可以用更小的 \(f\) 值算，所以这本质是个容斥套 dp。

算出来之后平移一下即可

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

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

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

using namespace std;
using i64 = long long;

const int si = 1e6 + 10;
const int mod = 998244353;

int inv[si], fact[si], invf[si];
void init(int n) {
    inv[1] = 1, fact[0] = invf[0] = 1;
    for(int i = 2; i <= n; ++i)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 1; i <= n; ++i)
        fact[i] = 1ll * fact[i - 1] * i % mod,
        invf[i] = 1ll * invf[i - 1] * inv[i] % mod;
}
int C(int n, int m) {
    if(m < 0 || n < m) return 0;
    return 1ll * fact[n] * invf[n - m] % mod * invf[m] % mod;
}
int qpow(int a, int b) {
    int ret = 1ll % mod;
    for(; b; b >>= 1) {
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
    }
    return ret % mod;
}

signed main() {

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

    int n, m, k;
    cin >> n >> m >> k;
    if(k == 1) { cout << "1" << endl; return 0; }
    init(si - 10);

    int ret = 0, ans = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            ret = 0;
            for(int u = 0; u <= 2; ++u) {
                for(int v = 0; v <= 2; ++v) {
                    int t = (u == 1 ? -2 : 1) * (v == 1 ? -2 : 1);
                    (ret += t * C((i - u) * (j - v), k) + mod) %= mod;
                }
            }
            ret = ret % mod * i % mod * j % mod * (n - i + 1ll + mod) % mod * (m - j + 1ll + mod) % mod, (ans += ret) %= mod;
        }
    }
    ans *= qpow(C(n * m, k), mod - 2);
    cout << (ans + mod) % mod << endl;

    return 0;
}

ABC297G Constrained Nim 2ψ(｀∇´)ψ

题面暂略。

手推可以发现 \(\text{SG}(x) = x \pmod (l + r) / l\)。

具体过程暂时省略。

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

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

#define endl '\n'

using namespace std;
using i64 = long long;

int n, l, r;
int Sg(int v) { return v % (l + r) / l; }

int main() {

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

    int ret = 0; cin >> n >> l >> r;
    for(int i = 1, x; i <= n; ++i)
        cin >> x, ret ^= Sg(x);
    cout << (ret ? "First" : "Second") << endl;

    return 0;
}

ABC298F Rock Scoreψ(｀∇´)ψ

题面暂略

首先是惯用套路，对于 \(x,y\) 分别存一下位置（并且离散化）

注意到最优的位置一定是保存了的 \(x, y\) 的交界处。

但是这样复杂度就 \(O(N^2)\) 了，咋搞呢，因为 \(sx + sy\) 的时候还是要减去交界位置的值的。

那么就不能直接分别枚举 \(x, y\) 然后两个最大值相加。

但是其实会减去的位置只有给出来的 \(O(N)\) 个，所以我们其实可以扫描 \(x\)，并且对所有 \(y\) 保存一个 set，从大到小排序。

遇到交界处有值的直接 skip，直到找到一个最大的位置（就是 set 中的第一个合法位置）就行了。

可以证明我们 skip 的次数一定是 \(O(N)\) 级别的（某个点在某个 \(x\) 被 skip 了，那么之后肯定不会 skip 了啊）。

然后就简单的做完了。

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

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

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

using namespace std;
using i64 = long long;

const int si = 4e5 + 10;

int n;
int x[si], y[si], v[si];
int rx[si], ry[si];
int sx[si], sy[si];
std::vector<int> d;
int val(int x) { return lower_bound(d.begin(), d.end(), x) - d.begin() + 1; }
std::map<std::pair<int, int>, int> mp;

signed main() {

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

    cin >> n, mp.clear(), d.clear();
    for(int i = 1; i <= n; ++i)
        cin >> x[i] >> y[i] >> v[i], d.push_back(x[i]), d.push_back(y[i]);
    sort(d.begin(), d.end()); d.erase(unique(d.begin(), d.end()), d.end());
    for(int i = 1; i <= n; ++i) {
        rx[i] = val(x[i]), ry[i] = val(y[i]);
        sx[rx[i]] += v[i], sy[ry[i]] += v[i];
        mp[make_pair(rx[i], ry[i])] = v[i];
    }

    int ans = -1;
    for(int i = 1; i <= n; ++i)
        ans = max(ans, sx[rx[i]] + sy[ry[i]] - v[i]);
    std::vector<std::pair<int, int>> a;
    for(int i = 1; i <= (int)d.size(); ++i) 
        a.push_back(make_pair(sy[i], i));
    sort(a.begin(), a.end()); reverse(a.begin(), a.end());
    for(int i = 1; i <= (int)d.size(); ++i) {
        for(int j = 0; j < (int)a.size(); ++j) {
            auto [va, id] = a[j];
            if(mp[make_pair(i, id)] != 0) continue;
            ans = max(ans, sx[i] + va); break;
        }
    }
    cout << ans << endl;
    return 0;
}
最后更新: May 9, 2023