2021.08.14【NOIP提高B组】模拟 【USACO 2021 US Open, Silver】Do You Know Your ABCs?

NOIP提高B组】模拟 【USACO 2021 US Open, Silver】Do You Know Your ABCs?"/>

2021.08.14【NOIP提高B组】模拟 【USACO 2021 US Open, Silver】Do You Know Your ABCs?

思路：

直接暴力枚举每个位置对应的数，然后把a,b,c判断出来，然后check就可以了

c o d e code code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>using namespace std;int t, ans;
int n, b[10], c[10], a[10];
map<pair<int, pair<int, int> >, int>q;bool check_()
{return c[1]<=c[2]&&c[2]<=c[3]&&!q[make_pair(c[1], make_pair(c[2], c[3]))]&&(!b[1]||b[1]==c[1])&&(!b[2]||b[2]==c[2])&&(!b[3]||b[3]==c[3])&&(!b[4]||(b[4]==c[1]+c[2]))&&(!b[5]||(b[5]==c[1]+c[3]))&&(!b[6]||(b[6]==c[2]+c[3]))&&(!b[7]||(b[7]==c[1]+c[2]+c[3]));
}void check()
{
//	for(int i=1; i<=7; i++)
//		cout<<b[i]<<' ';
//	cout<<endl;memset(c, 0, sizeof(c));if(b[1]&&b[2]&&b[3]){c[1]=b[1], c[2]=b[2], c[3]=b[3];if(check_())ans++, q[make_pair(c[1], make_pair(c[2], c[3]))]=1;return;}if(b[1]&&b[2]){c[1]=b[1], c[2]=b[2];if(b[5])c[3]=b[5]-c[1];else if(b[7])c[3]=b[7]-c[1]-c[2];else if(b[6])c[3]=b[6]-c[2];	if(check_())ans++, q[make_pair(c[1], make_pair(c[2], c[3]))]=1;return;}if(b[2]&&b[3]){c[2]=b[2], c[3]=b[3];if(b[5])c[1]=b[5]-c[3];else if(b[7])c[1]=b[7]-c[3]-c[2];else if(b[4])c[1]=b[4]-c[2];if(check_())ans++, q[make_pair(c[1], make_pair(c[2], c[3]))]=1;return;}if(b[1]&&b[3]){c[1]=b[1], c[3]=b[3];if(b[4])c[2]=b[4]-c[1];else if(b[7])c[2]=b[7]-c[1]-c[3];else if(b[6])c[2]=b[6]-c[3];	if(check_())ans++, q[make_pair(c[1], make_pair(c[2], c[3]))]=1;return;}if(b[1]){c[1]=b[1];if(b[4])c[2]=b[4]-c[1];if(b[5])c[3]=b[5]-c[1];if(b[7])c[6]=b[7]-c[1];if(!c[6])c[6]=b[6];if(b[6]&&c[3])c[2]=b[6]-c[3];elseif(b[6]&&c[2])c[3]=b[6]-c[2];if(check_())ans++, q[make_pair(c[1], make_pair(c[2], c[3]))]=1;return;}if(b[2]){c[2]=b[2];if(b[4])c[1]=b[4]-c[2];if(b[6])c[3]=b[6]-c[2];if(b[7])c[5]=b[7]-c[2];if(!c[5])c[5]=b[5];if(b[5]&&c[3])c[1]=b[5]-c[3];elseif(b[5]&&c[1])c[3]=b[5]-c[1];if(check_())ans++, q[make_pair(c[1], make_pair(c[2], c[3]))]=1;return;}if(b[3]){c[3]=b[3];if(b[5])c[1]=b[5]-c[3];if(b[6])c[2]=b[6]-c[3];if(b[7])c[4]=b[7]-c[3];if(!c[4])c[4]=b[4];if(b[4]&&c[1])c[2]=b[4]-c[1];elseif(b[4]&&c[2])c[1]=b[4]-c[2];if(check_())ans++, q[make_pair(c[1], make_pair(c[2], c[3]))]=1;return;}c[1]=b[7]-b[6];c[2]=b[7]-b[5];c[3]=b[7]-b[4];if(check_())ans++, q[make_pair(c[1], make_pair(c[2], c[3]))]=1;
}void dfs(int x, int k)
{if(x==8&&k!=n+1)return;if(k>n){check();swap(b[3], b[4]);check();swap(b[3], b[4]);return;}dfs(x+1, k);b[x]=a[k];dfs(x+1, k+1);b[x]=0;
}int main()
{scanf("%d", &t);while(t--){scanf("%d", &n);for(int i=1; i<=n; i++)scanf("%d", &a[i]);sort(a+1, a+1+n);dfs(1, 1);printf("%d\n", ans);ans=0, q.clear();
//		memset(c, 0, sizeof(c));
//		memset(b, 0, sizeof(b));}return 0;
}