这几天在学模拟退火,我在洛谷Hydro OJ 各交了一份同样的代码,代码如下:

/*
    I will never forget it.
*/

// 392699

#include <bits/stdc++.h>

using namespace std;

void fr(int &a, bool f = 0, char ch = getchar()) {
    for (a = 0; ch < '0' || ch > '9'; ch = getchar()) ch == '-' ? f = 1 : 0;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) a = a * 10 + ch - '0';
    a = f ? -a : a;
}
int fr() {
    int a;
    return fr(a), a;
}

const int N = 1e4;
const double alpha = 0.974, eps = 1e-7;

int n;
double ansx, ansy, ansd, x[N + 10], y[N + 10], w[N + 10];

double dist(double xa, double ya, double xb, double yb) { return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb)); }

double calc(double tx, double ty) {
    double res = 0;
    for (int i = 1; i <= n; i++) res += dist(x[i], y[i], tx, ty) * w[i];
    if (res < ansd) ansd = res, ansx = tx, ansy = ty;
    return res;
}

double rnd() { return (double)rand() / RAND_MAX; }

void SimulateAnneal() {
    double temp = 2e3, nowx = ansx, nowy = ansy;
    while (temp > eps) {
        double tx = nowx + temp * (rnd() * 2 - 1), ty = nowy + temp * (rnd() * 2 - 1);
        double delta = calc(tx, ty) - calc(nowx, nowy);
        if (delta < 0 || rnd() < exp(-delta / temp)) nowx = tx, nowy = ty;
        temp *= alpha;
    }
}

struct OI {
    int RP, score;
} CSPS2021, NOIP2021;

int main() {
    CSPS2021.RP++, CSPS2021.score++, NOIP2021.RP++, NOIP2021.score++, 392699;
    srand(999392699);
    fr(n);
    for (int i = 1; i <= n; i++) scanf("%lf%lf%lf", &x[i], &y[i], &w[i]), ansx += x[i], ansy += y[i];
    ansx /= n, ansy /= n, ansd = calc(ansx, ansy);
    for (int i = 1; i <= 5; i++) SimulateAnneal();
    for (int i = 1; i <= 7000; i++) {
        double tx = ansx + 0.001 * (rnd() * 2 - 1), ty = ansy + 0.001 * (rnd() * 2 - 1);
        calc(tx, ty);
    }
    return printf("%.3lf %.3lf\n", ansx, ansy), 0;
}

洛谷评测记录 Hydro OJ 评测记录

可以发现在洛谷上的评测最大点时间约为 100ms ,然而在 Hydro OJ 上却 TLE 了。

请问这是为什么?为何两个 OJ 之间评测的差异会相差这么多?

2 条评论

  • 1