URAL 2004 Scientists from Spilkovo (De Bruijn序列)

注意：这是一篇从旧博客恢复的文章。

原地址：http://freemeepo.com/acm/1369.html

注：有更新

http://acm.timus.ru/problem.aspx?space=1&num=2004

2004. Scientists from Spilkovo
Time limit: 0.5 second
Memory limit: 64 MB
Misha and Dima are promising young scientists. They make incredible discoveries every day together with their colleagues in the Spilkovo innovative center. Now Misha and Dima are studying the properties of an amazing function F which is written as follows.
C++:
int F(int x, int n)
{
    return (((x & ((1 << (n / 2)) - 1)) << ((n + 1) / 2)) | (x >> (n / 2)));
}
Pascal:
function F(x, n: integer): integer;
begin
    F := (((x and ((1 shl (n div 2)) - 1)) shl ((n + 1) div 2)) or (x shr (n div 2)));
end;
The friends want to perform the following computational experiment.

All integers from 0 to 2n − 1 are written.
Each integer x is replaced by F(x, n).
Each integer obtained after step 2 is written as a binary string of length n (if the integer has less than n bits, some leading zeroes are added; if the integer has more than n bits, only last n bits are written).
The result of the experiment is a binary string of minimum length, that contains all the strings obtained after step 3 as its substrings.
If you can perform this experiment, maybe you are able to work in Spilkovo too!
Input
The only line contains an integer n (1 ≤ n ≤ 20).
Output
Output the required binary string. If there are several optimal solutions, you may output any of them.
Sample
input    output
1
10
Problem Author: Ilya Kuchumov
Problem Source: Ural Regional School Programming Contest 2013
Tags: none  (
hide tags for unsolved problems
)

组队赛里的一题，当时读了题目就想把它做出来。

首先读懂题目，题中的那个函数的意思其实是将一个数写成二进制形式之后，把前一半与后一半交换，例如11 01变成01 11，101 10变成10 101。

题目要求输入一个n，对0到2^n-1所有的数，使用上面的那个函数进行处理，得到2^n个二进制序列，最后求一个最短的串s，使所有的二进制序列都是s的子串。

分析之后发现用不用上面那个函数完全没有区别，所以根本不用考虑。但还是不会做。

看了discussion之后发现这个东西叫做De Bruijn序列。

查了一些资料，找到了一篇matrix67写的介绍De Bruijn sequence的文章

下载地址：https://debug.fanzheng.org/static/upload/files/%E6%AC%A7%E6%8B%89%E8%B7%AF%E5%BE%84%E5%92%8CDe%20Bruijn%E5%BA%8F%E5%88%97.pdf

以及这篇文章http://www.matrix67.com/blog/archives/3985

然后倒是看懂了什么意思了，但是依然不会生成这个序列。

查了wiki之后找到了一个python版的代码

def de_bruijn(k, n):
    """
    De Bruijn sequence for alphabet size k 
    and subsequences of length n.
    """
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

print de_bruijn(2, 3)

不会python……花了很长时间来改成了C++版的。

另外这题跟De Bruijn序列还有点不一样，这题不是环形的，所以最后要加上序列的前n-1个元素，补成一个环。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<list>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<iomanip>
#include<bitset>
#include<sstream>
#include<fstream>
#define debug puts
#define pi (acos(-1.0))
#define eps (1e-8)
#define inf (1<<30)
using namespace std;
//k为元素值范围，n为串长度
void db(int n,int k,vector<int> &v,int a[],int t=1,int p=1)
{
    if (t>n)
    {
        if (n%p==0)
            for (int i=1; i<=p; i++)
                v.push_back(a[i]);
    }
    else
    {
        a[t]=a[t-p];
        db(n,k,v,a,t+1,p);
        for (int i=a[t-p]+1; i<k; i++)
        {
            a[t]=i;
            db(n,k,v,a,t+1,t);
        }
    }
}
vector<int> de_bruijn(int n,int k)
{
    vector<int> v;
    int a[n*k];
    memset(a,0,sizeof(a));
    db(n,k,v,a);
    return v;
}
int main()
{
    int n;
    cin>>n;
    vector<int> v=de_bruijn(n,2);
    for (int i=0; i<v.size(); i++)
        cout<<v[i];
    for (int i=0; i<n-1; i++)
        cout<<v[i];
    return 0;
}

FanZheng's Debug Blog

URAL 2004 Scientists from Spilkovo (De Bruijn序列)

Comments