GXOI / GZOI 2019 大赏

2020-04-18

从 LOJ 的通过人数可以看出, 这里没有毒瘤题.

假的, 都是毒瘤.

「GXOI / GZOI2019」与或和

题目链接

解题思路

在二进制下逐位考虑, 那么此时的矩阵就是 0-1 矩阵.

如果子矩阵 AND 值为 $1$, 则子矩阵内都为 $1$.

同理, 如果子矩阵 OR 值为 $1$, 则子矩阵任意存在一个 $1$ 即可.

先考虑 AND 的情况.

记 $f(i, j)$ 为位置 $(i, j)$ 上方 (包含 $(i, j)$) 最多 $1$ 的个数. 那么固定行的位置 $i$, 从左向右枚举列的位置 $j$, 每个位置 $(i, j)$ 对全 $1$ 子矩阵的贡献可看作 $f(i, j)$ 向左延伸的最大距离, 用单调栈维护这个过程即可.

OR 的情况类似. 任意存在一个 $1$ 的情况不好统计, 如果枚举矩阵中每一个位置 $(i, j)$, 那么以这个位置为右下角的子矩阵共有 $i \times j$ 个. 可以用所有情况减去子矩阵内都为 $0$ 的情况. 这样就 AND 一样了.

时间复杂度 $(n ^ 2 \log A)$, 其中 $A$ 为矩阵内最大值.

代码实现

随手打了个 $998244353$ 作为模数结果调半天的是屑…

> 点击显示 / 隐藏 
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
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 1e3 + 5, P = 1e9 + 7;

int n;
int A[MAXN][MAXN];

int f[MAXN];
int stk[MAXN], top;

int solve1(const int& k) {
    int ret = 0;
    for (int j = 1; j <= n; ++j) f[j] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            f[j] = ((A[i][j] >> k) & 1)? f[j] + 1: 0;
        int s = stk[top = 0] = 0;
        for (int j = 1; j <= n; ++j) {
            s += f[j];
            while (top > 0 && f[stk[top]] > f[j])
                s -= (stk[top] - stk[top - 1]) * (f[stk[top]] - f[j]), --top;
            stk[++top] = j;
            ret = (ret + s) % P;
        }
    }
    return (1LL << k) * ret % P;
}

int solve2(const int& k) {
    int ret = 0;
    for (int j = 1; j <= n; ++j) f[j] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            f[j] = ((A[i][j] >> k) & 1)? 0: f[j] + 1;
        int s = stk[top = 0] = 0;
        for (int j = 1; j <= n; ++j) {
            s += f[j];
            while (top > 0 && f[stk[top]] > f[j])
                s -= (stk[top] - stk[top - 1]) * (f[stk[top]] - f[j]), --top;
            stk[++top] = j;
            ret = (ret + (i * j - s)) % P;
        }
    }
    return (1LL << k) * ret % P;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n);
    int MxA = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            read(A[i][j]), MxA = max(MxA, A[i][j]);
    // solve
    int a1 = 0, a2 = 0;
    for (int k = 0; (1LL << k) <= MxA; ++k)
        a1 = (a1 + solve1(k)) % P, a2 = (a2 + solve2(k)) % P;
    // output
    printf("%d %d\n", a1, a2);
    return 0;
}

「GXOI / GZOI2019」宝牌一大堆

题目链接

解题思路

麻将题.

首先考虑 “国士无双” 和 “七对子”. 前者枚举 $14$ 张牌中选择哪一张牌出现两次, 统计分数即可. 后者选择分数最高的 $7$ 组雀头即可.

注意到 $\binom{4}{4} = 1 < \binom{4}{3} = 4$, 在题目条件下, 即使是宝牌, 组合成杠子一定不优. 所以现在需要考虑的部分只有 “$3 \times 4 + 2$”.

如果之前有做过其他麻将 / 斗地主一类的题, 容易有高维 DP 的思路.

