# Topcoder SRM 634 Div2 T3 SpecialStrings 题解

2018 年 9 月 2 日 12:59

## 文章目录

Topcoder Single Round Match 634 Div 2 T3 SpecialStrings 题解

## Translation

• 每个字符都是 0 或 1；
• 对于所有 S = UV，U 和 V 都是非空字符串，U 都按字典序严格小于 V。

• current will contain between 1 and 50 characters, inclusive.
• current will be a special string.
• Time limit (s): 2.000
• Memory limit (MB): 256

## Examples

"01"


Returns: ""

"01" 是唯一的长度为 2 的特殊串。

"01" is the only special string of length 2.

"00101"


Returns: "00111"

The special strings of length 5 are "00001", "00011", "00101", "00111", "01011", "01111".

"0010111"


Returns: "0011011"

## Original

A string S is called special if it satisfies the following two properties:

• Each character in S is either '0' or '1'.
• Whenever S = UV where both U and V are nonempty strings, U is strictly smaller than V in lexicographic order.

For example, the string S = "00101" is special because we have "0" < "0101", "00" < "101", "001" < "01", and "0010" < "1".
You are given a string current that is guaranteed to be special. Let N be the length of current. Consider the lexicographically sorted list of all special strings of length N. Compute and return the string that comes immediatelly after current in this list. If current happens to be the last string in the list, return an empty string instead.

## Analysis

（一开始我居然想到了容斥/二项式反演…… :new_moon_with_face: ）

• 所有 special string 都以 1 结尾；
• 所有 special string 的前导 0 数量一定比后面连续的 0 最大数量大。

## Code

#include <bits/stdc++.h>
using namespace std;
const int maxn=55;
int n;
long long num;
string a,ans;

class SpecialStrings {
public:
string findNext( string current ) ;
};
inline void write(long long x){
string tmp;
for (int i=n-1;i>=0;i--) tmp+=(x&((long long)1<<i))?'1':'0';
cout<<tmp<<endl;
}
inline bool check(long long x){
for (int i=1;i<n;i++){
string aa="",bb="";
for (int j=n-1;j>=i;j--) aa+=(x&((long long)1<<j))?'1':'0';
for (int j=i-1;j>=0;j--) bb+=(x&((long long)1<<j))?'1':'0';
if (!(aa<bb)) return false;
}
return true;
}
string SpecialStrings::findNext(string current) {
n=current.length();a=current;
num=0;
for (int i=0;i<n;i++) num=num*2+(current[i]-'0');
long long snum=num;
for (int i=0;i<n;i++) if (!(num&((long long)1<<i))){
a[n-i-1]='1';num+=(long long)1<<i;
if (check(num)) break;
}
if (!check(num)) return "";
for (int i=n-1;i>=0;i--) if (num&((long long)1<<i)){
long long nxtnum=num;
nxtnum-=(long long)1<<i;
if (nxtnum<=snum) continue;
if (check(nxtnum)) num=nxtnum;
}
if (num<=snum) return "";
char tmp[maxn];
for (int i=n-1;i>=0;i--) tmp[i]=(num&1)?'1':'0',num>>=1;
ans="";
for (int i=0;i<n;i++) ans+=tmp[i];
return ans;
}