2019.8.3 集训解题报告

今天在讲讲座,讲斜率优化、四边形不等式优化、凸包,还有一大堆东西。

因为就觉得自己目前最重要的不是这些,就回机房做题了,(GD 的省一应该用不到这些 QAQ)


[HAOI2009] 逆序对数列

做了一下以前高中部上课题和作业题,把以前有一道题的笔记订正了,原来是错的,因为数据范围不一样。

这道题还带一个前缀和优化。可以发现,朴素的做法是 $O(nk^2)$ 的,在这道题的数据会超时。然后又会发现,第 3 层循环的作用就是把 $f[i][…]$ 加起来,所以说可以想到前缀和的做法。详情见题解

还有,记得要取模!

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e3+5;
const int Mod = 1e4;
int n, k, f[MAXN][MAXN];

int main() {
scanf ("%d%d",&n,&k);

f[1][0]=1;

for (int i=2; i<=n; i++) {
int sum = 0;
for (int j=0; j<=k; j++) {
sum += f[i-1][j];
sum %= Mod;
f[i][j]=sum;
if ( j-i+1 >= 0 ) {
sum = ( sum-f[i-1][j-i+1]+Mod )%Mod;
}
}
}

printf ("%d\n",f[n][k]);
return 0;
}

[HNOI] 消防局的设立

洛谷下不了数据,还是 $LOJ$ 好 qwq

这道题有两种做法,我自己第一次想觉得是贪心 + $dfs$ 。不过这道题在试炼场中被归为“动态规划”,然鹅我菜的并不知道怎么在“图”中进行 $dp$ 。题解第一篇就是贪心,才 21 行,但是我还是忍住去写 $dp$ 了。

其实这种 ”图“ 中 $dp$ ,就是树形 $dp$ ,之前没有打过。就看了题解 qwq

设计状态:$f[i][j]$,其中 $i$ 表示当前节点,$j$ 的范围是 0~4,分别表示:

$f[i][0]$:当前点作为消防站,需要的最小站点数

$f[i][1]$:儿子节点作为消防站,需要的最小站点数

$f[i][2]$:孙子节点作为消防站,需要的最小站点数

$f[i][3]$:儿子节点被覆盖,需要的最小站点数

$f[i][4]$:孙子节点被覆盖,需要的最小站点数

至于转移方程,我懒得写了,放个题解链接在这里当做标记。

$Code$

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1005;
const int INF = 2e9;

struct Node {
int next, v;
}edge[MAXN];

int f[MAXN][5], n, cnt, head[MAXN];

inline void AddEdge (int u, int v) {
cnt++;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt;
return;
}

void dfs (int x) {
f[x][0]=1;
f[x][3]=0;
f[x][4]=0;

for (int i=head[x]; i!=0; i=edge[i].next) {
int v=edge[i].v;
dfs (v);
f[x][0]+=f[v][4];
f[x][3]+=f[v][2];
f[x][4]+=f[v][3];
}

if (head[x] >= 0) {
f[x][1]=INF;
f[x][2]=INF;
for (int i=head[x]; i!=0; i=edge[i].next) {
int v=edge[i].v;
int a=f[v][0];
int b=f[v][1];
for (int j=head[x]; j!=0; j=edge[j].next) {
if (i == j) continue;
int k=edge[j].v;
a += f[k][3];
b += f[k][2];
}
f[x][1]=min(a,f[x][1]);
f[x][2]=min(b,f[x][2]);
}
} else {
f[x][1]=f[x][2]=1;
}

for (int i=1; i<=4; i++) {
f[x][i]=min(f[x][i], f[x][i-1]);
}
return;
}
int main() {
scanf ("%d",&n);
for (int i=2; i<=n; i++) {
int t;
scanf ("%d",&t);
AddEdge (t,i);
}

dfs(1);

printf ("%d\n",f[1][2]);
return 0;
}

这只是第一种做法,还有贪心的做法,说学会了基本上就能解决形如半径为 $k$ 的最小覆盖问题,复杂度仅为 $O(nk)$ 。

如果 1 为根节点,那么可以考虑最深节点的覆盖问题,如果它要被覆盖,有 3 种情况:

  1. 爷爷
  2. 父亲
  3. 兄弟

为了让这个消防站最不浪费,肯定把站点设在爷爷节点,如此刷新最深未被覆盖的节点,把站点设在他的爷爷节点,这样的贪心策略一定最优。

当然还有一些优化(对于这道题不加这些优化也可以过),深度可以在读入的时候处理,对于判断是否被覆盖的问题,用一个数组 MinDis[i] 储存距离 $i$ 最近的消防站离 $i$ 的距离,如果这个距离大于 2 的话,就要加个消防站,每次从父节点和爷爷节点更新。

$Code$

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e3+5;

int MinDis[MAXN], n, num[MAXN], fa[MAXN], dis[MAXN], ans;

bool cmp (int a, int b) {
return dis[a]>dis[b];
}

int main() {
memset (MinDis, 0x7f, sizeof (MinDis));
scanf ("%d",&n);
num[1]=1;
for (int i=2; i<=n; i++) {
scanf ("%d",&fa[i]);
dis[i]=dis[fa[i]]+1;
num[i]=i;
}
sort (num+1, num+n+1, cmp);
for (int i=1;i<=n;i++) {
int j=num[i];
int f=fa[j], pa=fa[fa[j]];
MinDis[j]=min (MinDis[j], min(MinDis[f]+1, MinDis[pa]+2));
if (MinDis[j] > 2) {
MinDis[pa]=0;
ans++;
MinDis[fa[pa]]=min (1, MinDis[fa[pa]]);
MinDis[fa[fa[pa]]]=min (2, MinDis[fa[fa[pa]]]);
}
}
printf ("%d\n",ans);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×