P8452 「SWTR-8」15B03 题解

· · 题解

分析

首先考虑第一问。

任何两张课桌不能相邻的含义是任何一张张课桌周围一圈都没有课桌。我们可以先想如何摆放课桌，就知道如何撤去课桌了。

很容易想到一种构造方法：四角都放课桌（如果符合要求），然后隔一行摆一行课桌直到第 \frac n 2 行，下半部分对称摆，摆一行时，隔一列摆一张课桌。这样可以使得撤去的课桌数量最少，因为四角的摆放使得课桌的周围一圈跑到边界之外，相当于多了一部分空间，其他按照要求摆放就可以撤去最少的课桌。

撤去课桌数量怎么计算呢？撤去的课桌是整行整列撤去的，那么行撤去的课桌数就是 \frac {n} {2} \times m，同理，列撤去的课桌数量就是 \frac {m} {2} \times n，多算了 \frac {n} {2} \times \frac m 2，再减去它即可。

化简可得撤去的课桌数量为 \frac {3mn} 4。

再考虑第二问。

我们发现，每张课桌最大距离具有某种对称关系。比如左上角的课桌距离右下角的课桌最远，那么右上角的课桌距离左下角的课桌的距离与此相等，左下角和右下角同理，也就是说，一般情况下，课桌的距离是成 4 出现的。当然有特殊情况：位于中线上的课桌。只位于行中线或列中线的课桌成对出现。同时位于行中线和列中线的课桌只有一张。所以我们只统计左上部分的课桌最远距离就能得到整体的最远距离了。

最远距离如何求呢？显然，对于左上部分的课桌，右下角的课桌距离它们最远，计算即可。

需要注意的是，当 n=1,m=2 或 n=2,m=1 或 n=2,m=2 时，只有一张课桌，所以距离是 0。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int T, n, m;
double ans;
inline int read(){//快读
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
signed main () {
    T = read(); T = read();
    while (T--) {
        ans = 0.0;
        n = read(); m = read();
        cout << n / 2 * m + m / 2 * n - (m / 2) * (n / 2) << ' ';//计算公式
        for (register int i = 1; i <= ((n + 1) >> 1); i += 2)
            for (register int j = 1; j <= ((m + 1) >> 1); j += 2)
                if (i == (n + 1) / 2 && j == (m + 1) / 2)//位于正中央
                    ans += sqrt(1.0 * (n - i) * (n - i) + (m - j) * (m - j));
                else if (i == (n + 1) / 2 || j == (m + 1) / 2)//位于边中线或列中线
                    ans += sqrt(1.0 * (n - i) * (n - i) + (m - j) * (m - j)) * 2;
                else//一般情况
                    ans += sqrt(1.0 * (n - i) * (n - i) + (m - j) * (m - j)) * 4;               
        if ((n == 1 && m == 2) || (n == 2 && m == 1) || (n == 2 && m == 2))//特殊情况
            cout << 0 << "\n";
        else
            printf("%.9lf\n", ans);
    }
    return 0;
}