题目链接：https://loj.ac/problem/2537 考虑到题目是一颗二叉树，有一个简单的O(N^2)的DP做法。f(i,j)表示i号点取值为数集中第j大数的概率，每一次我们从子树合并上来。j被取到有两种情况：j更大并且当前选择的是最大值 j更小并且当前选择的是最小值分情况讨论，发现要转移需要一个选到比j小的值的概率和(比j大的可以直接用1减比j小的)。那么我们维护两个前缀和(对两边的元素分别计算)，即可完成一次合并。 如何优化这个算法呢？假设两边子树可以产生的j值集合分别为A，B。考虑A值域上这样连续的一段数：满足不存在B[i]使得A[l]<=B[i]<=A
【题目描述】给定一棵n个点的有根树，编号依次为1到n，其中1号点是根节点。每个节点都被染上了某一种颜色，其中第i个节点的颜色为c[i]。如果c[i]=c[j]，那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离，为了方便起见，你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面，你将面临m个问题。 每个问题包含两个整数x和d，表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色。请写一个程序，快速回答这些询问。 【输入】第一行包含一个正整数T(1<=T<=500)，表示测试数据的组数。 每组数据中，第
Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a non-empty substring of its name. For example, if the company name is "hornsandhoofs", then substrings "sand" and "hor" could b
题目描述Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some interesting features: The tree consists of straight branches, bifurcations and leaves. The trunk stemming from the ground is also a branch. Each branch ends with either a bifurcation or a leaf on its top end. E
题目描述永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。 现在有两种操作： B x y 表示在岛 x 与岛 y 之间修建一座新桥。 Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。 输入输出格式输入格式： 输入文件第一行是用空格隔开的两
Rockdu's Blog