题解：P12055 [THUPC 2025 决赛] 一个 01 串，n 次三目运算符，最后值为 1
题外话
警示后人：不要分讨太投入导致忘记要输出 Yes/No，主播因此浪费 30min+。
代码后附做题游记（逃。
题目思路
首先可以发现三目运算符最后结果想为 1?1:x 或者 0?x:1 中的一个。
然后发现第一种情况的第一个
在考虑情况之前我们先找一点性质：可以发现，0?x:0 的嵌套最终结果是最后一个数，我们可以考虑在最后一个数的位置放 0?x:0 换位 0?x:1。而且这个式子还有性质就是里面涉及到的重要的数字的所在位置的奇偶性是一致的。
然后我们考虑第一种情况，即如果该 01 串的第一个数是 1?1:x，后面的不用管怎么算，只需要输出合法即可。
接下来我们考虑第二种情况，即如果该 01 串的最后一个数是 0?x:1，中间乱搞然后合法输出。否则该串一定进入上一种情况中进行一次判断，若该串的第二个位置是 1?0:x 使得第一位变成 0?x:1，中间乱搞然后合法输出。但是注意一下如果第一位是 101。
最后我们来考虑第三种情况，即如果该 01 串的第一个数是
Code
注释里的做题游记占了代码总长的
已注释掉暴戾语言，求过。
#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···
颢爷
我成啦！
*/