UVa 11166 Power Signs-编程阁

题目描述

给定一个正整数n nn，它的二进制表示为不含前导零的二进制字符串。我们需要将n nn表示为带符号的二进制表示（signed binary representation \texttt{signed binary representation}signed binary representation），即：

n = ∑ i = 0 k a i × 2 i n = \sum_{i=0}^{k} a_i \times 2^in=i=0∑kai×2i

其中a i ∈ { − 1 , 0 , 1 } a_i \in \{-1, 0, 1\}ai∈{−1,0,1}。

在二进制表示中，每一位a i a_iai只能是0 00或1 11，因此表示是唯一的。但是在带符号的二进制表示中，每一位可以是− 1 -1−1、0 00或1 11，因此表示不唯一。题目要求我们找到一种带符号的二进制表示，使得其中非零数字（即+ 1 +1+1或− 1 -1−1）的个数最少。如果存在多种最优解，则输出其中字典序最小的一个（按照ASCII \texttt{ASCII}ASCII码顺序比较，其中字符的顺序为'+' < '-' < '0'）。

输入包含多个测试用例（最多25 2525个），每个测试用例一行，是一个正整数n < 2 50000 n < 2^{50000}n<250000的二进制表示（不含前导零）。输入以n = 0 n = 0n=0结束，该行不需处理。

对于每个测试用例，输出一行，给出满足条件的带符号二进制表示，用字符'+'表示+ 1 +1+1，'-'表示− 1 -1−1，'0'表示0 00，且不含前导零。

题目分析

本题的关键在于理解如何通过带符号的二进制表示来减少非零数字的个数。观察普通的二进制表示，连续的1 11串可以通过进位和借位的方式，转换为更少的非零数字。

例如，二进制数7 77的普通表示是111 111111（即4 + 2 + 1 4+2+14+2+1），其中有3 33个非零数字。但我们可以将其表示为100 − 100-100−（即8 − 1 8-18−1），这样只有2 22个非零数字（+ 1 +1+1和− 1 -1−1）。更一般地，连续的k kk个1 11可以表示为：

11 … 1 ⏟ k 个 = 2 k − 1 = 2 k − 2 0 \underbrace{1 1 \dots 1}_{k \text{个}} = 2^k - 1 = 2^k - 2^0k个11…1=2k−1=2k−20

即一个+ 1 +1+1在高位，k − 1 k-1k−1个0 00在中间，一个− 1 -1−1在最低位。这样就将k kk个非零数字减少到了2 22个。

然而，这还不是最优的。因为当我们进行这样的转换时，会产生一个进位（即将连续1 11串前面的0 00变为1 11）。这个进位可能与更高位的1 11形成新的、更长的连续1 11串，从而可以进一步优化，减少更多的非零数字。

解题思路

基于以上分析，我们可以设计一个贪心算法，从二进制表示的最低位向最高位扫描，处理连续的1 11串。

算法步骤

初始化：在二进制字符串前添加一个字符'0'作为哨兵，用于处理可能的最高位进位。
从低位向高位扫描：
- 对于每个位置i ii（从最低位到最高位），如果当前字符是'1'，则向前（向高位方向）寻找连续'1'的起始位置j jj（即s [ j ] = ′ 0 ′ s[j] = '0's[j]=′0′且s [ j + 1.. i ] s[j+1..i]s[j+1..i]都是'1'）。
- 计算连续1 11的长度l e n = i − j len = i - jlen=i−j。
- 如果l e n ≥ 2 len \ge 2len≥2，则进行转换：
  - 将s [ i ] s[i]s[i]改为'-'（表示− 1 -1−1）。
  - 将s [ j + 1.. i − 1 ] s[j+1..i-1]s[j+1..i−1]改为'0'。
  - 将s [ j ] s[j]s[j]改为'1'（进位）。
  - 注意：这里进位设为'1'而不是'+'，因为它可能与更高位的'1'构成更长的连续1 11串，从而在后续扫描中被进一步优化。
