自动搬运

查看原文

来自洛谷，原作者为

	AThls123 别翻车了，不要再翻车了

搬运于2025-08-24 22:40:28，当前版本为作者最后更新于2022-10-25 22:42:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目简述

原题链接

给定 $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

一共有

• 一个 $00$

• 一个 $11$

• 一个 $01$

• 没有一个 $10$，但每段末尾的$0$会和右边开头的 $0$ 合成一个 $10$

综上，这样只要按照如上构造方法，无论有多少段，其中 $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 伟大的神，相比之下，伟大的神明显更难，思维难度更高一点。