抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

七つの海

今日、海を見た。もう怖くない

博客

随笔

朋友

归档

关于

Nowcoder 2020 暑期多校训练 （2）

七海

题解

发布于：2020年7月13日

次浏览

比完看到群里一群 hack 老哥和暴躁老哥，萌新不敢说话（

3FUEYCMFGCVMO_XE2OY.png

看着带佬们讨论，发现争议的 hack，卡常数，栈空间等问题都和我们没有关系…… 那没事了（

A - All with Pairs

给定 n 个字符串，定义 f(s, t) 的值为满足 s 的前缀和 t 的后缀相等的最长长度，且不存在时为 0；

现要求计算出 \(\sum_{i=1}^n \sum_{j=1}^n f^2(s_i, s_j)\ mod\ 998244353\)；也就是说求给定的 n 个字符串中任意两个字符串的“公共前后缀”长度之在模意义下的和；

数据范围：n ≤ 1e5，Σ|s| ≤ 1e6；

和上一次多校的第一题一样，是我不喜欢的字符串题目，所以直接对着题解说好了：要求求出所有的两个字符串排列的最大公共顶针字串的长度在模意义下的和；因为字符串总长并不大，所以可以用 O(Σ|s|) 的时间预处理所有字符串的前/后缀哈希，利用哈希进行子串匹配；

接下来再遍历所有字符串的后/前缀，和已经预处理的哈希进行匹配即可；但是因为我们只计算最大公共子串长度的和，不必要的子串需要减掉，所以可以考虑使用 KMP 构建出 next 数组，然后利用这个 next 数组主动地去重；

仿造标程写的代码↓↓，并且重构了一下相关的板子：

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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <vector>

using namespace std;
using longs = long long;
using ulongs = unsigned long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 1, ch = getchar();
    while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

const uint N = 1e6 + 5;
const uint M = 1e5 + 5;
const uint mod = 998244353;

namespace StringHash
{
    using hashArray = vector<ulongs>;

    struct hashMachine
    {
        int base, offset;
        hashArray pow;

        static int idx(const char ch){return ch - 'a';}

        explicit hashMachine(int n, int b = 233, int k = 5): base(b), offset(k)
        {
            pow.resize(n);
            pow[0] = 1;
            for (int i = 1; i < n; ++ i)
                pow[i] = pow[i - 1] * base;
        }

        void make(const char *s, hashArray &var) const
        {
            int n = strlen(s);
            for (int i = 1; i <= n; ++ i)
                var[i] = var[i - 1] * base + idx(s[i - 1]) + offset;
        }

        ulongs get(hashArray &var, int l, int r) const
        {
            if (!l) return var[r];
            auto len = r - l;
            return var[r] - var[l] * pow[len];
        }
    };
}

void buildKMP(const string &s, vector<int> &kmp)
{
    kmp[0] = -1;
    int i = 0, j = -1;
    int length = s.length();
    while(i < length)
    {
        if(-1 == j || s[i] == s[j])
            kmp[++ i] = ++ j;
        else j = kmp[j];
    }
}

char s[N];
unordered_map<ulongs, uint> $map;
vector<int> $next[M];
vector<ulongs> $hash[M];
ulongs cnt[N], ans = 0;

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

    auto hm = StringHash::hashMachine(N, 6151);
    auto handleHash = [&](int ii)
    {
        auto len = strlen(s);
        $next[ii].resize(len + 1);
        $hash[ii].resize(len + 1);
        buildKMP(s, $next[ii]);
        hm.make(s, $hash[ii]);
        for (uint i = 0; i < len; ++ i)
            ++ $map[hm.get($hash[ii], i, len)];
    };
    int n; cin >> n;
    for (int i = 0; i < n; ++ i)
        cin >> s, handleHash(i);
    for (int i = 0; i < n; ++ i)
    {
        auto length = $hash[i].size() - 1;
        auto &kmp = $next[i];
        for (uint j = 1; j <= length; ++ j)
        {
            cnt[j] = $map[hm.get($hash[i], 0, j)];
            if (kmp[j] != -1) cnt[kmp[j]] -= cnt[j];
        }
        for (uint j = 1; j <= length; ++ j)
            ans = (ans + cnt[j] * j % mod * j) % mod;
    }
    cout << ans << endl;

    return 0;
}

吐槽：翻了一遍你科和武大的榜，竟然没有人做这个题，草（

再吐槽：牛客的 g++14 编译这个抛出了难以置信的 Assembler Error ↓↓，最后是 clang++ 编译过的（

8W_0LU94U_I7GH9.png

啊这…… ICE？这太怪了（

B - Boundary

