Calling【牛客tracker 每日一题】

Calling时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述空。你有6 66种正方形纸片其中第i ( 1 ≤ i ≤ 6 ) i\ (1 \le i \le 6)i(1≤i≤6)种边长为i ii每一种都有k i k_iki​个你需要把它们放在至多s ss个面积为36 ( 6 × 6 ) 36\ ( 6 \times 6)36(6×6)的正方形框中显然我们可以一个框一个框的放要求如下每个框不必放满。比如你可以把至多36 3636个边长为1 11的正方形纸片放在一个框中也可以把30 3030个边长为1 11的正方形放在一个框中也可以把1 11个边长为5 55的正方形纸片放在一个框中等。每个框放的正方形边长不必相同。比如一个框中可以同时出现边长为3 33和边长为1 11的正方形。请问能否放得下若可以输出Yes否则输出No。输入描述第一行一个正整数T ( 1 ≤ T ≤ 10 5 ) T\ (1 \le T \le 10^5)T(1≤T≤105)表示T TT组数据。对于每组数据第一行一个非负整数s ( 0 ≤ s ≤ 10 9 ) s\ (0 \le s \le 10^9)s(0≤s≤109)。第二行6 66个非负整数为k i ( 0 ≤ k i ≤ 10 4 ) k_i\ (0 \le k_i \le 10^4)ki​(0≤ki​≤104)。输出描述T TT行每行一个字符串Yes或No表示对应数据的答案。请注意区分大小写。示例 1输入4 15 3 1 4 1 5 9 20 0 0 0 1 4 1 10 1 1 4 5 1 4 1024 123 456 1 3 4 10输出No Yes No Yes数据范围与提示1 ≤ T ≤ 10 5 1 \le T \le 10^51≤T≤1050 ≤ s ≤ 10 9 0 \le s \le 10^90≤s≤1090 ≤ k i ≤ 10 4 0 \le k_i \le 10^40≤ki​≤104本题是二维装箱正方形装6 × 6 6 \times 66×6容器判定问题核心思路面积必要条件所有纸片总面积∑ i 1 6 i 2 k i ≤ 36 s \sum_{i1}^{6} i^2 k_i \le 36s∑i16​i2ki​≤36s且框数需求不能少于大块纸片的数量边长≥ 4 \ge 4≥4的正方形每个框至多放1 11个。按边长从大到小贪心装箱边长6 66必须独占一个框边长5 55独占一个框剩余36 − 25 11 36 - 25 1136−2511的边角空间只能填1 × 1 1 \times 11×1最多11 1111个边长4 44独占一个框剩余20 2020空间可放5 55个2 × 2 2 \times 22×2或20 2020个1 × 1 1 \times 11×1也可混放边长3 33每框最多放4 44个2 × 2 2 \times 22×2排列剩余空间可放1 × 1 1 \times 11×1不足4 44个的框剩余空间还可放2 × 2 2 \times 22×2每框至多1 11个且需配合1 × 1 1 \times 11×1填缝边长2 22、1 11用于填充前几类框的剩余空间最后不足的部分再用新框。统计总共需要的框数与s ss比较同时校验面积条件即可。解题思路本题是二维装箱判定问题。给定 6 种正方形纸片边长分别为1 ∼ 6 1\sim61∼6数量分别为k 1 ∼ k 6 k_1\sim k_6k1​∼k6​需要放入至多s ss个6 × 6 6\times66×6的正方形框中。每个框不必放满可以混合放置不同边长的纸片。问能否全部放下。由于每个框面积固定为36 3636且纸片边长均为整数可以按照从大到小的贪心策略依次处理每种纸片并记录每个框剩余空间能容纳的较小纸片数量。若最终所有纸片都能被容纳则输出Yes否则输出No。1. 问题等价转化每个6 × 6 6\times66×6框容量为面积36 3636。纸片面积分别为1 , 4 , 9 , 16 , 25 , 36 1,4,9,16,25,361,4,9,16,25,36。大尺寸纸片会限制小尺寸纸片的放置方式。例如边长6 66的纸片必须独占一个框边长5 55的纸片占一个框后剩余11 1111面积只能放1 × 1 1\times11×1边长4 44的纸片占一个框后剩余20 2020面积可放5 55个2 × 2 2\times22×2或20 2020个1 × 1 1\times11×1等。由于所有容器尺寸相同且纸片边长均为整数可以采用贪心优先放置大纸片并尽可能用次大的纸片填充剩余空间最后用最小的纸片填充。若这种贪心都无法放下则一定无解。用变量one记录当前所有框剩余空间中可容纳的1 × 1 1\times11×1纸片总数two记录可容纳的2 × 2 2\times22×2纸片总数s表示剩余可用的空框数量。2. 算法实现按边长从大到小依次处理边长 6k 6 k_6k6​每个必须独占一个框。若s k_6则无解否则s - k_6。边长 5k 5 k_5k5​每个独占一个框剩余11 1111面积只能放1 × 1 1\times11×1。若s k_5则无解否则s - k_5one k_5 * 11。边长 4k 4 k_4k4​每个独占一个框剩余20 2020面积最多放5 55个2 × 2 2\times22×2。若s k_4则无解否则s - k_4two k_4 * 5。边长 3k 3 k_3k3​每个框最多放4 44个。若s * 4 k_3则无解。然后用s - k_3 / 4消耗掉放满4 44个的框。余数k_3 % 4需要额外一个框根据余数不同该框内剩余空间可放2 × 2 2\times22×2和1 × 1 1\times11×1余1 11放1 11个3 × 3 3\times33×3剩余27 2727面积 →two 5one 7。余2 22放2 22个3 × 3 3\times33×3剩余18 1818面积 →two 3one 6。余3 33放3 33个3 × 3 3\times33×3剩余9 99面积 →two 1one 5。若有余数则s--。处理剩余空框所有剩余空框s都可以用来放2 × 2 2\times22×2和1 × 1 1\times11×1。每个空框最多放9 99个2 × 2 2\times22×2因此two s * 9。边长 2k 2 k_2k2​若two k_2则无解否则two - k_2剩余的2 × 2 2\times22×2位置可转换为1 × 1 1\times11×1每个位置提供4 44个1 × 1 1\times11×1即one two * 4。边长 1k 1 k_1k1​若one k_1则无解否则输出Yes。3. 复杂度分析时间复杂度每组数据只需常数次判断和简单运算O ( 1 ) O(1)O(1)。总共有T ≤ 10 5 T \le 10^5T≤105组总时间复杂度O ( T ) O(T)O(T)非常高效。空间复杂度仅使用常数个变量O ( 1 ) O(1)O(1)。总结本题通过贪心策略从大到小处理纸片并精确计算每个框剩余空间能容纳的较小纸片数量。由于所有边长均为整数且容器固定贪心选择优先用次大纸片填充能够保证空间利用率最大从而正确判定可行性。算法简单且运行极快。代码简要说明使用数组k存储 6 种纸片的数量下标0 ∼ 5 0\sim50∼5分别对应边长1 ∼ 6 1\sim61∼6。变量one记录可容纳的1 × 1 1\times11×1总数two记录可容纳的2 × 2 2\times22×2总数s为剩余空框数。依次处理边长6 , 5 , 4 , 3 6,5,4,36,5,4,3并更新one、two和s。处理边长3 33时根据余数分情况增加剩余容量。最后用剩余空框补足2 × 2 2\times22×2容量再将多余的2 × 2 2\times22×2容量转换为1 × 1 1\times11×1检查是否满足1 × 1 1\times11×1的需求。若所有检查通过输出Yes否则No。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll s;arrayll,6k;voidSolve(){cins;for(lli:k){cini;}ll one0;ll two0;if(sk[5]){coutNo\n;return;}s-k[5];if(sk[4]){coutNo\n;return;}s-k[4];onek[4]*11;if(sk[3]){coutNo\n;return;}s-k[3];twok[3]*5;if(s*4k[2]){coutNo\n;return;}s-k[2]/4;switch(k[2]%4){case1:s--;two5;one7;break;case2:s--;two3;one6;break;case3:s--;two;one5;break;}twos*9;if(twok[1]){coutNo\n;return;}two-k[1];onetwo*4;if(onek[0]){coutNo\n;return;}coutYes\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;while(T--)Solve();return0;}