暑假集训 杭电多校 Round 6

比赛链接

补题链接

「1004」 Count

签到题，\(n \not= k\) 时答案为 \(m ^ {n - k}\) ，\(n = k\) 时答案为 \(m ^ n\)。

时间复杂度：\(O(logn)\)

空间复杂度：\(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

const int mod = 998244353;
using i64 = long long;

void solve() {
    i64 n, m, k;
    std::cin >> n >> m >> k;
    i64 t = n - k ? n - k : n;
    i64 res = 1;
    while (t) {
        if (t & 1) res = (__int128_t)res * m % mod;
        m = (__int128_t)m * m % mod;
        t >>= 1;
    }

    std::cout << res << '\n';
}

int main() {
    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

「1002」 Pair Sum and Perfect Square

先枚举所有满足题意的 \(i、j\) 使得 \(p_i + p_j\) 为完全平方数，由于 \(P\) 在这里是 \(1\) 到 \(n\) 的排列，所以合法的 \((i, j)\) 只有 \(O(n ^ {\frac{3}{2}})\) 种可能，接下来就是一个二维数点的问题了，即对于每次查询的区间 \((L, R)\) ，需找到多少点 \((i, j)\) 落在 \((L, L)\) 和 \((R, R)\) 组成的正方形内。

时间复杂度：\(O(n ^ {\frac{3}{2}} + q(logq + logn))\)

空间复杂度：\(O(n + k)\)

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 <iostream>
#include <algorithm>
#include <cmath>

const int MAX_N = 5e5 + 5;
const int MAX_Q = 5e5 + 5;

int n;
int per[MAX_N];
int id[MAX_N];

int q;
struct Query {
    int x;
    int y;
    int id;
} query[4 * MAX_Q];
int res[4 * MAX_Q];

namespace __BIT {
    int tree[MAX_N];

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

    int prefix(int idx) {
        int res = 0;
        while (idx) {
            res += tree[idx];
            idx -= lowbit(idx);
        }

        return res;
    }

    void add(int idx, int val = 1) {
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }
}

using namespace __BIT;

void solve() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> per[i];
        id[per[i]] = i;
    }
    std::cin >> q;
    int all = 4 * q;
    for (int i = 0, l, r; i < all; i += 4) {
        std::cin >> l >> r;
        query[i] = {r, r, i};
        query[i + 1] = {l - 1, r, i + 1};
        query[i + 2] = {r, l - 1, i + 2};
        query[i + 3] = {l - 1, l - 1, i + 3};
    }
    std::sort(query, query + all, [](const Query& q1, const Query& q2) {
        return q1.x < q2.x;
    });
    int j = 0;
    for (int i = 1; i <= n; i++) {
        for (int t = 2; ; t++) {
            int pf = t * t - per[i];
            if (pf <= 0) continue;
            if (pf >= per[i]) break;
            while (j < all && i > query[j].x) {
                // 当前区间已经统计完成
                res[query[j].id] = prefix(query[j].y);
                j++;
            }
            add(id[pf]);
        }
    }
    while (j < all) {
        res[query[j].id] = prefix(query[j].y);
        j++;
    }
    for (int i = 0; i < all; i += 4) {
        std::cout << res[i] - res[i + 1] - res[i + 2] + res[i + 3] << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

「1006」 Perfect square number

使用一个数组动态维护所有跨越 \(a_i\) 的序列中增加 \(k \ (-300 \leq k \leq 300)\) 后序列和为完全平方数的个数。当迭代次数从 \(i - 1\) 转移到 \(i\) 时，我们只需要考虑更新以 \(a_i\) 开头的序列，同时减去以 \(a_{i - 1}\) 结尾的序列中计算过的冗余即可。

时间复杂度：\(O(n ^ 2 \sqrt{k})\)

空间复杂度：\(O(n + k)\)

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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

const int MAX_N = 300, MAX_K = 300;

int a[MAX_N + 5];
int s[MAX_N + 5];
inline int sum(int l, int r) {
    return s[r] - s[l - 1];
}
int lp[MAX_N + 5], rp[MAX_N + 5];
int plus[2 * MAX_K + 5];
inline int& get_plus(int k) {
    // 记录跨越当前 a[i] 的序列中有多少个序列增加 k 后为完全平方数
    return plus[k + MAX_K];
}

int ub(int x) {
    int t = std::sqrt(x);
    while (t * t < x) t++;

    return t;
}

bool check(int s) {
    int b = ub(s);
    return b * b == s;
}

void solve() {
    memset(plus, 0x00, sizeof(plus));
    memset(lp, 0x00, sizeof(lp));
    memset(rp, 0x00, sizeof(rp));
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= n; i++) {
        lp[i] += lp[i - 1];
        for (int j = 1; j <= i; j++) {
            if (check(sum(j, i))) lp[i]++;
        }
    }
    for (int i = n; i >= 1; i--) {
        rp[i] += rp[i + 1];
        for (int j = i; j <= n; j++) {
            if (check(sum(i, j))) rp[i]++;
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            int ds = sum(i, j);
            int b = ub(ds);
            for (int ib = b; ib * ib - ds <= MAX_K; ib++) {
                get_plus(ib * ib - ds)++;
            }
            for (int ib = b - 1; ib > 0 && ib * ib - ds >= -MAX_K; ib--) {
                get_plus(ib * ib - ds)++;
            }
        }
        for (int j = i - 1; j >= 1; j--) {
            int ds = sum(j, i - 1);
            int b = ub(ds);
            for (int ib = b; ib * ib - ds <= MAX_K; ib++) {
                get_plus(ib * ib - ds)--;
            }
            for (int ib = b - 1; ib > 0 && ib * ib - ds >= -MAX_K; ib--) {
                get_plus(ib * ib - ds)--;
            }
        }
        int p = 0;
        for (int k = -a[i] + 1; k <= MAX_K - a[i]; k++) p = std::max(p, get_plus(k));
        res = std::max(res, p + lp[i - 1] + rp[i + 1]);
    }

    std::cout << res << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

「1003」 Vector

若三个向量线性无关，则只需要判断 \(A_4\) 是否落在向量 \(A_1\) ，\(A_2\) ，\(A_3\) 的张集里面即可（由于相关系数只能是非负数，所以这里的张集是一个无穷大的三棱锥）；若三个向量线性相关，则其张集一定可以在一个平面内表示，此时用类似的方式判断 \(A_4\) 是否属于该集合即可。

这里要注意零向量的情况。

时间复杂度：\(O(1)\)

空间复杂度：\(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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
#include <iostream>

namespace __3dvector {
    using i64 = long long;
    struct Vec {
        i64 x, y, z;
        Vec(i64 _x = 0, i64 _y = 0, i64 _z = 0): x(_x), y(_y), z(_z) {}
    };
    Vec zero(0, 0, 0);
    bool operator==(const Vec& v1, const Vec& v2) {
        return v1.x == v2.x && v1.y == v2.y && v1.z == v2.z;
    }
    bool operator!=(const Vec& v1, const Vec& v2) {
        return v1.x != v2.x || v1.y != v2.y || v1.z != v2.z;
    }
    Vec operator+(const Vec& v1, const Vec& v2) {
        return Vec(v1.x + v2.x, v1.y + v2.y, v1.z + v2.z);
    }
    i64 dot(const Vec& v1, const Vec& v2) {
        return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
    }
    Vec cross(const Vec& v1, const Vec& v2) {
        return Vec(
            v1.y * v2.z - v1.z * v2.y,
            - v1.x * v2.z + v1.z * v2.x,
            v1.x * v2.y - v1.y * v2.x
        );
    }
}

using namespace __3dvector;

inline int sgn(i64 x) {
    return (x > 0) - (x < 0);
}

bool judge(const Vec& v1, const Vec& v2) {
    return sgn(v1.x) * sgn(v2.x) >= 0 && sgn(v1.y) * sgn(v2.y) >= 0 && sgn(v1.z) * sgn(v2.z) >= 0;
}

void solve() {
    Vec v[4];
    for (int i = 0; i < 4; i++) std::cin >> v[i].x >> v[i].y >> v[i].z;
    i64 x1 = v[0].x, x2 = v[1].x, x3 = v[2].x;
    i64 y1 = v[0].y, y2 = v[1].y, y3 = v[2].y;
    i64 z1 = v[0].z, z2 = v[1].z, z3 = v[2].z;
    
    i64 det = x1 * y2 * z3 + x2 * y3 * z1 + x3 * y1 * z2 - x3 * y2 * z1 - x2 * y1 * z3 - x1 * y3 * z2; // 计算行列式
    if (det) {
        Vec cr1 = cross(v[0], v[1]), cr2 = cross(v[1], v[2]), cr3 = cross(v[2], v[0]); // 3 个平面的法向量
        Vec vt = v[0] + v[1] + v[2];
        i64 dt1 = dot(vt, cr1);
        i64 d1 = dot(v[3], cr1), d2 = dot(v[3], cr2), d3 = dot(v[3], cr3);
        if (sgn(d1) * sgn(dt1) >= 0 && sgn(d2) * sgn(dt1) >= 0 && sgn(d3) * sgn(dt1) >= 0) {
            std::cout << "YES\n";
            return;
        }
    }
    else {
        // rank <= 2
        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 3; j++) {
                Vec cr = cross(v[i], v[j]);
                if (cr == zero) {
                    // v[i] 与 v[j] 平行
                    if (cross(v[3], v[i]) == zero && cross(v[3], v[j]) == zero && (v[i] != zero && judge(v[3], v[i]) || v[j] != zero && judge(v[3], v[j]))) {
                        std::cout << "YES\n";
                        return;
                    }
                    else if (v[i] == zero && v[j] == zero) {
                        if (v[3] == zero) {
                            std::cout << "YES\n";
                            return;
                        }
                    }
                }
                else {
                    // v[i] 与 v[j] 不平行
                    if (dot(v[3], cr) == 0) {
                        // 则 v[3] 必须与两个向量共面
                        Vec cri = cross(v[3], v[i]), crj = cross(v[3], v[j]);
                        Vec vt = v[i] + v[j];
                        Vec crit = cross(vt, v[i]), crjt = cross(vt, v[j]);
                        if (judge(cri, crit) && judge(crj, crjt)) {
                            std::cout << "YES\n";
                            return;
                        }
                    }
                }
            }
        }
    }

    std::cout << "NO\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}
ACM
#杭电多校
暑假集训 杭电多校 Round 6
https://goer17.github.io/2023/08/03/暑假集训 杭电多校 Round 6/
作者
Captain_Lee
发布于
2023年8月3日
许可协议