首页 > 试题广场 >

树与序列问题

[编程题]树与序列问题
  • 热度指数:1688 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一棵树,树的点编号为1到n,以1为根,树的边有边权,定义s(x,y)=x到y路径上边权的最小值。
现需要构造一个1到n的排列p[],使得最大,输出这个最大值即可。
示例1

输入

3,6,7,5

输出

77
示例2

输入

4,3,9,6

输出

297

备注:
树的边集不会直接给出,但会给出随机种子和构造方式,输入数据包含题干中的n和三个随机种子seed1,seed2,seed3.
构造方式如下
////////////////////////////
定义数组u[],v[],w[]                         //u[i],v[i]分别表示第i条边的两个端点,w[i]表示第i条边的边权。
定义变量seed4.
定义循环变量 i 从1到n-1
循环体开始
        seed4=((seed1+seed2)%998244353)*seed3%998244353;
        u[i]=i+1;
        v[i]=(seed4%i)+1;
        w[i]=seed2*seed3%12131415;
        seed3=seed2;
        seed2=seed1;
        seed1=seed4;
循环体结束
//////////////////////////////////////////////////////
输出一个整数,表示答案。
保证构造出的数据合法。
n<=200000,seed1,seed2,seed3<=1e10
因为s(x,y)=x到y路径上边权的最小值,想让答案尽可能大,我们肯定希望每个s(p[i],p[i+1])都取到边权的最大值,但遗憾的是这是做不到,这个很好验证,自己随便画个图就知道了。那么现在的问题就是这个最大值是多少呢?
因为p为一个排列,因此我们可知每个点都至少要访问一次,因此所有边至少都要被遍历一遍。因此最短边必然会算入答案,且可能不止一次。而最大边最多出现一次(只有w=(p[i],p[i+1])时才可能出现)。为了使得答案尽可能大,我们希望所有边都出现一次。即最大的答案也就是所有边权的和。
不过以上最大值只是我们的猜想,是否有这样的排列p能使得答案=所有边权的和?若必然有,那么我们可以确定答案就是所有边权的和。
我们可以这样构造排列。任选一个点为起点进行bfs。不过bfs过程中,用优先队列维护,以边的大小作为比较准则(即边越大越先出队该点)。节点出队的顺序即为构造出的使答案最大的排列。
class Solution {
public:
    /**
     *
     * @param n int整型
     * @param seed1 long长整型
     * @param seed2 long长整型
     * @param seed3 long长整型
     * @return long长整型
     */
    long long work(int n, long long seed1, long long seed2, long long seed3) {
        // write code here
        long long res = 0;
        for(int i=1;i<n;i++){
            long long seed4=((seed1+seed2)%998244353)*seed3%998244353;
            res+=seed2*seed3%12131415;
            seed3=seed2;
            seed2=seed1;
            seed1=seed4;
        }
        return res;
    }
};


发表于 2020-04-22 17:01:10 回复(4)
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param seed1 long长整型 
     * @param seed2 long长整型 
     * @param seed3 long长整型 
     * @return long长整型
     */

    long long work(int n, long long seed1, long long seed2, long long seed3) {
        long long s = 0;
        for(int i=1;i<n;i++){
            long long seed4 = (((seed1+seed2)%998244353)*seed3)%998244353;
            s += (seed2*seed3)%12131415;
            seed3 = seed2;
            seed2 = seed1;
            seed1 = seed4;
        }
        return s;
    }
};

发表于 2020-09-03 16:42:29 回复(0)
以示例输入为例
3,6,7,5
生成
      u -> v  = w
i=1   2 -> 1  = 35
i=2   3 -> 2  = 42

树结构 1 <-35- 2 <-42- 3

i的排列有以下6种
p[1,2,3]    1 -> 2  min(w)=35  2->3 min(w)=42    sum=77 p[1,3,2]    1 -> 3  min(w)=35  3->2 min(w)=42    sum=77
p[2,1,3]    2 -> 1  min(w)=35  1->3 min(w)=35    sum=70
p[2,3,1]    2 -> 3  min(w)=42  3->1 min(w)=35    sum=77
p[3,1,2]    3 -> 1  min(w)=35  1->2 min(w)=35    sum=70
p[3,2,1]    3 -> 2  min(w)=42  2->1 min(w)=35    sum=77
                                                 max(sum)=77
可以看出所求的最大值即所有边的权重和,直接利用题目给的生成树方法,求权值和就ok了 

发表于 2020-06-12 21:48:17 回复(0)
class Solution:
    def work(self , n , seed1 , seed2 , seed3 ):
        res=0
        for i in range(n-1):
            seed4=((seed1+seed2)%998244353)*seed3%998244353
            res+=seed2*seed3%12131415
            seed3,seed2,seed1=seed2,seed1,seed4
        return res

发表于 2020-04-08 13:10:47 回复(3)