中下

$\text{score：24 + 40 + 0 = 64 rk：23/34}$

Problem A：Mythological V

题目描述

小S打算送给小M一棵 $n$ 个点的圣诞树，点从 $1$ 到 $n$ 标号，他打算给树上挂上 $m$ 个礼物，每个礼物在树上的某个点上，礼物可以重叠。

小M给了小S $q$ 个限制，其中第 $i$ 个形如“第 $a_i$ 个礼物和第 $b_i$ 个礼物在树上的最短路径经过了点 $c_i$”。

小S想要构造出符合小M条件的挂礼物方案。可怜的小S当然不会啦，所以他向你求助。

数据范围

对 $100\%$ 的数据，$n, m \le 250, ~ q \le 5 \times 10^4$

题解

好久没写过 $2-SAT$ 了

虽然我的暴力虽然 $\text{WA}$ 了但竟然没有 $\text{T}$？说不定改对了能过呢

考虑两个礼物 $a, b$ 放置位置经过 $c$ 代表着什么，说明 $a, b$ 放置的位置在以 $c$ 为根的树上位于不同的 $c$ 儿子的子树上

那么现在以 $1$ 为根，设 $g_{i, j, 0}$ 表示第 $j$ 个礼物不在 $i$ 点的子树上，而 $g_{i, j, 1}$ 表示在

对每个题目所给限制，连边有 $g_{c, a, 0} \rightarrow g_{c, b, 1}$（表示 $a$ 在 $c$ 祖先不包括 $c$ 的子树中，那么 $b$ 一定在 $c$ 子树中）、$g_{i, a, 1} \rightarrow g_{i, b, 0}$、$g_{i, b, 1} \rightarrow g_{i, a, 0}$（其中 $i$ 表示 $c$ 的儿子结点）

当然还有最基本的限制，对某个节点 $u$ 以及某个礼物 $i$，$g_{1, i, 0} \rightarrow g_{1, i, 1}$（强制要求 $i$ 在 $1$ 的子树中）、$g_{u, i, 1} \rightarrow g_{fa_u, i, 1}$、$g_{u, i, 0} \rightarrow g_{son_u, i, 0}$、$g_{u, i, 1} \rightarrow g_{v, i, 0}$（其中 $u, v$ 的两个子树无交集）

时间复杂度 $O (N + M) = O (n^2m + qn^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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN = 250 + 10;
const int MAXM = 250 + 10;
const int MAXK = MAXN * MAXN * 2;
const int MAXL = 3e07;

struct LFS { int to, next; } ;
LFS Link[MAXL];
int Head[MAXK]= {0}, size = 0;
void Insert (int u, int v) {
	Link[++ size].to = v;
	Link[size].next = Head[u];

	Head[u] = size;
}

vector<int> G[MAXN];
int father[MAXN]= {0}, depth[MAXN]= {0};
void DFS (int root, int fa) {
	father[root] = fa;
	for (int i = 0; i < (int) G[root].size(); i ++) {
		int v = G[root][i];
		if (v == fa) continue;
		depth[v] = depth[root] + 1;
		DFS (v, root);
	}
}
bool isanc (int y, int x) {
	if (! x) return false;
	return x == y ? true : isanc (y, father[x]);
}

int N, M, Q;
int g[MAXN][MAXN][2]= {0}, m = 0;

int dfn[MAXK]= {0}, low[MAXK]= {0}, ord = 0;
int stack[MAXK]= {0}, top = 0;
bool insta[MAXK]= {false};
int bel[MAXK]= {0}, co = 0;
void Tarjan (int u) {
	dfn[u] = low[u] = ++ ord;
	stack[++ top] = u; insta[u] = true;
	for (int i = Head[u]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (! dfn[v]) {
			Tarjan (v);
			low[u] = min (low[u], low[v]);
		}
		else if (insta[v]) low[u] = min (low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		co ++; int x;
		do {
			x = stack[top --];
			insta[x] = false, bel[x] = co;
		} while (x != u);
	}
}

int ans[MAXN]= {0};

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), M = getnum (), Q = getnum ();
	for (int i = 1; i < N; i ++) {
		int u = getnum (), v = getnum ();
		G[u].push_back(v); G[v].push_back(u);
	}
	depth[1] = 1, DFS (1, 0);
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++)
			g[i][j][1] = ++ m, g[i][j][0] = ++ m;
	for (int i = 1; i <= Q; i ++) {
		int a = getnum (), b = getnum (), u = getnum ();
		if (father[u]) { Insert (g[u][a][0], g[u][b][1]); Insert (g[u][b][0], g[u][a][1]); }
		for (int j = 0; j < (int) G[u].size(); j ++) {
			int v = G[u][j];
			if (v != father[u]) {
				Insert (g[v][a][1], g[v][b][0]);
				Insert (g[v][b][1], g[v][a][0]);
			}
		}
	}
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++) {
			if (father[i]) Insert (g[i][j][1], g[father[i]][j][1]);
			for (int k = 0; k < (int) G[i].size(); k ++)
				if (G[i][k] != father[i])
					Insert (g[i][j][0], g[G[i][k]][j][0]);
		}
	for (int i = 1; i <= M; i ++) Insert (g[1][i][0], g[1][i][1]);
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= N; j ++)
			if (! isanc (i, j) && ! isanc (j, i))
				for (int k = 1; k <= M; k ++)
					Insert (g[i][k][1], g[j][k][0]);
	for (int i = 1; i <= m; i ++)
		if (! dfn[i])
			Tarjan (i);
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++)
			if (bel[g[i][j][1]] < bel[g[i][j][0]])
				ans[j] = depth[ans[j]] < depth[i] ? i : ans[j];
	for (int i = 1; i <= M; i ++) {
		if (i > 1) putchar (' ');
		printf ("%d", ans[i]);
	} puts ("");

	return 0;
}

