AtCoder Regular Contest 127

• 2021 年 11 月 17 日
• 筆記
• ----OnlineJudge----, ----其他----, OnlineJudge - 題集, 其他 - 思路題

Portal

B

Description

給出\(n(\leq5\times10^4),L(\leq15)\)，構造\(3n\)個不同\(L\)位的三進制數，使得在這\(3n\)個數的每一位上，0/1/2各出現\(n\)次。在這樣的前提下，使得其中的最大數儘可能小。

Solution

易知最大的\(n\)個數一定是2開頭的，那麼就令這\(n\)個數為\(200..0_{(3)},200..0_{(3)}+1,…,200..0_{(3)}+n-1\)。

將這些數中的0換成1，1換成2，2換成0，作為最小的\(n\)個數；將這些數中的0換成2，1換成0，2換成1，作為中間的\(n\)個數。

C

Description

對於無前綴零的\(1..2^n(n\leq10^6)\)這些二進制數，將其作為字符串按字典序排列，求第\(x(\leq2^n-1)\)個（\(x\)以二進制給出）。

Solution

考慮這個排列是怎麼生成的。按位數將二進制數加入到排列中（新加入的用[]標註）：

• 1位：[1]
• 2位：1 [10 11]
• 3位：1 10 [100 101] 11 [110 111]
• 4位：1 10 100 [1000 1001] 101 [1010 1011] 11 110 [1100 1101] 111 [1110 1111]

發現\(i\)位數都是在\(i-1\)位數後插入兩個，那麼除第一位為1外，一個序列可以分成：一個空串 + \(2^k-1\)個0首串 + \(2^k-1\)個1首串。於是可以遞歸求解。第\(x\)個串（從0開始）是：

• 空串，當\(x=0\)。
• 0首串中的第\(x-1\)個，當\(x<2^k\)。
• 1首串中的第\(x-2^k\)個，當\(2^k \leq x\)。

遞歸至多\(n\)次，便可確定每一位的取值。你或許會擔心對大數\(x\)進行運算會讓複雜度退化到\(O(n^2)\)，不過其實是不會的。

判斷\(x\)與\(2^k\)的大小隻要觀察\(x\)的首位；\(x-2^k\)只需移除首位上的1。對於判0操作，可以維護\(x\)中1的數目，若\(x\)中沒有1說明\(x=0\)。對於\(x-1\)操作，尋找到最後的1位，將其置0並將後面所有位置1，這一過程中可以維護\(x\)中1的數目。由於\(x-1\)操作最多執行\(n\)次，而第\(k\)位每\(2^k\)次操作中才會被借位一次，且一經借位後方都被置1，使得借位的複雜度大大降低。

Code

//Binary Strings
#include <cstdio>
#include <cstring>
const int N=1e6+10;
int n; char x[N],y[N];
bool equal0()
{
    for(int i=n;i>=1;i--) if(x[i]=='1') return false;
    return true;
}
void minus1()
{
    int k=n;
    while(x[k]=='0') k--;
    x[k]='0';
    for(int i=k+1;i<=n;i++) x[i]='1';
}
int main()
{
    scanf("%d",&n);
    scanf("%s",x+1);
    int m=strlen(x+1);
    for(int i=n;i>=1;i--) x[i]=(i-n+m>0)?x[i-n+m]:'0';
    for(int i=1;i<=n;i++) y[i]=0;
    minus1();
    y[1]='1';
    for(int k=1;k<=n;k++)
    {
        if(equal0()) break;
        if(x[k]=='0') y[k+1]='0',minus1();
        else y[k+1]='1',x[k]='0';
    }
    puts(y+1);
    return 0;
}