2019.8.3 集训解题报告 - 粉粉何所似？

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

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

[HAOI2009] 逆序对数列

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

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

还有，记得要取模！

#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

#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 种情况：

爷爷
父亲
兄弟

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

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

Code

#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;
}