寒鸽儿のBlog

题面及数据范围

The Olympic Games will be held in JOI Kingdom soon. In order to welcome participants from all over the world, the buildings on the way from the airport to the accommodation will be decorated. There are $2N$ buildings, numbered from $1$ to $2N$ from the airport.
President K is in charge of the decoration project. He asked the public to make decoration plans. After examining them, he finally chose two plans, the plan A and the plan B. In the plan A, the luxury level of the building $i$ ($1 \leqslant i \leqslant 2N$) is $A_i$. In the plan B, the luxury level of the building $i$ ($1 \leqslant i \leqslant 2N$) is $B_i$.
Both plans are very good, and it is difficult to choose one of them. He decided to decorate the buildings in the following way: for each building, one of the plan A or B will be chosen. In order to decorate the buildings in a fair way, the plan A will be chosen for N buildings, and the plan B will be chosen for the remaining N buildings.
Moreover, since the participants will be excited if the luxury levels are increasing on the way from the airport to the accommodation, the following condition should be satisfied: $C_i \leqslant C_{i+1}$for every $i$ with $1 \leqslant i \leqslant 2N - 1$, where $C_i$ is the luxury level of the building $i$ ($1 \leqslant i \leqslant 2N$).
Write a program which, given the number of buildings and the luxury levels of the buildings for each plan, decides whether it is possible to choose decoration plans satisfying the above condition, and output one way to decorate the buildings if it is possible.
$1 \leqslant N \leqslant 500 000$
$1 \leqslant A_i, B_i \leqslant 1 000 000 000 (1 \leqslant i \leqslant 2N)$

思路

首先来考虑暴力, 记$f_{i,j,0|1}$为前$i$个数中选$j$个数, 第$j$个数选$A|B$的合法性。是$\mathcal{O(n^2)}$的。
然后考虑性质, 我们可以输出暴力dp的表格, 发现对于所有的位置$i$, $f_{i, j, 0|1}$合法的$j$是连续的, 本着大胆猜想不用求证的精神(我太菜了不会证), 我们认为合法区间就是连续的, 因此我们可以考虑求第$i$位置选择$A|B$时选$A$的个数区间的两个边界(即最多和最少)。求区间$f_{i, 0|1}$的dp显然是$\mathcal{O(n)}$。那么由于合法值域的连续性, 只要选$A$序列的个数区间包含$n$, 就表示有合法的解。
然后来考虑如何构造解, 上述性质显然适用于子问题, 记录已选值的个数, 将其与可选值的范围叠加, 只要满足区间覆盖$n$即可。

代码

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long ll;

const int maxn = 1234567, inf = 0x3f3f3f3f;

int a[maxn], b[maxn];
int dp[maxn][2][2];
char ans[maxn];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, cnt0 = 0, cnt1 = 0, lst = INT_MAX;
	cin >> n;
	n <<= 1;
	for(int i = 0; i < n; ++i) cin >> a[i];
	for(int i = 0; i < n; ++i) cin >> b[i];
	dp[0][0][0] = dp[0][0][1] = 1;
	dp[0][1][0] = dp[0][1][1] = 0;
	for(int i = 1; i < n; ++i) {
		dp[i][0][0] = dp[i][1][0] = inf;
		dp[i][0][1] = dp[i][1][1] = 0;
		if(a[i] >= a[i-1]) dp[i][0][0] = dp[i-1][0][0] + 1, dp[i][0][1] = dp[i-1][0][1] + 1;
		if(b[i] >= a[i-1]) dp[i][1][0] = min(dp[i][1][0], dp[i-1][0][0]), dp[i][1][1] = max(dp[i][1][1], dp[i-1][0][1]);
		if(a[i] >= b[i-1]) dp[i][0][0] = min(dp[i][0][0], dp[i-1][1][0] + 1), dp[i][0][1] = max(dp[i][0][1], dp[i-1][1][1] + 1);
		if(b[i] >= b[i-1]) dp[i][1][0] = min(dp[i][1][0], dp[i-1][1][0]), dp[i][1][1] = max(dp[i][1][1], dp[i-1][1][1]);
	}
	if((dp[n-1][0][1] < dp[n-1][0][0] || dp[n-1][0][1] < (n>>1) || dp[n-1][0][0] > (n>>1)) && (dp[n-1][1][1] < dp[n-1][1][0] || dp[n-1][1][1] < (n>>1) || dp[n-1][1][0] > (n>>1))) {
		cout << "-1\n";
		return 0;
	}
	for(int i = n-1; ~i; --i) {
		if(dp[i][0][0] <= dp[i][0][1] && cnt0 + dp[i][0][1] >= (n>>1) && cnt1 + (i+1-dp[i][0][0]) >= (n>>1) && a[i] <= lst) {
			ans[i] = 'A'; lst = a[i]; ++cnt0;
		} else {
			ans[i] = 'B'; lst = b[i]; ++cnt1;
		}
	}
	cout << ans << endl;
	return 0;
}