将1，2，...，9共9个数排成下列形态的三角形。
a
b c
d e
f g h i
其中：a～i分别表示1，2，...，9中的一个数字，并要求同时满足下列条件：
（1）a<f<i;
（2）b<d, g<h, c<e
（3）a+b+d+f=f+g+h+i=i+e+c+a=P
程序要求：根据输入的边长之和P，输出满足上述条件的三角形的方案个数，如果没有方案，则输出No（区分大小写）。
输入边长之和P；输出方案数，若没有输出No。
大致思路：先确定a,f,i的值，最后递归搜索，所有可以找到的情况（包括不符合只有6000多种）可以一秒内完成。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <stack> #include <cstdlib> #include <iomanip> #include <cmath> #include <cassert> #include <ctime> #include <cstdlib> #include <map> #include <set> using namespace std; #pragma comment(linker, "/stck:1024000000,1024000000") #define lowbit(x) (x&(-x)) #define max(x,y) (x>=y?x:y) #define min(x,y) (x<=y?x:y) #define MAX 100000000000000000 #define MOD 1000 #define pi acos(-1.0) #define ei exp(1) #define PI 3.1415926535897932384626433832 #define ios() ios::sync_with_stdio(true) #define INF 1044266558 #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; //a,b,c,d,e,f,g,h,i; int n,a[10],b[4][3],c[4][3],d[4],vis[35]; int cnt=0; void judge(int one,int two,int three) { d[0]=b[0][0]+c[one][0]; d[1]=b[1][0]+c[two][0]; d[2]=b[2][0]+c[three][0]; if(d[0]==d[1] && d[1]==d[2]) { vis[d[0]]++; /*printf("%d: ",d[0]); printf("%d %d %d ",b[0][1],c[one][1],c[one][2]); printf("%d %d %d ",b[1][1],c[two][1],c[two][2]); printf("%d %d %d ",b[2][1],c[three][1],c[three][2]); printf(" ");*/ } } void check(int m,int k) { for(int i=m+1;i<=9;i++) { if(!a[i]) { c[k][0]=m+i; c[k][1]=m; c[k][2]=i; if(k==2) { judge(0,1,2); judge(0,2,1); judge(1,0,2); judge(1,2,0); judge(2,0,1); judge(2,1,0); /*do { cnt++; for(int z=0;z<3;z++) d[z]=c[z]+b[z]; if(d[0]==d[1] && d[1]==d[2]) vis[d[0]]++; }while(next_permutation(c,c+3));*/ return ; } a[i]=1; for(int j=m+1;j<=9;j++) { if(!a[j]) { a[j]=1; check(j,k+1); a[j]=0; break; } } a[i]=0; } } } void solve() { memset(vis,0,sizeof(vis)); memset(a,0,sizeof(a)); for(int i=1;i<=9;i++) { a[i]=1; for(int j=i+1;j<=9;j++) { a[j]=1; for(int k=j+1;k<=9;k++) { if(i==j || j==k || i==k) continue; a[k]=1; b[0][0]=i+j; b[1][0]=j+k; b[2][0]=k+i; b[0][1]=i; b[1][1]=j; b[2][1]=k; for(int z=1;z<=9;z++) { if(!a[z]) { a[z]=1; check(z,0); a[z]=0; break; } } a[k]=0; } a[j]=0; } a[i]=0; } } int main() { solve(); /*for(int i=1;i<=30;i++) printf("[%d:%d] ",i,vis[i]); printf(" %d ",cnt);*/ scanf("%d",&n); if(vis[n]) printf("%d ",vis[n]); else printf("No "); return 0; }