现在需要注意顺子, 刻子, 以及雀头的个数. 记 $f(i, j, k, l, s)$ 表示考虑完第 $i$ 张牌, 共组合成 $j$ 组面子, 准备以第 $i-1$ 张牌开始的顺子有 $k$ 组, 准备以第 $i$ 张牌开始的顺子有 $l$ 组, 且雀头的个数为 $s$.

以顺子为例, 记 $s$ 为第 $i + 1$ 张牌加入 $c$ 张时对分数的贡献, $\operatorname{Cnt}(i + 1)$ 为第 $i + 1$ 张牌剩余个数, 那么有

剩下的刻子和雀头的转移类似, 也就是在顺子的基础上多挑出一些牌组成刻子 / 雀头.

还有一些值得注意的地方:

  1. 三组顺子和三组刻子的等价的, 每次枚举顺子组数不超过 $2$ 即可.
  2. 形同 8m, 9m, ..., E, N, ..., Z, B, ... 的牌型不能组成顺子, 在枚举 $k$, $l$ 的时候需要特判.
  3. 在遇到 $f$ 为 $0$ 的情况可以避免不必要的转移.

记 $n = 34 \times 5 \times 3 \times 3 \times 2 \times 5 = 15300$, 那么时间复杂度为 $O(T 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
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
// LOJ #3084
// DeP
#include <bits/stdc++.h>
using namespace std;

template<typename T> inline void ckmax(T& x, const T& y) { if (x < y) x = y; }

typedef long long LL;
const int MAXN = 16, MAXM = 35;

int C[MAXN][MAXN];

int n;
int Cnt[MAXM], isDora[MAXM];

map<string, int> Mahj;

void Prepare() {
    // binom
    C[0][0] = C[1][0] = C[1][1] = 1;
    for (int i = 2; i < MAXN; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
    // string --> type
    string s;
    for (int i = 1; i <= 9; ++i)
        s = "m", Mahj[char('0' + i) + s] = 0 + i;
    for (int i = 1; i <= 9; ++i)
        s = "p", Mahj[char('0' + i) + s] = 9 + i;
    for (int i = 1; i <= 9; ++i)
        s = "s", Mahj[char('0' + i) + s] = 18 + i;
    Mahj["E"] = 28, Mahj["S"] = 29, Mahj["W"] = 30, Mahj["N"] = 31;
    Mahj["Z"] = 32, Mahj["B"] = 33, Mahj["F"] = 34;
}

LL Normal() {
    static LL f[MAXM][5][3][3][2];
    // init
    memset(f, 0, sizeof f);
    // solve
    f[0][0][0][0][0] = 1;
    for (int i = 0; i + 1 < MAXM; ++i) for (int j = 0; j <= 4; ++j)
        for (int k = 0; k <= 2 && j + k <= 4; ++k) {
            if (k > 0 && (i == 9 || i == 18 || i >= 27)) break;
            for (int l = 0; l <= 2 && j + k + l <= 4; ++l) {
                if (l > 0 && (i == 9 || i == 18 || i >= 27)) break;
                if (!f[i][j][k][l][0] && !f[i][j][k][l][1]) continue;
                for (int c = k + l; c <= Cnt[i + 1]; ++c) {
                    LL s = C[Cnt[i + 1]][c] * (1LL << (c * isDora[i + 1]));
                    LL f0 = s * f[i][j][k][l][0], f1 = s * f[i][j][k][l][1];
                    // Shuntsu
                    if (j + k <= 4 && c - k - l <= 2) {
                        ckmax(f[i + 1][j + k][l][c - k - l][0], f0);
                        ckmax(f[i + 1][j + k][l][c - k - l][1], f1);
                    }
                    // Koutsu
                    if (j + k + 1 <= 4 && c - k - l - 3 >= 0) {
                        ckmax(f[i + 1][j + k + 1][l][c - k - l - 3][0], f0);
                        ckmax(f[i + 1][j + k + 1][l][c - k - l - 3][1], f1);
                    }
                    // Jantou
                    if (j + k <= 4 && c - k - l - 2 >= 0)
                        ckmax(f[i + 1][j + k][l][c - k - l - 2][1], f0);
                }
            }
        }
    return f[MAXM - 1][4][0][0][1];
}

inline LL KokushiMusou() {
    static int Need[] = { 1, 9, 10, 18, 19, 27, 28, 29, 30, 31, 32, 33, 34 };
    for (int i = 0; i < 13; ++i)
        if (Cnt[Need[i]] == 0) return 0;
    LL ret = 0;
    for (int i = 0; i < 13; ++i) {
        const int& dmahj = Need[i];
        LL now = 1;
        for (int j = 0; j < 13; ++j) if (j != i) {
            const int& smahj = Need[j];
            now *= C[Cnt[smahj]][1] * (1LL << isDora[smahj]);
        }
        ret = max(now * C[Cnt[dmahj]][2] * (1LL << (2 * isDora[dmahj])), ret);
    }
    return 13 * ret;
}

inline LL SevenTiles() {
    static LL Points[MAXM];
    int tot = 0;
    for (int i = 1; i < MAXM; ++i) if (Cnt[i] >= 2)
        Points[tot++] = C[Cnt[i]][2] * (1LL << (2 * isDora[i]));
    if (tot < 7) return 0;
    sort(Points, Points + tot, greater<LL>());
    LL ret = 1;
    for (int i = 0; i < 7; ++i) ret *= Points[i];
    return 7 * ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int Ti;
    cin >> Ti;
    Prepare();
    while (Ti--) {
        static string S;
        // init
        memset(isDora, 0, sizeof isDora);
        for (int i = 1; i < MAXM; ++i) Cnt[i] = 4;
        // input
        while (cin >> S && S[0] != '0')
            --Cnt[Mahj[S]];
        while (cin >> S && S[0] != '0')
            isDora[Mahj[S]] = 1;
        // solve & output
        cout << max(max(KokushiMusou(), SevenTiles()), Normal()) << '\n';
    }
    return 0;
}

「GXOI / GZOI2019」特技飞行

题目链接

解题思路

很贴切实际地, 嘉宾团看到的动作和实际在哪个交点选择哪个操作并没有关系, 对答案的贡献只和观察范围内的交点个数有关.

所以题目可分作两个部分. 第一部分考虑交点的动作选择, 第二部分统计嘉宾团观察交点个数.

考虑如何处理第一部分.

注意到两直线相交的条件为 $y_0$ 和 $y_1$ 在 $x_{st}$ 处和 $x_{ed}$ 处的呈逆序, 并保证直线交点个数不大 ($\le 500,000$). 那么直接枚举直线, 暴力统计所有满足的直线计算交点即可. 具体可通过在 set 中二分实现.

设不计嘉宾团的影响下的答案为 $w$, 选择 $x$ 处交点交换, 共有 $m$ 个交点. 则有

容易发现 $w$ 是关于 $x$ 的一次函数, 其极值显然在 $x$ 的上下界处取到.

一个显然的上界是交点个数. 注意到交换航线的操作并不影响纵坐标相对顺序, “能交换就交换” 一定能保持原有的相对位置.

如果将一个位置向在终点处对应位置的实际编号连边, 一定会构成多个环. 实际上是多个置换. 而让大小为 $l$ 的环有序的交换次数为 $l - 1$.

记环个数为 $c$, 总次数为

此处 DFS 遍历一遍所有环统计个数即可.

考虑如何处理第二部分.

倾斜的正方形不好处理, 考虑旋转坐标轴, 使得正方形的边同坐标轴平行即可. 这里我将坐标轴逆时针旋转 $\frac{\pi}{4}$, 并将横纵坐标同时乘 $\sqrt 2$, 得出原坐标系下点 $(x, y)$ 在旋转后的坐标系中坐标为 $(x + y, y - x)$.

此时直接二维数点即可. 拆成扫描线后是经典问题, 同时只需要 BIT 即可实现.

记交点个数为 $m$, 那么时间复杂度为 $O\big( n \log n + (m + k) \log (m + k) \big)$.

代码实现

想清楚细节之后写起来就十分快乐, 调试的时候就非常快乐了 (

> 点击显示 / 隐藏 
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
// LOJ #3085
// DeP
#include <set>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
typedef pair<int, int> Pii;

const int MAXN = 1e5 + 5, MAXM = 5e5 + 5;

namespace Geo {
    const double EPS = 1e-9;

    inline int dcmp(const double& p) {
        return (fabs(p) < EPS)? 0: (p < 0? -1: 1);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0.0, double _y = 0.0): x(_x), y(_y) { }
        Vector operator + (const Vector& rhs) const { return Vector(x + rhs.x, y + rhs.y); }
        Vector operator - (const Vector& rhs) const { return Vector(x - rhs.x, y - rhs.y); }
        Vector operator * (const double& p) const { return Vector(p * x, p * y); }
    };
    typedef Vector Point;

    inline double Dot(const Vector& A, const Vector& B) {
        return A.x * B.x + A.y * B.y;
    }
    inline double Cross(const Vector& A, const Vector& B) {
        return A.x * B.y - A.y * B.x;
    }

    inline Point LineIntersection(Point P, Vector v, Point Q, Vector w) {
        return P + v * (Cross(w, P - Q) / Cross(v, w));
    }
}
using namespace Geo;

int n, K, a, b, c, xst, xed;
int Y0[MAXN], Y1[MAXN];

int nP;
int pre[MAXN], vis[MAXN];
Point P[MAXM];

void FindLineIntersection() {
    static set<Pii> S;
    nP = 0;
    for (int i = 1; i <= n; ++i) {
        Point p1 = Point(xst, Y0[i]), p2 = Point(xed, Y1[i]);
        for (auto ite = S.lower_bound(Pii(Y1[i], i)); ite != S.end(); ++ite) {
            const int& j = ite->second;
            Point p3 = Point(xst, Y0[j]), p4 = Point(xed, Y1[j]);
            P[++nP] = LineIntersection(p1, p2 - p1, p3, p4 - p3);
        }
        S.insert(Pii(Y1[i], i));
    }
    int cur = 0;
    for (auto v: S) pre[++cur] = v.second;
}

void dfs(const int& u) { if (!vis[u]) vis[u] = true, dfs(pre[u]); }

namespace BIT {
    int n, C[MAXM + MAXN * 2];

    inline int lowbit(const int& x) { return x & -x; }

    inline void Mdy(const int& p, const int& v) {
        for (int i = p; i <= n + 1; i += lowbit(i)) C[i] += v;
    }
    inline void Mdy(const int& L, const int& R, const int& v) {
        Mdy(L, v), Mdy(R + 1, -v);
    }

    inline int Qry(const int& p) {
        int ret = 0;
        for (int i = p; i; i -= lowbit(i)) ret += C[i];
        return ret;
    }
}

inline Point Trans(const double& x, const double& y) {
    return Point(x + y, y - x);
}

struct Ask {
    double x, L, R; int type;
    Ask() = default;
    Ask(double _x, double _L, double _R, int _t): x(_x), L(_L), R(_R), type(_t) { }
    bool operator < (const Ask& rhs) const {
        return (dcmp(x - rhs.x) != 0)? x < rhs.x: type < rhs.type;
    }
} Q[MAXN * 2 + MAXM];

int UselessGuest() {
    static double B[MAXN * 2 + MAXM];
    // input
    read(K);
    int nq = 0, nB = 0;
    for (int p, q, r, i = 1; i <= K; ++i) {
        read(p), read(q), read(r);
        double r0 = p - r + q, r1 = p + q + r, c1 = q - p + r, c0 = q - p - r;
        Q[++nq] = Ask(r0, c0, c1, 1), Q[++nq] = Ask(r1, c0, c1, -1);
        B[++nB] = c0, B[++nB] = c1;
    }
    for (int i = 1; i <= nP; ++i) {
        Point p = Trans(P[i].x, P[i].y);
        Q[++nq] = Ask(p.x, p.y, p.y, 0), B[++nB] = p.y;
    }
    // pre done
    sort(B + 1, B + 1 + nB);
    nB = unique(B + 1, B + 1 + nB) - B - 1;
    sort(Q + 1, Q + 1 + nq);
    // solve
    int ret = 0;
    BIT::n = nB;
    for (int i = 1; i <= nq; ++i) {
        if (Q[i].type == 0) {
            int p = lower_bound(B + 1, B + nB + 1, Q[i].L) - B;
            ret += (BIT::Qry(p) > 0);
        } else {
            int L = lower_bound(B + 1, B + nB + 1, Q[i].L) - B,
                R = lower_bound(B + 1, B + nB + 1, Q[i].R) - B;
            BIT::Mdy(L, R, Q[i].type);
        }
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(a), read(b), read(c), read(xst), read(xed);
    for (int i = 1; i <= n; ++i) read(Y0[i]);
    for (int i = 1; i <= n; ++i) read(Y1[i]);
    // solve
    FindLineIntersection();
    int CircleCnt = 0;
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) dfs(i), ++CircleCnt;
    int bonus = UselessGuest();
    // output
    LL a1 = a * nP, a2 = (a - b) * (n - CircleCnt) + b * nP;
    if (a1 > a2) swap(a1, a2);
    printf("%lld %lld\n", a1 + 1LL * bonus * c, a2 + 1LL * bonus * c);
    return 0;
}

「GXOI / GZOI2019」逼死强迫症

题目链接

解题思路

推了个 12 x 12 的矩阵当场弃疗, 翻题解结果只需要 4 x 4…

假定不考虑 $1 \times 1$ 方砖的影响, 那么剩下的就是经典问题了, 其方案数为 Fibonacci 数列, 并记 Fibonacci 数列第 $n$ 项为 $f_n$, 同时有 $f_0 = 1$.

如果将两个 $1\times 1$ 方砖填入 $2 \times n$ 的格子, 且要求两方砖分别处于第一列和最后一列, 那么只在 $n \ge 3$ 的情况下有合法方案, 可能的方案只有两种, 且具体排布方式和 $n$ 的奇偶性相关.

此时可以得到这样的思路: 枚举两方砖的间距, 将整体分成两部分, 统计方案数. 可以得出方案数为

卷积! 卷个锤子. 交换求和顺序, 得

设 Fibonacci 数列的前缀和第 $n$ 项为 $s_n$, 有 $s_n = s_{n - 1} + s_{n - 2} + 1 = f_{n + 2} - 1$. 归纳可证.

带入原式, 得

设 $g_n = \sum\limits_{ i = 0 } ^ n f_i \cdot f_{n - i}$, 那么可化为

现在的问题在于如何快速求出 $g_n$.

想必大家都知道接下来要做什么

设 $\mathbf{A_{n}} = \begin{bmatrix} f_{n - 1} \ f_n \ g_{n - 1} \ g_{n} \end{bmatrix}$, 有

矩阵快速幂即可.

时间复杂度为 $O(T \cdot 4 ^ 3 \log n)$.

那个 12 x 12 的矩阵是大力设状态, xjb 转移的产物.

代码实现

> 点击显示 / 隐藏 
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
// LOJ #3086
// DeP
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXM = 4, P = 1e9 + 7;

const int A[MAXM][MAXM] = {
    { 0, 1, 0, 0 }, { 1, 1, 0, 0 }, { 0, 0, 0, 1 }, { 1, 1, 1, 1 }
};
const int B[MAXM][MAXM] = {
    { 1, 0, 0, 0 }, { 1, 0, 0, 0 }, { 1, 0, 0, 0 }, { 2, 0, 0, 0 }
};

struct Matrix {
    int g[MAXM][MAXM];
    Matrix() { memset(g, 0, sizeof g); }
    Matrix operator * (const Matrix& rhs) const {
        Matrix ret;
        for (int i = 0; i < MAXM; ++i)
            for (int k = 0; k < MAXM; ++k)
                for (int j = 0; j < MAXM; ++j)
                    ret.g[i][j] = (ret.g[i][j] + 1LL * g[i][k] * rhs.g[k][j] % P) % P;
        return ret;
    }
    inline void init() {
        for (int i = 0; i < MAXM; ++i) g[i][i] = 1;
    }
};

Matrix fpow(Matrix base, int b) {
    Matrix ret; ret.init();
    while (b > 0) {
        if (b & 1) ret = ret * base;
        base = base * base, b >>= 1;
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti, n;
    scanf("%d", &Ti);
    Matrix res, base;
    for (int i = 0; i < MAXM; ++i)
        for (int j = 0; j < MAXM; ++j) base.g[i][j] = A[i][j];
    while (Ti--) {
        scanf("%d", &n);
        if (n <= 2) { puts("0"); continue; }
        for (int i = 0; i < MAXM; ++i)
            for (int j = 0; j < MAXM; ++j) res.g[i][j] = B[i][j];
        res = fpow(base, n - 2) * res;
        int g1 = res.g[3][0], f1 = res.g[1][0], f2 = res.g[0][0];
        printf("%lld\n", ((2LL * g1 - 2LL * f2 - 4LL * f1 + 2) % P + P) % P);
    }
    return 0;
}

「GXOI / GZOI2019」旅行者

题目链接

解题思路

并不优美的题.

我们称 $k$ 座感兴趣的城市为关键点.

官方题解有一个时间复杂度为 $O(T \cdot m \log m \log k)$ 的做法:

每次枚举关键点在二进制下的每一位, 按二进制下该位在值将关键点分作两个部分. 建立源点 $s$ 向某一部分连边, 边权为 $0$. 建立汇点 $t$, 令另一部分向 $t$ 连边, 边权为 $0$. 此时 $s$ 到 $t$ 的最短路即为第一部分关键点到另一部分关键点距离的最小值. 重复 $\log k$ 次即可.

但是还存在时间复杂度为 $O(T \cdot m \log m)$ 的做法.

同样建立源点 $s$, 向所有关键点连边, 边权为 $0$, 求 $s$ 出发的最短路. 在反图上建立源点 $s$, 向所有关键点连边, 边权为 $0$, 在反图上再次求以 $s$ 为起点的最短路.

两次求最短路的同时, 分别记录到达点 $u$ 的最短路长度 $d_1(u), d_2(u)$, 以及 $p_1(u), p_2(u)$, 表示到达 $u$ 的最短路是从关键点 $p(u)$ 出发的.

对于关键点间最短距离, 其路径上一定不存在另一个关键点. 那么, 枚举每条边 $(u, v, w)$, 在保证 $p_1(u) \neq p_2(v)$ 的情况下用 $d_1(u) + w + d_2(v)$ 更新答案即可.

具体实现时不需要显式地建出 $s$. 因为 $s$ 到关键点一定是最短路, 直接将最短路长度初始化后丢进堆里就好了.

由于只跑两次最短路, 使用 priority_queue 实现的 Dijkstra, 时间复杂度为 $O(T \cdot m \log m)$.

我实在看不懂那些长篇大论的题解在证个什么.

代码实现

> 点击显示 / 隐藏 
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
// LOJ #3087
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 19 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    }
}
using IO::read;

typedef long long LL;
typedef pair<LL, int> Pli;

const int MAXN = 1e5 + 5, MAXM = 5e5 + 5;

int n, m, K;
int A[MAXN];
int U[MAXM], V[MAXM], W[MAXM];

LL d1[MAXN], d2[MAXN];
int p1[MAXN], p2[MAXN];

namespace Graph {
    struct Edge { int nxt, to, w; } edges[MAXM];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to, int w) {
        edges[++eidx] = (Edge){ head[from], to, w }, head[from] = eidx;
    }

    void Dijkstra(int* pre, LL* d) {
        priority_queue<Pli, vector<Pli>, greater<Pli> > PQ;
        for (int u, i = 1; i <= K; ++i)
            u = A[i], PQ.push(Pli(d[u] = 0, u)), pre[u] = u;
        while (!PQ.empty()) {
            int u = PQ.top().second; LL w = PQ.top().first; PQ.pop();
            if (w != d[u]) continue;
            for (int v, i = head[u]; ~i; i = edges[i].nxt)
                if ((d[v = edges[i].to] > d[u] + edges[i].w))
                    pre[v] = pre[u], PQ.push(Pli(d[v] = d[u] + edges[i].w, v));
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti;
    read(Ti);
    while (Ti--) {
        // init
        memset(d1, 0x3f, sizeof d1);
        memset(d2, 0x3f, sizeof d2);
        // input
        read(n), read(m), read(K);
        for (int i = 1; i <= m; ++i)
            read(U[i]), read(V[i]), read(W[i]);
        for (int i = 1; i <= K; ++i) read(A[i]);
        // predone 1
        Graph::init();
        for (int i = 1; i <= m; ++i) Graph::AddEdge(U[i], V[i], W[i]);
        Graph::Dijkstra(p1, d1);
        // predone 2
        Graph::init();
        for (int i = 1; i <= m; ++i) Graph::AddEdge(V[i], U[i], W[i]);
        Graph::Dijkstra(p2, d2);
        // solve
        LL ans = LLONG_MAX;
        for (int i = 1; i <= m; ++i) {
            const int &u = U[i], &v = V[i], &w = W[i];
            if (p1[u] != p2[v]) ans = min(ans, d1[u] + d2[v] + w);
        }
        // output
        printf("%lld\n", ans);
    }
    return 0;
}

「GXOI / GZOI2019」旧词

题目链接

解题思路

早已跌下神坛的树链剖分.

如果直接做, $x$ 的限制不好处理. 考虑离线, 动态加入 $x$ 的权值, 在一定的时机处理询问.

现在来讨论一个询问 $(x, y)$ 的答案, 同时称点 $u$ 的权值为 $A_u = \text{depth}(u) ^ k$. 经过上面的处理后, $y$ 的权值对答案的贡献次数为 $y$ 子树内已加入的节点数量.

形式化地, 记 $y$ 子树内已加入节点数量为 $s_y$, 那么其对答案的贡献为 $s_y \cdot A_y$. 以此类推, $y$ 的某个祖先对答案的贡献则需要抠去重复计算的部分, 即对于 $y$ 的祖先 $u$, 记 $y$ 和 $u$ 之间最靠近 $u$ 的节点为 $v$, 那么 $u$ 的答案的贡献为 $(s_u - s_v) \cdot A_u$.

然后… 然后我就不知道怎么维护了, 参考 mrsrz 的题解 之后可以发现

对给定树重链剖分, 直接维护每一条重链对答案的贡献, 接着考虑轻链对答案的影响.

借助重链剖分后轻重链的结构关系, 轻链两端点一定满足上述 $u$ 和 $v$ 之间的关系. 即计算答案时, 加上轻链顶和轻链底两节点 $s_u$ 的差值乘上轻链顶节点的权值之后的结果.

修改时维护上述信息即可, 可以用 BIT 简单实现.

时间复杂度 $O(n \log k + q \log ^ 2 n)$.

还有一种做法为类似树上差分的思路, 将 LCA 处的值 “平摊” 到根节点到 LCA 的路径上. 利用线段树打上计算次数的标记, 维护权值的增量, 询问时求标记和增量乘积的和就好了.

代码实现

> 点击显示 / 隐藏 
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
// LOJ #3088
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 5e4 + 5, MAXQ = 5e4 + 5, P = 998244353;

int fpow(int base, int b) {
    int ret = 1;
    while (b > 0) {
        if (b & 1) ret = 1LL * ret * base % P;
        base = 1LL * base * base % P, b >>= 1;
    }
    return ret;
}

struct Ask {
    int idx, x, y;
    bool operator < (const Ask& rhs) const {
        return x < rhs.x;
    }
} Q[MAXQ];

int n, q, K;
int pre[MAXN], dfn[MAXN];
int A[MAXN], f[MAXN], Ans[MAXN], depth[MAXN];

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXN];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
    }
}

