题目11：在20×20的网格中同一直线上四个数的最大乘积是多少？

欧拉计划

题目11：在20×20的网格中同一直线上四个数的最大乘积是多少？

Largest product in a grid

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

题目翻译：

在以下这个 20×20 的网格中，四个处于同一对角线上的相邻数字用红色标了出来：

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

这四个数字的乘积是：26 × 63 × 78 × 14 = 1788696。

在这个 20×20 网格中，处于任何方向上（上，下，左，右或者对角线）的四个相邻数字的乘积的最大值是多少？


视频讲解：




思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

歌者文明清理员

这难道得一个一个比？

陈尚涵

歌者文明清理员 发表于 2023-6-28 07:27
这难道得一个一个比？

二维前缀和啊 一次计算 终程序O(1)
我买了豪的象征

欧拉计划

陈尚涵 发表于 2023-6-28 08:44
二维前缀和啊 一次计算 终程序O(1)
我买了豪的象征

O(1) ？愿闻其详~

欧拉计划

陈尚涵 发表于 2023-6-28 08:44
二维前缀和啊 一次计算 终程序O(1)
我买了豪的象征

哈哈，我明白了，肉眼获取答案~

陈尚涵

欧拉计划 发表于 2023-6-29 03:20
哈哈，我明白了，肉眼获取答案~

什么啊，前缀和就是把求和的部分优化到了O(1)级别，和暴力区别不大

欧拉计划

陈尚涵 发表于 2023-6-29 08:04
什么啊，前缀和就是把求和的部分优化到了O(1)级别，和暴力区别不大

效率差不多的，用前缀和（积）的思路先进行一轮预处理需要耗费 O(n^2) 的时间，然后肉眼观察最大值是 O(1)，但需要额外付出更多的空间来存放预处理结果。

陈尚涵

欧拉计划 发表于 2023-6-29 15:15
效率差不多的，用前缀和的思路先进行一轮预处理需要耗费 O(n^2) 的时间，然后肉眼观察最大值是 O(1)

什么叫做肉眼观察啊
O(n^2)预处理之后，每一次处理不就都是O(1)了吗，如果暴力的话就是O(n)，总结大概是O(4*n^2)，应该还是优化了不少的

欧拉计划

陈尚涵 发表于 2023-6-29 15:33
什么叫做肉眼观察啊
O(n^2)预处理之后，每一次处理不就都是O(1)了吗，如果暴力的话就是O(n)，总结大概是 ...

想看看你的代码

陈尚涵

欧拉计划 发表于 2023-6-29 15:39
想看看你的代码

还没写呢
但是我想到一个问题，上下和对角线怎么用前缀和写？

欧拉计划

陈尚涵 发表于 2023-6-29 15:41
还没写呢
但是我想到一个问题，上下和对角线怎么用前缀和写？

再创建额外的空间来存储，4 个方向应该要创建 4 份额外的空间，尝试一下~

plus

欧拉计划官网打不开了，是需要梯子了么

zhangjinxuan

陈尚涵 发表于 2023-6-28 08:44
二维前缀和啊 一次计算 终程序O(1)
我买了豪的象征

只要没有 0，都 好

zhangjinxuan

类似于循环展开了

过多循环的确会降低代码的运行效率，因此，在面对与有限次的循环，可以直接展开。

这是一个很古老的帖子：https://fishc.com.cn/thread-217189-1-1.html

陈尚涵

zhangjinxuan 发表于 2023-6-30 21:09
只要没有 0，都 好

啥意思

元豪

陈尚涵 发表于 2023-6-28 08:44
二维前缀和啊 一次计算 终程序O(1)
我买了豪的象征

Kazimierz

这题很简单，直接开125个线段树，每个线段树维护一个区间里面所有数的乘积，然后遍历每个线段树的长度为4的区间，最后求最大值即可
答案: 70600674 (狗头保命)

#include <bits/stdc++.h>
#define lowbit(x) (x)&(-x)
#define ls u<<1
#define rs u<<1|1
#define Mid(x,y) (x+y)>>1
using namespace std;

typedef long long LL;
const int N = 25;
int a[N][N], n = 20,cnt,b[N];

struct Node
{
    int l,r;
    LL v;
}tr[125][4*N];

void pushup(int u)
{
    tr[cnt][u].v = tr[cnt][ls].v * tr[cnt][rs].v;
}

void build(int u,int l,int r)
{
    tr[cnt][u] = {l,r};
    if(l==r)
    {
        tr[cnt][u].v = b[l];
        return;
    }
    int mid = Mid(l,r);
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(u);
}

LL query(int u,int l,int r,int cnt)
{
    if(tr[cnt][u].l>=l&&tr[cnt][u].r<=r) return tr[cnt][u].v;
    int mid = Mid(tr[cnt][u].l,tr[cnt][u].r);
    LL v = 1;
    if(l<=mid) v = query(ls,l,r,cnt);
    if(r>mid) v *= query(rs,l,r,cnt);
    return v;
}

int main()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>a[i][j];
    
    for(int i=1;i<=n;i++)
    {
        memset(b,0,sizeof b);
        for(int j=1;j<=n;j++) b[j] = a[i][j]; //构建每一行
        build(1,1,n);
        cnt++;
    }
    
    for(int i=1;i<=n;i++)
    {
        memset(b,0,sizeof b);
        for(int j=1;j<=n;j++) b[j] = a[j][i]; //构建每一列
        build(1,1,n);
        cnt++;
    }
    
    //主对角线
    for(int i=1;i<=n;i++) //遍历第一行
    {
        memset(b,0,sizeof b);
        for(int x = 1,y = i,j = 1;x<=n&&y<=n;x++,y++,j++) b[j] = a[x][y];
        build(1,1,n);
        cnt++;
    }
    for(int i=1;i<=n;i++) //遍历第一列
    {
        memset(b,0,sizeof b);
        for(int x = i,y = 1,j = 1;x<=n&&y<=n;x++,y++,j++) b[j] = a[x][y];
        build(1,1,n);
        cnt++;
    }
    
    //次对角线
    for(int i=1;i<=n;i++) //遍历第一行
    {
        memset(b,0,sizeof b);
        for(int x = 1,y = i,j = 1;x<=n&&y>=1;x++,y--,j++) b[j] = a[x][y];
        build(1,1,n);
        cnt++;
    }
    for(int i=1;i<=n;i++) //遍历最后一列
    {
        memset(b,0,sizeof b);
        for(int x = i,y = n,j = 1;x<=n&&y>=1;x++,y--,j++) b[j] = a[x][y];
        build(1,1,n);
        cnt++;
    }
    
    LL ans = 0;
    for(int i=0;i<cnt;i++)
    {
        for(int j=1;j<=n-3;j++) ans = max(ans,query(1,j,j+3,i));
    }
    cout<<ans<<endl;
    return 0;
}

鱼C-小师妹

歌者文明清理员

plus 发表于 2023-6-30 16:22
欧拉计划官网打不开了，是需要梯子了么

哦，可恶的中国屏蔽了谷歌，大多数国外网站用了谷歌，你可以看 -> https://fishc.com.cn/thread-230335-1-1.html

zhangjinxuan

陈尚涵 发表于 2023-6-29 15:33
什么叫做肉眼观察啊
O(n^2)预处理之后，每一次处理不就都是O(1)了吗，如果暴力的话就是O(n)，总结大概是 ...

既然只有 4 个数字，为什么不直接 a[i ][j], a[i-1][j], a[i-2][j], a[i-3][j], 呢

而且前缀和用的空间又多，何必呢