拼三角【牛客tracker 每日一题】
拼三角
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
给出6根棍子，能否在选出3根拼成一个三角形的同时剩下的3根也能组成一个三角形？
输入描述：
首先在一行中给出一个t , 1 ≤ t ≤ 10 3 t,1≤t≤10^3t,1≤t≤103，代表测试数据的组数
接下来t行，每行给出6 66个数字代表棍子长度，棍子长度为正且小于10 9 10^9109
输出描述：
在一行中输出“ Y e s ” o r “ N o ” “Yes” or “No”“Yes”or“No”
示例1
输入：
2 1 1 1 1 1 1 1 2 3 4 5 6输出：
Yes No解题思路
本题核心是暴力枚举分组 + 三角形合法性判定，利用极小的枚举量实现高效求解。6根棍子划分为两组各3根，总组合数仅C 6 3 = 20 C_6^3=20C63=20种，完全可以暴力枚举所有方案。通过二进制掩码遍历所有3根棍子的子集，将棍子分为两组；对每组棍子验证三角形构成条件：任意两边之和大于第三边。只要存在一种分组方式，让两组都能构成三角形，就输出Yes，遍历完所有方案都不满足则输出No。算法为常数级运算，单组测试用例计算量极小，完美适配t ≤ 10 3 t \le 10^3t≤103的数据规模。
总结
核心逻辑：枚举6根棍子的所有3+3划分方式，判断两组是否同时满足三角形条件。
关键操作：二进制掩码枚举子集、三角形三边关系校验。
效率保障：常数级暴力枚举，无复杂计算，极速处理所有测试用例。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=2e5+5,INF=1e18,MOD=1e9+7,base=1331;llcheck(ll a,ll b,ll c){returna+b>c&&b+c>a&&a+c>b;}voidsolve(){vector<ll>v(6);for(ll i=0;i<6;i++)cin>>v[i];ll flag=0;for(ll i=0;i<(1<<6);i++){ll cnt=0;for(ll j=0;j<6;j++)if((1<<j)&i)cnt++;if(cnt!=3)continue;ll idx1=0,idx2=0;vector<ll>tmp1(3),tmp2(3);for(ll j=0;j<6;j++){if((1<<j)&i)tmp1[idx1++]=v[j];elsetmp2[idx2++]=v[j];}if(check(tmp1[0],tmp1[1],tmp1[2])&&check(tmp2[0],tmp2[1],tmp2[2]))flag=1;}if(flag)cout<<"Yes\n";elsecout<<"No\n";}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll tt;cin>>tt;while(tt--)solve();return0;}