平面上给定 n 个点的坐标，找一个圆，有如下要求：

  • 原点（0，0）在该圆的边界上
  • 除原点外有尽可能多的点在此圆边界上

问该圆的边界上除了原点之外的点的数量。

数据范围：n ≤ 2000；

直接想到四点共圆，遍历两个点确定一个三角形——也就是圆，再遍历第三个点判断是否在这个圆上就行了，时间复杂度 O(n³)；可这就是个大暴力做法，就算跑不满也会被 2000 的数据卡掉可是我 WA 了，神秘；

于是思考复杂度较低的做法：若点共圆，那么它们确定的圆心相等，可以去遍历所有三角形确定的圆心然后找到聚集点……还是算了吧；除了圆心之外，同一个圆弧对应的圆周角是相等的，比起二维的坐标，一维的圆周角的众数显然更加好找，那么就可以这么做了；

但是圆弧对应的圆周角可能不在同一个圆上，还有可能出现在镜像中，所以还需要叉乘判断方向；这也许也是我上面暴力的方法出错的原因吧（只考虑互补 / 相等，直接比较 |cos| 怕不是什么样的点都算进去了）；

补充：听完讲题，还真有人通过中垂线找圆心做；这…… 使用分数类？有点想看这样通过的代码，找找看吧…… 啊这不用找了，eps 设为 0 才能 A，设为 1e-8 反而 A 不了，那没事了……

首先是按照标准做法，计算角度：

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

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 1, ch = getchar();
    while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

template <class T> struct fraction
{
    T num, den;
#ifdef WIN32
    using _t = __int64;
#else
    using _t = __int128;
#endif

    fraction() = default;
    fraction(T u, T v): num(u), den(v)
    { if (!v) num = 1; else if (v < 0) num = -u, den = -v; }

    constexpr static const long double $eps = 0;
    static int sgn(long double x) {return x < -$eps ? -1 : x > $eps;}
    static T gcd(T a, T b) {return a < b ? gcd(b, a) : (!b ? a : gcd(b, a % b));}

    auto toNumber() const { return (long double) num / den; }
    int compareTo(const fraction &rhs) const {return sgn(this->toNumber() - rhs.toNumber());}
    bool equals(const fraction &rhs) const {return den == 0 || rhs.den == 0 ? den == rhs.den : !compareTo(rhs);}
    fraction &reduce() { auto x = gcd(num, den); num /= x, den /= x; return *this;}
    auto atan2() const {return std::atan2(num, den);}
    fraction reciprocal() const {return {den, num};}

    bool operator ==(const fraction &rhs) const { return num * rhs.den == den * rhs.num;}
    bool operator <(const fraction &rhs) const {return den && (!rhs.den || (_t)num * rhs.den < (_t)den * rhs.num);}
    fraction operator -() const {return {-num, den};}

    friend ostream &operator <<(ostream &os, const fraction &frac)
    {if (frac.den) os << frac.num << "/" << frac.den; else os << "NaN"; return os;}
};

namespace Geo
{
    using number = longs;

    const long double eps = fraction<longs>::$eps;
    int compareTo(number x) {return x < -eps ? -1 : x > eps;}
    int compareTo(number a, number b) {return compareTo(a-b);}

    struct point
    {
        number x, y;

        point() = default;
        point(number x, number y) : x(x), y(y) {}

        point operator +(const point &rhs) const {return {x + rhs.x, y + rhs.y};}
        point operator -(const point &rhs) const {return {x - rhs.x, y - rhs.y};}
        number operator *(const point &rhs) const {return x * rhs.x + y * rhs.y;}
        point operator *(const number rhs) const {return {rhs * x, rhs * y};}
        point operator /(const number rhs) const {return {x / rhs, y / rhs};}
        point &operator +=(const point& rhs) {x += rhs.x; y += rhs.y; return *this;}
        point &operator -=(const point& rhs) {x -= rhs.x; y -= rhs.y; return *this;}
        point &operator *=(const number rhs) {x *= rhs; y *= rhs; return *this;}
        point &operator /=(const number rhs) {x /= rhs; y /= rhs; return *this;}
        bool operator ==(const point &rhs) const {return x == rhs.x && y == rhs.y;}
        bool operator !=(const point &rhs) const {return !(rhs == *this);}

