Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

水题笔记 TJU ACM 2020第一学期 作业6 [杂题]

Posted on Edited on In

有那么几个题挺有意思的 记录一下

题目

VOJ

D - Fix Wiring

题意: 给\(n \le 100\)个点, \(\frac{n(n - 1)}{2}\)条边, 和他们的边权, 让你来连边, 求最小和最大的最小生成树权值

最小的显然, 让我们看最大的

考虑这个题和这个非常像, 考虑目前已经选出一颗最小生成树, 新加入一个点和与他相连的边, 你要让一条边成为最小生成树中的边, 就要让他与最小生成树中点的边权都大于这条边

于是我们只需要把边权从大到小排序, 然后按照\(n - 1, n - 2, \cdots, 1\)的个数分组, 每组找最小值作为最小生成树的边就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN (100)
#define LL long long
using namespace std;
int n, a[MAXN * MAXN + 5];
LL ans;
bool cmp(int x, int y) { return x > y; }
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= (n - 1) * n / 2; i++) scanf("%d", &a[++a[0]]);
	sort(a + 1, a + a[0] + 1, cmp);
	for (int i = a[0]; i >= a[0] - n + 2; i--) ans += a[i];
	printf("%lld ", ans);
	ans = 0;
	for (int i = n - 1, j = 0; i >= 1; i--)
		ans += a[j += i];
	printf("%lld", ans);
	return 0;
}

P - 加工零件

1号要做原料当且仅当a与1的距离的奇偶性与L相同, 且小于L

dijkstra跑一跑就好了

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000)
#define pii pair<int, int>
using namespace std;
struct edg {
	int from, to, next;
} b[MAXN * 2 + 5];
struct cmp {
	bool operator () (const pii& x, const pii& y) {
		return x.second > y.second;
	}
};
int g[MAXN + 5], cntb, n, m, dis[MAXN][2], q;
bool vis[MAXN + 5][2];
void ade(int fr, int t) {
	b[++cntb] = {fr, t, g[fr]};
	g[fr] = cntb;
}
void dijk() {
	priority_queue<pii, vector<pii>, cmp> q;
	q.push(make_pair(1, 0));
	memset(dis, 0x7f, sizeof(dis));
	memset(vis, false, sizeof(vis));
	dis[1][0] = 0;
	while (!q.empty()) {
		pii now = q.top();
		q.pop();
		if (vis[now.first][now.second & 1]) continue;
		vis[now.first][now.second & 1] = true;
		for (int i = g[now.first]; i; i = b[i].next)
			if (dis[b[i].to][(now.second & 1) ^ 1] > now.second + 1)
				dis[b[i].to][(now.second & 1) ^ 1] = now.second + 1, q.push(make_pair(b[i].to, dis[b[i].to][(now.second & 1) ^ 1]));
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1, xi, yi; i <= m; i++) scanf("%d%d", &xi, &yi), ade(xi, yi), ade(yi, xi);
	dijk();
	for (int i = 1, a, l; i <= q; i++)
		scanf("%d%d", &a, &l), puts((dis[a][l & 1] <= l) ? "Yes" : "No");
	return 0;
}

R - 括号树

显然这个树的条件屁用没有

考虑链上咋做, 令f[n]为以n为结尾的合法括号串个数, 显然f[n] = (s[n - 1] == ')') ? (f[x] + 1) : 0, 其中x是n前面与n最近的使[x, n]是合法括号串的数

我一直在考虑怎么转换成\((1, -1)\)序列来做, 似乎得用线段树之类的

后来抄题解才知道直接用栈就行了, 左括号入栈其编号就行, 右括号出栈栈顶就是x了

我是傻逼

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
// 前括号压栈, 后括号弹栈

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define LL long long
#define MAXN (500000)
using namespace std;
struct edg {
	int from, to, next;
} b[MAXN + 5];
int g[MAXN + 5], cntb, n, a[MAXN + 5], fa[MAXN + 5];
bool vis[MAXN + 5];
char s[MAXN + 5];
LL f[MAXN + 5], ans;
stack<int> gary, pek;
void ade(int fr, int t) {
	b[++cntb] = {fr, t, g[fr]};
	g[fr] = cntb;
}
void dfs(int now) {
	if (~a[now]) gary.push(now);
	else if (!gary.empty()) {
		vis[now] = true;
		pek.push(gary.top());
		f[now] = f[fa[gary.top()]] + 1;
		gary.pop();
	}
	for (int i = g[now]; i; i = b[i].next)
		dfs(b[i].to);
	if (~a[now]) gary.pop();
	if (vis[now]) gary.push(pek.top()), pek.pop();
}
void calc(int now, LL xans) {
	ans ^= (xans + f[now]) * now;
	for (int i = g[now]; i; i = b[i].next)
		calc(b[i].to, xans + f[now]);
}
int main() {
	memset(vis, false, sizeof(vis));
	scanf("%d", &n);
	scanf("%s", s);
	for (int i = 1; i <= n; i++) a[i] = (s[i - 1] == '(') ? 1 : -1;
	for (int i = 2; i <= n; i++) scanf("%d", &fa[i]), ade(fa[i], i);
	dfs(1);
	calc(1, 0ll);
	printf("%lld", ans);
	return 0;
}

By Cansult