UVA12967 题解

题目传送门

思路

转换一下题意，发现题目就是让你求所给图形每一层的元素之和。

我们观察一下节点 P 向一侧展开的图，第一层的节点 P 只有唯一一个方案，这里我就把它抽象成 1；再展开得到两个节点 A，分别是 [1,1]；第三层的三个节点 T，两边的元素仍然是 1，中间的元素为 1+1=2，所以是 [1,2,1]；第四层的四个节点 H 分别是 [1,1+2,2+1,1]，即 [1,3,3,1]。

到这里不难发现，这不就是杨辉三角吗？让我们求第 n 层的元素之和，根据杨辉三角的性质第 n 层元素之和就是 2^{n-1}。回归题目，把这个答案乘 4 再减去角上多算的四个 1 即是每一层的元素之和，公式就是：

数据范围较大，记得强制转换为整数，否则无法得到正确答案。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,a;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        if(a==1) printf("1\n");
        else printf("%.0f\n",4*(pow(2,a-1)-1));
    }
    return 0;
}

感谢 QWQAWAQWQAWA 的题解，在强制转化为整数这个细节上借鉴了他的题解。