说在前面码农题目思路是简单的就是有点废手。在只能交 3 次的且只有 2.5h 时间的考场上我居然过了大模拟题目我太强了。前置芝士贪心、一个清醒的大脑、一对敏锐的眼睛和十根勤劳的手指大模拟。注意该文章篇幅较长给出了详细的证明和算法步骤可自行选择观看。题目是有问题的“输入保证两个字符串均包含至少一个111和一个222”而样例四与题目描述矛盾。题目一开始提到的“输入保证两种颜色的液体至少各有一个单位”符合样例四故我认为第一句话应该把“均”字改成“总共”。该题解中所有的思路的构建与证明都基于“输入保证两种颜色的液体至少各有一个单位”这句话之上请务必牢记在心。题目分析思路是比较好想的。思路建立在贪心之上我们尽可能多合并能合并的颜色。指定一个烧杯中唯一可能出现的颜色令其为xxx。分别查看两个试管如果最顶层存在xxx将其倒入烧杯每次倾倒花费代价111。否则将颜色多的试管的顶层倒入另一个试管中花费代价111。在两个试管内的颜色的段数至少有一个大于111的情况下重复步骤 2、3否则分类讨论如果烧杯是空的直接退出此时必定分拣完成。否则讨论两试管液体存在性及颜色。若试管111和试管222均为非空。若两试管内颜色相同则将试管111的液体倒入试管222最后将试管333的倒入试管111花费代价222。否则检查哪个试管的剩下的颜色为xxx将烧杯中的颜色倒入该试管花费代价111。若仅有试管111非空。将烧杯中的液体倒入试管222花费代价111。若仅有试管222非空。将烧杯中的液体倒入试管111花费代价111。将xxx换一个数重复上述过程答案取两次代价的最小值。由于这个算法是我们凭直觉搞出来的所以这里给出证明。证明先证总体思路引理 1一次操作最多合并两段颜色成一段。证明一次操作只能将一个试管烧杯中的液体的某一个段倒入另一个试管烧杯故最多只能合并两段颜色成为一段。引理 2我们需要尽可能地多合并相同的颜色。证明考虑终止态一定是两个试管内分别有一段颜色且两烧杯内颜色段数不同总段数为222从题目描述得初始态段数一定不小于222由引理 1颜色段数单调不增因此为了加速该过程我们需要尽可能合并。故总体思路正确。再证退出循环前的思路引理 3步骤 3 能减少颜色段数并且保证了一定能到达步骤 4。证明此时两试管顶部的颜色一定与xxx不同且两试管顶部颜色相同。采用反证法将数量小的倒入数量大的考虑以下情况x1x 1x1试管一内部[2[2[2试管二内部[21212[21212[21212。一次操作后试管一[[[试管二[2121[2121[2121。两次操作后试管一[[[试管二[212[212[212。此时理应进行操作 3由于试管一为空无法进行因此条件永远无法达成循环永远无法退出。而如果数量大的倒入数量小的就能在减少颜色段数的同时避免该情况。引理 4操作过程中至多有一次不减少颜色段数。证明在操作时如果是第一次将xxx放入烧杯那么颜色段数不会减少否则如果是放入烧杯的操作那么颜色段必然减少111。如果是两试管相互倒液体的操作由引理 3颜色段也会减少111。引理 5最优方案严格满足引理 4。证明在倾倒过程中可能会存在两试管顶部异色的情况此时如果不放入烧杯中一定无法再次减少颜色段数违背了引理 2因此只能将这一段放入烧杯如果这是第一次此类操作那么颜色段不变结合引理 4最多只有一次操作不影响颜色段数量因而最优。引理 6满足两个烧杯中的颜色段数全部小于等于111的情况后退出是最优的。证明在满足该情况前至少有一个烧杯存在大于111个连续段所以最少还要进行一次操作 2 或操作 3。故退出循环前的思路正确。最后证明退出循环后的思路。引理 7若烧杯为空可以直接终止操作。证明有题目描述至少存在两种颜色那么只有一个试管非空或两个试管均为空的情况将不可能存在若两个试管均非空则一定不是同种颜色自动达成终止态直接退出。引理 8若烧杯非空最多进行两次操作且最优。证明对于仅有一个试管非空的情况此时试管内颜色一定不为xxx直接将烧杯中的液体倒入另一试管达成终止态花费代价111若两个试管非空如果颜色相同一定不能从烧杯直接倒因此先合并两个试管内的液体再从烧杯直接倒花费代价222若两个试管颜色不同可以直接合并烧杯和一个试管花费代价111。同时不可能存在两个试管同时为空的情况。在引理 6的条件下这一步一定最优。故退出循环后的思路正确。综上该算法思路全部正确。□\square□。注意事项P1P 1P1只能输出一个数字即最小代价。类似于样例444的情况代码无法处理需要特殊判断。AC 代码长达 3.71KB 的代码。#includebits/stdc.h#definePIIpairint,int#definefirfirst#definesecsecondusingnamespacestd;namespacezcq_qwq{constintN1e55,inf0x3f3f3f3f;intt,n,mninf,res[3];dequePIIq[4],p[4];vectorPIIans[3];voidmerge(intx,PII v){// 把 v 这个东西放到 q[x] 里面if(q[x].empty())q[x].push_back(v);elseif(q[x].back().firv.fir)q[x].back().secv.sec;elseq[x].push_back(v);}boolcheck(){returnq[1].size()1q[2].size()1;}voidclear(){for(inti1;i3;i)q[i].clear();ans[1].clear(),ans[2].clear(),res[1]res[2]0;}voidbig_question(intx){// 确定 q[3] 里面存的是啥颜色for(inti1;i3;i){p[i]q[i];}intsum0;while(!check()){if(!q[1].empty()q[1].back().firx){merge(3,q[1].back()),q[1].pop_back(),sum;ans[x].push_back({1,3});}elseif(!q[2].empty()q[2].back().firx){merge(3,q[2].back()),q[2].pop_back(),sum;ans[x].push_back({2,3});}else{inttmpmax(q[1].size(),q[2].size());if(tmpq[1].size()){merge(2,q[1].back()),q[1].pop_back(),sum;ans[x].push_back({1,2});}else{merge(1,q[2].back()),q[2].pop_back(),sum;ans[x].push_back({2,1});}}}// 接下来是大分讨if(!q[1].empty()!q[2].empty()!q[3].empty()){if(q[1].back().firq[2].back().fir){ans[x].push_back({1,2}),ans[x].push_back({3,1}),sum2;}else{if(q[1].back().firx){ans[x].push_back({3,1}),sum;}else{ans[x].push_back({3,2}),sum;}}}elseif(!q[1].empty()!q[3].empty()){ans[x].push_back({3,2}),sum;}elseif(!q[2].empty()!q[3].empty()){ans[x].push_back({3,1}),sum;}res[x]sum;mnmin(mn,sum);for(inti1;i3;i){q[i]p[i];}}voidsolve(){mninf;clear();intP;cinnP;for(inti1;in;i){charc;intx;cinc;xc-0;PII t{x,1};merge(1,t);}for(inti1;in;i){charc;intx;cinc;xc-0;PII t{x,1};merge(2,t);}if(q[1].size()1q[2].size()2){if(q[1].back().firq[2].back().fir){cout1\n2 1endl;return;}}elseif(q[1].size()2q[2].size()1){if(q[1].back().firq[2].back().fir){cout1\n1 2endl;return;}}big_question(1),big_question(2);coutmnendl;if(P1)return;if(mnres[1]){for(autoi:ans[1])couti.fir i.secendl;}else{for(autoi:ans[2])couti.fir i.secendl;}}voidmain(){cint;while(t--){solve();}}}signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);zcq_qwq::main();return0;}/* 这个东西显然是策略的问题只要策略对了即可 看起来是这样的策略每次遇到指定颜色段就放到烧杯里这样烧杯里面一定是一种颜色的。 最后再把烧杯里面的倒回来 由于我们指定的哪一个颜色放到烧杯里面可能对答案有影响所以我们跑两次取最小值。 接下来只需要思考如何判断可以直接倒了。 如果两边烧杯的段数同时 1就可以直接倒。 */说在后面若代码、思路讲解有误欢迎提出