【8.14模拟赛.7219】【洛谷P7556】[USACO21OPEN] Do You Know Your ABCs? S【暴力】【数学】

暴力】【数学】"/>

【8.14模拟赛.7219】【洛谷P7556】[USACO21OPEN] Do You Know Your ABCs? S【暴力】【数学】

题目链接：洛谷

分析

最多有七个数，分别为A,B,C,A+B,A+C,B+C,A+B+C
大小一定是只有两种排列方法的很显然。
可发现A+(B+C)=B+(A+C)=C+(A+B)=A+B+C
枚举每个数放的位置
根据上面的规律求出七个数 必须非负且A<B<C
用数组标记去重

上代码

#include<iostream> 
#include<cstdio>
#include<algorithm>
using namespace std;int n,ans,t,f[10],a[10],b[10],p[10],d[100001][4];void dfs(int x)
{if(x>n){int h=0;for(int i=1;i<=7;i++) a[i]=b[i];//赋值一下不改变bif(a[7]!=0) h=a[7];else{for(int i=1;i<=3;i++){if(a[i]!=0&&a[7-i]!=0) h=a[7]=a[7-i]+a[i];}}for(int i=1;i<=6;i++){if(a[i]!=0){if(a[7-i]==0){if(h-a[i]<0) return;else a[7-i]=h-a[i];}else if(h-a[i]!=a[7-i]) return;}}for(int i=1;i<=3;i++){if(a[i]==0){if(i==1&&a[2]!=0&&a[4]!=0) a[1]=a[4]-a[2];if(i==1&&a[3]!=0&&a[5]!=0) a[1]=a[5]-a[3];if(i==2&&a[4]!=0&&a[1]!=0) a[2]=a[4]-a[1];if(i==2&&a[6]!=0&&a[3]!=0) a[2]=a[6]-a[3];if(i==3&&a[5]!=0&&a[1]!=0) a[3]=a[5]-a[1];if(i==3&&a[6]!=0&&a[2]!=0) a[3]=a[6]-a[2];a[7-i]=h-a[i];if(a[i]<0||a[7-i]<0) return;}}if(a[1]+a[2]!=a[4]) return;if(a[1]+a[3]!=a[5]) return;if(a[2]+a[3]!=a[6]) return;if(a[1]<=a[2]&&a[2]<=a[3]){for(int i=1;i<=ans;i++)//去重{if(a[1]==d[i][1]&&a[2]==d[i][2]&&a[3]==d[i][3]){return;} 	}ans++; d[ans][1]=a[1];d[ans][2]=a[2];d[ans][3]=a[3];}return;}for(int i=1;i<=7;i++){if(!p[i]){b[i]=f[x];p[i]=1;dfs(x+1);p[i]=0;b[i]=0;}}
}int main()
{cin>>t;while(t--){ans=0;cin>>n;for(int i=1;i<=n;i++){scanf("%d",&f[i]);}dfs(1);cout<<ans<<endl;}return 0;
}