inline int lowbit(const int& x) { return x & -x; }

namespace BIT1 {
    int C[MAXN];

    inline void Mdy(const int& p, const int& v) {
        for (int i = p; i <= n + 1; i += lowbit(i)) C[i] += v;
    }
    inline void Mdy(const int& L, const int& R, const int& v) {
        Mdy(L, v), Mdy(R + 1, -v);
    }

    inline int Qry(const int& p) {
        int ret = 0;
        for (int i = p; i; i -= lowbit(i)) ret += C[i];
        return ret;
    }
    inline int Dff(const int& u, const int& v) {
        return Qry(dfn[u]) - ((v > 0)? Qry(dfn[v]): 0);
    }
}

namespace BIT2 {
    int C[MAXN];

    inline void Mdy(const int& p, const int& v) {
        for (int i = p; i <= n; i += lowbit(i)) C[i] = (C[i] + v) % P;
    }

    inline int Qry(const int& p) {
        int ret = 0;
        for (int i = p; i; i -= lowbit(i)) ret = (ret + C[i]) % P;
        return ret;
    }
    inline int Qry(const int& L, const int& R) {
        return ((Qry(R) - Qry(L - 1)) % P + P) % P;
    }
}

namespace HLD {
    using namespace Graph;
    int size[MAXN], son[MAXN], topfa[MAXN], clk;

