题解

本题要求在给定城镇数量 $n$ 的情况下，规划城镇和道路的位置，使得在满足特定条件下啤酒摊的数量达到最大。这些条件包括：

1. 修建尽可能少的双向道路，让任意两个城镇保持连通，并且当任意一条道路关闭时，这种连通性依然得以维持。
2. 所有道路必须是几何直线，旅行者要能够沿着完整的直线道路通行，不能中途换路。
3. 啤酒摊设置在道路的交叉点，每个交叉点仅设一个摊位。

思路分析

• 道路构建：为了满足“任意一条道路关闭时，所有城镇仍保持连通”的条件，我们需要构建一个哈密顿回路（即一个经过每个顶点恰好一次的回路）。因为哈密顿回路是一个环形结构，去掉其中任意一条边，剩下的边依然能让所有顶点保持连通，而且它是满足连通性的最少边数的回路。
• 啤酒摊数量计算：啤酒摊的数量取决于道路交叉点的数量。
  • 当 $n\leq2$ 时：由于城镇数量过少，无法形成道路交叉点，所以啤酒摊数量为 0。
  • 当 $n$ 为偶数时：
    • 我们可以将 $n$ 个城镇均匀分布在一个圆周上。在这种情况下，每两条不相邻的边都会相交于圆内一点。
    • 对于一个有 $n$ 个顶点的多边形，从每个顶点出发，与不相邻的顶点相连的边数为 $n - 3$ 条（除去自身以及相邻的两个顶点）。
    • 因为有 $n$ 个顶点，所以总共有 $n\times(n - 3)$ 条这样的边。但每一条边都被重复计算了两次（例如从顶点 $A$ 到顶点 $B$ 的边和从顶点 $B$ 到顶点 $A$ 的边是同一条边），所以实际不同的边数为 $\frac{n\times(n - 3)}{2}$。
    • 然而，在计算交叉点时，由于是偶数个顶点，会存在一个额外的交叉点（所有对角线的中心点），所以最终的交叉点数量为 $\frac{n\times(n - 4)}{2}+1$。
  • 当 $n$ 为奇数时：同样将 $n$ 个城镇均匀分布在圆周上，每两条不相邻的边会相交于圆内一点。此时，交叉点的数量就是 $\frac{n\times(n - 3)}{2}$。

#include<iostream>
using namespace std;

int n;

int main(){
    cin >> n; // 读取测试用例的数量
    while(n--){
        int a;
        cin >> a; // 读取每个测试用例中的城镇数量
        if(a<=2) cout << 0<< endl; // 当城镇数量小于等于 2 时，啤酒摊数量为 0
        else if(a%2==0)
        {
            cout << a*(a-4)/2+1 << endl; // 当城镇数量为偶数时，计算并输出啤酒摊数量
        }
        else cout << a*(a-3)/2 << endl; // 当城镇数量为奇数时，计算并输出啤酒摊数量
    }
}

这段代码通过读取测试用例的数量，然后针对每个测试用例读取城镇数量 $a$，根据 $a$ 的不同情况计算并输出啤酒摊的最大数量。

综上所述，该题的核心在于根据城镇数量的奇偶性，通过数学方法计算出道路交叉点的数量，从而得到啤酒摊的最大数量。