题解 P2165 【[AHOI2009]飞行棋】

Heartlessly · 2019-07-08 20:37:43 · 题解

Description

给出圆周上的 n 个点，已知点与点之间的弧长，其值均为正整数，并依照圆周顺序排列。求从中选出 4 个点且能围成矩形的方案数。(1 \leq n \leq 20)

Solution

最容易想到的方法是维护前缀和数组，枚举 4 个点，计算点与点之间的弧长，判断相对的两条弧是否都相等即可（弧长相等，所对的弦长也相等，即矩形的对边相等）。时间复杂度为 O({\rm C}_n^4)，由于题目数据范围很小，可以轻松过。

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 20;
int n, sum, ans, a[MAXN + 5], pre[MAXN + 5];

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        pre[i] = pre[i - 1] + a[i];
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            for (int k = j + 1; k <= n; ++k)
                for (int l = k + 1; l <= n; ++l) {
                    int a = pre[i] + pre[n] - pre[l], b = pre[j] - pre[i], 
                    c = pre[k] - pre[j], d = pre[l] - pre[k];
                    //a,b,c,d 表示 4 个点把圆分成 4 段弧的长度各是多少，
                    //注意 a 要拆成两条弧算。
                    if (a == c && b == d) ++ans;//相对的两条弧都相等
                }
    write(ans);
    putchar('\n');
    return 0;
}

稍微聪明一点的做法？

首先要知道圆内接矩形的对角线是该圆的直径，因为 90^\circ 圆周角所对的弦是直径。假设有 cnt 条直径，那么任意 2 条不同的直径都能组成一个新的矩形，答案即为 {\rm C}_{cnt}^2 。我们只需要枚举 2 个点，判断这 2 个点之间的距离是不是圆周长的一半，就可以得到直径的数量。时间复杂度为 O({\rm C}_n^2) 。

注意特判圆周长是奇数时无解（所给的弧都是正整数，但半圆是小数，说明不存在直径），但是数据水不特判能过。