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_nGnG10,1 G_1 0, 1G10,1Gn0Gn−1, 1Gn−1R(n≥2) G_n 0G_{n-1},\; 1G_{n-1}^{R} \quad (n \ge 2)Gn0Gn−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−1gn−1对于in−2,n−3,…,0i n-2, n-3, \dots, 0in−2,n−3,…,0有kiki1⊕gik_i k_{i1} \oplus g_ikiki1⊕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码的最后一个单词后继为第一个单词。

UVa 11663 Gray Inc

相关推荐

Linux --- 共享内存

2026全国足浴管理软件权威评测榜

Windows Docker环境搭建：从WSL虚拟化到Docker Desktop配置全指南

更多资讯

ARTEX漏洞推送六渠道完整配置：钉钉、飞书、企业微信、Telegram与邮件实战

Macro desktop-cef 深度解析：用 Chromium（CEF）为 macOS 构建 Tauri 桌面端

BlueprintJS 选型与上手指南：React 数据密集型应用的桌面 UI 底座

awesome-openclaw技能生态指南：ClawHub与5400+个Skills如何挑选与安装

从自动点到AI智能助手：ShizukuDhizuku-list自动化AI工具盘点，让手机替你干活

WPF三种启动方式 + 静态资源 + 数据绑定满分知识点整理

今日更新

AI智能体开发实战：从技术原理到商业落地

OpenShell 完全定制指南：从安装到深度配置，打造高效 Windows 开始菜单

Superpowers技能体系全解析：从Skills引入到安装的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？