求助:本题的奇妙的问题
查看原帖
求助:本题的奇妙的问题
365751
Mr_罗楼主2022/12/3 21:18

RT,我在本地和洛谷在线 IDE 运行样例 #10,全部是正确的:

10
9
10
9
10

但是提交后给我报的错是酱:

Wrong Answer.wrong answer On line 1 column 1, read 0, expected 1.

请问这是为什么?

代码:

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 18, K = (1 << N);
const double eps = 1e-6;
int n, m;
double x[N], y[N];
int f[K + 10], ln[N][N];
int ft[K + 10];

void get_line (double &a, double &b, double x, double y, double X, double Y)
{
    a = -(y * X - Y * x) / (x * X * X - x * x * X);
    b = (y * X * X - Y * x * x) / (x * X * X - x * x * X);
}
// void equation (double &a, double &b, int i, int j)
// {
// 	a = -(y * X - Y * x) / (X * X * x - x * x * X);
// 	b = (y * X * X - Y * x * x) / (x * X * X - X * x * x);
// }

void solve()
{
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf ("%lf%lf", &x[i], &y[i]);
    memset (ln, 0, sizeof ln);
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (x[i] == x[j])
                continue;
            double a, b;
            get_line (a, b, x[i], y[i], x[j], y[j]);
            if (a > -eps)
                continue;
            for (int k = 1; k <= n; k++)
            {
                // printf ("%d %.6f %.6f %.6f\n", k, x[k], y[k], a * x[k] * x[k] + b * x[k]);
                if (fabs (a * x[k] * x[k] + b * x[k] - y[k]) < eps)
                    ln[i][j] |= (1 << k - 1);
            }
            ln[j][i] = ln[i][j];
            // printf ("%d-%d %d: %.6f %.6f\n", i, j, ln[i][j], a, b);
        }
    }
    for (int s = 0; s < (1 << n); s++)
    {
        for (int i = 1; i <= n; i++)
        {
            if ((s & (1 << i - 1)) == 0)
            {
                ft[s] = i;
                break;
            }
        }
    }
    memset (f, 0x3f, sizeof f);
    f[0] = 0;
    for (int s = 0; s < (1 << n); s++)
    {
        // printf ("%d %d\n", s, f[s]);
        int i = ft[s];
        for (int j = i + 1; j <= n; j++)
        {
            if (s & (1 << j - 1))
                continue;
            f[s | ln[i][j]] = min (f[s | ln[i][j]], f[s] + 1);
        }
        for (int j = 1; j <= n; j++)
        {
            if (s & (1 << j - 1))
                continue;
            f[s | (1 << j - 1)] = min (f[s | (1 << j - 1)], f[s] + 1);
        }
    }
    printf ("%d\n", f[(1 << n) - 1]);
}

int main()
{
    int T;
    scanf ("%d", &T);
    while (T--)
        solve();
    return 0;
}
2022/12/3 21:18
加载中...