小编A. *_*ski的帖子

虽然我还是初学者,但我喜欢解决与图形相关的问题(最短路径,搜索等).最近我遇到了这样的问题:

给定具有N个节点和E边缘的非定向加权(无负值)图形(两个节点之间最多1个边缘,边缘只能放置在两个不同节点之间)和一个必须访问的X节点列表,找到从节点0开始的最短路径,访问所有X节点并返回到节点0.总是至少有一条路径连接任意两个节点.

限制为1 <= N <= 40 000/1 <= X <= 15/1 <= E <= 50 000

这是一个例子:

红色节点(0)应该是路径的开始和结束.您必须访问所有蓝色节点(1,2,3,4)并返回.这里最短的路径是:

0 - > 3 - > 4 - > 3 - > 2 - > 1 - > 0,总成本为30

我想过使用Dijkstra找到所有X(蓝色)节点之间的最短路径,然后贪婪地选择最近的未访问的X(蓝色)节点,但它不起作用(在纸上提出32而不是30).我后来也注意到,只是找到所有X节点对之间的最短路径将花费O(X*N ^ 2)时间,这个时间太多而节点太多了.

我唯一可以找到的电路是Eulerian电路,它只允许访问每个节点一次(我不需要它).这可以用Dijkstra解决,还是有其他算法可以解决这个问题？

我有一个只包含数字0-9的字符串.字符串的长度可以在1到1,000,000个字符之间.我需要在线性时间内找到字符串中不存在的最小数字.这里有些例子:

1023456789       //Smallest number not in string is 11
1023479          //Smallest number not in string is 5
112131405678910  //Smallest number not in string is 15

大小为1,000,000,我认为字符串中不存在的最小数字必须至多为6位数.

我的方法是生成所有数字0到999,999并将它们全部插入到一个向量中(按顺序).然后制作一个标记已经看到的字符串的地图.然后我遍历字符串,对于每个位置,我得到从它开始的所有子字符串,大小为1到6,并且我在地图中将所有这些子字符串标记为true.最后,我只是逐个检查所有键,当我发现第一个在地图中有假值时,我打印出来.

以下是一些代码段:

string tmp="0";
string numbers[999999];

void increase(int pos)
{
    if(pos==-1)tmp.insert(0,"1");
    else if(tmp.at(pos)!='9')tmp.at(pos)++;
    else
    {
        tmp.at(pos)='0';
        increase(pos-1);
    }
}

//And later inside main
for(int j=0;j<999999;j++)
{
    numbers[j]=tmp;
    increase(tmp.size()-1);
}

for(int j=0;j<input.size();j++)
    {
        for(int k=0;k<6;k++)
        {
            string temp="";
            if(j+k<input.size())
            {
                temp+=input.at(j+k);
                appeared[temp]=true;
            }
        }
    }

int counter=0;
while(appeared[numbers[counter]])counter++;
cout<<numbers[counter]<<endl;

关于算法第一部分的说明.我生成一次矢量,然后我用它100个字符串.我需要在不到4秒的时间内解析所有100个字符串.

这个算法对我来说太慢了,因为它是目前的.我可以优化一些代码,还是应该考虑不同的方法？

在为编程竞赛（如 ACM、Code Jam 等）练习时，我遇到了一些问题，需要我生成一些向量元素的所有可能组合。

假设我有向量 {1,2,3}，我需要生成以下组合（顺序不重要）：

1
2
3
1 2
1 3
2 3
1 2 3

到目前为止，我已经使用以下代码完成了它：

void getCombinations(int a)
{
    printCombination();
    for(int j=a;j<vec.size();j++)
    {
        combination.pb(vec.at(j));
        getCombinations(j+1);
        combination.pop_back();
    }
}

调用 getCombinations(0); 为我做这项工作。但是有更好（更快）的方法吗？我最近听说了位掩码。据我所知，它只是针对 1 到 2^N-1 之间的所有数字，我将该数字转换为二进制，其中 1 和 0 表示该元素是否包含在组合中。

我如何有效地实现这一点？如果我把每个数字都按照标准的方式（一直除以 2）变成二进制，然后检查所有的数字，似乎浪费了很多时间。有没有更快的方法？我是否应该继续使用递归（除非我遇到一些递归无法完成工作的大数字（堆栈限制））？