笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

JOID1T1 Sol瞎写

posted on 2020-03-20 23:55:20 | under 题解 |

想不到吧,我这种老年选手还去打JOI(

明天可能会鸽。不得不说JOI的题跟AGC的题画风确实不一样,可能不适合我这种才疏学浅的选手.jpg

然后写一个Sol证明我打过233

T2、3都不会,别骂了别骂了QAQ


题意:给定等长的两个偶长度序列 $A,B$ 。从这两个序列中各挑出一半互不相同的位置组成一个新的序列,使之满足从头到尾单调。

首先一个自然的想法,因为是后面限制前面所以要倒着做。然后就是自然的 $dp$ (你问我为什么这个是自然的,我只能说在尝试暴力/带悔贪心/建图都GG了之后,这个就变成自然的了)。$dp$ 分两部分,一部分用来确定所有状态是否合法,一部分用来最优化可以补上的数值。

那么 $f_{i,0/1}$ 表示 $i$ 个元素,在第 $i$ 个元素填 $0/1$ 的时候是否合法。转移是 general 的。然后考虑根据这个 $dp$,显然可以构造出一种答案,但是这种答案不保证每个都选了 $n$ 个,但是这个答案可以保证每个位置的数都尽量选最小的。在这个答案里,不妨记 $0$ 的个数与 $1$ 的个数的差是 $k$。

然后考虑如何去调整这个序列使之合法。再定义 $dp$ ,$g_{i,0/1}$ 表示当第 $i$ 个位置的状态为 $0/1$ 时,$i\sim n$ 在满足 $1\sim _{i-1}$ 的约束时,这些位置最多可以提供多少差值。

那么考虑根据 $g$ 的定义,最后的答案一定可以转化成改变一个后缀。于是直接去找这个差值即可。复杂度 $O(n)$ 。

using namespace std ;

#define Trump return Output(), 0

const int N = 1000010 ;

int n ;
int cnt ;
int res[N] ;
int ans[N] ;
int f[N][2] ;
int g[N][2] ;
int base[N][2] ;

void Output(){
    for (int i = 1 ; i <= n ; ++ i)
        printf("%c", (char)('A' + ans[i])) ;
}
int getsign(int x){
    return x ? 1 : -1 ;
}
int main(){
    cin >> n ; n *= 2 ;
    for (int i = 0 ; i <= n ; ++ i)
        g[i][0] = g[i][1] = -1000001 ;
    for (int j = 0 ; j < 2 ; ++ j)
        for (int i = 1 ; i <= n ; ++ i)
            scanf("%d", &base[i][j]) ;
    f[n][0] = f[n][1] = 1 ; int p = n - 1 ;
    for (int i = p ; i >= 1 ; -- i)
        for (int j = 0 ; j <= 1 ; ++ j)
            for (int k = 0 ; k <= 1 ; ++ k){
                if (!f[i + 1][k]) continue ;
                if (base[i][j] <= base[i + 1][k])
                    f[i][j] |= f[i + 1][k] ;
            }
    if (!(f[1][1] or f[1][0])) return puts("-1"), 0 ;
    ans[++ cnt] = ((base[1][0] >= base[1][1]) and (f[1][1])) ? 1 : 0 ;
    for (int i = 2 ; i <= n ; ++ i){
        if (base[i][0] < base[i][1]){
            ++ cnt ; int q = cnt - 1 ;
            ans[cnt] = (base[i - 1][ans[q]] > base[i][0]) ? 1 : 0 ;
        }
        else {
            ++ cnt ; int q = cnt - 1 ;
            ans[cnt] = (base[i - 1][ans[q]] > base[i][1]) ? 0 : 1 ;
        }
    }
    //for (int i = 1 ; i <= n ; ++ i) cout << ans[i] << " " ; puts("") ;
    int t = 0, dif = 0 ; g[n][ans[n]] = 0 ;
    for (int i = 1 ; i <= n ; ++ i) t += getsign(ans[i]) ;
    if (!t) Trump ; g[n][!ans[n]] = 2 * getsign(!ans[n]) * getsign(t < 0) ;
    for (int i = p ; i >= 1 ; -- i)
        for (int j = 0 ; j <= 1 ; ++ j){
            dif = (ans[i] ^ j) ? (2 * getsign(!ans[i]) * getsign(t < 0)) : 0 ;
            for (int k = 0 ; k <= 1 ; ++ k){
                if (g[i + 1][k] == -1000001) continue ;
                if (base[i + 1][k] < base[i][j]) continue ;
                if (base[i - 1][ans[i - 1]] > base[i][j]) continue ;
                g[i][j] = max(g[i][j], g[i + 1][k] + dif) ;
            }
        }
    cnt = 0 ; int pq ;
    res[++ cnt] = pq = (bool)(g[1][1] > g[1][0])  ;
    if (max(g[1][0], g[1][1]) < (getsign(t > 0) * t)) return puts("-1"), 0 ;
    for (int i = 1 ; i < n ; ++ i){
        dif = (ans[i] ^ pq) ? (2 * getsign(!ans[i]) * getsign(t < 0)) : 0 ;
        for (int k = 0 ; k <= 1 ; ++ k){
            if (base[i + 1][k] < base[i][pq]) continue ;
            if (g[i + 1][k] + dif == g[i][pq]) { res[++ cnt] = pq = k ; break ; }
        }
    }
    //for (int i = 1 ; i <= n ; ++ i) cout << res[i] << " " ; puts("") ;
    for (int i = 1 ; i <= n ; ++ i)
        if (g[i][res[i]] == (getsign(t > 0) * t)){
            for (int j = i ; j <= n ; ++ j) ans[j] = res[j] ;
            Trump ;
        }
    Trump ;
}