https://ac.nowcoder.com/acm/contest/4114

题解 https://ac.nowcoder.com/discuss/363557?type=101&order=0&pos=9&page=1

A. 黑色气球

 

题意:有n个气球,矩阵i,j表示第i,j个气球的高度和,求每个气球的高度。

当n=2时,由于答案唯一且高度为正整数,所以高度一定都为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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int maxn = 1e5 + 10;
ll n;
ll sum;
ll a[1010][1010];
int main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%lld", &a[i][j]);
sum += a[i][j];
}
}
if (n == 2) {
printf("1 1\n");
return 0;
}
sum /= (2 * n - 2);
for (int i = 1; i <= n; i++) {
ll tmp = 0;
for (int j = 1; j <= n; j++)tmp += a[i][j];
printf("%lld%s", (tmp - sum) / (n - 2), i == n ? "\n" : " ");
}
return 0;
}

 

C. 无向图定向

 

题意:有一个无向图,给每条边定向,使得最长路最短,输出最长路长度。

染色问题

对所有独立集染色,最终相同颜色的点之间一定没有连边,不同颜色的点集之间一定存在连边。

缩点后变为了完全图,完全图定向使得最长路最短的结论就是结点数-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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int maxn = 1e6 + 10;
int n, m;
vector<int>G[maxn];
int ans = INF;
int col[maxn];
bool check(int u, int c) {
for (int v : G[u]) {
if (col[v] == c)return false;
}
return true;
}
void dfs(int u, int c) {
if (c >= ans)return;
if (u > n) {
ans = min(ans, c);
return;
}
for (int i = 1; i <= c; i++) {
if (check(u, i)) {
col[u] = i;
dfs(u + 1, c);
col[u] = 0;
}
}
col[u] = c + 1;
dfs(u + 1, c + 1);
col[u] = 0;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
cout << ans - 1 << endl;
return 0;
}

 

E. 棋技哥

 

题意:一个棋盘,每个格子初始有给定黑色或白色。两个人轮流操作,每个人选择一个格子并翻动该格子与棋盘左上角形成的矩形中所有格子。现在两人都想让先手的那个人获胜,问是否能达到目的。

每次翻动一定会翻左上角那个格子。若左上角能获胜,则其它格子一定可以通过某种方式翻好(从最外侧不断向内缩小没翻好的范围即可),只是时间问题。但左上角属性是确定的,改不了,所以只要判断左上角。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int maxn = 1e5 + 10;
char a[1000][1000];
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)scanf(" %c", &a[i][j]);
}
if (a[0][0] == '0')puts("aoligei");
else puts("call");
}
return 0;
}

 

G. 火山哥周游世界

 

题意:给定一棵边带权树,以及 K 个点,求从树上每个点遍历所有这 K 个点的最小花费。

树形dp

两个数组,存从一个点向下遍历最小花费和向外遍历最小花费。

最终一定是停在K个点中最远的那个不回来了,所以还要存最远的那个点到这个点的距离。

向外遍历也是类似。

详见大佬博客,讲得很详细。

https://blog.csdn.net/qq_43804974/article/details/104071065

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int maxn = 1e6 + 10;
int n, K;
bool key[maxn];
struct E
{
int v;
ll w;
};
vector<E>G[maxn];
struct nd
{
ll val, maxl;
bool judge;
}f[maxn],g[maxn];
int fa[maxn];
ll vv[maxn];
void dfs1(int u, int _fa) {
fa[u] = _fa;
if (key[u])f[u].judge = true;
ll nval = 0, nmaxl = 0;
for (E e : G[u]) {
int v = e.v; ll w = e.w;
if (v == _fa) {
vv[u] = w;
continue;
}
dfs1(v, u);
f[u].judge |= f[v].judge;
if (f[v].judge) {
nval += f[v].val + f[v].maxl + 2 * w;
nmaxl = max(nmaxl, f[v].maxl + w);
}
}
f[u].maxl = nmaxl;
f[u].val = nval - nmaxl;
}
void dfs2(int u, int _fa) {
if (key[u])g[u].judge = true;
ll nval = 0, nmaxl = 0;
for (E e : G[_fa]) {
int v = e.v; ll w = e.w;
if (v == u || v == fa[_fa] || !f[v].judge)continue;
g[u].judge = true;
nval += f[v].val + f[v].maxl + 2 * w;
nmaxl = max(nmaxl, f[v].maxl + w + vv[u]);
}
if (g[_fa].judge) {
g[u].judge = true;
nval += g[_fa].val + g[_fa].maxl + 2 * vv[u];
nmaxl = max(nmaxl, g[_fa].maxl + vv[u]);
}
g[u].maxl = nmaxl;
g[u].val = nval - nmaxl;
for (E e : G[u]) {
if (e.v == _fa)continue;
dfs2(e.v, u);
}
}
int main() {
scanf("%d%d", &n, &K);
for (int i = 1; i < n; i++) {
int u, v; ll w;
scanf("%d%d%lld", &u, &v, &w);
G[u].push_back(E{ v,w });
G[v].push_back(E{ u,w });
}
for (int i = 0; i < K; i++) {
int x;
scanf("%d", &x);
key[x] = true;
}
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; i++) {
printf("%lld\n", f[i].val + g[i].val + min(f[i].maxl, g[i].maxl));
}
return 0;
}