球队1,2,3记为a,b,c,易知|a-b|=d1,|b-c|=d2,a+b+c=k,绝对值不好处理,需要枚举a,b,c的大小关系,故默认a>b>c,这时d1,d2的值便可能为其相反数,因为很可能不是a>b>c,通过改变d1,d2的值,我们可以得到a,b,c的解:
a=2 * d1 + d2 + k,b=a-d1,c=b-d2。算法流程:1.n必须是3的倍数 2.枚举球队a,b,c的大小关系,解需大于等于0且小于n/3.
tips:枚举大小关系可以用 next_permutation,数组索引做球队编号,值表示相对大小关系,本题arr=[1,2,3].
#include<bits/stdc++.h> using namespace std; using ll=long long ; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--){ ll n,k,d1,d2; cin>>n>>k>>d1>>d2; if (n%3!=0) { cout<<"no\n"; continue; } vector<int> arr={1,2,3}; bool ans=false; ll tmpD1, tmpD2, team1, team2, team3; do{ if (arr[0] > arr[1]) tmpD1 = d1; else tmpD1 = -d1; if (arr[1] > arr[2]) tmpD2 = d2; else tmpD2 = -d2; if ((2 * tmpD1 + tmpD2 + k) % 3 == 0) { team1 = (2 * tmpD1 + tmpD2 + k) / 3; team2 = team1 - tmpD1; team3 = team2 - tmpD2; if (team1 >= 0 && team2 >= 0 && team3 >= 0 && team1 <= n / 3 && team2 <= n / 3 && team3 <= n / 3) { ans = true; } } } while (next_permutation(arr.begin(), arr.end()) && !ans); cout<<(ans? "yes":"no")<<endl; } }