2019-2020 XX Open Cup Grand Prix of Korea 虚拟参赛 暨 补题

 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

const int maxn = 510;

int n, m, ans = 0;
char str[maxn][maxn];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%s", str[i] + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int ii = n - i + 1, jj = m - j + 1;
			int a = str[i][j] - '0', b = str[ii][jj] - '0';
			if (i == ii && j == jj) {
				if (a != 8) {
					ans = -1;
					break;
				}
			}
			else {
				if (a == 6) {
					if (b == 6)
						ans++;
					else if (b != 9) {
						ans = -1;
						break;
					}
				}
				else if (a == 9) {
					if (b == 9)
						ans++;
					else if (b != 6) {
						ans = -1;
						break;
					}
				}
				else if (a == 8) {
					if (b != 8) {
						ans = -1;
						break;
					}
				}
				else if (a == 7) {
					if (b != 7) {
						ans = -1;
						break;
					}
					else
						ans++;
				}
			}
		}
		if (ans == -1)
			break;
	}
	if (ans == -1)
		puts("-1");
	else
		printf("%d\n", ans/2);
	return 0;
}

  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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

const int maxn = 3e5+10;
const int P = 1e9+7;

int Plus(LL a, LL b) {
	return a + b >= P ? (a + b) % P : a + b;
}

int Mult(LL a, LL b) {
	return a * b >= P ? a * b % P : a * b;
}

struct SegmentTreeNode {
	int l, r, mid, pk, b;
} tree[maxn << 2];

int n, pw[maxn], G = 1, last_2[maxn], cnt = 0, gid[maxn];
LL pre[maxn];
vector<int> p2;

void Build(int v, int l, int r) {
	tree[v] = SegmentTreeNode{l, r, (l+r)>>1, 0, 0};
	if (l == r)
		return;
	else {
		Build(LCH(v), l, tree[v].mid);
		Build(RCH(v), tree[v].mid+1, tree[v].r);
	}
}

void Init() {
	pw[0] = 1;
	for (int i = 1; i <= n; i++)
		pw[i] = Mult(pw[i-1], 2);
	Build(1, 1, n);
}

void UpdateNode(int v, int pk, int b) {
	tree[v].b = Mult(pw[pk], tree[v].b);
	tree[v].b = Plus(tree[v].b, b);
	tree[v].pk += pk;
}

void Down(int v) {
	UpdateNode(LCH(v), tree[v].pk, tree[v].b);
	UpdateNode(RCH(v), tree[v].pk, tree[v].b);
	tree[v].pk = tree[v].b = 0;
}

void Update(int v, int l, int r, int pk, int b) {
	if (tree[v].l == l && tree[v].r == r)
		UpdateNode(v, pk, b);
	else {
		Down(v);
		if (l > tree[v].mid)
			Update(RCH(v), l, r, pk, b);
		else if (r <= tree[v].mid)
			Update(LCH(v), l, r, pk, b);
		else {
			Update(LCH(v), l, tree[v].mid, pk, b);
			Update(RCH(v), tree[v].mid+1, r, pk, b);
		}
	}
}

int Query(int v, int p, int x) {
	if (tree[v].l == tree[v].r)
		return Plus(Mult(pw[tree[v].pk], x), tree[v].b);
	Down(v);
	if (p > tree[v].mid)
		return Query(RCH(v), p, x);
	else
		return Query(LCH(v), p, x);
}

int main() {
	scanf("%d", &n);
	Init();
	pre[1] = 0;
	last_2[1] = -1;
	for (int i = 1; i <= n; i++) {
		int op;
		scanf("%d", &op);
		if (op == 1){
			int k;
			scanf("%d", &k);
			if (k) {
				Update(1, 1, G++, 0, k);
				pre[G] = pre[G-1] + k;
				last_2[G] = 0;
			}
			else {
				Update(1, 1, G++, 1, 0);
				Update(1, G, G, 1, 1);
				pre[G] = 0;
				last_2[G] = last_2[G-1] ? last_2[G-1] : G;
				gid[G] = cnt++;
				p2.push_back(G);
			}
		}
		else if (op == 2){
			int g, x;
			scanf("%d%d", &g, &x);
			printf("%d\n", Query(1, g+1, x-1));
		}
		//下面写的和狗屎一样丑, 能力有限, 见谅
		else {
			int x;
			scanf("%d", &x);
			int cur = G, res = 1, L = 2, R = G, flag = 1;
			for (int i = p2.size() - 1; ~i; i--) {
				// 等于0也可回溯上一步
				if (x - pre[cur] >= 0) {
					x -= pre[cur];
					if (x & 1) {
						res = p2[i];
						flag = 0;
						break;
					}
					else {
						if (x == 0) {
							cur = last_2[p2[i]];
							i = gid[cur];
						}
						x >>= 1;
						cur = p2[i] - 1;
						R = cur;
					}
				}
				else {
					L = p2[i] + 1, R = cur;
					break;
				}
			}
			if (flag) {
				while (L <= R) {
					int mid = (L + R) >> 1;
					if (x - (pre[cur] - pre[mid-1]) < 0) {
						L = mid + 1;
						res = mid;
					}
					else
						R = mid - 1;
				}
			}
			printf("%d\n", res-1);
		}
	}
	return 0;
}

 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

