顏色網格算法

我剛剛在我現在正在嘗試解決的網站上遇到問題。這是問題。顏色網格算法

給你一個N×N的網格。每個單元在開始時都具有白色（顏色0）。

每行和每列都有一個與其相關的特定顏色。用新顏色V填充行或列意味着將該行或列的所有單元格更改爲V（從而覆蓋單元格的先前顏色）。

現在，給定P這樣的操作序列，計算最終網格中的顏色總和。操作可以像COL 1 6的含義，用6填充第一列。對於行也是如此。

在我看來相當簡單的問題，但我的解決方案似乎並未被接受。顯然我錯過了一些東西。這是我到目前爲止所嘗試的。用false（未填充）初始化每個行和列的標誌。跟蹤填充列數和行數。現在從最後一個操作開始（從反向）。

如果它對列進行了操作，請檢查該列之前是否已填滿，即檢查該列的標誌。如果不是，請檢查填充的行數。現在sum = sum + (N - rows_filled) * (Number to be filled in the column).更新列的標誌爲真意味着填充。增加一列填充。如果列之前已填充，請繼續下一步操作。同樣的邏輯也適用於行操作。這一直持續到填充的行數=填充的列數= N或直到處理完所有操作。

任何人都可以幫我找出這個邏輯有什麼問題嗎？如果您對這個問題有更好的解決方法，請分享。

來源

2014-07-05 aandis

你的算法聽上去不錯，也許你已經在執行的問題嗎？也許你可以嘗試與一些隨機示例的bruteforce forward實現進行比較？ –

@PeterdeRivaz的實現相當簡單。我很確定，那裏沒有錯。 – aandis

如果有更好的方法來解決這個問題，我很樂意聽到他們。 :) – aandis

問題是整數只處理32位整數，所以你的計算溢出。

需要注意的是：

(576055795*10)%2**32 = 1465590654

朗處理64位整數，所以正常工作。

來源

2014-07-05 21:33:47

看起來你正試圖解決在HackerRank的[IOI] Color Grid問題。由於比賽已經結束，我想可以討論解決方案。

你需要發揮更加關注這個問題的制約：

1 <= N <= 6000  # Grid size 
1 <= P <= 400000 # Number of paint operations

注意，P是可能大於N 很多倍，在這種情況下，幾乎所有的塗料業務將具有零效應在最終的結果上，因爲它們將在隨後的操作中被塗在同一行或列上。

如果您嘗試計算每個操作的後果，您的代碼將在達到解決方案之前超時。相反，你應該集中精力忽視那些沒有任何效果的行動。

您可以通過例如記憶上一個對每行和每列執行的操作，並且只在計算完所有輸入數據後這些操作的效果。

（正如@Peter de Rivaz指出的那樣，你必須在64位累加器加起來單元格的值，以避免溢出。）

來源

2014-07-05 22:18:06

或者只是以相反的方式進行;） – aandis

顏色網格算法

回答

相關問題