- 特殊情况：如果l e n = 2 len = 2len=2且j = 0 j = 0j=0（即连续两个1 11在最高位），则直接将这两个位置设为'+'，不进行转换（因为转换后最高位会变成'-'，可能不是字典序最小）。
- 如果l e n = 1 len = 1len=1（单个1 11），则直接将该位置设为'+'。
处理最高位进位：扫描结束后，如果哨兵位s [ 0 ] s[0]s[0]变成了'1'，则将其改为'+'。
输出结果：如果s [ 0 ] = ′ 0 ′ s[0] = '0's[0]=′0′，则从s [ 1 ] s[1]s[1]开始输出；否则从s [ 0 ] s[0]s[0]开始输出。这样可以确保没有前导零。

算法正确性说明

该算法是贪心的，从最低位开始，每次遇到连续长度≥ 2 \ge 2≥2的1 11串就进行转换。这样做的正确性基于以下观察：

最优子结构：一个数的最优带符号二进制表示，其最低位的决策不会影响更高位的最优性（因为转换只产生向高位的进位，不影响已经处理过的低位）。
贪心选择性质：对于连续的k kk个1 11，立即进行转换（变为2 k − 1 2^k - 12k−1）总是比保持原样更优或至少不差（当k ≥ 3 k \ge 3k≥3时严格更优，k = 2 k = 2k=2时需要特殊处理字典序）。
字典序最小：由于我们从低位向高位处理，且在高位尽量保持'+'（而不是'-'），最终得到的表示在非零数字最少的前提下是字典序最小的。

时间复杂度

扫描整个字符串一次，每次处理连续1 11串时可能会修改多个字符，但每个字符最多被修改一次（从'1'改为'0'或'-'），因此总时间复杂度为O ( n ) O(n)O(n)，其中n nn是二进制字符串的长度。由于n ≤ 50000 n \le 50000n≤50000，算法完全可行。

空间复杂度

只需要存储输入字符串和一些辅助变量，因此空间复杂度为O ( n ) O(n)O(n)。

代码实现

// Power Signs// UVa ID: 11166// Verdict: Accepted// Submission Date: 2025-12-20// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=50010;intmain(){chars[MAXN];while(scanf("%s",s+1)==1&&s[1]!='0'){s[0]='0';intn=strlen(s+1);// 从低位向高位扫描（i从n到1）for(inti=n;i>0;i--){if(s[i]=='1'){intj=i-1;// 向前寻找连续1的起始位置while(s[j]=='1')j--;// 检查连续1的长度// 连续1的长度≥2if(i-j>=2){// 特殊情况：连续2个1且在最高位（j==0）if(i-j==2&&j==0)s[i]=s[i-1]='+';else{// 一般情况：转换连续1// 最后一个1变成-1s[i]='-';// 中间的1变成0for(intk=i-1;k>j;k--)s[k]='0';// 进位（前面的0变成1），不变为+，因为有可能与前面的1构成更长的连续1串，// 从而可以得到非0数字更少的表示，从而可能会更优s[j]='1';}}elses[i]='+';// 单个1，直接变成+}}// 处理可能的最高位进位if(s[0]=='1')s[0]='+';// 输出结果if(s[0]=='0')printf("%s\n",s+1);elseprintf("%s\n",s);}return0;}

示例分析

样例输入

10000 1111 10111 0

样例输出

+0000 +000- ++00-

解释

10000 1000010000（二进制16 1616）：
- 没有连续1 11，直接转换为+0000。
1111 11111111（二进制15 1515）：
- 从低位扫描，连续4 44个1 11，转换为1000 − 1000-1000−，即+000-。
10111 1011110111（二进制23 2323）：
- 首先处理低三位111 111111，转换为100 − 100-100−，同时进位使前面变为1 11，得到1100 − 1100-1100−。
- 然后处理新的连续两个1 11（在第二位和第三位），但由于它们在最高位且长度为2 22，不转换，直接设为++，最终得到++00-。