8.28集训

第一题 在一个无向图里面找到一个生成树,使得代价最小

其中代价定义为 每个点的深度h(根节点深度为1)*权值v 切了

但是我想得太复杂,写的时间太长,没给第二题留下充足的时间思考

如果再给我一个小时,我未尝不可把第二题切了

枚举每个节点作为根节点,跑dfs或者bfs都可以

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠!
const int N = 1e5+66;

typedef pair<int, int> pr;

map<pr, bool> yhm_exist;
int to[N << 1], nex[N << 1], head[N << 1], cnt;

inline void add(int x, int y)
{
to[++ cnt] = y;
nex[cnt] = head[x];
head[x] = cnt;
}

int val[N], dep[N], vis[N];

queue <pr> q;

inline int yhm(int now, int FA, int n)
{
memset (dep, 0, sizeof dep);
memset (vis, 0, sizeof vis);
q.push(pr(now, FA)), dep[now] = 1, vis[now] = 1;
int i, x, y, fa, res(0);
while (! q.empty())
{
x = q.front().first, fa = q.front().second; q.pop();
for (i = head[x]; i; i = nex[i])
{
y = to[i];
if (y == fa) continue;
if (! vis[y] || dep[y] > dep[x] + 1)
{
vis[y] = 1;
dep[y] = dep[x] + 1;
q.push(pr(y, x));
}
}
}
for (i = 1; i <= n; ++ i) res += dep[i] * val[i];
return res;
}

inline int thestars()
{
int i, j(0), k, n, m, res(123456789), ans(0);
int x, y;
scanf ("%d%d", &n, &m);
for (i = 1; i <= n; ++ i) scanf ("%d", val + i);
for (i = 1; i <= m; ++ i)
{
scanf ("%d%d", &x, &y);
++ x, ++ y;
if (x > y) swap(x, y);
if (yhm_exist[pr(x, y)]) continue;
add(x, y), add(y, x);
yhm_exist[pr(x, y)] = 1;
}
if (n - 1 > m) {puts("-1"); fclose (stdin), fclose (stdout); return 0;}
for (x = 1; x <= n; ++ x)
{
res = min(res, yhm(x, 0, n));
for (i = 1; i <= n; ++ i) if (! vis[i]) {j = 1; break;}
}
if (j) puts("-1");
else cout << res;
return 0;
}

int youngore = thestars();

signed main() {;}

第二题,给定点,给定每次删点范围,点不可重复删,问每次可以删掉多少点?

数据量十万

mapy[y].erase(x);

mapx.erase(it1, it2);

这两个函数说尽了一切,第一行是在y坐标上删除,第二行是在x坐标上全删除

总结STL是真的niub

学好STL会省很大的劲,pb_ds封装了平衡树…..

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠!
const int N = 1e5+66;

map <int, multiset <int> > mapx, mapy;

inline int thestars()
{
freopen ("city.in", "r", stdin), freopen ("city.out", "w", stdout);
int i, n, m, cnt;
int opt, n1, n2;
scanf ("%d%d", &n, &m);
for (i = 1; i <= n; ++ i)
{
int x, y;
scanf ("%d%d", &x, &y);
mapx[x].insert(y), mapy[y].insert(x);
}
for (i = 1; i <= m; ++ i)
{
scanf ("%d%d%d", &opt, &n1, &n2); cnt = 0;
if (! opt)
{
map <int, multiset <int> > :: iterator it, it1, it2;
it1 = mapx.lower_bound(n1);
it2 = mapx.upper_bound(n2);

for (it = it1; it != it2; ++ it)
{
multiset <int> &myset = (it -> second);
int x = it -> first;
cnt += myset.size();
for (multiset <int> :: iterator it = myset.begin(); it != myset.end(); ++ it)
{
int y = *it;
mapy[y].erase(x);
}
}

mapx.erase(it1, it2);
} else
{
map <int, multiset <int> > :: iterator it, it1, it2;
it1 = mapy.lower_bound(n1);
it2 = mapy.upper_bound(n2);

for (it = it1; it != it2; ++ it)
{
multiset <int> &myset = (it -> second);
int y = it -> first;
cnt += myset.size();
for (multiset <int> :: iterator it = myset.begin(); it != myset.end(); ++ it)
{
int x = *it;
mapx[x].erase(y);
}
}

mapy.erase(it1, it2);
}
cout << cnt << '\n';
}
return 0;
}

int youngore = thestars();

signed main() {;}

第三题

从1开始dfs,因为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
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠!
const int N = 2e6+66, inf = 1e9+7;

vector<int>e[N];
int a[N], cnt, res;
int head[N], rt[N << 2][6];

struct yhm{int ls, rs, sum;} tr[N << 2];

inline void insert(int &o, int l, int r, int p, int w)
{
if (! o) o = ++ cnt;
tr[o].sum = max(tr[o].sum, w);
if (l == r) return;
if (p <= mid) insert(tr[o].ls, l, mid, p, w);
if (p > mid) insert(tr[o].rs, mid + 1, r, p, w);
}

inline int query(int o, int l, int r, int x, int y)
{
int sum(0);
if (! o) return 0;
if (l >= x && r <= y) return tr[o].sum;
if (x <= mid) sum = max(sum, query(tr[o].ls, l, mid, x, y));
if (y > mid) sum = max(sum, query(tr[o].rs, mid + 1, r, x, y));
return sum;
}

inline void merge(int &l, int r)
{
if (! l) {l = r; return;}
if (! r) return;
tr[l].sum = max (tr[l].sum, tr[r].sum);
merge (tr[l].ls, tr[r].ls), merge (tr[l].rs, tr[r].rs);
}

inline void dfs(int x)
{
int dododo(0), kakaka(0), i, y;
insert (rt[x][0], 0, inf, a[x], 1);
insert (rt[x][1], 0, inf, a[x], 1);
for (i = 0; i < e[x].size(); ++ i)
{
y = e[x][i];
dfs(y);
dododo = max (dododo, query (rt[y][0], 0, inf, 0, a[x] - 1));
kakaka = max (kakaka, query (rt[y][1], 0, inf, a[x] + 1, inf));
merge (rt[x][0], rt[y][0]);
merge (rt[x][1], rt[y][1]);
}
insert (rt[x][0], 0, inf, a[x], dododo + 1);
insert (rt[x][1], 0, inf, a[x], kakaka + 1);
res = max (res, dododo + kakaka + 1);
}

inline int thestars()
{
int i, n, fx;
scanf ("%d", &n);
for (i = 1; i <= n; ++ i)
{
scanf ("%d%d", &a[i], &fx);
if (fx) e[fx].push_back(i);
}
dfs(1);
cout << res;
return 0;
}

int youngore = thestars();

signed main() {;}