http://codeforces.com/contest/1304

D. Shortest and Longest LIS

 

题意：有一个排列，给出了每个元素与它后面一个元素的大小关系，要求构造出这个序列，满足大小关系且最长上升子序列最大/最小。

构造

考虑如何填小于的位置，要最长，显然是从左到右，从小到大填，然后剩下的位置从从大到小填。

要最短，就从后向前，从小到大填小于号，再从大到小填剩下的。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
int T, n;
char s[N];
int ans1[N], ans2[N];
int main() {
	cin >> T;
	while (T--) {
		scanf("%d%s", &n, s + 1);
		fill(ans1 + 1, ans1 + n + 1, 0);
		fill(ans2 + 1, ans2 + n + 1, 0);
		int cnt = 0;
		for (int i = 1; i < n; i++) {
			if (s[i] == '<')ans2[i] = ++cnt;
		}
		cnt = n;
		for (int i = 1; i <= n; i++)if (!ans2[i])ans2[i] = cnt--;
		cnt = 0;
		for (int i = n - 1; i >= 1; i--) {
			if (s[i] == '<') {
				int j = i;
				while (j > 0 && s[j] == '<')j--;
				j++;
				for (int k = j; k <= i; k++)ans1[k] = ++cnt;
				i = j - 1;
			}
		}
		cnt = n;
		for (int i = 1; i <= n; i++)if (!ans1[i])ans1[i] = cnt--;
		for (int i = 1; i <= n; i++)printf("%d%s", ans1[i], i == n ? "\n" : " ");
		for (int i = 1; i <= n; i++)printf("%d%s", ans2[i], i == n ? "\n" : " ");
	}
	return 0;
}

 

E. 1-Trees and Queries

 

题意：有一棵树，每次询问添加一条边，并询问是否满足a，b点存在距离为k的路径。

由于每条边可以经过多次，所以到终点可以不断加2，因此只要判断是否有奇偶性与k相同的路径即可。

添加了一条边后，可能有三种奇偶性不同的路径：dis(a,b),dis(a,x)+dis(b,y)+1,dis(a,y)+dis(b,x)+1dis(a,b),dis(a,x)+dis(b,y)+1,dis(a,y)+dis(b,x)+1，要考虑四个点的不同位置情况。

接下来对原树处理LCA直接求就好了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
int n, q;
int fa[N], dep[N], topf[N], son[N], clk, siz[N];
vector<int>G[N];
void dfs1(int u, int _fa) {
	siz[u] = 1; fa[u] = _fa;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dep[v] = dep[u] + 1;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]])son[u] = v;
	}
}
void dfs2(int u, int topfa) {
	topf[u] = topfa;
	if (!son[u])return;
	dfs2(son[u], topfa);
	for (int v : G[u]) {
		if (!topf[v])dfs2(v, v);
	}
}
int LCA(int u, int v) {
	while (topf[u] ^ topf[v])
		dep[topf[u]] < dep[topf[v]] ? v = fa[topf[v]] : u = fa[topf[u]];
	return dep[u] < dep[v] ? u : v;
}
int dis(int u, int v) {
	int lca = LCA(u, v);
	return dep[u] - dep[lca] + dep[v] - dep[lca];
}
bool check(int x, int y) {
	return x <= y && (x % 2 == y % 2);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	scanf("%d", &q);
	while (q--) {
		int x, y, a, b, k;
		scanf("%d%d%d%d%d", &x, &y, &a, &b, &k);
		int a1 = dis(a, b), a2 = dis(a, x) + dis(y, b) + 1, a3 = dis(a, y) + dis(x, b) + 1;
		if (check(a1, k) || check(a2, k) || check(a3, k))puts("YES");
		else puts("NO");
	}
	return 0;
}

 

F1. Animal Observation (easy version)

 

题意：n⋅mn\cdot m 的网格，每次从第 ii 行和第 i+1i+1 行选一个高为 22，长为 k,k≤20k,k\leq 20 的矩形，获得其中所有值，但同一个的值不能重复获得，问最终 nn 行最大能得到多少。1≤n≤50,1≤m≤2⋅1041 \le n \le 50,1 \le m \le 2 \cdot 10^4

dp

dp[i][j]dp[i][j] 表示第 i，i+1i，i+1 行，选第 jj 格开始的矩形，共获得的最大值。

则对于不相交的矩形， dp[i][j]=dp[i−1][p]+sum[i,i+1][j,j+k−1]dp[i][j]=dp[i-1][p]+sum[i,i+1][j,j+k-1]。

对于有相交的，还要减去相交部分的面积。

