目标

  • 撑过联赛初赛
  • 推进 dp 能力
  • 推进图论知识
  • 数据结构什么的

做题记录

20/10/01

  • P3038 [USACO11DEC]Grass Planting G

树剖,调了很久的原因是 query 的时候没有下传标记

  • SP1043 GSS1 – Can you answer these queries I

线段树维护稍微复杂的信息——求最大子段和

需要维护最大前缀和,最大后缀和,最大字段和和区间和,难点在于 pushup

  • SP1716 GSS3 – Can you answer these queries III

带修版 GSS1

使用权值线段树和树状数组重做本题

20/10/02

  • 重写了一波高精度
  • P3369 【模板】普通平衡树

使用权值线段树过去的(而且跑的不慢),除了查排名对应的数之外其他都很好想,想通了就可以直接 A 掉

20/10/03

  • P1111 修复公路

并查集

  • P1346 电车

01bfs 优化的最短路

匈牙利算法

  • P2756 飞行员配对方案问题

二分图最大匹配,匈牙利算法

  • P6190 [NOI Online #1 入门组]魔法

使用矩阵快速幂优化 Floyd,复杂度 O(n^3+n^2m+n^3\log k)

F_{i,j} 为使用过一次魔法,从 ij 的最短路。单位矩阵为 D_{i,j},即不使用魔法,求出 D\times F^k 即可。此处矩阵乘法变成了 min

  • P1637 三元上升子序列

权值线段树可以水过去

线段树不开 4 倍空间见祖宗

不开 long long 见祖宗

20/10/04

  • P3385 【模板】负环

SPFA,如果一个点入队 n-1 次,说明这个图存在负环,判断即可。

  • P5960 【模板】差分约束算法

差分约束

  • P3388 【模板】割点(割顶)

割点,注意图可能不连通,要分别对每个连通块 tarjan

20/10/05

  • P3370 【模板】字符串哈希

字符串哈希

  • P3375 【模板】KMP字符串匹配

KMP

20/10/11

  • P1993 小 K 的农场

差分约束

  • P4114 Qtree1

边转点,树剖

  • P2294 [HNOI2005]狡猾的商人

前缀和思想+差分约束(第一次用链式前向星存图嘻嘻嘻)

20/10/12

  • P1351 联合权值

\sum\sum w_iw_j-\sum w_i^2=(\sum w_i)^2-\sum w_i^2

20/10/13

  • P4513 小白逛公园

带修区间最大子段和,练代码能力(

  • P1272 重建道路

树形背包,设 f_{u,j} 表示以 u 为根节点的子树保留 j 个节点需要删的边的最少数量(保留与父节点连边)。预处理 f_{u,1}=size_u。则 f_{u,j}=\min_k^{size_u}\lbrace f_{u,j-k}+f_{v,k}-1\rbrace,这里的 -1 是因为初始化的时候删过了,重新加回来。

取答案时 ans=\min(f_{1,p},\min_{u=2}^n\lbrace f_{u,p}+1\rbrace) 这里 +1 是因为连接其父亲的边要删掉

20/10/14

  • P3387 【模板】缩点

tarjan + 拓扑

  • P1726 上白泽慧音

强连通分量裸题

20/10/19

  • P2656 采蘑菇

强联通分量 + spfa 最长路

20/10/20

  • T143332 区间统计

学长的题,给定一个序列,q 次询问,求 [l,r]x 的个数。

离线做法复杂度 O(n+q),注意到 ans(l,r,x)=count(1,r,x)-count(1,l-1,x),故把所有询问读入,分别按照 lr 桶排序,存储下其对应的询问编号,最后暴力扫一遍序列,两个指针遍历排序过的询问,记录 ans(l,r,x),最后输出即可。

20/10/21

  • P2679 子串

dp,f[i][j][k][0/1] 表示到了 a 串第 i 位,匹配到了 b 串第 j 位,使用了 k 个子串,a 串第 i 位是否选(0/1)的方案数

f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1],若 a[i] == b[j],则 f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k][1]

最后输出 f[n][m][k][0]+f[n][m][k][1] 即可,i 的那一维滚动掉即可。

20/10/22

  • P1514 引水入城

dp+搜索+贪心

注意读题!!!注意判边界!!!注意贪心!!!

  • P2585 [ZJOI2006]三色二叉树

树上dp,氵

20/10/24

  • P1569 Generic Cow Protests

线性dp
[SDOI2005]区间

求区间并 差分,水、

  • P2426 删数

区间dp

20/10/25

  • P1435 [IOI2000]回文字串

区间dp,poj卡空间,被迫滚动数组

注意到 f_{i,j} 只可能由 f_{i,j-1}f_{i+1,j}f_{i+1,j-1} 转移而来,所以可以倒序枚举 i,并将其滚动掉。

