3244. KL排序

wzf2018

用了三种理解 1.先比较再四舍五入输出,发现会17行wa;
2.先四舍五入再比较,发现会在更后面的点wa;
3.先比较再四舍五入输出(比较时将差值小于1e-7视作相等),然后就过了…

我命由我不由天

香香

ryu234

这个回答确实帮上大忙了

三七茧茧

存在特判数据出错。是因为先把散度值四舍五入,然后再进行比较。应该是先进行比较,然后在输出的时候强制转换成四舍五入的形式。

150042

原来不止在比较的时候要考虑1e-7,求kl的时候也要考虑1e-7…

MasterKiller

emm.....怎么说呢。特判数据这个行为,也不好说哪不对。但总是怪怪的……

Fifnmar

这道题考察了浮点数的比较和运算,挺好的。但我得说,如果用 C++ 的话就不要写 C 的 fabs 了,那个已经是 Deprecated 了,应该用 abs。此外,用 C 库的话最好加上 std:: 声明来显式要求用 C++ 版本。我遇到过神奇的情况会调 C 语言的函数 Orz。

下面是建类的邪教写法,不过我第一反应就是这样子所以就这么写了 Orz。

class Variable {
    std::vector<double> distribution;

  public:
    constexpr static auto ERR = 1e-7;

    Variable(std::vector<uint32_t> const &experiment) {
            // mp1 -> m plus 1.
        double mp1 = accumulate(experiment.begin(), experiment.end(), (uint32_t)1);
        auto k_reciprocal = 1.0 / (double)experiment.size();
        for (auto i : experiment) {
            distribution.push_back((i + k_reciprocal) / mp1);
        }
    }

    double relative_entropy(Variable const &denom) const {
        auto iter = denom.distribution.begin();
        auto ret = accumulate(distribution.begin(), distribution.end(), 0.0,
                              [&iter](double accum, double inc) mutable {
                                  return accum + inc * std::log(inc / *iter++);
                              });
        return std::abs(ret) < ERR ? 0.0 : ret;
    }
};

class Y : public Variable {
    uint32_t _id;
    double _kl_dis;

  public:
    Y(std::vector<uint32_t> const &experiment, Variable const &x, uint32_t id)
        : Variable(experiment), _id(id) {
        _kl_dis = x.relative_entropy(*this);
    }

    uint32_t id() const { return _id; }

    double kl_dis() const { return _kl_dis; }

    bool operator<(Y const &rhs) const {
        if (std::abs(_kl_dis - rhs._kl_dis) < ERR) {
            return _id < rhs._id;
        } else {
            return _kl_dis < rhs._kl_dis;
        }
    }
};

int main() {
    using namespace std;
    uint32_t t; cin >> t;
    for (uint32_t query = 0; query < t; ++query) {
        printf("case #%u:\n", query);
        uint32_t k, n; cin >> k >> n;
        vector<uint32_t> exp(k);
        for (auto &i : exp) {
            cin >> i;
        }
        Variable x(exp);
        vector<Y> yarr;
        for (uint32_t i = 1; i <= n; ++i) {
            for (auto &i : exp) {
                cin >> i;
            }
            yarr.push_back({exp, x, i});
        }
        sort(yarr.begin(), yarr.end());
        for (auto const &y : yarr) {
            printf("%u %.4lf\n", y.id(), y.kl_dis());
        }
    }
}
10175102262 LarsPendragon

这道题大概是答案有误,在输出结果前加一句

if(***==197/*指代y的编号,下同*/)printf("107 0.3438\n");
else if(***==107)printf("197 0.3438\n");

就可以避免WA

ultmaster

特判错误数据666。。。

ryu234

单看题目我其实也没有理解到比较的时候要算离散值小于1e-7的情况,看了评论才知道不仅是算kl的时候要算散度值小于1e-7,比较的时候还要算两者的差值小于1e-7

10175101282

答案无误,可以参考statistics里面别人的代码……注意浮点数误差。

爱丽丝_青贝尔克

表示没有碰到这种情况,你是不是先近似再比较了

10175102214

额,我想问一下,这道题到底是检测数据有问题还是向他们说的那样没错误,只是打开方式不对。。。如果是后者,可为啥我改了好几次还是错的。。。

10175101115

应该是比较的时候没有算提示里离散值小于1e-7的情况,我一开始也是这里出错了。。

10175101103-STARK

用long double类型存储就不会有精度问题了

Fifnmar

反对。C 语言中的 long double 的表示是未定义的,不应该使用 long double, 只应该使用 floatdouble,除非你有 platform-specific 需求。

而且对层主的发言也不赞同。面向测试数据做题本来就是旁门左道。

CCXXXI_

这么坑的题我得留个名
本身没什么难度,靠模糊不清的描述卡人,真的没意思
Hard难度不该是这么来的


from math import log, isclose, fabs
from functools import cmp_to_key as c2k


def p(xy, i):
    return (xy[i] + 1 / K) / (sum(xy) + 1)


def kl(y):
    rtn = sum((p(x, i) * log(p(x, i) / p(y, i))) for i in range(K))
    return 0 if fabs(rtn) < 1e-7 else rtn


@c2k
def fuck(a, b):
    return 0 if isclose(a, b, abs_tol=1e-7) else a - b


T = int(input())
for t in range(T):
    K, N = map(int, input().split())
    x = [int(num) for num in input().split()]
    yy = [[int(num) for num in input().split()] for _ in range(N)]
    print(f'case #{t}:')
    ans = [(j + 1, kl(y)) for j, y in enumerate(yy)]
    ans.sort(key=lambda x: fuck(x[1]))
    for idx, num in ans:
        print(idx, f'{num:.4f}')
你当前正在回复 博客/题目
存在问题!