UVa 13052 Fisa Flood

题目描述Fisa Flood\texttt{Fisa Flood}Fisa Flood是Udesc\texttt{Udesc}Udesc国第一家生产软饮料的工厂。该工厂推出两种口味的罐装饮料白色罐装Fisadasa\texttt{Fisadasa}Fisadasa记为DDD和深红色罐装Fisaloca\texttt{Fisaloca}Fisaloca记为LLL。促销规则为归还两个空罐可换得一罐新饮料具体兑换方式如下两个DDD空罐 → 一罐DDD两个LLL空罐 → 一罐DDD一个DDD空罐 一个LLL空罐 → 一罐LLL。促销罐与普通罐一样可继续参与兑换。小男孩Nikas\texttt{Nikas}Nikas购买了AAA罐DDD和BBB罐LLL。他喝完所有罐子后不断用空罐兑换新罐并继续饮用直到无法再兑换为止。由于兑换顺序可能影响最终喝到的罐子类型他需要知道最后一罐是DDD还是LLL的概率。输入格式第一行一个整数TTT1≤T≤1111 \le T \le 1111≤T≤111表示测试用例数。接下来TTT行每行两个整数AAA和BBB0≤A,B≤10000 \le A, B \le 10000≤A,B≤1000分别表示购买的DDD罐数和LLL罐数。输出格式对于每个测试用例输出一行Case x: p q其中xxx从111开始编号ppp表示最后一罐为DDD的概率qqq表示最后一罐为LLL的概率四舍五入保留三位小数。样例输入3 1 0 0 2 1 1输出Case 1: 1.000 0.000 Case 2: 1.000 0.000 Case 3: 0.000 1.000题目分析本题的核心是计算在给定初始罐数(A,B)(A, B)(A,B)下经过无限次“两罐换一罐”的兑换后最终剩余那一罐的类型。由于每次兑换都会消耗两个罐子并产生一个新的罐子总罐数每次减少111因此无论兑换顺序如何最终一定会剩下一罐除非一开始就没有罐子。我们需要确定这一罐是DDD还是LLL。观察兑换规则它定义了一个二元运算⊗\otimes⊗D⊗DDD \otimes D DD⊗DDL⊗LDL \otimes L DL⊗LDD⊗LLD \otimes L LD⊗LLL⊗DLL \otimes D LL⊗DL。若将DDD编码为111LLL编码为000则上述运算等价于a⊗b1⊕a⊕b a \otimes b 1 \oplus a \oplus ba⊗b1⊕a⊕b其中⊕\oplus⊕表示按位异或XOR\mathrm{XOR}XOR。这个运算实际上就是同或XNOR\mathrm{XNOR}XNOR即a⊗b¬(a⊕b)a \otimes b \neg (a \oplus b)a⊗b¬(a⊕b)。同或运算具有结合律和交换律因为异或和取反都是可结合的且取反与异或结合时整体仍满足结合律。因此将所有罐子按任意顺序进行两两合并最终结果与合并顺序无关只取决于所有初始罐子的集合。设共有NABN A BNAB个罐子其中DDD的个数为AAA。将所有罐子的编码111或000依次做同或运算由于同或满足结合律最终结果可以表示为若NNN为奇数则结果等于A mod 2A \bmod 2Amod2即DDD个数的奇偶性若NNN为偶数则结果等于1⊕(A mod 2)1 \oplus (A \bmod 2)1⊕(Amod2)。这个结论可以这样理解同或运算等价于将参与运算的所有位先做异或再取反如果参与个数为奇数则不取反偶数则取反因为连续取反会抵消。更形式化地若记xA mod 2x A \bmod 2xAmod2NABN ABNAB则最终结果为resultx⊕((N1) mod 2) result x \oplus ((N 1) \bmod 2)resultx⊕((N1)mod2)当result1result1result1时最后一罐为DDD为000时最后一罐为LLL。由于结果唯一确定概率ppp和qqq只能取1.01.01.0或0.00.00.0不存在随机性因此直接按公式计算即可。但需要特别注意边界情况当A0A0A0且B0B0B0时没有任何罐子不存在“最后一罐”此时应输出0.000 0.0000.000\ 0.0000.0000.000而上述公式会错误地给出1.000 0.0001.000\ 0.0001.0000.000因此必须单独处理该特例。解题思路编码映射将DDD看作111LLL看作000兑换规则转化为同或运算。合并顺序无关性由同或运算的结合律最终结果与兑换顺序无关仅由初始罐子总数和DDD的个数决定。计算公式计算xA mod 2x A \bmod 2xAmod2计算NABN A BNAB计算rx⊕((N1) mod 2)r x \oplus ((N 1) \bmod 2)rx⊕((N1)mod2)若r1r 1r1则p1.0,q0.0p 1.0, q 0.0p1.0,q0.0否则p0.0,q1.0p 0.0, q 1.0p0.0,q1.0。特判若A0A 0A0且B0B 0B0直接输出Case x: 0.000 0.000。输出格式保留三位小数使用printf(%.3f)或cout配合fixed setprecision(3)均可。复杂度分析每组测试用例仅需常数次整数运算和判断时间复杂度O(1)O(1)O(1)空间复杂度O(1)O(1)O(1)。对于T≤111T \le 111T≤111的数据规模可轻松通过。代码实现// Fisa Flood// UVa ID: 13052// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){intT;scanf(%d,T);for(intcs1;csT;cs){intA,B;scanf(%d %d,A,B);// 特判没有任何罐子时不存在最后一罐if(A0B0){printf(Case %d: 0.000 0.000\n,cs);continue;}intxA1;// 异或值D1, L0intnAB;// 总罐数intrx^((n1)1);// 1-D, 0-Ldoublepr?1.0:0.0;doubleq1.0-p;printf(Case %d: %.3f %.3f\n,cs,p,q);}return0;}总结本题的核心数学工具是将兑换规则抽象为同或运算并利用其结合律得到与顺序无关的结论。关键在于正确推导出最终罐子类型的表达式并注意处理AB0AB0AB0的边界情况。该题虽然描述较长但实质是一个简单的组合数学问题体现了将实际问题转化为代数模型的重要性。通过本题可以加深对位运算性质的理解并练习特例的容错处理。