企业官网建设流程全解析

题目描述

一个由nnn对（共2n2n2n个）人组成的群体围成一个圆圈。每个人必须且只能与另一个人握手一次，从而形成nnn条握手连线。若两条连线在圆内相交，则称为交叉握手。题目要求计算在避免任何交叉的前提下，能够覆盖全体成员的握手方案总数。题目给出了n=3n = 3n=3的示意图，用以说明合法的握手方式。

输入格式

输入包含若干组数据，每组数据之间以一个空行分隔。每组数据仅包含一个整数nnn，表示群体中人的对数为nnn，满足1≤n≤101 \le n \le 101≤n≤10。

输出格式

对于每组数据，输出一个整数，表示该组数据对应的无交叉握手方案总数。不同数据集之间的输出用一个空行分隔。

样例输入

4

样例输出

14

题目分析

该问题本质上是圆上2n2n2n个点的非交叉完美匹配计数问题。将2n2n2n个人按顺时针顺序编号为1,2,…,2n1, 2, \dots, 2n1,2,…,2n。要求用nnn条弦将2n2n2n个点两两配对，并且任意两条弦在圆内均不相交。这类计数问题在组合数学中具有经典结论，其方案数恰好等于第nnn个卡特兰数（Catalan Number\texttt{Catalan Number}Catalan Number），记为CnC_nCn​。

卡特兰数的定义为

Cn=1n+1(2nn) C_n = \frac{1}{n+1}\binom{2n}{n}Cn​=n+11​(n2n​)

其前若干项为C1=1C_1 = 1C1​=1，C2=2C_2 = 2C2​=2，C3=5C_3 = 5C3​=5，C4=14C_4 = 14C4​=14，C5=42C_5 = 42C5​=42。当n=4n = 4n=4时，方案数为141414，与样例输出一致。题目给定nnn的上界为101010，因此第101010个卡特兰数C10=16796C_{10} = 16796C10​=16796，结果远小于323232位有符号整数的表示范围，使用646464位整数存储完全足够。

解题思路

由于nnn的范围极小（1≤n≤101 \le n \le 101≤n≤10），可以直接采用递推方式预处理出所有可能用到的卡特兰数。递推公式为

Cn=Cn−1×2(2n−1)n+1 C_n = C_{n-1} \times \frac{2(2n-1)}{n+1}Cn​=Cn−1​×n+12(2n−1)​

该公式由卡特兰数的通项公式变形而来，能保证每一步除法均为整除，避免浮点误差。预处理时从C1=1C_1 = 1C1​=1开始，依次计算至C19C_{19}C19​（远大于nnn的上界101010），并将结果存入数组catalan[n]\textit{catalan}[n]catalan[n]。对于每个输入的nnn，直接输出catalan[n]\textit{catalan}[n]catalan[n]即可。由于输入可能包含多组数据且以空行分隔，采用while (cin >> n)循环读取，并在每组输出前根据是否为第一组决定是否打印空行，从而满足输出格式要求。时间复杂度为O(nmax⁡)O(n_{\max})O(nmax​)，空间复杂度为O(nmax⁡)O(n_{\max})O(nmax​)，其中nmax⁡=20n_{\max} = 20nmax​=20。

代码实现

// Safe Salutations// UVa ID: 991// Verdict: Accepted// Submission Date: 2016-12-24// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAX_N=20;longlongintcatalan[MAX_N]={0,1};voidgetCatalan(){for(intn=2;n<MAX_N;n++)catalan[n]=2*catalan[n-1]*(2*n-1)/(n+1);}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);getCatalan();intn,cases=0;while(cin>>n){if(cases++>0)cout<<'\n';cout<<catalan[n]<<'\n';}return0;}

总结

本题的关键在于识别出无交叉握手方案数即为卡特兰数，并利用递推公式Cn=Cn−1×2(2n−1)n+1C_n = C_{n-1} \times \frac{2(2n-1)}{n+1}Cn​=Cn−1​×n+12(2n−1)​进行预处理。由于nnn非常小，直接打表输出即可，无需动态规划或组合数运算。代码中注意多组数据之间的空行分隔，以及使用646464位整数防止溢出。掌握卡特兰数的经典模型（如括号匹配、二叉树计数、非交叉匹配等）对解决此类问题具有重要帮助。