Luogu P1352
题目大意
有 $n$ 个人，每个人有一个上司，当他不和他的上司一起跳舞时，他会有一个快乐值，求当一些人一起跳舞时，所有人的快乐值总和最大值。
分析
且给出的关系一定是一棵树。
题面中的这个信息可以让我们知道这是一道树形dp的模板题，每个人的上司就是这个人的父节点。
树形dp
基本思路
我们用 dp[i][0] 表示不选该节点时的最大快乐值， 用 dp[i][1] 表示选该节点时的最大快乐值，用mc[i]表示该人的快乐值。
可以得到以下式子：
这就是树形dp的基本实现。
选根
和一般的树形dp题目不一样，这道题不是从每一个节点开始遍历都可以得到答案，需要找没有父节点（没有上司）的节点开始遍历。
模板题，就不给出代码了。
Luogu P1685
题目大意
给你一个 DAG （有向无环图），给你起点和终点，求所有从起点到终点的路径的时间之和，以及方案数减一乘上渡船时间，数据保证能从起点到达终点。
分析
首先考虑暴力 dfs ，但通过分析，可以发现这是一种不可行的策略，因为搜索到某个点时，到它的所有路径不一定被搜完，如果直接搜下去会影响正确性，如果回溯重新搜索会浪费时间。
于是我们就要在搜索到一个点时使得它的入度为零，可以利用拓扑排序实现，同时利用一个类似动态规划加 bfs 的思路记录目前到达这个点的方案数和目前所有路径长度之和。
这道题的转移方程：
其中 $to$ 表示东边的点， $from$ 表示西边的点 ， $dp[i][0]$ 表示到第 $i$ 个点的路径数量， $dp[i][1]$ 表示目前到第 $i$ 个点的路径长度总和。
同时，这道题的边最好使用类似链式前向星的思路实现，使用 vector 会使代码难度及时间复杂度变高。
代码：
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
| struct edge {
int from,to,length;
int lst,nxt;
};
edge led[50005]={};
int dis[20005][2]={},ed[20005][2]={},cnt[20005]={};
void wk() {
memset(ed,-1,sizeof ed);
int n,m,st,edt,tm;
read(n),read(m),read(st),read(edt),read(tm);
dis[st][0]=1;
for(int i=1;i<=m;++i) {
int fr,to,val;
read(fr),read(to),read(val);
led[i].from=fr;
led[i].to=to;
led[i].length=val;
led[i].lst=ed[fr][1];
led[i].nxt=-1;
cnt[to]++;
if(ed[fr][0]==-1) ed[fr][0]=ed[fr][1]=i;
else {
led[ed[fr][1]].nxt=i;
ed[fr][1]=i;
}
}
deque<int> que;
for(int i=1;i<=n;++i) {
if(!cnt[i]) {
que.push_back(i);
}
}
while(!que.empty()) {
int node=que.front();
que.pop_front();
for(int i=ed[node][0];i!=-1;i=led[i].nxt) {
(dis[led[i].to][0]+=dis[node][0])%=10000;
(dis[led[i].to][1]+=dis[node][0]*led[i].length+dis[node][1])%=10000;
if(!(--cnt[led[i].to])) {
que.push_back(led[i].to);
}
}
}
write((1ll*dis[edt][1]+1ll*(dis[edt][0]-1)*tm)%10000);
}
|
Luogu P2607
建议先做P1352 没有上司的舞会树形dp板子题，有助于此题的完成。
题目大意
给你 $ n $ 个骑士，他们每人都有一个痛恨的人，不能和那个痛恨的人同时作战，当他作战时，他的战斗力是 $a_{i}$ ，规划一种布兵方案使得军队战斗力最强。
分析
通过阅读题面，可以将这些骑士与他们痛恨人的关系化为一棵树，对于每个人，痛恨的人是他这个节点的父亲，于是，对于以下数据，问题出现了。
所有骑士形成了一个环，对于这种情况，我们就要破环。
此处做另外说明，对于一个有 $n$ 边，有 $n$ 个点的无根树，且每个节点都有父亲的情况下，这个树一定会出现环。
破环
破环操作，说白了就是在树上找环并从环上任意一个点切开进行两次树形dp。
于是我们可以写出以下代码
1
2
3
4
5
6
| for(int i=1;i<=n;++i) {
if(!v[i]) {
find_c(i);
}
}
|
意思就是对于每一个没有访问过的节点，都对它做一次找环操作。
这里再做一次说明，在此题中，因为每个节点都有父节点，所以任意一个节点 $ i ~ (1 \leq i \leq n)$ 没有被访问过时，将它作为无根树的根时，它必然在一个环中，所以当一个节点 $ i $ 不在之前的任意一个环中，它必然在一个新的环中。
找环操作可以参见以下代码，有注释
1
2
3
4
5
6
7
8
9
10
11
12
| int root;
void find_c(int n) {
root=n;
v[root]=true;
while(!v[gf[root]]) {
root=gf[root];
v[root]=true;
}
dfs();
}
|
树形dp
这里几乎就是树形dp的模板了，只需要注意代码中的关键点。
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
| int dp[Maxn][2]={};
void dfs2(int pt) {
v[pt]=true;
dp[pt][0]=0;
dp[pt][1]=a[pt];
for(int i=0;i<v[pt].size();++i) {
if(v[pt][i]!=root) {
dfs2(v[pt][i]);
dp[pt][0]+=max(dp[v[pt][i]][1],dp[v[pt][i]][0]);
dp[pt][1]+=dp[v[pt][i]][0];
}
else {
dp[v[pt][i]][1]=-1<<20;
}
}
}
void dfs() {
int ans=0;
dfs2(root);
ans=max(dp[root][0],dp[root][1]);
root=gf[root];
dfs2(root);
sum+=ans;
}
|
CF 1713D
题目大意
有 $2^{n}$ 个人进行一轮淘汰赛，每次可以询问其中任意两人谁赢的场数多，最后输出淘汰赛的冠军。
分析
一道优质交互题。
首先看最多的交互次数，是 $\lceil 1/3 \times 2^{n+1} \rceil $ ，即 $\lceil 2/3 \times 2^{n} \rceil $ ，考虑到总的比赛场数是 $2^{n}-1$ ，可以尝试用 $2$ 次询问获得 $3$ 场比赛的结果。
那么如何用 $2$ 次询问获得 $3$ 场比赛的结果呢？
我们来分析一下，$4$ 个人之间（假设这四个人分别是 $p_{1}$ ， $p_{2}$ ， $p_{3}$ ， $p_{4}$ ），会进行 $3$ 场比赛，先是 $p_{1}$ 和 $p_{2}$ 比赛 ， 然后 $p_{3}$ 和 $p_{4}$ 比赛。我们如果对第一轮直接交战的人进行比较，那么就错了。
我们考虑先对 $p_{1}$ 和 $p_{3}$ 进行比较，如果 $p_{1}$ 和 $p_{3}$ 胜利场数一样，那么他们不可能同时进入下一轮，因为如果同时进入下一轮，他们当中就一定会有一个人胜利，胜利场数就不可能一样，所以直接比较 $p_{2}$ 和 $p_{4}$ 就可以知道这 $4$ 个人中胜者是谁。
接下来分析 $p_{1}$ 比 $p_{3}$ 胜利场数多的情况。在这种情况下，$p_{3}$ 不可能是 $4$ 个人中的胜者，同时 $p_{1}$ 一定通过了第 $1$ 轮，即 $p_{2}$ 不是 $4$ 个人中的胜者了。所以只需要比较 $p_{1}$ 和 $p_{4}$ 即可。
同理，$p_{1}$ 比 $p_{3}$ 胜利场数少时，只需要比较 $p_{2}$ 和 $p_{3}$ 即可。
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
| #define sx fflush(stdout)
int win[(1<<17)|5]={};
void wk() {
int n,result;
read(n);
int m=1<<n;
for(int i=1;i<=m;++i) win[i]=i;
for(int l=1;l<=n;l+=2,m/=4) {
if(l==n) {
printf("? %d %d\n",win[1],win[2]);
sx;
read(result);
if(result==1) {
printf("! %d\n",win[1]);
}
else printf("! %d\n",win[2]);
sx;
return ;
}
for(int i=1;i*4<=m;++i) {
printf("? %d %d\n",win[i*4-3],win[i*4-1]);
sx;
read(result);
if(!result) {
printf("? %d %d\n",win[i*4-2],win[i*4]);
sx;
read(result);
if(result==1) win[i]=win[i*4-2];
else win[i]=win[i*4];
}
else if(result==2) {
printf("? %d %d\n",win[i*4-2],win[i*4-1]);
sx;
read(result);
if(result==1) win[i]=win[i*4-2];
else win[i]=win[i*4-1];
}
else {
printf("? %d %d\n",win[i*4-3],win[i*4]);
sx;
read(result);
if(result==1) win[i]=win[i*4-3];
else win[i]=win[i*4];
}
}
}
printf("! %d\n",win[1]);
sx;
}
|
CF 1806E
题目大意
给你一棵树，然后定义一个函数 $ f(x,y) $，接下来给你 $ q $ 组询问 $x_{i},y_{i}$，让你求每一次的 $ f(x_{i},y_{i})$。
分析
首先我们尝试根据这个函数的定义暴力求值，代码实现如下。
1
2
3
4
| ll BFquery(int g,int h) {
if(!g) return 0;
return 1ll*a[g]*a[h]+BFquery(p[g],p[h]);
}
|
每次调用这个函数即可。时间复杂度是 $ O(nq) $,不足以通过此题。
于是我们来分析题目中用粗体标注的一个条件：每次给出的 $x_{i}$ 和 $y_{i}$，它们深度相同。
这就表明一个点的权值只会和与它处于同一深度的任意一个点相乘，这就减少了相乘点对的组数，也增加了它们出现的次数，会导致我们多次计算同一个 $f(x,y)$ 的值，增大时间复杂度。
对于这个问题，我们可以尝试用类似记忆化搜索的方法来解决，但是为了不超过空间限制，也不能全部记录，即对于每一组 $x,y$，我们可以设一个值 $B$，即在不记录答案的情况下，最多计算 $B$ 次。对于余下的计算，每次的值都会被存储在一个 map 中，这样时间复杂度可以优化至近似 $O(Bq)$。
而另外一种方法，存储深度较大的部分而不存储深度较小的部分，目前没有找到这方面正确的做法，如果以后找到我会补上。
下面是代码。
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
| int n,q,a[100005]={},p[100005]={},d[100005]={},rp[100005]={},f,s,cnt=0,P;
ll res;
vector<int> v[100005],op[100005];
map<ll,ll> mp;
const int M=100005,B=500;
ll BFquery(int g,int h) {
if(!g) return 0;
if(g>h) swap(g,h);
if(mp[1ll*g*M+h]!=0) return mp[1ll*g*M+h];
else {
mp[1ll*g*M+h]=1ll*a[g]*a[h]+BFquery(p[g],p[h]);
return mp[1ll*g*M+h];
}
}
void wk() {
read(n),read(q);
for(int i=1;i<=n;++i) read(a[i]);
for(int i=2,x;i<=n;++i) {
read(x);
v[x].emplace_back(i);
p[i]=x;
}
while(q--) {
read(f),read(s);
if(f>s) swap(f,s);
res=0;
P=B;
while(f && s && P>0) {
res+=1ll*a[f]*a[s];
f=p[f];
s=p[s];
--P;
}
if(f) res+=BFquery(f,s);
writeln(res);
}
}
|