「Luogu P2165」「AHOI2009」飞行棋

Description

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

Source

[Luogu]P2165

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)$ 。

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

$\rm hack$ 数据：

Input

5
5 1 1 5 1

Output

0

#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, cnt, pre[MAXN + 5];

int main() {
    read(n);
    for (int x, i = 1; i <= n; ++i) {
        read(x);
        pre[i] = pre[i - 1] + x;
    }
    if (pre[n] & 1) {//特判圆周长是奇数的情况 
        puts("0");
        return 0;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (pre[j] - pre[i] == pre[n] / 2)//判断两点间弧长是否为圆周长的一半
                ++cnt;
    write(cnt * (cnt - 1) / 2);//答案为 C(cnt, 2)
    putchar('\n');
    return 0;
}

由于前缀和数组是单调递增的，我们甚至还可以用二分查找把时间复杂度优化到 $O(n \log n)$ 。

即把枚举过程换成：

for (int i = 1; i <= n; ++i)
    if (binary_search(pre + i + 1, pre + n + 1, pre[i] + pre[n] / 2))
        ++cnt;//用 STL 中的 binary_search 检查是否存在合法的 j

当然，由于这个单调递增的性质，也可以用尺取法（双指针法），时间复杂度为 $O(n)$ 。

for (int l = 1, r = 2; l <= n && r <= n; ) {
    if (pre[r] - pre[l] < pre[n] / 2) ++r;
    //若两点间的弧长小于圆周长的一半，则移动右端点，使弧长增大
    else if (pre[r] - pre[l] > pre[n] / 2) ++l;
    //若两点间的弧长大于圆周长的一半，则移动左端点，使弧长减小
    else ++l, ++r, ++cnt;
    //若两点间的弧长等于圆周长的一半，则更新 cnt，
    //同时移动左端点和右端点，寻找新的直径
}

Code

#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, cnt, pre[MAXN + 5];

int main() {
    read(n);
    for (int x, i = 1; i <= n; ++i) {
        read(x);
        pre[i] = pre[i - 1] + x;
    }
    if (pre[n] & 1) {//特判圆周长是奇数的情况 
        puts("0");
        return 0;
    }
    for (int l = 1, r = 2; l <= n && r <= n; ) {
        if (pre[r] - pre[l] < pre[n] / 2) ++r;
        //若两点间的弧长小于圆周长的一半，则移动右端点，使弧长增大
        else if (pre[r] - pre[l] > pre[n] / 2) ++l;
        //若两点间的弧长大于圆周长的一半，则移动左端点，使弧长减小
        else ++l, ++r, ++cnt;
        //若两点间的弧长等于圆周长的一半，则更新 cnt，
        //同时移动左端点和右端点，寻找新的直径
    }
    write(cnt * (cnt - 1) / 2);
    putchar('\n');
    return 0;
}