【2020年牛客暑假第二场】F题Fake Maxpooling

传送门：https://ac.nowcoder.com/acm/contest/5667/F

题意

题目描述 Given a matrix of size$n×m$and an integer$k$,where$A_{i\times j} = lcm(i,j)$the least common multiple of $i$ and $j$. You should determine the sum of the maximums among all $k×k$ submatrices.

输入描述 Only one line containing three integers$n,m,k(1\leq n,m\leq 5000,1\leq k \leq min \{i,j\}$

输出描述 Only one line containing one integer, denoting the answer.

输入 $3$ $4$ $2$

输出 $38$

思路

队友用的是二维ST表AC的，这里是单调队列。

矩阵的所有lcm可以在单调过程中记忆化，复杂度会减少，如果先做预处理（单调前全部计算出会加大复杂度）。

只需要纵向做一遍单调队列，然后把纵向所有的单调队列存在Max二维数组里， 之后在横向做一遍单调队列，这样k*k的方格就能找到最大值了。

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
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<double, double> pdd;

##define INF 0x7f7f7f
##define mem(a,b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
// const ll mod = 1e9 + 7;
// const int maxn = 1e5 + 10;
// const double eps = 1e-6;

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

struct Monotone_queue
{
    static const int maxn = 5001;
    int n, m, k; // 个数、窗口大小
    int q[maxn], p[maxn], head, tail; // q是单调队列，p是对应y序号，头节点、尾节点
    int Max[maxn][maxn];
    void read()
    {
        cin >> n >> m >> k;
    }
    void Monotone()
    {
        for(int i = 1;i <= n; i++)
        {
            head = 1; tail = 0;
            for(int j = 1;j <= m; j++)
            {
                int val = i * j / gcd(i, j);
                while(head <= tail && q[tail] <= val)
                    tail--;
                q[++tail] = val;
                p[tail] = j;
                while(head <= tail && p[head] <= j - k)
                    head++;
                if(j >= k)
                    Max[i][j - k + 1] = q[head];
            }
        }
    }

    ll ans = 0;

    void value()
    {
        for(int j = 1; j<= m - k + 1; j++)
        {
            head = 1; tail = 0;
            for(int i = 1;i <= n; i++)
            {
                int val = Max[i][j];
                while(head <= tail && q[tail] <= val)
                    tail--;
                q[++tail] = val;
                p[tail] = i;
                while(head <= tail && p[head] <= i - k)
                    head++;
                if(i >= k)
                    ans += q[head];
            }
        }
        cout << ans << endl;
    }
}Worker;

void solve()
{
    Worker.read();
    Worker.Monotone();
    Worker.value();
}

signed main()
{
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
##else
    ios::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while(T--)
        solve();
##endif
    return 0;
}

deque模拟单调队列

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
// 双向队列模拟

struct num{
    int index, x;
};

deque<num> q; // max
deque<num> p; // min

int s[2][10000005];
int cnt = 1;

void solve()
{
    int n, k, x;
    num t;
    cin >> n >> k;
    for(int i = 1;i <= n; i++)
    {
        cin >> x;
        t.index = i; t.x = x;
        while(!q.empty() && x >= q.back().x)
        {
            q.pop_back();
        }
        while(!p.empty() && x <= p.back().x)
        {
            p.pop_back();
        }
        q.push_back(t);
        p.push_back(t);
        while(i - k >= q.front().index)
        {
            q.pop_front();
        }
        while(i - k >= p.front().index)
        {
            p.pop_front();
        }
        if(i >= k)
        {
            s[0][cnt] = q.front().x;
            s[1][cnt] = p.front().x;
            cnt++;
        }
    }
    for(int i = 1;i < cnt; i++)
        cout << s[1][i] << " ";
    cout << endl;
    for(int i = 1;i < cnt; i++)
        cout << s[0][i] << " ";
    cout << endl;
}

数组模拟单调队列

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
// 数组模拟

struct Monotone_queue{
    static const int maxn = 10000005;
    int n, k, a[maxn]; // 个数、窗口大小、值
    int q[maxn], p[maxn], head, tail; // q是单调队列，p是对应y序号，头节点、尾节点

    void read()
    {
        cin >> n >> k;
        for(int i = 1;i <= n; i++)
            cin >> a[i];
    }

    void Monotone_min()
    {
        head = 1; tail = 0;
        for(int i = 1;i <= n; i++)
        {
            while(head <= tail && q[tail] >= a[i])
            {
                tail--;
            }
            q[++tail] = a[i];
            p[tail] = i;
            while(p[head] <= i - k)
                head++;
            if(i >= k)
                cout << q[head] << " ";
        }
        cout << endl;
    }

    void Monotone_max()
    {
        head = 1; tail = 0;
        for(int i = 1;i <= n; i++)
        {
            while(head <= tail && q[tail] <= a[i])
            {
                tail--;
            }
            q[++tail] = a[i];
            p[tail] = i;
            while(p[head] <= i - k)
                head++;
            if(i >= k)
                cout << q[head] << " ";
        }
        cout << endl;
    }
}Worker;

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/07/14/2020-nowcoder-shujia-2-f/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！