[CF 550E] Brackets in Implications

作法：

這題就是個構造題，看了這份code之後就覺得我寫的解也太複雜了QQ
首先我是考慮用遞迴來輸出解，所以對於一個區間$[L,R]$來說，當要 print $[L,R]$ 中的數時，用一個 map 來存這個區間的切的端點是誰，也就是令那個值等於 $mid$ 的話，要先遞迴下去$[L,mid]$輸出，再遞迴下去$[mid+1,R]$輸出。首先觀察出當$a[n]=1$時無解，所以只須考慮$a[n]=0$的情形。注意到因為$1\rightarrow 0=0$，因此可以先讓所有的$0$把他左邊所有的$1$都吃掉，讓整串剩下全部都是$0$。如果只剩一個$0$那就做完了。否則如果剩下的$0$的個數$\geq 3$，那麼就可以把倒數第二和第3個$0$包起來變成$1$，$1$再往左把所有的$0$作用掉，最後再和右邊的$0$作用。至於兩個$0$的情形，如果$a[n-1]=0$，那麼可以推得此時也無解（怎麼消都還是長一樣），所以只須考慮原本的兩個$0$之間有$1$的情形，這時則可以先用$1$把那個$0$消掉，這樣就變成只有一個$0$的情形了。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxn=100000+10 ;
 
map<pii,int> mp ;
int a[maxn] ;
void print(int l,int r)
{
    if(l==r){printf("%d",a[l]) ; return ;}
    int mid=mp[pii(l,r)] ;
    printf("(") ; print(l,mid) ; printf(")") ;
    printf("->") ;
    printf("(") ; print(mid+1,r) ; printf(")") ;
}
 
int pos[maxn] ;
main()
{
    int n,cnt=0 ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) , cnt+=(a[i]==0) ;
    if(a[n]==1){printf("NO\n") ; return 0 ;}
    if(cnt==2 && a[n-1]==0){printf("NO\n") ; return 0 ;}
    printf("YES\n") ;
    if(cnt==2)
    {
        int p=1 ;
        while(a[p]) p++ ;
        for(int i=p+2;i<=n-1;i++) mp[pii(p+1,i)]=i-1 ;
        mp[pii{p,n-1}]=p ;
        mp[pii{p,n}]=n-1 ;
        for(int i=1;i<p;i++) mp[pii{i,n}]=i ;
        print(1,n) ;
    }
    else
    {
        cnt=0 ;
        for(int i=1;i<=n;)
        {
            int j=i ;
            while(a[j]) j++ ; pos[++cnt]=j ;
            for(int k=i;k<j;k++) mp[pii(k,j)]=k ;
            i=j+1 ;
        }
        if(cnt%2==0)
        {
            mp[pii(pos[cnt-3]+1,pos[cnt-1])]=pos[cnt-2] ;
            mp[pii(pos[cnt-4]+1,pos[cnt-1])]=pos[cnt-3] ;
            mp[pii(pos[cnt-4]+1,n)]=pos[cnt-1] ;
            pos[cnt-3]=n ; cnt-=3 ;
        }
        if(cnt==1){print(1,n) ; return 0 ;}
        mp[pii(1,n)]=pos[cnt-1] ;
        for(int i=1;i<=cnt-1;i+=2)
            mp[pii(pos[i-1]+1,pos[i+1])]=pos[i] ,
            mp[pii(pos[i-1]+1,n)]=pos[i+1] ;
        print(1,n) ;
    }
}