        number dot(const point &rhs) const {return x * rhs.x + y * rhs.y;}
        number cross(const point &rhs) const {return rhs.y * x - rhs.x * y;}
        auto length() const {return sqrt(dot(*this));}
        auto distance(const point &b) const {return (*this - b).length();}
        auto distance(const point &ls, const point &rs) const
        {return fabs((ls - *this).cross(rs - *this)) / ls.distance(rs);}
        point normal() const {return (x || y) ? *this / length() : point(0, 0);}
        auto angle() const {return atan2(y, x);}
        point rotate(number a) const
        {number c = cos(a), s = sin(a); return {c * x - s * y, s * x + c * y};}
        point perpendicular() const {return {-y, x};}
        point symmetry() const {return {-x, -y};}
        number square() const { return x * x + y * y; }
    };
}

template <class T> int sgn(T t) {return t ? (t < 0 ? -1 : 1) : t;}

using point = Geo::point;
using frac = fraction<longs>;

const int N = 2060;

point a[N];
vector<frac> li;

frac cosLemmaSquare(const point &p1, const point &p2)
{
    auto aa = p1.square(), bb = (p2 - p1).square(), cc = p2.square();
    longs x = bb + cc - aa, f = sgn(x);
    return {f * x * x, 4ll * bb * cc};
}

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

    longs n, ans = 1;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].y;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++ j)
            if (a[i].cross(a[j]) > 0)
                li.push_back(cosLemmaSquare(a[i], a[j]));
        sort(li.begin(), li.end(), [](frac &a, frac &b){return a.compareTo(b) < 0;});
        longs len = li.size(), l = 0;
        while (l < len)
        {
            auto r = l;
            while (r < len && li[r] == li[l]) ++ r;
            ans = max(ans, r - l + 1);
            l = r;
        }
        li.clear();
    }
    cout << ans << endl;

    return 0;
}

需要注意的是，如果使用精准比较（“<” 和 “==” 运算符），中间结果可能会爆 long long，所以如果在 Windows 环境下则可以考虑在合适的误差下使用浮点比较（equals 和 compareTo 方法）；

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

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 1, ch = getchar();
    while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

template <class T> struct fraction
{
    T num, den;

    fraction() = default;
    fraction(T u, T v): num(u), den(v)
    { if (!v) num = 1; else if (v < 0) num = -u, den = -v; }

    constexpr static const long double $eps = 0;
    static int sgn(long double x) {return x < -$eps ? -1 : x > $eps;}
    static T gcd(T a, T b) {return a < b ? gcd(b, a) : (!b ? a : gcd(b, a % b));}

    auto toNumber() const { return (long double) num / den; }
    int compareTo(const fraction &rhs) const {return sgn(this->toNumber() - rhs.toNumber());}
    bool equals(const fraction &rhs) const {return den == 0 || rhs.den == 0 ? den == rhs.den : !compareTo(rhs);}
    fraction &reduce() { auto x = gcd(num, den); num /= x, den /= x; return *this;}

    bool operator ==(const fraction &rhs) const { return num * rhs.den == den * rhs.num;}
    bool operator <(const fraction &rhs) const {return den && (!rhs.den || compareTo(rhs) < 0);}
    fraction operator -() const {return {-num, den};}
};


namespace Geo
{
    using number = longs;
    const number eps = fraction<longs>::$eps;

    int compareTo(number x) {return x < -eps ? -1 : x > eps;}
    int compareTo(number a, number b) {return compareTo(a-b);}

    struct point
    {
        number x, y;

        point() = default;
        point(number x, number y) : x(x), y(y) {}

        point operator +(const point &rhs) const {return {x + rhs.x, y + rhs.y};}
        point operator -(const point &rhs) const {return {x - rhs.x, y - rhs.y};}
        number operator *(const point &rhs) const {return x * rhs.x + y * rhs.y;}
        point operator *(const number rhs) const {return {rhs * x, rhs * y};}
        point operator /(const number rhs) const {return {x / rhs, y / rhs};}
        point &operator +=(const point& rhs) {x += rhs.x; y += rhs.y; return *this;}
        point &operator -=(const point& rhs) {x -= rhs.x; y -= rhs.y; return *this;}
        point &operator *=(const number rhs) {x *= rhs; y *= rhs; return *this;}
        point &operator /=(const number rhs) {x /= rhs; y /= rhs; return *this;}
        bool operator ==(const point &rhs) const {return x == rhs.x && y == rhs.y;}
        bool operator !=(const point &rhs) const {return !(rhs == *this);}

        number dot(const point &rhs) const {return x * rhs.x + y * rhs.y;}
        number cross(const point &rhs) const {return rhs.y * x - rhs.x * y;}
        number length() const {return sqrt(dot(*this));}
        number distance(const point &b) const {return (*this - b).length();}
        number distance(const point &ls, const point &rs) const
        {return fabs((ls - *this).cross(rs - *this)) / ls.distance(rs);}
        point normal() const {return (x || y) ? *this / length() : point(0, 0);}
        number angle() const {return atan2(y, x);}
        point rotate(number a) const
        {number c = cos(a), s = sin(a); return {c * x - s * y, s * x + c * y};}
        point perpendicular() const {return {-y, x};}
        point symmetry() const {return {-x, -y};}
        number square() const { return x * x + y * y; }
    };
}

