Topcoder Single Round Match 634 Div 2 T3 SpecialStrings 题解

Translation

如果一个字符串 S 满足以下条件，则我们说这个字符串是“特殊的”：

例如，字符串 S = 00101 是“特殊的”，因为我们知道 0 < 0101，00 < 101，001 < 01，且 0010 < 1。
现在给你一个字符串 current，保证这一定是个特殊的字符串。假设 N 是 current 的位数。考虑列出所有长度为 N 的特殊字符串的表，计算并返回第一个 current 后面的字符串。如果 current 已经是最后一个则返回一个空串。

数据范围：$1 \leqslant N \leqslant 50$。

  • 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"

长度为 5 的特殊串有："00001"，"00011"，"00101"，"00111"，"01011"，"01111"。

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

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

这种题目肯定是构造。—— Captain Slow

首先暴力的解法肯定要超时，$1 \leqslant N \leqslant 50$，$2^{50}$ 已经是一个天文数字了，更何况要加上 check special string……

先观察样例里的 special string，可以发现规律：

嗯，知道了这个，我们就可以知道：从字符串的右边往左边开始不断把 0 改为 1，这样最后总会得到一个 special string（大不了除了前导零全都改成 1）（如果得不到就返回空串呗）。
但是这样得到的一个 special string 并不能保证是 current 之后的第一个。我们要从左到右重新修正一番。具体方法是：从左到右，逢 1 就改成 0 试试，保证满足：它仍然是 special string，并且字典序严格大于 current。因为我们优先从左边把 1 改成 0，保证了字典序最小。

于是算法分为两个步骤：从右往左把 0 变成 1，从左往右把 1 变成 0。时间复杂度 $\Theta (N^2)$。

一开始这个神奇的想法我也没想到，还在想二项式反演 $QwQ$，直到去 he 了某个大佬的 solution……话说这种想法真的很难想到啊……

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;
}