634 人解决,721 人已尝试。
950 份提交通过,共有 4247 份提交。
1.7 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
一个随机变量 $x$ 可能取 $K$ 个值。在没有做实验时,我们事先给它的估计是均匀分布 $\frac{1}{K}$。在做 $M$ 次随机取值的实验之后,若取某个值 $i$ 的次数为 $L_i$,则该随机变量 $x$ 的分布记为 $p(x=i)=\frac{L_i+1/K}{M+1}$。
对于两个可以取同一组值的随机变量 $x$ 和 $y$,$y$ 到 $x$ 的 KL 散度表示为:
$$\sum_{i=1}^K p(x=i) \ln \frac{p(x=i)}{p(y=i)}$$
说明:$\ln$ 是以 $e$ 为底的对数。
现在有 $N+1$ 个随机变量 $x,y_1,\ldots,y_N$,并有它们在多次实验中取每个值的次数。请计算 $y_j$ $(j=1,2,3,\ldots,N)$ 到 $x$ 的 KL 散度值,散度值要求精确到小数点后4位。并根据 $y_j$ 到 $x$ 的KL散度由小到大对 $y_1,\ldots,y_N$ 进行排序。若散度值一样则以输入顺序排序。
第 1 行:整数 $T(1 \leq T \leq 10)$ 为测试数据组数。
每组测试数据按照如下格式进行输入:
第 1 行:两个整数 $K$ 和 $N$ 的值,$2 \leq k \leq 10, 2 \leq N \leq 200$,$K$ 为随机变量可能的取值个数,$N$ 为待排序的随机变量个数。
第 2 行:$K$ 个整数,整数取值范围在 $[0,1000]$ 之间,表示 $x$ 在实验中取每个值的次数。
第 3~N+2 行:每行 $K$ 个整数,整数取值范围在 $[0,1000]$ 之间,表示待排序的随机变量 $y_j$ 在实验中取每个值的次数。按输入顺序 $j(j=1,\ldots,N)$ 是每个待排序随机变量的标号。
对于每组测试数据,输出一行对应的编号(编号从 0 开始,格式:case #0:
等),然后接下来 $N$ 行输出排序的结果。每行输出一个整数和一个浮点数,分别是排序后的标号 $j$ 和对应的随机变量 $y_j$ 到 $x$ 的 KL 散度值,两个数之间以一个空格分隔,浮点数四舍五入到小数点后 4 位。
3 2 2 1 1 0 5 5 0 2 3 3 3 2 3 6 1 7 7 3 2 2 3 4 5 6 7 7 6 3
case #0: 1 0.5928 2 0.5928 case #1: 3 0.0000 1 0.0141 2 0.2477 case #2: 1 0.0070 2 0.1632
ln是以e为底的对数,C语言提供了标准库函数log计算以e为的对数。
函数原型:double log(double x);
头文件:<math.h>
在计算过程,请进行如下判断:
if(fabs(散度值)<1e-7) 散度值=0.0000;
浮点数的数据类型请定义为 double
。
对第三组测试数据的解释:
3 2 //K=3,N=2,随机变量可能的取值个数为3,待排序的随机变量个数为 2 2 3 4 //x在实验中取第一个值的次数为2,取第二个值的次数为3, 取第三个值的次数为4,实验次数M=9 5 6 7 //y1在实验中取第一个值的次数为5,取第二个值的次数为6,取第三个值的次数为7,实验次数M=18 7 6 3 //y2在实验中取第一个值的次数为7,取第二个值的次数为6,取第三个值的次数为3,实验次数M=16
634 人解决,721 人已尝试。
950 份提交通过,共有 4247 份提交。
1.7 EMB 奖励。