const int maxn = 1e5+10;
const int maxm = 3e5+10;

int n, m, s, t, vis[maxn];
vector<int> G[maxm], G2[maxm], ans;

struct Edge {
	int u, v, c, flag;
} edges[maxm];

bool cmp( int i, int j) {
	return edges[i].c < edges[j].c;
}

void dfs(int v) {
	vis[v] = 1;
	for (auto i : G2[v]) {
		Edge &e = edges[i];
		e.flag = 1;
		if (!vis[e.u])
			dfs(e.u);
	}
}

bool dfs2(int u) {
	if (u == t)
		return true;
	vis[u] = 2;
	Edge &e = edges[G[u][0]];
	if (vis[e.v] == 2)
		return false;
	ans.push_back(e.c);
	return dfs2(e.v);
}

void Print() {
	for (auto x : ans)
		printf("%d ", x);
	puts("");
}

int main() {
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		edges[i] = Edge{u, v, c, 0};
		G2[v].push_back(i);
	}
	dfs(t);
	for (int i = 1; i <= m; i++) {
		Edge &e = edges[i];
		if (e.flag) {
			G[e.u].push_back(i);
		}
	}
	if (!G[s].size())
		puts("IMPOSSIBLE");
	else {
		for (int i = 1; i <= n; i++)
			sort(G[i].begin(), G[i].end(), cmp);
		if (dfs2(s))
			Print();
		else
			puts("TOO LONG");
	}
	return 0;
}

 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

const int maxn = 2.5e5 + 10;

int n, a[maxn], b[maxn];
LL ans;
vector<int> sa, sb;

LL sol() {
	LL res = 0;
	sa.clear();
	sb.clear();
	for (int i = 1; i <= n; i++) {
		if (a[i])
			sa.push_back(i);
		if (b[i])
			sb.push_back(i);
	}
	for (int i = 0; i < sa.size(); i++)
		res += llabs(sa[i] - sb[i]);
	return res;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	for (int i = 1; i <= n; i++)
		scanf("%d", b + i);
	if ((n&1) == 0) {
		for (int i = 1; i <= n; i++) {
			a[i] = (a[i] > n/2);
			b[i] = (b[i] <= n/2);
		}
		ans = sol();
	}
	else {
		int pa = -1, pb = -1;
		for (int i = 1; i <= n; i++) {
			if (a[i] == n/2 + 1)
				pa = i;
			if (b[i] == n/2 + 1)
				pb = i;
			a[i] = a[i] > n/2 + 1;
			b[i] = b[i] <= n/2;
		}
		a[pa] = 1, b[pb] = 1;
		ans = sol();
		a[pa] = 0, b[pb] = 0;
		ans = min(ans, sol());
	}
	printf("%lld\n", ans);
	return 0;
}

 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

const int maxn = 2.5e5+10;

struct Segment {
	int l, r, w;
	bool operator < (const Segment &S) const {
		return l == S.l ? r > S.r : l < S.l;
	}
} segments[maxn];

int n;

vector<int> son[maxn];
vector<int> stk;

void Build() {
	stk.push_back(0);
	for (int i = 1; i <= n; i++) {
		Segment &s = segments[i];
		int fa = stk.back();
		while (!(segments[fa].l <= s.l && s.r <= segments[fa].r)) {
			stk.pop_back();
			fa = stk.back();
		}
		son[fa].push_back(i);
		stk.push_back(i);
	}
#ifdef D
	printf("Tree:\n");
	for (int i = 0; i <= n; i++) {
		printf("%d:\n", i);
		for (auto v : son[i])
			printf("%d ", v);
		puts("");
	}
#endif
}

MaxHeap heap[maxn];
int idx = 0;

// 启发式合并
int Merge(int x, int y) {
	vector<LL> pool;
	if (heap[x].size() > heap[y].size())
		swap(x, y);
	while (!heap[x].empty()) {
		pool.push_back(heap[x].top() + heap[y].top());
		heap[x].pop(), heap[y].pop();
	}
	for (auto t : pool)
		heap[y].push(t);
	return y;
}

// 返回的是当前点的堆(的下标)
int dfs(int u) {
	if (!son[u].size()) {
		heap[++idx].push(segments[u].w);
		return idx;
	}
	int cur = dfs(son[u][0]);
	for (int i = 1; i < son[u].size(); i++) {
		int p = dfs(son[u][i]);
		cur = Merge(cur, p);
	}
	heap[cur].push(segments[u].w);
	return cur;
}

