颜色网格算法
我刚刚在一个我现在想解决的网站上遇到问题。 这是问题。
你得到一个N×N的网格。 每个单元在开始时都具有白色（颜色0）。
每行和每列都有一个与之相关的特定颜色。 用新颜色V填充行或列意味着将该行或列的所有单元格更改为V（从而覆盖单元格的先前颜色）。
现在，给定一系列P这样的操作，计算最终网格中的颜色总和。 操作可以像COL 1 6的含义，用6填充第一列。对于行也是如此。
在我看来，这是一个相当简单的问题，但我的解决方案似乎并未被接受。 显然我错过了一些东西。 这是我到目前为止所尝试的。 用false（未填充）初始化每个行和列的标志。 跟踪填充列数和行数。 现在从最后一个操作开始（从反向）。
如果它在列上进行操作，请检查该列之前是否已填充，即检查该列的标志。 如果不是，请检查填充的行数。 现在sum = sum + (N - rows_filled) * (Number to be filled in the column). 将该列的标志更新为true意味着已填充。 增加一列填充。 如果列之前已填充，请继续下一步操作。 同样的逻辑也适用于行操作。 这一直持续到填充的行数=填充的列数= N或直到处理完所有操作。
任何人都可以帮助我发现，这个逻辑有什么问题？ 如果您对这个问题有更好的解决方法，请分享。
问题是Integer只能处理32位整数，所以你的计算溢出了。
注意：
(576055795*10)%2**32 = 1465590654
长柄64位整数可以正常工作。
看起来你正试图解决HackerRank的[IOI]颜色网格问题。 由于比赛已经结束，我想可以讨论解决方案。
你需要更密切地关注这个问题的限制：
1 <= N <= 6000 # Grid size
1 <= P <= 400000 # Number of paint operations
请注意，P可能比N大很多倍，在这种情况下，几乎所有的绘制操作对最终结果都没有影响，因为它们将在随后的操作中被绘制在同一行或列上。
如果您尝试计算每个操作的结果，那么您的代码将在达到解决方案之前超时。 相反，你应该集中精力忽视那些没有任何效果的行动。
例如，您可以通过记忆上一次对每行和每列执行的操作，并在用完所有输入数据后计算这些操作的效果。
（正如@Peter de Rivaz指出的那样，你必须在64位累加器中加上单元值以避免溢出。）
链接地址: http://www.djcxy.com/p/63841.html上一篇: Color Grid algorithm