小编Ant*_*ith的帖子

我正在解决在给定数组中找到不同整数的数量的基本问题。

我的想法是声明一个std::unordered_set，将所有给定的整数插入到集合中，然后输出集合的大小。这是我实现此策略的代码：

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

int main()
{
    int N;
    cin >> N;
    
    int input;
    unordered_set <int> S;
    for(int i = 0; i < N; ++i){
        cin >> input;
        S.insert(input);
    }
    
    cout << S.size() << endl;

    return 0;
}

这种策略几乎适用于所有输入。在其他输入情况下，它超时。

我很好奇我的程序为什么会超时，所以我cout << i << endl;在 for 循环中添加了一行。我发现当我进入输入案例时，53000循环的第一次左右迭代几乎会立即通过，但之后100每秒只会发生几次迭代。

我已经阅读了O(N)如果发生大量冲突，散列集如何以插入结束，所以我认为输入在std::unordered_set.

然而，这是不可能的。std::unordered_set用于整数的哈希函数将它们映射到自身（至少在我的计算机上），因此不同整数之间不会发生冲突。我使用写在这个链接上的代码访问了哈希函数。

我的问题是，输入本身是否有可能 …

我最近了解了Flood-Fill Algorithm，这是一种可以获取图形并O(N)及时为每个节点分配组件编号的算法。

例如，可以使用 Flood-Fill 算法有效解决的一个常见问题是找到一块N*N板上最大的区域，其中该区域中的每个节点都与另一个具有相同 ID 的节点相邻，或者直接向上、向下、到向左，或向右。

在这个棋盘中，最大的区域都是 3，分别由全 1 和全 9 组成。

然而，我最近开始怀疑我们是否可以扩展这个问题；具体来说，如果我们能在图中找到最大的区域，使得该区域中的每个节点都与具有两个可能 ID 的另一个节点相邻。在上图中，最大的此类区域由 1 和 9 组成，大小为 7。

这是我试图解决这个问题的思考过程：

想法 1：O(N^4) 算法

我们可以O(N^4)使用基本的洪水填充算法及时解决这个问题。我们通过测试所有O(N^2)水平或垂直相邻的方块对来做到这一点。对于每一对方块，如果它们有不同的 ID，那么我们从两个方块中的一个运行填充。

然后，通过修改洪水填充算法，使其传播到具有两个可能 ID 之一的正方形，我们可以及时测试每一对O(N^2)--> O(N^2) pairs * O(N^2) flood fill per pair = O(N^4) algorithm。

然后，我有了一个洞见：An Possably O(N^2) Algorithm

首先，我们通过电路板运行常规的洪水填充并将电路板分成一个“组件图”（其中原始图中的每个组件都减少为单个节点）。

现在，我们通过组件图的边缘而不是节点进行洪水填充。我们用一对整数标记每条边，表示它连接的两个组件内的两个 ID，然后通过边填充，就好像它们本身是节点一样。

我相信，如果正确实施，将产生一种O(N^2)算法，因为N*N板中边数的上限是4*N*N.

现在，我的问题是，我的思维过程在逻辑上是否合理？如果没有，有人可以建议另一种算法来解决这个问题吗？

我正在尝试解决这个问题：https : //cses.fi/problemset/task/1144/

给定一个最多200000包含元素的数组，我的任务是处理最多200000查询，这些查询要么让我更新数组中的单个值，要么让我找到给定范围内的 a 和 b 之间的元素数（对于例如，查询会询问从索引1到5范围内有多少元素[2, 3]）。

我目前的想法是首先对给定数组中的值使用索引压缩（因为值可以高达10^9，因此保留一个简单的出现数组会超出存储限制），然后保留另一个包含每个压缩出现次数的数组数字。然后，可以使用求和段树来处理和更新查询。

但是，我在尝试实施这种方法时遇到了问题。我意识到更新单个数组值会迫使我更改压缩数组。

例如，给定一个数组[1, 5, 3, 3, 2]，我将定义一个压缩函数C，使得

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;

然后，出现数组将是[1, 1, 2, 1]，并且处理总和查询将是有效的。但是，如果我被指示更新一个值，例如，将第三个元素更改为4，那么这会使所有内容失去平衡。压缩功能必须更改为

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;

这将迫使我重建我的事件数组，从而导致O(N)更新时间。

由于N可以达到200000，我目前的方法不能有效地解决问题，尽管我认为我对索引压缩有正确的想法。有人可以用我的方法指出我正确的方向吗？

我的任务是找到矩阵内的所有子矩阵，使得每个计数的子矩阵都满足特定条件，并且也不属于另一个有效子矩阵的一部分。

我的第一个想法是编写一个递归过程，以便我们可以return在发现当前子矩阵有效时简单地从当前子矩阵中提取（以防止对该子矩阵的任何子矩阵进行测试）。这是我尝试执行此操作的代码：

void find(int xmin, int xmax, int ymin, int ymax){
    if(xmin > xmax || ymin > ymax){return;}
    else if(works(xmin, xmax, ymin, ymax)){++ANS; return;}

    find(xmin + 1, xmax, ymin, ymax);
    find(xmin, xmax - 1, ymin, ymax);
    find(xmin, xmax, ymin + 1, ymax);
    find(xmin, xmax, ymin, ymax - 1);
}

我当前方法的问题似乎在于它允许多次访问子矩阵，这意味着这些return语句是无效的，并且实际上并没有阻止对工作子矩阵的子矩阵进行计数，因为它们从其他矩阵访问。不过，我认为我编写递归程序的想法是正确的。有人可以指出我正确的方向吗？

我正在尝试解决这个问题：https : //cses.fi/problemset/task/1160/

基本上，这个问题要求编码器Q在后继N节点图中处理最短路径查询，其中Q和N的数字高达 100000。我已经被这个问题困住了好几天，我的想法都不够快，可以通过所有测试用例。

我的第一个想法是使用某种全对最短路径算法，例如 Floyd-Warshall 算法。然而，这种算法将在运行O(N^3 + Q)时间，这是方法太慢了这个问题。

我的第二个想法是使用广度优先搜索单独处理每个查询。这个算法会O(Q*N)及时运行，这比我的第一个想法快，但对于问题来说仍然太慢。

我尝试在网上搜索解决方案，但没有找到任何解释。有人可以指出我正确的方向吗？

我了解到数字类型（例如intand ）long long在 C++ 中以基二格式存储。可以使用按位运算符访问和修改这些单独的位。

但是，我最近想知道为什么数字没有以std::cout2 为基数打印到屏幕上，并认为它们在打印之前必须已转换为 10 基数。换句话说，由于std::cout以 10 为基数输出这些数字，我认为必须进行一些转换过程才能将这些数字从 2 基数转换为 10 基数。

总的来说，我的问题是，std::cout实际上是否将数字从基数 2 转换为基数 10，它是如何做到的？我在这里犯了其他一些逻辑错误吗？