自动搬运

查看原文

来自洛谷，原作者为

	xxgirlxx DL 厨||关注 xxgirlxx 谢谢喵，关注 xxboyxx 谢谢喵||主页：https://www.luogu.com.cn/problem/U546944

搬运于2025-08-24 23:12:28，当前版本为作者最后更新于2025-04-30 16:47:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题外话

警示后人：不要分讨太投入导致忘记要输出 Yes/No，主播因此浪费 30min+。

代码后附做题游记（逃。

题目思路

首先可以发现三目运算符最后结果想为 $1$，最后一步的结构一定是 1?1:x 或者 0?x:1 中的一个。

然后发现第一种情况的第一个 $1$ 可能是我们不需要考虑的，这是一种情况，第二种情况中的第一个 $0$ 和最后一个 $1$ 也可能是我们不需要考虑的，这又是两种情况。所以我们需要讨论三种情况。

在考虑情况之前我们先找一点性质：可以发现，0?x:0 的嵌套最终结果是最后一个数，我们可以考虑在最后一个数的位置放 $1$ 来将这一串化为一个 $1$，即将嵌套中的最后一个 0?x:0 换位 0?x:1。而且这个式子还有性质就是里面涉及到的重要的数字的所在位置的奇偶性是一致的。

然后我们考虑第一种情况，即如果该 01 串的第一个数是 $1$，那么我们就需要找到另一个 $1$，而且这个 $1$ 化出来后必须是第二个数，这个时候就可以用到上面的性质了：我们从第二个数开始一个个跳着（就是从 $x$ 跳到 $x+2$）往后找，直到找到一个 $1$ 为止。这样我们就弄出了 1?1:x，后面的不用管怎么算，只需要输出合法即可。

接下来我们考虑第二种情况，即如果该 01 串的最后一个数是 $1$，那么我们就需要使得第一个数是 $0$。这个时候我们需要结合上一种情况：如果该串的第一位是 $0$，那么直接就构成了 0?x:1，中间乱搞然后合法输出。否则该串一定进入上一种情况中进行一次判断，若该串的第二个位置是 $1$，那么该串会直接在上一种情况中输出解而不会到这种情况中。否则前三位可以构成 1?0:x 使得第一位变成 $0$，然后就构成了 0?x:1，中间乱搞然后合法输出。但是注意一下如果第一位是 $1$ 就需要判断长度，因为针对第一位是 $1$ 的情况，长度必须大于 $5$ 才行，因为需要做两次运算，如果不判断长度，就需要特判这个 hack：101。

最后我们来考虑第三种情况，即如果该 01 串的第一个数是 $0$，那么我们就需要使得最后一个数是 $1$。可以发现，使得最后一个数为 $1$，可以转化为在该串中取一个后缀，使得该后缀的最终值为 $1$，因此我们可以考虑将这部分用分成的三种情况中的一种情况的方法来做：但是用第三种情况等于无限嵌套，根本做不出来；第二种情况需要最后一个位置为 $1$，在这里被固定了，无法保证是通解；而第一种情况则是要求第一个数为 $1$，放到这里来就是可以选择的，我们可以通过选择合适的后缀的起点来使得第一位为 $1$，更适用且是通解，因为如果你连最后是个 $1$ 都弄不出来你整个也就做不了了。所以我们考虑将这部分转化为第一种情况，注意因为要化为 $1$ 所以后缀的长度一定是奇数，且需保证第一位为 $1$ 然后中间在偶数位上有 $1$ 就可以按第一种情况的方法做了。

Code

注释里的做题游记占了代码总长的 $\frac{3}{5}$，抽象。

已注释掉暴戾语言，求过。

