CF1620F

dottle · 2022-08-05 20:01:00 · 题解

考虑怎么样的图是不二分的，那么有一个比较令人注意的情况：3 2 1 这样的一个长为 3 的下降子序列，互相有连边。那么没有长为 3 的下降序列这一条件是必要的，其实这也是充分的，因为根据狄尔沃什这个东西等价于数列可以分为两个上升子序列。上升子序列内部不会有连边，那么就二分了。这样充分和必要就都有了。

然后考虑怎么判断能否划分为两个上升子序列。依次考虑每个数，前面的数构成的子序列只有末尾的两个数是重要的，并且其中有一个要么是 a_{i-1}，要么是 -a_{i-1}，那么我们当然是希望另一个数越小越好。就可以记录 A 为两个子序列其中有一个以 a_{i-1} 结尾时，另一个的最小结尾；B 代表 -a_{i-1}。然后转移就考虑这个数接在哪个子序列后面，贪心地来说我们会接在能接的中较大的那个的后面。然后记一下是从哪里转移来的就可以输出方案了，此部分的细节不再赘述。

时间复杂度 O(n)。

#include<bits/stdc++.h>
#define int long long
const int N=1000050;
using namespace std;

int n,a[N];
int ty[2][N];

int calc(int a,int b,int c){
    if(a>b)swap(a,b);
    if(c>=b)return a;
    if(c>=a)return b;
    return n+1;
}// 结尾为 a 和 b，求出把 c 接上去以后另一段的结尾最小是多少

void print(int k,int p){
    if(p>1)print(ty[k][p],p-1);
    cout<<(k?-a[p]:a[p])<<' ';
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int A=-n,B=-n;
    for(int i=2;i<=n;i++){
        int x=A,y=B;
        if(calc(x,a[i-1],a[i])<calc(y,-a[i-1],a[i]))
            A=calc(x,a[i-1],a[i]),ty[0][i]=0;
        else 
            A=calc(y,-a[i-1],a[i]),ty[0][i]=1;
        if(calc(x,a[i-1],-a[i])<calc(y,-a[i-1],-a[i]))
            B=calc(x,a[i-1],-a[i]),ty[1][i]=0;
        else 
            B=calc(y,-a[i-1],-a[i]),ty[1][i]=1;
    }
    if(min(A,B)==n+1){
        cout<<"NO"<<endl;
        return;
    }
    else cout<<"YES"<<endl;
    if(A!=n+1)print(0,n);
    else print(1,n); 
    cout<<endl;
}

main(){
    ios::sync_with_stdio(false);
    int _T=1;cin>>_T;
    while(_T--)solve();

}