    void dfs(int u) {
        son[u] = -1, size[u] = 1;
        depth[u] = depth[pre[u]] + 1;
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            dfs(v = edges[i].to), size[v] += size[u];
            if (son[u] == -1 || size[v] > size[son[u]]) son[u] = v;
        }
    }
    void dfs(int u, int top) {
        topfa[u] = top, dfn[u] = ++clk;
        if (~son[u]) dfs(son[u], top);
        for (int v, i = head[u]; ~i; i = edges[i].nxt)
            if ((v = edges[i].to) != son[u]) dfs(v, v);
    }

    inline void solve(int rt = 1) { dfs(rt), dfs(rt, rt); }

    void Mdy(const int& p) {
        for (int u = p; u > 0; u = pre[topfa[u]]) {
            BIT1::Mdy(dfn[topfa[u]], dfn[u], 1);
            BIT2::Mdy(dfn[u], -f[u]);
            BIT2::Mdy(dfn[u], f[u] = 1LL * A[u] * BIT1::Dff(u, son[u]) % P);
        }
    }

    int Qry(const int& p) {
        int ret = 0;
        for (int u = p, lst = 0; u > 0; u = pre[topfa[u]]) {
            ret = (ret + 1LL * A[u] * BIT1::Dff(u, lst) % P) % P;
            if (u != topfa[u])
                ret = (ret + BIT2::Qry(dfn[topfa[u]], dfn[pre[u]])) % P;
            lst = topfa[u];
        }
        return ret;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init();
    // input
    read(n), read(q), read(K);
    for (int i = 2; i <= n; ++i)
        read(pre[i]), Graph::AddEdge(pre[i], i);
    for (int x, y, i = 1; i <= q; ++i)
        read(x), read(y), Q[i] = (Ask){ i, x, y };
    // solve
    HLD::solve(1);
    for (int u = 1; u <= n; ++u) A[u] = fpow(depth[u], K);
    sort(Q + 1, Q + q + 1);
    for (int x = 1, i = 1; i <= q; ++i) {
        const Ask& p = Q[i];
        while (x <= n && x <= p.x) HLD::Mdy(x++);
        Ans[p.idx] = HLD::Qry(p.y);
    }
    // output
    for (int i = 1; i <= q; ++i) printf("%d\n", Ans[i]);
    return 0;
}
© 2019-2023 DepletedPrism's Blog - Powered by Hexo - Theme Chan