P8589 『JROI-8』对了，还有花，少女，银河 题解

· · 题解

题目简述

原题链接

给定 n，请构造一个长度为 n 的仅包含 0,1 的数字串，满足 01,00,10,11 出现的次数相等，或报告无解。

这里“出现”指与原字符串中连续的一部分完全相同。例如，在 1011101 中，01,00,10,11 分别出现了 2,0,2,2 次。

思路

显然，这是构造的题。

本人做这道题的时候用了一点小技巧。

那么如何判断能否构造？

只需要一个简单的暴力 DFS 就可以了。 当然你也可以用特殊性质来猜，或者如果你是大佬的话可能一下子就想出来了。

DFS 程序如下：

#include<iostream>
using namespace std;
int a[100],flag;
void print(int n){
    for(int i=1;i<=n;i++){
        cout<<a[i];
    }cout<<endl;
}
bool check(int n){
    int x01=0,x11=0,x10=0,x00=0;
    for(int i=2;i<=n;i++){
        if(a[i-1]==0&&a[i]==0)x00++;
        if(a[i-1]==0&&a[i]==1)x01++;
        if(a[i-1]==1&&a[i]==0)x10++;
        if(a[i-1]==1&&a[i]==1)x11++;
    }
    if(x00==x01&&x01==x10&&x10==x11){flag=1;return true;}
    return false;
}
void dfs(int step,int n){
    if(step==n+1){
        if(check(n))print(n);
        return;
    }
    a[step]=1;
    dfs(step+1,n);
    a[step]=0;
    dfs(step+1,n);
}
int main(){
    int n;
    cin>>n;
    for(int j=1;j<=n;j++)a[j]=3;
    flag=0;
    dfs(1,n);
    if(flag)cout<<"yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

运行这个程序之后发现只有在 4n+1(n \in \mathbf{N^*}) 的时候才可能有解。

然后，难道真的要用这程序来输出答案吗？

当然不是，这只是个判断。

解题的重点在下面：

有了上面的判断就可以写答案程序了

综上有以下两点

  1. 当 n \bmod 4=1 \ (n\in\mathbb N^*) 时，可以构造序列

  2. 其他情况均无解

对于构造序列，其实题目已经给出来了（上面的程序也给出来了）

看样例：

输入 #2
5
输出 #2
00110

这不就给出来了

先输出 \dfrac{n-1}{4} 个 0011，最后输出 0

如下：

\begin{matrix}\\\underbrace{0011\cdots 00110}\\n\end{matrix}

证明

对于每一段的0011

一共有

综上，这样只要按照如上构造方法，无论有多少段，其中 01,00,10,11 的数量均是相等的。

Code

#include<iostream>
using namespace std;
int main() {
    long long n;cin >> n;
    if ((n - 1) % 4 == 0&&n!=1) {
        for (int i = 1; i <= n/4; i++)cout << "0011";
        cout << 0 << endl;
        return 0;
    }
    else cout<<-1<<endl;
    return 0;
}

听说CSP考试前交题解可以rp++。

顺便推荐做一下之前月赛的题目P8437 伟大的神，相比之下，伟大的神明显更难，思维难度更高一点。