小编214*_*647的帖子

路径的"长度"是路径中的边数.

给定源和目标顶点,我想找到从源顶点到给定长度 k 的目标顶点的路径数.

• 我们可以根据需要多次访问每个顶点,因此如果路径来自a于b:a -> c -> b -> c -> b它被认为是有效的.这意味着可以有循环,我们可以不止一次通过目的地.

• 两个顶点可以通过多个边连接.因此,如果顶点a顶点b通过两条边连接,那么a -> b通过边1和a -> b边2 的路径被认为是不同的.

• 顶点数N <= 70,路径长度K <= 10 ^ 9.

• 由于答案可能非常大,因此应以模数为单位进行报告.

这是我到目前为止所想到的:

我们可以使用广度优先搜索而不将任何顶点标记为访问,在每次迭代时,我们跟踪我们对该路径所需的边数'n_e'和产品 'p'中每个边缘的重复边数路径有.

如果n_e大于k,则搜索搜索应该终止,如果我们以n_e等于k 到达目的地,我们终止搜索并添加p到路径数的计数.

我认为我们可以使用深度优先搜索而不是广度优先搜索,因为我们不需要最短路径,并且在广度优先搜索中使用的Q的大小可能是不够的.

我正在考虑的第二种算法类似于使用这种方法的Floyd Warshall的算法.只有我们不需要最短的路径,所以我不确定这是否正确.

我的第一个算法的问题是'K'可以达到1000000000,这意味着我的搜索将一直运行,直到它有10 ^ 9个边缘,n_e边缘计数将在每个级别增加1,这将非常慢,我不确定它会终止大输入.

所以我需要一种不同的方法来解决这个问题; 任何帮助将不胜感激.

