a862. 數之數織 - 旦旦解題農場

內容

數織是一種邏輯遊戲，以猜謎的方式繪畫黑白點陣圖。在一個網格中，每一行和列都有一組數，玩家需根據它們來填滿或留空格子，最後就可以由此得出一幅圖畫。例如，「4 8 3」的意思就是指該行或列上有三條獨立的線，分別佔了4、8和3格，而每條線最少要由一個空格分開。傳統上，玩家是以黑色填滿格子，和以「×」號標記一定不需要填充的格子。數織是一個NP完全的問題。

就是這個東西

給你一個數織，你要解他，就這樣

但因為解一般數織太難了

所以這邊加一個限制

左邊跟上面的那些格子中只會有一個數字

補充：

怕有人沒完過或不知道

一個數字代表有連續個格子出現在一條線

並且長度為該格子的數值

然後如果要輸出解答的話輸出檔又會太大

所以輸出有幾組可行的解就好

輸入說明

第一行輸入一數$T$，代表有$T$筆側資

對於每筆側資，第一行輸入一數$N$，代表有這個數織是個$N*N$的正方形

再輸入

$1$行$N$個數字$lft_i$

$1$行$N$個數字$up_i$

這$2$行的輸入格式舉例如下：

會對上圖每個白格分別輸出「格中數字」

(格子中只會有一個數字)

左上到左下，上左到上右

所以這$2$行的輸入為

3 1 3 2 1

1 1 3 3 2

輸出說明

對於每筆側資，輸出有幾組可行的解

範例輸入

範例輸出

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (1%): 1.5s , <1M
公開測資點#1 (14%): 1.5s , <10M
公開測資點#2 (45%): 1.5s , <10M
公開測資點#3 (40%): 1.5s , <10M

提示：

$IO優化$ : cin.tie(nullptr), ios::sync_with_stdio(false);

$Subtask \qquad Score \qquad Extra\ Input\ Limits$

$\quad$ $\#0$ $\qquad \quad \; \;$ $\ \ 1\%$ $\qquad$ $N = 1$

$\quad$ $\#1$ $\qquad \quad \; \;$ $14\%$ $\qquad$ $N = 2$

$\quad$ $\#2$ $\qquad \quad \; \;$ $45\%$ $\qquad$ $N = 5$

$\quad$ $\#3$ $\qquad \quad \; \;$ $40\%$ $\qquad$ $N = 10$

$For\ all\ subtask:\ \ T \leq 10^5,\ \ 0 \leq lft_i,\ up_i \leq N$

保證每筆測資皆有解(沒有好像也沒差)

保證單筆測資點答案總和$\leq 10^8$

標籤:

111學年度上學期進階班期末考 DFS brute_force

出處:

[管理者：

chrislaiisme (卍乂_第11屆ㄟ進階助教 a.k.a. ...)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」