using point = Geo::point;
using frac = fraction<longs>;

const int N = 2060;

point a[N];
vector<frac> li;

frac getSlope(const point &ll, const point &rr = {0, 0})
{
    auto ld = ll.square(), rd = rr.square();
    if (!ld) ld = 1; if (!rd) rd = 1;
    return {rr.y * ld - ll.y * rd, rr.x * ld - ll.x * rd};
}

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

    longs n, ans = 1;
    cin >> n;
    for (int i = 0; i < n; ++ i)
        cin >> a[i].x >> a[i].y;
    for (int i = 0; i < n; ++ i)
    {
        frac tmp = getSlope(a[i]);
        for (int j = i + 1; j < n; ++ j)
        {
            frac ff = getSlope(a[i], a[j]);
            if (ff.equals(tmp)) continue;
            li.push_back(ff);
        }
        sort(li.begin(), li.end());
        auto len = li.size();
        for (int l = 0, r = 0; l < len;)
        {
            r = l;
            while (r < len && li[r].equals(li[l])) ++ r;
            ans = max(ans, r - l + 1ll);
            l = r;
        }
        li.clear();
    }
    cout << ans << endl;

    return 0;
}

新嫖的分数类板子↑↑；这是武大仓鼠队使用圆的反演的做法，比较神奇的是这个题必须在允许误差为 0 时才可以 A。至于圆的反演，那是平面几何中的，有点像复变里的共形映射，之后应该会开篇文章专门学吧（

C - Cover the Tree

给一颗 n 个节点的无根树，你需要给出多条链使得该树所有树边被覆盖，且链的数量尽可能少；

数据范围：n ≤ 2e5；

D - Duration

签到题，直接读入计算即可但是队友白给两发草

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

using namespace std;

inline int nextInt()
{
    int x = 0, f = 1, ch = getchar();
    while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

int main()
{
    auto h1 = nextInt(), m1 = nextInt(), s1 = nextInt();
    auto h2 = nextInt(), m2 = nextInt(), s2 = nextInt();
    auto $1 = h1 * 3600 + m1 * 60 + s1;
    auto $2 = h2 * 3600 + m2 * 60 + s2;
    cout << abs($1 - $2);

    return 0;
}

E - Exclusive OR

给长为 n 的数组 A，现要求你在数组中可重复的选出 i 个数字，使得这 i 个数字的异或和最大；要求你对於一组数据，输出 i ∈ [1, n] 时的答案；

数据范围：n ≤ 2e5，A ≤ 2e18；

F - Fake Maxpooling

给定 n × m 的矩阵，找到其中所有 k × k 矩阵的最大值并求和；

数据范围：k ≤ n, m ≤ 5000

一看是个二维最值，自信满满的敲了个二维 ST 表的板子然后 T 了…… 用 gprof 分析显示 gcd 用时 33%，ST 表构造用时 30%，花掉了大量的时间；二维 ST 表是 O(n²log²n) 的，求出 gcd 也是 O(nmlogn) 的，难怪过不了……

NF0Q2_TXK0U5ESOA0XH.png

后来一看洛谷那个二维 ST 表的板子题数据规模是 100……

但是转念一项我那个板子与其说是二维 ST 表不如说是倍增 DP，复杂度应该只有一个 log ——生成表的那个；因为正方形大小是确定的，所以不需要保留多维数据，可以直接滚动，所以也不存在空间方面的问题…… 那果然就是 33% gcd 的错了！因为空间只有 256 MB 比较紧巴，所以 gcd 的记忆化直接在 mat 数组里做了，之后再遍历一波手动求 lcm 就行（

然后就过了，めでたしめでたし（虽然比赛时是队友写的滑动窗口就是了

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

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 1, ch = getchar();
    while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

const int N = 5005;
int mat[N][N];

inline longs gcd(longs a, longs b)
{
    if (a < b) gcd(b, a);
    if (mat[a][b]) return mat[a][b];
    if (!b) return mat[a][b] = a;
    else return mat[a][b] = gcd(b, a % b);
}

namespace STtable2D_simple
{
    int log[N], high[N][N];
    uint _log;
    int row, col, sq, _max;

    template <class T> T max4(T t1, T t2, T t3, T t4)
    { return max(max(t1, t2), max(t3, t4)); }

    auto import = []
    {
        for (int i = 1; i <= row; ++ i)
            for (int j = 1; j <= col; ++ j)
                high[i][j] = mat[i][j];
        _log = log[sq];
    };

    void init(uint k)
    {
        log[0] = -1;
        for (uint i = 1; i <= k; ++ i)
            log[i] = log[i >> 1u] + 1;
        memset(high, 0x80, sizeof(high));
        import();
    }

    void make(uint a, uint b)
    {
        for (uint p = 0; p < _log; ++ p)
            for (int i = 1; i + (1u << p) <= a; ++ i)
                for (int j = 1; j + (1u << p) <= b; ++ j)
                    high[i][j] = max4<int>(
                            high[i][j],
                            high[i + (1u << p)][j + (1u << p)],
                            high[i + (1u << p)][j],
                            high[i][j + (1u << p)]
                    );
    }

    void query(int x, int y)
    {
        _max = max4<int>(
                high[x][y],
                high[x + sq - (1u << _log)][y + sq - (1u << _log)],
                high[x][y + sq - (1u << _log)],
                high[x + sq - (1u << _log)][y]
        );
    }

    auto solve(int n, int m, int k)
    {
        row = n, col = m, sq = k;
        init(k); make(n, m);
        longs ans = 0;
        const int $row = n - k + 1, $col = m - k + 1;
        for (int i = 1; i <= $row; ++ i)
            for (int j = 1; j <= $col; ++ j)
                query(i, j), ans += _max;
        return ans;
    }
}

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

    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            gcd(i, j);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            mat[i][j] = i * j / mat[i][j];
    auto xx = STtable2D_simple::solve(n, m, k);
    cout << xx << endl;

    return 0;
}

