是否可以进一步优化此代码，以便我不会在竞争性网站上出现 Time Limit Exceeded 或 TLE？

Question

在一个竞争性编码网站上，我遇到了这个问题。我能够使用下面的代码为基本用例解决它。然而，大输入超过了时间限制，我试图减少循环次数，但仍然花费了大约2秒的时间，但是，限制只有1秒。

是否还有进一步优化此代码的余地？例如，我们可以删除嵌套循环吗？

static void Main(string[] args)
    {
        string[] first = (Console.ReadLine()).Split(null);          //Sample input -  3 1 2 2 3
        int N = int.Parse(first[0]);
        int X = (int.Parse(first[1]) - 1);
        int Y = (int.Parse(first[2]) - 1);
        int Z = (int.Parse(first[3]) - 1);
        int T = (int.Parse(first[4]) - 1);
        string second = Console.ReadLine();                         // Sample input - 1 2 3
        List<int> list = new List<int>();

        //Converting string inputs to int
        list = second.Split().Select(str => int.Parse(str)).ToList();

        List<int> xorList = new List<int>();
        int xor = 0;
        int temp = 0;
        //Calculate the digits(using bitwise AND) of sub-matrix only, instead of entire matrix, and in the same loop, calculate bitwise XOR also.
        for (int i = X; i <= Z; i++)
        {
            for (int j = Y; j <= T; j++)
            {
                temp = list[i] & list[j];
                xor ^= temp;                    
            }
        }            
        Console.WriteLine(xor);            
    }

编辑： 对于大输入，矩阵的大小可以大到 100000 x 100000。此外，数字序列可以有大至 1000000000 的整数。

对于这样的整数，需要 2 秒。

Answer 1

首先，我们假设问题出在布尔值而不是整数。

那么查看问题的一种方法是，我们在感兴趣的子矩阵的顶部有一些布尔值，在它的左侧有一些布尔值。然后，如果为 True 的顶部布尔值绘制垂直线，为 True 的侧布尔值绘制水平线：

然后任务是计算交叉点的数量并确定该数字是偶数（结果：零）还是奇数（结果：一）。

现在更明显的是，不用一个一个地计算它们就可以完成，它可以通过将顶部的 True 布尔值的数量乘以侧面的 True 布尔值的数量来完成。事实上，我们可以对这些数字进行按位与运算，因为乘积的最低有效位与数字与运算的最低有效位相同。

这只需要线性时间，来计算 X..Z 范围和 Y..T 范围内的 True 布尔值的数量。

要解决整个问题，请对所有 32 位整数执行此操作。当然，这样做有捷径，因为不需要完整计数（只需要计数的最低有效位），也不需要完整产品。

也许您更喜欢更代数的解释，那么看到这一点的一种方式是我们使用 AND 分布在 XOR 上的事实将 a&d ^ a&e ^ a&f ^ b&d ^ b&e ^ b&f ^ c&d ^ c&e ^ c&f（3x3 示例）重写为 (a ^ b ^ c) & (d ^ e ^ f)。

一般来说，

horizontal = XOR of list[X .. Z]
vertical = XOR of list[Y .. T]
result = horizontal & vertical

是否可以进一步优化此代码，以便我不会在竞争性网站上出现 Time Limit Exceeded 或 TLE？

Can this code be further optimized so that I do not get Time Limit Exceeded or TLE on competitive website?

c#

optimization

performance

bitwise-operators

bitwise-xor