C. Symmetrical Polygons

Codeforces

Codeforces Round 1057 (Div. 2)

问题描述

给定 $n$ 根木棍，第 $i$ 根木棍的长度为 $a_i$ 。你需要选择这些木棍的一个非空子集，用它们作为多边形的边。每根被选中的木棍都必须完整地用作多边形的一条边。不允许将两根或多根木棍端对端平行连接以形成更长的边。

你的目标是构建一个对称、严格凸且非退化的多边形：

对称：存在一条对称线，当多边形沿此线对折时，两半完全重合。
严格凸：所有内角都严格小于 $180^\circ$ 。
非退化：没有两条连续的边至少部分重合，没有边的长度为零，也没有角等于 $180^\circ$ 。

在所有可以用这些木棍构成的此类多边形中，找出可能的最大周长。如果不存在有效的多边形，输出 0。

解题思路

一个对称多边形可以通过拥有成对等长的边来构建，这些边形成对称线两侧的“左”半部分和“右”半部分。这条对称线可以穿过两个顶点，也可以由两条平行的边定义。

我们来考虑这样一个多边形的结构。这些边可以分为两组：

成对的边：这些是成对等长的木棍。它们将形成多边形对称的“左”和“右”部分。
对称轴上的边：这些是位于对称轴上的木棍。一个对称多边形最多可以有两条这样的边，它们必须相互平行。可以认为一条是“顶”底，另一条是“底”底。也可能没有或只有一条这样的边。

核心思想是最大化周长。为此，我们应尽可能多地使用木棍。

首先，我们可以找出所有成对的等长木棍。这些成对的木棍将构成我们多边形周长的主体。假设每对木棍中一根木棍的长度总和为 sum_pairs。这些成对木棍对总周长的贡献将是 2 * sum_pairs。

剩下的木棍都是长度唯一的。这些是位于对称轴上的“顶”底和“底”底的候选者。我们将这些长度唯一的木棍按降序排序。为了最大化周长，我们应选择最长的两根唯一木棍作为我们的底。设它们的长度为 $b_1$ 和 $b_2$ （ $b_1 \ge b_2$ ）。

为了形成一个有效的、严格凸的多边形，必须满足一个多边形不等式定理的变种。成对的边长总和必须大于它们需要跨越的两个底之间的“间隙”。如果底是平行的，对称多边形一侧的边长总和必须大于两底之差的一半。即 sum_pairs > (b1 - b2) / 2，简化为 2 * sum_pairs > b1 - b2。

因此，整体算法如下：

计算每种木棍长度的出现次数。
对于任何出现两次或以上的木棍长度，我们可以形成对。将每对的长度加到一个运行总和 ans 中。例如，如果我们有三根长度为 5 的木棍，我们用两根形成一对（对周长贡献 $2 \times 5$ ），第三根成为底的候选。
未用于配对的木棍（剩余的）是我们顶底和底底的候选。
将这些候选底木棍按降序排序。
遍历排序后的候选底。对于每对相邻的候选 $(b_i, b_{i+1})$ ，检查它们是否能与我们的成对边形成一个有效的多边形。条件是 2 * ans > b_i - b_{i+1}。
总周长将是 2 * ans + b_i + b_{i+1}。我们希望找到可能的最大周长，所以我们取满足条件的第一对底 $(b_i, b_{i+1})$ 。由于底是按降序排序的，第一对有效的将产生最大周长。
我们也可以只有一个底，甚至没有底。我们可以通过在候选列表中添加两个长度为 0 的“虚拟”底来模拟这种情况。这涵盖了多边形在对称轴上的一个顶点处闭合的情况。

如果没有底的组合满足不等式，或者我们无法形成任何对且少于三根唯一木棍来形成一个基本的多边形，那么就不可能形成这样的对称多边形，答案为 0。

查看代码

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <tuple>
#include <vector>
using namespace std;
#define int long long
// #define mod 1000000007

#define N 500005
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = 0;
    vector<int> b;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (i < n - 1 && a[i] == a[i + 1]) {
            ans += a[i];
            i++;
            cnt += 2;
        } else {
            b.push_back(a[i]);
        }
    }
    // 逆序排序 B 中的项目
    sort(b.begin(), b.end(), greater<int>());
    // 在 b 的末尾添加 0
    b.push_back(0);
    b.push_back(0);
    for (int i = 0; i < b.size() - 1; i++) {
        if (b[i] == 0 && b[i+1] == 0 && cnt < 4){
            cout << 0 << endl;
            return ;
        }
        if ((b[i] - b[i + 1]) < ans * 2)  {
            cout << b[i] + b[i + 1] + 2 * ans << endl;
            return;
        }
    }
    cout << 0 << endl;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef DEBUG
    freopen("./input.txt", "r", stdin);
#endif
    int t;
    cin >> t;
    while (t--) {
#ifdef DEBUG
        static int test_num = 1;
        cout << "test case: " << test_num++ << endl;
#endif
        solve();
    }
}

B. Bitwise Reversion D. Not Alone