这是问题(链接:http://opc.iarcs.org.in/index.php/problems/FINDPERM):

数字1,...,N的排列是这些数字的重新排列.例如,
2 4 5 1 7 6 3 8
是1,2,...,8的置换.当然,
1 2 3 4 5 6 7 8
也是1,2,...,8的置换.
与N的每个排列相关联的是长度为N的正整数的特殊序列,称为其反转序列.该序列的第i个元素是严格小于i的数字j的数量,并且在该排列中出现在i的右侧.对于置换
2 4 5 1 7 6 3 8
,反转序列是
0 1 0 2 2 1 2 0
第二个元素是1,因为1严格小于2,在这个排列中它出现在2的右边.类似地,第5个元素是2,因为1和3严格小于5但在此排列中出现在5的右侧,依此类推.
作为另一个例子,置换的反转序列
8 7 6 5 4 3 2 1
是
0 1 2 3 4 5 6 7
在这个问题中,你将得到一些置换的反演序列.您的任务是从此序列重建置换.

我想出了这段代码:

#include <iostream>

using namespace std;

void insert(int key, int *array, int value , int size){
    int i …

我不想找到所有最小的生成树,但我想知道它们中有多少,这是我考虑的方法:

• 使用prim或kruskal算法找到一个最小生成树,然后找到所有生成树的权重,并在它等于最小生成树的权重时递增运行计数器.

我找不到任何方法来查找所有生成树的权重,并且生成树的数量可能非常大,因此此方法可能不适合该问题.由于最小生成树的数量是指数级的,因此将它们计算起来并不是一个好主意.

• 所有权重都是正数.
• 我们也可以假设图表中没有重量超过三次.
• 顶点数量将小于或等于40,000.
• 边数将小于或等于100,000.

图中只有一个最小生成树,顶点权重不同.我认为找到最小生成树数量的最佳方法必须是使用此属性的东西.

编辑:

我找到了解决这个问题的方法,但我不确定,为什么会这样.任何人都可以解释一下.

解决方案:找到最小生成树的长度的问题是众所周知的; 用于查找最小生成树的两个最简单的算法是Prim算法和Kruskal算法.在这两个中,Kruskal的算法按其权重的递增顺序处理边缘.然而,Kruskal算法需要考虑一个重要的关键点:当考虑按权重排序的边缘列表时,可以将边缘贪婪地添加到生成树中(只要它们不连接已经以某种方式连接的两个顶点) ).

现在考虑使用Kruskal算法的部分形成的生成树.我们插入了一些长度小于N的边,现在必须选择长度为N的几条边.算法表明如果可能的话,我们必须在任何长度大于N的边之前插入这些边.但是,我们可以以我们想要的任何顺序插入这些边.另请注意,无论我们插入哪个边缘,它都不会改变图形的连通性.(让我们考虑两个可能的图形,一个具有从顶点A到顶点B的边缘,一个没有边缘.第二个图形必须具有A和B作为相同连通分量的一部分;否则从A到B的边缘将被插入到一点.)

这两个事实共同意味着我们的答案将是使用Kruskal算法的方式数量的乘积来插入长度为K的边(对于K的每个可能值).由于任何长度最多有三个边缘,因此可以强制使用不同的情况,并且可以在每个步骤之后确定连接的组件,因为它们通常是正常的.

我正在尝试解决在线判断问题:http://opc.iarcs.org.in/index.php/problems/LEAFEAT

问题简而言之:

如果我们给出一个整数L和一组N个整数s1,s2,s3..sN,我们必须找到从0到L-1的数字,它们不能被任何'si'整除.

例如,如果我们得到, L = 20和S = {3,2,5}然后有6个号码从0到19,其不被整除3,2或5.

L <= 1000000000且N <= 20.

我使用包含 - 排除原则来解决这个问题:

/*Let 'T' be the number of integers that are divisible by any of the 'si's in the 
given range*/

for i in range 1 to N
  for all subsets A of length i
    if i is odd then:
      T += 1 + (L-1)/lcm(all the elements of A)
    else
      T -= 1 + (L-1)/lcm(all the elements of A) …

我正在制作一个解决这个问题的程序:http://opc.iarcs.org.in/index.php/problems/BOOKLIST

我使用矢量的唯一地方是:

for(int i =0;i < total_books; i++){
    int temp;
    cin >> temp;
    books_order.push_back(temp);
}

和

for(int i = 0;i < total_entries; i++){
    int index;
    cin >> index;
    index--;
    cout << books_order[index] << endl;
    books_order.erase(books_order.begin()+index);
}

(这是我的完整代码:http://cpaste.org/1377/)

我从向量中使用的唯一函数是vector :: erase,vector :: push_back和vector :: begin.对于大输入,我的代码花费的时间超过3秒(这是该问题的时间限制),但是当我删除向量函数时,它运行得更快(但是给出了错误的答案)

我明白在这个问题中使用向量是错误的,我的算法很慢,但我不明白为什么它很慢.

如果您知道为什么我使用的功能很慢,请向我解释.谢谢.

我们在2D平面上给出N(N <= 10 ⁶)个点并且给出整数D(N <= 10 ⁶),我们想要找到两个点p1,p2(p1右边的p2)使得它们之间的差异p1.y并且p2.y至少是D并且p2.x - p1.x被最小化.

x轴和y轴的范围为0..10 ⁶

这是USACO过去的比赛中的一个问题.

这是我尝试解决它:
MAXY = N个点中的最大y轴.
假设我们知道p1,那么我们很容易找到p2; 通过将其y轴在该范围内的所有点都设置p1.y+D为MAXY或在0到0的范围内,p1.y-D并获取具有最大x轴的点大于p.x.这将是p2的最佳选择.

但是由于我们不知道p1,我们将不得不尝试p1的所有点,因此找到p2的最佳选择应该有效地完成.

我使用了一个分段树.树中的每个节点都将按照x轴的排序顺序存储相应范围内的所有点.在查询时,如果一个节点落在查询范围内,那么我们在数组上进行二进制搜索,p1.x并返回大于它的最小元素.

对于p1的每个选择,我们使用范围0,p1.yD和p1.y + D,MAXY两次查询树,并且在返回的两个点中取最佳值.

树的构建可以在O(NlogN)时间内完成.每个查询都需要O(logN*logN)时间,我们进行N次查询,因此所用的总时间为(Nlogn*logn),可能不会在2秒的时间限制内运行.(10 ⁶*20*20).所采用的存储器也将是O(NlogN),其大约为80mb(100000*20*4kb),这太大,因为限制是64mb.

我们如何更快地进行查询并使用更小的空间？

我使用维基百科的伪代码在c ++中编写了这个BFS代码.该函数采用两个参数s,t.其中s是源节点,t是目标,如果目标是fount,则搜索返回目标本身,否则返回-1.这是我的代码:

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

struct vertex{
vector<int> edges;
bool visited;
};

int dist = 0;

int BFS(vertex Graph[],int v,int target){
deque<int> Q;
Q.push_front(v);
Graph[v].visited = true;
    while(!Q.empty()){
        int t = Q.back();
        Q.pop_back();
            if(t == target){
                return t;
            }
            for(unsigned int i = 0;i < Graph[t].edges.size();i++){
                int u = Graph[t].edges[i];
                if(!Graph[u].visited){
                    Graph[u].visited = true;
                    Q.push_front(u);
                }
            }
    }
    return -1;
} 

int main(){
int n;
cin >> n;
vertex Graph[n];
int k;
cin >> …

这是我想解决的问题,

您将获得一个包含2行和N列的表.每个单元格中都有一个整数.这样一个表的分数定义如下:对于每一列,考虑列中两个数字的总和; 如此获得的N个数的最大值是得分.例如,对于表格

7 1 6 2
1 2 3 4

得分为max(7 + 1; 1 + 2; 6 + 3; 2 + 4)= 9.表的第一行是固定的,并作为输入给出.考虑第二行的N种可能方式:

1; 2; ::: ;; N
2; 3; ::: ;; N; 1
3; 4; ::: ;; N; 1; 2
|
N; 1; ::: ;; ; N 1

例如,对于上面的示例,我们将以下各项视为第二行的可能性.

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

您的任务是找到第二行上述每个选项的分数.在上面的示例中,您将评估以下四个表,

7 1 6 2
1 2 3 4
7 1 6 2 …