傳說中,大陸人的幾何學(簡稱大陸幾何學)與平凡的幾何學不同,是門高深且帶有些許神秘色彩的學問。例如,在大陸幾何學中,長方形的其中一個邊長可能會大於另外三邊長的和。
因為大陸幾何學實在是太艱深了,所以這裡只談談大陸幾何學的其中一個應用:大陸方陣。
大陸方陣是一個能夠有效抵禦進攻的軍隊布陣方式,以下將會描述大陸方陣的結構。
假設現在有一塊長方形的空地,首先將這塊空地切成N*M的小方形空地,接著軍隊的每個營安置在小空地中。
安置完畢後,大陸方陣即成形。此時每個小空地可能處於四種狀態:
(1) 裡面沒有軍隊,以符號.
表示。
(2) 裡面有東西向列隊的軍隊,以符號-
表示。
(3) 裡面有南北向列隊的軍隊,以符號|
表示。
(4) 裡面有處於分散狀態的軍隊,以符號+
表示。
我們可以用符號代表一個小空地的狀態,就可以簡單地用俯視圖表達方陣的結構。為了方便,我們以上方代表北方。
為甚麼要這樣標示呢?因為在這樣的標示下,圖上包含幾個矩形,就是這個方陣的「能力指標」!
大陸數學家告訴我們,每種大陸方陣的防禦力強度可以表示為能力指標的函數,但是兩者的關係為何,已經超出凡人的理解範圍。
所以現在給你一個大陸方陣,請你求出它的能力指標。剩下的事情交給大陸數學家就可以了。
能力指標的完整定義方式如下:
能力指標的數值,代表在大陸方陣中,能找到幾個端點位置不完全相同的矩形部分
(1)
(2)
(3)
(4)
(5)
例如,以下幾個都是滿足上述五個條件的矩形:
+---+ +---+ |
+---+ +...| +-+-+ |
++-+ |-+| +-++ |
++ ++ |
以下幾個則不是:
++++ | +-|-+ +.+.- +---+ |
---| |..| |--+ |
++ -+ |
第一行有兩個數字
接下來有
子任務(測資) | 額外限制 | 分數 |
1 (0~3) | 4 | |
2 (0~7) | 16 | |
3 (0~10) | 17 | |
3 (11~13) | 19 | |
5 (0~17) | 無限制 | 44 |
輸出一個數字,代表給定大陸方陣的能力指標。
5 8 +-+-+--+ |..+|-++ ----++++ ++..+..| ++-----+
3
+-+-+--+
|..+|-++
----++++
++..+..|
++-----+
Problem Set by Yihda Yol
Problem Source: TOI 2017 二階練習題
No. | Testdata Range | Score |
---|---|---|
1 | 0~3 | 4 |
2 | 0~7 | 16 |
3 | 0~10 | 17 |
4 | 11~13 | 19 |
5 | 0~17 | 44 |