Problem B：Mythological IV

Problem C：Mythological VII

题目描述

数轴上有一行 $n$ 个点，每个点有权值。小M和小S在上面玩游戏。

小M和小S一开始都在第 $k$ 号点上，小M只能向左移动，小S只能向右移动。

令 $p_x$ 表示当前时刻小M的位置，$p_y$ 表示当前时刻小S的位置，要求任意时刻都满足 $(p_x, p_y]$ 这个区间的所有数和都 $\le 0$。

现在，小M想要知道 $p_x, p_y$ 能否同时等于 $1, n$。可怜的小M当然不会啦，所以她向你求助。

数据范围

对 $100\%$ 的数据，$1 \le n \le 10^5, ~ T \le 20, ~ a_i \in [- 10^{13}, 10^{13}]$

题解

题目是要满足前缀和 $sum_l \ge sum_r$

与 「JOISC 2017 Day 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;

const int INF = 1e09;

int T, N, K;
LL a[MAXN];

bool solve () {
	if (a[1] < a[N]) return false;
	int l = K, r = K, ll = K, lr = K;
	for (int i = l; i >= 1; i --)
		if (a[i] >= a[ll])
			ll = i;
	for (int i = r; i <= N; i ++)
		if (a[i] <= a[lr])
			lr = i;
	while (l != ll || r != lr) {
		int pl, pr; bool suc = false;
		for (pl = l; pl > ll; ) {
			if (a[pl - 1] < a[r]) break;
			if (a[-- pl] >= a[l]) break;
		}
		if (pl < l && a[pl] >= a[l]) { l = pl; suc = true; }
		for (pr = r; pr < lr; ) {
			if (a[pr + 1] > a[l]) break;
			if (a[++ pr] <= a[r]) break;
		}
		if (pr > r && a[pr] <= a[r]) { r = pr; suc = true; }
		if (! suc) return false;
	}
	l = 1, r = N;
	while (l != ll || r != lr) {
		int pl, pr; bool suc = false;
		for (pl = l; pl < ll; ) {
			if (a[pl + 1] < a[r]) break;
			if (a[++ pl] >= a[l]) break;
		}
		if (pl > l && a[pl] >= a[l]) { l = pl; suc = true; }
		for (pr = r; pr > lr; ) {
			if (a[pr - 1] > a[l]) break;
			if (a[-- pr] <= a[r]) break;
		}
		if (pr < r && a[pr] <= a[r]) { r = pr; suc = true; }
		if (! suc) return false;
	}
	return true;
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	bool isneg = false;
	while (! isdigit (ch)) {
		if (ch == '-') isneg = true;
		ch = getchar ();
	}
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return isneg ? - num : num;
}

int main () {
	T = getnum ();
	for (int Case = 1; Case <= T; Case ++) {
		N = getnum (), K = getnum ();
		for (int i = 1; i <= N; i ++) a[i] = getnum ();
		for (int i = 2; i <= N; i ++) a[i] += a[i - 1];
		solve () ? puts ("Yes") : puts ("No");
	}

	return 0;
}