for(int i=n-1;i>=1;i--)
    for(int j=i+1;j<=n;j++)
        if(s[i]==s[j]) f[i&1][j]=f[(i+1)&1][j-1];
        else f[i&1][j]=min(f[(i+1)&1][j],f[i&1][j-1])+1;
  • UVA10617 Again Palindrome

区间dp统计回文子串个数

        for(int len=2;len<=n;len++)
            for(int i=1,j=i+len-1;j<=n;i++,j++)
                if(s[i]==s[j])
                    f[i][j]=f[i+1][j]+f[i][j-1]+1ll;
                else
                    f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1];

不开 long long 见祖宗
hdu1421 搬寝室

贪心+dp

不注意多测见祖宗,不注意初始化见祖宗

  • P2401 不等数列

dp

题意:将1到n任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中,有多少个排列恰好有k个“<”。答案对2015取模。

每次考虑已经排好 [1,n-1] 的答案,然后考虑插入 n,如果将 n 放在序列尾,会多出来一个小于号,即包含一个 f_{n-1,k-1},如果把 n 放在序列首,会多出一个大于号,即包含一个 f_{n-1,k},如果把原来小于号换成 n,小于号个数不会变,即多出来 kf_{n-1,k},如果把大于号换成 n,多一个小于号,即多出来 i-1-kf_{n-1,k-1}

f_{n,k}=(k+1)f_{n-1,k}+(i-k)f_{n-1,k-1}

20/10/26

  • P3275 [SCOI2011]糖果

差分约束,SPFA时需要注意:

  1. 前向星空间开够,留下超级源的空间
  2. SPFA 写递归式的
  3. 玄学数据卡 SPFA 需要倒序建超级源的边

缩点+拓扑做法待填坑

  • P1594 护卫队

线性 dp

20/10/27

  • P3147 [USACO16OPEN]262144 P

数据经过加强,只能用一些奇奇怪怪的方法混过去。

发现若想合成 i,就需要先有两个 i-1,关键点便在这里。设 f_{i,j} 为从 j 为左端点能合成 i 的右端点。所以有状态转移方程 f_{i,j}=f_{i-1,f_{i-1,j}+1},即倍增思想。因为需要先合成第一个 i-1,右端点就是 f_{i-1,j},现在要从这个右端点开始继续向后寻找第二个 i-1,所以是 f_{i-1,f_{i-1,j}+1}

初始条件是 f_{a_i,i}=i,转移要求上面转移过来的两个量都有意义。

    for(int i=1;i<=n;i++)
        f[read()][i]=i;
    int ans=0;
    for(int i=1;i<=58;i++)
        for(int j=1;j<=n;j++)
            if(!f[i][j] && f[i-1][j] && f[i-1][f[i-1][j]+1])
                f[i][j]=f[i-1][f[i-1][j]+1],
                ans=i;
  • P1220 关路灯
    一定时间内关闭的路灯必然是连续的

f_{i,j,0/1} 表示关闭路灯 [i,j] 后站在 i 或站在 j 所耗费的最小功率。则 f_{i,j,0} 通过 f_{i+1,j,0/1} 转移得到,反之亦然。

转移太长懒得写了。

  • P3205 [HNOI2010]合唱队
    for(int i=1;i<=n;i++)
        a[i]=read(),f[i][i][0]=1;
    for(int len=2;len<=n;len++)
        for(int i=1,j=i+len-1;j<=n;i++,j++)
        {
            if(a[i]<a[i+1])
                f[i][j][0]=(f[i][j][0]+f[i+1][j][0])%mod;
            if(a[i]<a[j])
                f[i][j][0]=(f[i][j][0]+f[i+1][j][1])%mod;
            if(a[j]>a[i])
                f[i][j][1]=(f[i][j][1]+f[i][j-1][0])%mod;
            if(a[j]>a[j-1])
                f[i][j][1]=(f[i][j][1]+f[i][j-1][1])%mod;
        }

初始化的时候默认是左边进的不然会被重复计算

20/10/28

三道状压dp

  • P1879 [USACO06NOV]Corn Fields G

  • P1896 [SCOI2005]互不侵犯

  • P2704 [NOI2001]炮兵阵地

状压dp:预处理状态,判别,转移

20/10/29

  • P5658 括号树

括号匹配扩展到树上

要注意树上的栈要进行回溯

  • P1868 饥饿的奶牛

线性 dp,使用二分进行优化

20/10/30

  • P2583 地铁间谍/UVA1205

线性dp,思路较为巧妙

  • UVA437 巴比伦塔 The Tower of Babylon

可以记忆化搜索可以 DAG 上 dp

快读会锅不知道为什么

最后修改日期:2020年11月26日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。