int main() {
	scanf("%d", &n);
	segments[0] = Segment{1, 1000000, 0};
	for (int i = 1; i <= n; i++) {
		int l, r, w;
		scanf("%d%d%d", &l, &r, &w);
		segments[i] = Segment{l, r, w};
	}
	sort(segments, segments + n + 1);
	Build();
	int p = dfs(0);
	LL ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!heap[p].empty()) {
			ans += heap[p].top();
			heap[p].pop();
		}
		printf("%lld ", ans);
	}
	return 0;
}

  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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;

const int maxn = 2.5e5+10;

struct HeapTwo {
	PLI val[2];
	void Reset() {
		val[0] = val[1] = make_pair(INF, -1);
	}
	void Push(PLI x) {
		if (x < val[0])
			val[1] = val[0], val[0] = x;
		else if (x < val[1])
			val[1] = x;
	}
	LL Top(int u) {
		return val[u == val[0].second].first;
	}
} heap[maxn];

int n, size[maxn], vis[maxn];
vector<PIL> T[2][maxn], descendant, anscentant[maxn];

LL ans[maxn];

// 维护size用来点分, 同时记录点到根的距离.
void dfs(int k, int u, int f, LL dis) {
	size[u] = 1;
	descendant.emplace_back(u, dis);
	for (auto e : T[k][u]) {
		int v = e.first;
		LL w = e.second;
		if (v != f && !vis[v]) {
			dfs(k, v, u, dis + w);
			size[u] += size[v];
		}
	}
}

int Center(int k, int u) {
	// 每一次求重心的时候, 要重新求子代, 注意清空
	descendant.clear();
	dfs(k, u, 0, 0);
	int tot_size = descendant.size();
	for (auto des : descendant) {
		int is_center = 1;
		int x = des.first;
		for (auto e : T[k][x]) {
			int v = e.first;
			if (vis[v])
				continue;
			// size[x] > size[v] == v 是 x 的儿子
			if (size[x] > size[v] && (size[v] << 1) > tot_size) {
				is_center = 0;
				break;
			}
			// size[x] < size[v] == v 是 x 的父亲
			if (size[x] < size[v] && ((tot_size - size[x]) << 1) > tot_size) {
				is_center = 0;
				break;
			}
		}
		if (is_center) {
			// 找到重心, 需要以重心为根, 求一下子代到根(这个祖先)的距离
			descendant.clear();
			dfs(k, x, 0, 0);
			return x;
		}
	}
	return -1;
}

void Decomp0(int k, int u) {
	int c = Center(k, u);
	for (auto des : descendant)
		// c 为所有子代的一个祖先
		anscentant[des.first].emplace_back(c, des.second);
	// 删除c, 做剩下的森林
	vis[c] = 1;
	for (auto e : T[k][c]) {
		int v = e.first;
		if (!vis[v])
			Decomp0(k, v);
	}
	// 深搜, 可回溯, 节省空间(虽然不是很必要)
	vis[c] = 0;
}

void Decomp1(int k, int u) {
	int c = Center(k, u);
	// 先初始化堆
	for (auto des : descendant) {
		int v = des.first;
		for (auto ansc : anscentant[v]) {
			int a1 = ansc.first;
			heap[a1].Reset();
		}
	}
	// 对所有(L1, L2), 把所有 dist(T1, c, v) + dist(T2, a, v) 压入堆
	// 得到每个(L1, L2)的最小值和次小值
	for (auto des : descendant) {
		int v = des.first;
		LL dis2 = des.second;
		for (auto ansc : anscentant[v]) {
			int a1 = ansc.first;
			LL dis1 = ansc.second;
			heap[a1].Push(make_pair(dis1 + dis2, v));
		}
	}
	// 更新答案
	for (auto des : descendant) {
		int v = des.first;
		LL dis1 = des.second;
		for (auto ansc : anscentant[v]) {
			int a1 = ansc.first;
			LL dis2 = ansc.second;
			ans[v] = min(ans[v], dis1 + dis2 + heap[a1].Top(v));
		}
	}
	// 继续点分
	vis[c] = 1;
	for (auto e : T[k][c]) {
		int v = e.first;
		if (!vis[v])
			Decomp1(k, v);
	}
	vis[c] = 0;
}

int main() {
	scanf("%d", &n);
	for (int k = 0; k < 2; k++)
		for (int i = 1; i < n; i++) {
			int u, v;
			LL w;
			scanf("%d%d%lld", &u, &v, &w);
			T[k][u].emplace_back(v, w);
			T[k][v].emplace_back(u, w);
		}
	Decomp0(0, 1);
	for (int i = 1; i <= n; i++)
		ans[i] = INF;
	Decomp1(1, 1);
	for (int i = 1; i <= n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}