然后发现这个题目似乎并不需要“二维单调队列”，只需要一维单调队列横纵两次就可以了== 毕竟 ST 表都可以偷懒到这种程度，所以可以过也是可以过吧（

除了稳健的记忆化，将求出矩阵的 gcd 的时间变成了 O(nm) 之外，还可以使用出题人的申必方法：

1
2
3
4
for (int i = 1; i <= n; i ++) 
    for (int j = 1; j <= m; j ++) 
        if (!Gcd[i][j]) for (int k = 1; k * i <= n && k * j <= m; k ++) 
            Gcd[k * i][k * j] = k, A[k * i][k * j] = i * j * k;

这也是某种筛法，只是出题人也忘记它叫什么名字了== 但是还是看起来就很稳健的记忆化搜索比较好写（

值得一提的是，在比赛的时候有不少人都是“猜测”最大值出现在左下角/右下角 10 步位置内的，也都成功 AC 了。

G - Greater and Greater

给定长度为 n 的数组 A 以及长度为 m 的数组 B；在 A 中找到长度为 m 的子区间 S，使得对于 \(\forall i \in [1, m]\) 都有 \(S_i > B_i\)；要求求出这样的 S 的数目；

数据范围：n ≤ 150000，m ≤ min(n, 40000)；

H - Happy Triangle

q 次操作，可重集合中插入删除数据，在线询问对于一个数，判断集合中是否存在两个数，使得以它们为边长的线段可以组成一个非退化三角形；

数据范围：q ≤ 2e5；

这个可重集合用 multiset 都可以，关键问题在于怎么样快速判断是否存在可以凑成三角形的两个数；首先我们考虑只看大小相邻的两个边长 a, b；

I - Interval

J - Just Shuffle

给定一个长度为 n 的 1~n 的排列，要求你构造出一个置换 P，在恰好 k 次置换后将 1~n 变换为目标排列；

数据范围：n ≤ 1e5，1e8 ≤ k ≤ 1e9；

K - Keyboard Free

给定三个半径不同的同心圆的半径，每个圆的边界上有一个动点，并且组成一个三角形；求该三角形面积的数学期望；

数据范围：r ≤ 100；

后记

听完了题解，这个小哥哥讲题就比昨天那位好多了 == 虽然也没有讲很长时间但是和昨天那进行对比高下立判（ 虽然最后摆一句没看懂私聊，结果他本人不在我在的那个群里倒也有些麻烦== 不过参考之前竞赛培训加了好友那也多半是吹水吹逼而不会去讨论正经的学术问题吧可能只有我是这样的（ 最后我心心念念的二维 ST 表也过了，非常的好==

可是听完直播课之后回顾一遍题目，真正会做的又只有几个题呢？道阻且长啊（

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://shiraha.cn/2020/nowcoder-2020-summer-multi-2/

更新于：2020年7月13日

算法

ACM

Nowcoder

评论