Skip to content

1039: 樱

题目

题目描述

「いては散り、散っては咲く桜のように 巡り巡る绿に誘われ (开了又谢、谢了又开的樱花一样,循环的因缘之约) 来世できっとまた、お逢いしましょう (来生,我们一定会再相逢)」 ——《拝啓、御前様》

传说在世界的尽头有一片巨大的樱花林,这里的每一棵樱树都会开出不同颜色的樱花。

而每一棵樱树开出的樱花,一定能构成一个联通的区块。

这里我们定义:两个块相邻当且仅当这两个块有且仅有一个维度的坐标的差值为$1$。 现在,我们拿到了这片樱花林的地图,上面标注了每个格子樱花的花色。

我们需要一个程序去计算,在这片樱花林里,至少有多少棵樱树。

当然,由于世界内核的崩坏,这个世界的地图不一定是二维的。所以,你的程序需要处理更加复杂的情况。

一句话题意:$k$维超体的颜色块数。

输入格式

第一行一个整数n,表示地图的维数。

接下来一行$n$个整数$a_1,a_2,...,a_n$,表示每一维的大小。

接下来$\prod_{i=1}^{n}a_i$ 个整数,按照从第$n$维度到第$1$维度依次递增循环的顺序给出地图。

即:地图按照以下python3代码给出:

python for i_1 in range(1, a_1 + 1): for i_2 in range(1, a_2 + 1): ... for i_n in range(1, a_n + 1): output(MAP[i_1][i_2]...[i_n]) 其中output为自定义输出函数,输出数字后随机输出空格或换行

(为什么不用cpp?因为怕误导你们)

输出格式

一行一个整数,表示所求答案。

样例输入

[样例1]

1 20 3 2 3 1 0 4 1 0 2 3 3 4 3 1 3 0 4 4 4 3

[样例2]

2 3 3 0 1 1 0 1 2 2 1 2

样例输出

[样例1]

17

[样例2]

4

数据范围

对于$30\%$的数据,$n\le 2$;

对于另外$20\%$的数据,$n \le 100'000,\prod_{i=1}^{n}a_i \le 1000$;

对于$100\%$的数据,$n \le 100' 000, \prod_{i=1}^{n}a_i \le262'144, 0 \le$地图颜色$ < 256$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!