2019.8.3 集训解题报告
浏览 42 | 评论 0 | 字数 3689
Snowflake_Pink
2019年08月03日
  • 今天在讲讲座,讲斜率优化、四边形不等式优化、凸包,还有一大堆东西。

    因为就觉得自己目前最重要的不是这些,就回机房做题了,(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 种情况:

    1. 爷爷
    2. 父亲
    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;
    }
    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/71/
    最后修改时间:2020-04-13 11:35:29
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论