UVa 11663 Gray Inc

题目描述Gray Inc.\texttt{Gray Inc.}Gray Inc.是一家专门从事Gray\texttt{Gray}Gray码管理的软件公司。一个nnn位二进制码n≥1n \ge 1n≥1是一个由单词w0,w1,…w_0, w_1, \ldotsw0​,w1​,…组成的序列该序列包含所有可能的nnn位二进制单词。一个nnn位Gray\texttt{Gray}Gray码是一个nnn位二进制码使得任意两个连续单词之间恰好只有一位发生变化。Gray Inc.\texttt{Gray Inc.}Gray Inc.按下述方式生成其特有的Gray\texttt{Gray}Gray码记生成的nnn位Gray\texttt{Gray}Gray码为GnG_nGn​G10,1 G_1 0, 1G1​0,1Gn0Gn−1, 1Gn−1R(n≥2) G_n 0G_{n-1},\; 1G_{n-1}^{R} \quad (n \ge 2)Gn​0Gn−1​,1Gn−1R​(n≥2)其中bAbAbA将比特bbb附加到序列AAA中每个元素的前面ABABAB连接序列AAA与BBBARA^RAR序列AAA的逆序。GnG_nGn​不仅是Gray\texttt{Gray}Gray码而且是循环Gray\texttt{Gray}Gray码即第一个单词视为最后一个单词的后继。问题给定GnG_nGn​中的一个二进制单词www和一个自然数mmm求在循环顺序中位于www之后第mmm个位置的单词。输入格式输入包含若干测试用例每个用例一行包含一个整数mmm0m≤10000 m \le 10000m≤1000和一个二进制串www两者由一个空格分隔。www的长度nnn满足1≤n≤1001 \le n \le 1001≤n≤100。输入以一行0 0结束。输出格式对于每个测试用例输出一行即对应的nnn位二进制单词。样例输入1 0 3 0 1 1 1 11 6 011 123 010101010 0 0输出1 1 0 10 000 111100100题目分析本题给出的GnG_nGn​正是经典的二进制反射Gray\texttt{Gray}Gray码Binary Reflected Gray Code\texttt{Binary Reflected Gray Code}Binary Reflected Gray Code。若用索引kkk从000到2n−12^n - 12n−1表示序列中的位置则对应的Gray\texttt{Gray}Gray码单词为Gray(k)k⊕(k≫1) \text{Gray}(k) k \oplus (k \gg 1)Gray(k)k⊕(k≫1)反之给定Gray\texttt{Gray}Gray码ggg其对应的原始索引kkk可通过如下递推恢复最高位kn−1gn−1k_{n-1} g_{n-1}kn−1​gn−1​对于in−2,n−3,…,0i n-2, n-3, \dots, 0in−2,n−3,…,0有kiki1⊕gik_i k_{i1} \oplus g_iki​ki1​⊕gi​。其中⊕\oplus⊕表示按位异或。由于nnn最大为1001001002n2^n2n远超任何内置整数类型的表示范围不能直接转换为整数进行加减运算。但mmm的值很小≤1000\le 1000≤1000因此我们可以直接在二进制串上模拟“加mmm”的操作模2n2^n2n然后重新编码为Gray\texttt{Gray}Gray码输出。解题思路1. 解码Gray\texttt{Gray}Gray码 → 二进制索引给定输入单词www即Gray\texttt{Gray}Gray码我们首先将其还原为原始索引的二进制表示BBB高位在前。根据递推式B[0]w[0]B[0] w[0]B[0]w[0]对iii从111到n−1n-1n−1B[i](B[i−1]−’0’)⊕(w[i]−’0’)B[i] (B[i-1] - \text{0}) \oplus (w[i] - \text{0})B[i](B[i−1]−’0’)⊕(w[i]−’0’)。该过程只需一次线性扫描复杂度O(n)O(n)O(n)。2. 循环加法我们需要在模2n2^n2n意义下对BBB加上mmm。由于m≤1000m \le 1000m≤1000可以重复mmm次“加111”操作每次从最低位串的末尾开始模拟二进制加法从右向左扫描遇到1则改为0并继续进位遇到第一个0则改为1并停止如果所有位都是1则全部变为0即模2n2^n2n回绕。每次加111的复杂度为O(n)O(n)O(n)总复杂度O(n⋅m)O(n \cdot m)O(n⋅m)对于n≤100n \le 100n≤100、m≤1000m \le 1000m≤1000来说完全可行。3. 编码二进制索引 →Gray\texttt{Gray}Gray码得到加mmm后的二进制索引B′BB′后将其重新编码为Gray\texttt{Gray}Gray码G′GG′G′[0]B′[0]G[0] B[0]G′[0]B′[0]对iii从111到n−1n-1n−1G′[i](B′[i]−’0’)⊕(B′[i−1]−’0’)G[i] (B[i] - \text{0}) \oplus (B[i-1] - \text{0})G′[i](B′[i]−’0’)⊕(B′[i−1]−’0’)。同样只需一次线性扫描。4. 正确性说明由于Gray\texttt{Gray}Gray码与二进制索引之间存在双射一一对应且循环顺序就是索引递增顺序模2n2^n2n因此先解码、加mmm、再编码的过程完全正确。所有的操作均在二进制串上进行避免了高精度整数的处理。复杂度分析每个测试用例解码和编码各需O(n)O(n)O(n)时间。加法部分重复mmm次每次O(n)O(n)O(n)故总时间复杂度为O(n⋅m)O(n \cdot m)O(n⋅m)。空间复杂度O(n)O(n)O(n)仅需存储二进制串和Gray\texttt{Gray}Gray码串。代码实现// Gray Inc// UVa ID: 11663// Verdict: Accepted// Submission Date: 2026-06-19// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 格雷码解码为二进制索引串高位在前stringgrayToBinary(conststringgray){intn(int)gray.size();stringbin(n,0);bin[0]gray[0];for(inti1;in;i)bin[i]((bin[i-1]-0)^(gray[i]-0))0;returnbin;}// 二进制索引串编码为格雷码高位在前stringbinaryToGray(conststringbin){intn(int)bin.size();stringgray(n,0);gray[0]bin[0];for(inti1;in;i)gray[i]((bin[i]-0)^(bin[i-1]-0))0;returngray;}// 二进制串加 1模 2^n高位在前voidincrementBinary(stringbin){intn(int)bin.size();intin-1;while(i0bin[i]1){bin[i]0;--i;}if(i0)bin[i]1;// 若 i 0说明全 1 变为全 0已自动取模}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intm;string w;while(cinmw){if(m0w0)break;string bingrayToBinary(w);for(intstep0;stepm;step)incrementBinary(bin);coutbinaryToGray(bin)\n;}return0;}总结本题的核心在于识别出GnG_nGn​就是标准的二进制反射Gray\texttt{Gray}Gray码从而直接利用Gray\texttt{Gray}Gray码与二进制索引之间的转换关系。由于nnn较大100100100不能使用内置整数类型但mmm很小通过模拟二进制加法即可高效地完成“向后移动”操作。该解法简洁时间复杂度与n⋅mn \cdot mn⋅m成正比完全满足题目限制。注意处理循环回绕当二进制串全为1时加111后变为全0正好对应循环Gray\texttt{Gray}Gray码的最后一个单词后继为第一个单词。