#include<bits/stdc++.h>
using namespace std;
int t,n;
char a[3000010];
int main(){
	cin>>n,n=n*2+1;
	for(int i=1;i<=n;i++)cin>>a[i];
	if(a[1]=='1'){
		int f=0;
		if(a[2]=='1'){
			cout<<"Yes\n1?1:";
			int num=0;
			for(int i=5;i<=n;i+=2)num++,cout<<"(";
			cout<<a[3];
			for(int i=5;i<=n;i+=2)cout<<"?"<<a[i-1]<<":"<<a[i]<<")";
			return 0;
		}
		int num=0;
		for(int i=4;i<=n;i+=2){
			num++;
			if(a[i]=='1'){f=i;break;}
		}
		if(f!=0){
			cout<<"Yes\n1?";
			for(int i=1;i<=num;i++)cout<<"(";
			cout<<a[2];
			for(int i=4,j=1;j<=num;i+=2,j++)cout<<"?"<<a[i-1]<<":"<<a[i]<<")";
			cout<<":",num=0;
			for(int i=f+3;i<=n;i+=2)num++,cout<<"(";
			cout<<a[f+1];
			for(int i=f+3,j=1;j<=num;i+=2,j++)cout<<"?"<<a[i-1]<<":"<<a[i]<<")";
            return 0;
		}
	} 
	if(a[n]=='1'){
		if(n>=5||a[1]=='0'){
			if(a[1]=='0'){
				int num=0;
				cout<<"Yes\n0?";
				for(int i=4;i<=n;i+=2)num++,cout<<"(";
				cout<<a[2];
				for(int i=4,j=1;j<=num;i+=2,j++)cout<<"?"<<a[i-1]<<":"<<a[i]<<")";
				cout<<":1";
			}
			else{
				int num=0;
				cout<<"Yes\n(1?0:"<<a[3]<<")?";
				for(int i=6;i<=n;i+=2)num++,cout<<"(";
				cout<<a[4];
				for(int i=6,j=1;j<=num;i+=2,j++)cout<<"?"<<a[i-1]<<":"<<a[i]<<")";
				cout<<":1";
			}
			return 0;
		}
	}
	if(a[1]=='0'){
		int lst=0,f=0;
		for(int i=3;i<=n;i++){
			if(a[i]=='1'){
				if(i%2==1)lst=i;
				else if(lst!=0){f=i;break;}
			}
		}
		if(f!=0){
			int num=0;
			cout<<"Yes\n0?";
			for(int i=4;i<lst;i+=2)num++,cout<<"(";
			cout<<a[2];
			for(int i=4,j=1;j<=num;i+=2,j++)cout<<"?"<<a[i-1]<<":"<<a[i]<<")";
			cout<<":(1?",num=0;
			for(int i=lst+3;i<=f;i+=2)num++,cout<<"(";
			cout<<a[lst+1];
			for(int i=lst+3,j=1;j<=num;i+=2,j++)cout<<"?"<<a[i-1]<<":"<<a[i]<<")";
			cout<<":",num=0;
			for(int i=f+3;i<=n;i+=2)num++,cout<<"(";
			cout<<a[f+1];
			for(int i=f+3,j=1;j<=num;i+=2,j++)cout<<"?"<<a[i-1]<<":"<<a[i]<<")";
			cout<<")";
			return 0;
		}
	} 
	cout<<"No"; 
	return 0;
}
/*
好的如你所见我又开始做构造了
这是我的第三道构造黑
前两道分别是P6892和AT_arc189_e
在这里贴个专栏：
P6892:https://www.luogu.com.cn/article/gnqb5657
AT_arc189_e: https://www.luogu.com.cn/article/st0edth2
lc上场那个T2能算构造嘛？
没有方案的构造是没有灵魂滴！
首先搞清楚肯定正确的情况：
1?1:x和0?x:1一定是正确的
因此我们可以尝试着舍弃第一个数？
好像不行
这不就假了？
***
不会
三目运算符最强大的一集
哦哦哦可以发现一个东西就是你想要一个1可以是多个0?x:0嵌套然后最后一个是0?x:1
这样就可以弄出一个1来
然后你就会发现这样搞出来貌似0的位置的奇偶性都是一致的
这样第一位为1的话就非常容易了啊
至少其中一种有解是非常容易的
但是显然不是这种方式无解就无解
样例一就是反例
因为可以有最后一个位置是1然后搞成第一位为0的情况
so?
所以还要讨论两种情况？
***
讨厌分讨
虽然难的构造很少有不分讨的（逃
所以接下来就又分成两种：
一种是0?x:1（确定1）
另一种是0?x:1（确定0）
不管了
先把1?1:x的情况给写了
Coding···
哦哦哦发现一个corner case
就是如果1前面只有一个0就会逝
***
还得搞？
哦哦哦
这种情况下貌似就不行
***
为什么会T啊？
哦哦哦字符串加太屎了
改一下
欸nm为什么会WA啊
哦哦哦原来起始位置写错了
完成
所以现在还剩两种情况：
都是以0?x:1来使最终结果为1
但确定的东西不同
一个确定的是0
另一个确定的是1
先看看确定0的情况
那就是要使最后一个位置为1
这好搞吗？
感觉不好搞啊
1?1:x中的1之所以好搞是因为它不需要考虑位置的原因啊
反正从第二个位置开始就行了
但这种情况不行啊
它的最后一个位置必须是1
不好搞
这真不好搞
再尝试找找除了0?x:0嵌套之外的性质吧
有没有1的嵌套呢？
好像没有
主要是0之所以有性质是因为0刚好隔一个就行
所以0如果中间先弄的话是不会改变结果的
但是1就不行了
***
神秘
哦哦哦发现一种可以做确定1的情况的做法
就是你会发现你最后一位是1
需要第一位是0
但如果第一位不是0那么就肯定是1
那就会进入第一个进行判断
但是第一个又没有成功
就说明第二个位置一定是0
所以直接跑前三个就可以弄出0了
但是注意一下可能有101卡你
因为这种方法长度至少都得是5
所以还是要判断一下
Coding···
***
怎么WA了？
怎么是神秘错误
***
我**0?1:1也有错？
不符合模式？
什么模式？
这哪里不是三目运算符了？
进题目给的链接里找下数据和SPJ
***这么多怎么找？
尝试寻找旁边的大佬求助未果
终于找到了
看看SPJ
***我没输出Yes/No
幽默过头了哥们
好的过了
最后一种定0找1真**不知道咋做啊
这个1真心不好找啊
主要是你要找1
最后一个又不一定是1
假如说前面又足够多的数
最终化出来的结尾要么是100要么是10
这不得去前面找1？
这去前面找1那不得麻烦上天
***太难了
所以说会不会最终用的1不是最后一个1？
***很有可能啊
那会是哪个1？
哦哦哦可以在后面找两个连着的1
这样后面就不用管了
正确性也很好证
你连两个连着的1都没有剩下的你还能怎么搞出来？
肯定搞不出来
Coding···
哦哦哦还要注意一下这两个连着的1中前面那个必须在奇数位
否则你会发现搞不了
先assert一下验证一下正确性
完蛋
剩下的部分不是全是这个东西
也就是说这个不是通解
哦哦哦不一定要现在就连着
可以用操作来让它连着
翻译：只要有两个1之间差了偶数个数就可以
***
剩下的还有不是这个东西的
那**是什么？
欸欸欸这题怎么有个紫的双倍经验啊？
那这题是黑还是紫？
不管了
好好想想0?x:1定0怎么做
哦是不是还是得到前面去找1啊？
难绷
看看是不是需要两个1之间隔偶数位且后面的0的数量是奇数
毕竟奇数个才能使110算出来是0
那最后一位是1怎么办？
那不是都在上一种情况考虑过了吗？
再assert试试
都奋战3h+了
再试不出来就要崩溃看题解了
漂亮！
就是这个方法
Coding···
颢爷
我成啦！
*/