http://codeforces.com/contest/1468

H. K and Medians

 

题意:给定 n,kn,k,数列 aa 初始为 1n1-n 的排列,每次操作选择长为 kk 的子序列,除中位数外全部删去,问能否变为给定的数列 bb

思维

考虑最后一次删除,一定是选择以 bib_i 为中位数的某个序列,现在先把这个序列补上去,则 bib_i 左边需要被删除的数的个数为 k2\lfloor\frac{k}{2}\rfloor,右边需要被删除的数的个数为 k2\lfloor\frac{k}{2}\rfloor。现在要看能否从倒数第二次删除前的数列得到最后一次删除前的数列。

假设倒数第二次删除前的数列中在 bib_i 左边的需要被删除的数的个数大于 2×k22\times\lfloor\frac{k}{2}\rfloor,则右边需要被删除的数的个数小于 2×k22\times\lfloor\frac{k}{2}\rfloor,则在倒数第二次删除操作中可以从 bib_i 左边选择一个数作为中位数进行操作。

类似的,可以得到无论倒数第二次删除前的数列是什么样的,都能够操作为最后一次删除前的数列。

所以只需要判断最后一次删除能否做到即可,也就是是否存在一个 bib_i 满足左边需要被删除的数的个数大于等于 k2\lfloor\frac{k}{2}\rfloor,右边需要被删除的数的个数大于等于 k2\lfloor\frac{k}{2}\rfloor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n, k, m;
int b[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &k, &m);
for (int i = 1; i <= n; i++)b[i] = 0;
for (int i = 1; i <= m; i++) {
int x;
scanf("%d", &x);
b[x] = 1;
}
b[n + 1] = 1;
if ((n - m) % (k - 1)) {
puts("NO");
continue;
}
int cnt = 0;
for (int i = 1; i <= n + 1; i++) {
if (!b[i])cnt++;
else {
if (cnt >= k / 2) {
if (n - m - cnt >= k / 2) {
puts("YES");
}
else puts("NO");
break;
}
}
}
}
return 0;
}

 

A. LaIS

 

题意:定义数列 b1,b2,b3,bk1,bkb_1, b_2, b_3 \dots, b_{k - 1}, b_k 几乎递增:min(b1,b2)min(b2,b3)min(bk1,bk)\min(b_1, b_2) \le \min(b_2, b_3) \le \dots \le \min(b_{k - 1}, b_k)。给定数列 aa,问最长的几乎递增的子序列。

dp+树状数组+单调栈

首先能够推出来一个几乎递增的数列满足 bibi1bibi2b_i\ge b_{i-1}||b_i\ge b_{i-2},对于第一个情况可以用与LIS相同的方式求解。

那么接下来只求解第二种情况,还需要注意需要先排除掉第一种情况,所以要变成 bi1>bibi1b_{i-1}>b_{i}\ge b_{i-1}

先对于给定数列 aa 中元素 aia_i,当 aia_i 右边出现一个大于 aia_i 的数,再向右就可以选择 aia_i 作为 bi2b_{i-2} 了,所以需要先处理出每个数右边最近的大于他的数所在位置。这可以通过从右向左遍历并维护单调栈做到。

再从左到右遍历每个数,树状数组查询 dp[a[i]]=maxxaidp[x]+2dp[a[i]]=\max_{x\le a_i} dp[x]+2 进行第二种情况的转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n;
int a[N];
int r[N];
int st[N], tp;
int dp[N], dp2[N];
int mx[N];
void upd(int q, int x) {
for (int i = q; i <= n; i += (i&-i))mx[i] = max(mx[i], x);
}
int qry(int r) {
int ans = 0;
for (int i = r; i; i -= (i&-i))ans = max(ans, mx[i]);
return ans;
}
int mx2[N];
void upd2(int q, int x) {
for (int i = q; i <= n; i += (i&-i))mx2[i] = max(mx2[i], x);
}
int qry2(int r) {
int ans = 0;
for (int i = r; i; i -= (i&-i))ans = max(ans, mx2[i]);
return ans;
}
vector<int>vc[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
tp = 0;
a[n + 1] = INF;
st[++tp] = n + 1;
for (int i = 1; i <= n + 1; i++)vc[i].clear();
for (int i = n; i >= 1; i--) {
while (tp&&a[st[tp]] <= a[i])tp--;
r[i] = st[tp];
vc[r[i]].push_back(i);
st[++tp] = i;
}
fill(mx, mx + n + 1, 0);
fill(mx2, mx2 + n + 1, 0);
fill(dp, dp + n + 1, 0);
fill(dp2, dp2 + n + 1, 0);
for (int i = 1; i <= n; i++) {
dp2[i] = dp[a[i]] = max(dp[a[i]], qry(a[i]) + 1);
if (i > 1)dp2[i] = dp[a[i]] = max(dp2[i], qry2(a[i]) + 2);
upd(a[i], dp[a[i]]);
for (int u : vc[i])upd2(a[u], dp2[u]);
}
int ans = 0;
for (int i = 1; i <= n; i++)ans = max(ans, dp2[i]);
printf("%d\n", ans);
}
return 0;
}