P11628 [WC2025] 猫粮题目描述你的家里养了nnn只小猫。到了饭点你的猫都饿了每一只都需要吃至少mmm克的猫粮才能吃饱。你的家里有两种猫粮优质猫粮和普通猫粮。优质猫粮的味道非常好所以当你打开一袋优质猫粮后所有没吃饱的小猫会来争抢最后所有没吃饱的小猫中任意一只猫都有可能抢走这袋猫粮并吃掉其中的所有猫粮。普通猫粮的味道一般所以当你打开一袋猫粮放在某一只小猫面前时其他小猫不会争抢而这只小猫会吃掉这个袋子里的所有猫粮。在这两种情况下即使占有猫粮的小猫只需要吃掉这袋猫粮的一部分就能吃饱它也会吃掉整袋猫粮。你有nnn袋优质猫粮其中第iii袋里有aia_iai​克你还有nnn袋普通猫粮其中第iii袋里有bib_ibi​克。所有猫粮加在一起的重量恰好等于n×mn\times mn×m也就是所有小猫吃饱所需要的猫粮重量。同时所有袋子里的猫粮的重量都是111至m−1m-1m−1之间的整数。为了喂饱所有小猫你每次可以选择一袋猫粮打开等待这袋猫粮被吃完之后再打开下一袋直到所有猫粮都被吃完。你可以根据此时猫粮的食用情况决定之后猫粮的打开顺序以及将普通猫粮放在哪一只猫面前。你想知道是否存在一种喂猫粮的方案使得在每次打开优质猫粮时无论哪只没吃饱的猫抢到了猫粮最终所有猫都能吃饱。输入格式本题有多组测试数据。输入的第一行包含一个正整数TTT表示数据组数。接下来依次输入每组测试数据对于每组测试数据第一行包含两个正整数nnn和mmm表示猫的数量以及每只猫需要的猫粮克数。第二行包含nnn个整数a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​描述nnn袋优质猫粮的重量。第三行包含nnn个整数b1,b2,⋯ ,bnb_1,b_2,\cdots,b_nb1​,b2​,⋯,bn​描述nnn袋普通猫粮的重量。输出格式对于每组测试数据输出一行包含一个字符串如果存在满足条件的方案输出Yes否则输出No。输入输出样例 #1输入 #12 2 90 60 20 70 30 2 10 3 5 6 6输出 #1Yes No输入输出样例 #2输入 #2见附件输出 #2见附件说明/提示样例解释样例111解释第一组数据中可以先打开重量为606060克的优质猫粮。无论被哪一只小猫吃掉打开重量为303030克的普通猫粮喂给同一只小猫这样这只小猫就吃饱了。接下来打开重量为202020的优质猫粮被剩下的小猫吃掉。最后打开重量为707070的普通猫粮给这只小猫吃这样两只小猫都吃到了909090克猫粮就都吃饱了。第二组数据中可以证明不存在可以喂饱所有小猫的方案。样例222解释该样例满足特殊性质B\text{B}B。数据范围对于所有测试数据保证1≤T≤501 \le T \le 501≤T≤50;1≤n≤400002≤m≤1051 \le n \le 400002 \le m \le 10^51≤n≤400002≤m≤105;对于任意的1≤i≤n1 \le i \le n1≤i≤n有1≤ai,bi≤m−11 \le a_i, b_i \le m − 11≤ai​,bi​≤m−1;∑i1nai∑i1nbinm\displaystyle \sum_{i1}^na_i\sum_{i1}^n b_inmi1∑n​ai​i1∑n​bi​nm。::cute-table测试点编号n≤n\len≤特殊性质111111无2∼42\sim 42∼4222^5∼75\sim 75∼7555^8,98,98,94×1044\times 10^44×104A10∼1610\sim 1610∼16^B17∼2017\sim 2017∼20^无特殊性质 A保证m3m3m3。特殊性质 B保证任意两袋猫粮的重量互不相同即对于任意的1≤ij≤n1\le i\lt j\le n1≤ij≤n保证ai≠aja_i\neq a_jai​aj​bi≠bjb_i\neq b_jbi​bj​且对于任意的1≤i,j≤n1\le i,j\le n1≤i,j≤n保证ai≠bja_i\neq b_jai​bj​。C实现#includebits/stdc.h#definelc(p1)#definerc((p1)|1)#defineeb(x)emplace_back(x)#definepb(x)push_back(x)usingnamespacestd;usingpipairint,int;constintN100005;intn,m;inta[N],b[N],tota[N],totb[N],cnt0,kd0;voidsolve(){cinnm;memset(tota,0,sizeof(tota));memset(totb,0,sizeof(totb));kd0;cnt0;for(inti1;in;i){cina[i];tota[a[i]];}for(inti1;in;i){cinb[i];totb[b[i]];}boollg1;for(inti1;in;i){if(totb[b[i]]0)continue;if(tota[m-b[i]]0)tota[m-b[i]]--,totb[b[i]]--;elseif((totb[m-b[i]]0(b[i]!m-b[i]))||(totb[m-b[i]]2)){totb[m-b[i]]--;totb[b[i]]--;}elselg0;}for(inti1;im;i){if(tota[i])kd;while(tota[i]){tota[i]--,cnt;}}if(!(kd1||cnt2))lg0;if(lg)coutYes\n;elsecoutNo\n;}intmain(){intt;cint;while(t--)solve();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容