面积用前缀和维护，dp的最大值也用前缀函数维护，先前缀查询不相交的dp最大值，再 O(k)O(k) 查询相交的矩形。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 2e4 + 10;
int n, m, k;
int a[100][N], dp[100][N], sum[100][N], lmx[100][N], rmx[100][N];
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			scanf("%d", &a[i][j]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			sum[i][j] = sum[i][j - 1] + a[i][j];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = lmx[i - 1][max(0, j - k)];
			dp[i][j] = max(dp[i][j], rmx[i - 1][min(m + 1, j + k)]);
			for (int p = max(1, j - k + 1); p <= j; p++) {
				dp[i][j] = max(dp[i][j], dp[i - 1][p] - (sum[i][min(m, p + k - 1)] - sum[i][j - 1]));
			}
			for (int p = j + 1; p <= j + k - 1; p++) {
				dp[i][j] = max(dp[i][j], dp[i - 1][p] - (sum[i][min(m, j + k - 1)] - sum[i][p - 1]));
			}
			dp[i][j] += sum[i][min(m, j + k - 1)] - sum[i][j - 1] + sum[i + 1][min(m, j + k - 1)] - sum[i + 1][j - 1];
		}
		for (int j = 1; j <= m; j++)lmx[i][j] = max(lmx[i][j - 1], dp[i][j]);
		for (int j = m; j >= 1; j--)rmx[i][j] = max(rmx[i][j + 1], dp[i][j]);
	}
	int ans = 0;
	for (int i = 1; i <= m; i++)ans = max(ans, dp[n][i]);
	printf("%d\n", ans);
	return 0;
}

 

F2. Animal Observation (hard version)

 

题意：与上一题相同，但是 kk 的范围变为 1≤k≤m1 \le k \le m。

现在就不能暴力枚举 dp[i−1]dp[i-1] 了，所以要考虑维护dp的最大值，但是有些dp值要减去a值，而有些不用。

但是可以发现每一个a值只会在矩形包含它的时候被减去，之后就永远不会再用到，所以考虑滑动窗口。从 dp[i][1]dp[i][1] 滑到 dp[i][m]dp[i][m]，对比 dp[i][j]dp[i][j] 和 dp[i][j+1]dp[i][j+1] 可以发现，从 jj 变到 j+1j+1 时，包含 jj 的所有矩形的 dp[i−1]dp[i-1] 之前都减去了 a[i][j]a[i][j] ，而现在不用减了，所以要加回来，这是个区间的加；并且由于新增了一格 j+1j+1 ，所以所有包含 j+1j+1 的 dp[i−1]dp[i-1] 都要减去 a[i][j+1]a[i][j+1] ，这又是个区间的减。所以用线段树维护 dp[i−1]dp[i-1] 的最大值，同时在滑动时进行区间加减。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 2e4 + 10;
int n, m, k;
int a[100][N], dp[100][N], sum[100][N];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int tr[N << 2], laz[N << 2];
void down(int rt) {
	int& x = laz[rt];
	if (x) {
		tr[rt << 1] += x;
		tr[rt << 1 | 1] += x;
		laz[rt << 1] += x;
		laz[rt << 1 | 1] += x;
		x = 0;
	}
}
void update(int l, int r, int rt, int ql, int qr, int x) {
	if (ql <= l && qr >= r) {
		tr[rt] += x;
		laz[rt] += x;
		return;
	}
	down(rt);
	if (ql <= mid)update(lson, ql, qr, x);
	if (qr > mid)update(rson, ql, qr, x);
	tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]);
}
int get(int i, int l, int r) {
	return sum[i][r] - sum[i][l - 1];
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			scanf("%d", &a[i][j]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			sum[i][j] = sum[i][j - 1] + a[i][j];
	}
	for (int i = 1; i <= m; i++)dp[1][i] = get(1, i, min(m, i + k - 1)) + get(2, i, min(m, i + k - 1));
	for (int i = 2; i <= n; i++) {
		memset(laz, 0, sizeof(laz));
		memset(tr, 0, sizeof(tr));
		for (int j = 1; j <= m; j++)update(1, m, 1, j, j, dp[i - 1][j]);
		for (int j = 1; j <= k; j++)update(1, m, 1, 1, j, -a[i][j]);
		for (int j = 1; j <= m; j++) {
			dp[i][j] = tr[1] + get(i, j, min(m, j + k - 1)) + get(i + 1, j, min(m, j + k - 1));
			update(1, m, 1, max(1, j - k + 1), j, a[i][j]);
			update(1, m, 1, min(j + 1, m), min(j + k, m), -a[i][j + k]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i++)ans = max(ans, dp[n][i]);
	printf("%d\n", ans);
	return 0;
}