用了三种理解 1.先比较再四舍五入输出，发现会17行wa；
2.先四舍五入再比较，发现会在更后面的点wa;
3.先比较再四舍五入输出（比较时将差值小于1e-7视作相等），然后就过了…
3244. KL排序
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
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}')
香香
这个回答确实帮上大忙了