JOID1T1 Sol瞎写
皎月半洒花
2020-03-20 23:55:20
想不到吧，我这种老年选手还去打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)$ 。
```cpp
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 ;
}
```