目标

  • 撑过 CSP 复赛(确信)
  • dpdpdp
  • dsdsds
  • 数论数论数论
  • 图论图论图论

学习内容

  • 树上差分
  • 换根 dp
  • 扫描线
  • 网络流基础
  • 斜率优化

做题记录

20/11/02

  • P3128 [USACO15DEC]Max Flow P

树上差分模板

  • P4408 [NOI2003]逃学的小孩

求直径并枚举点即可,开 long long

  • P2052 [NOI2011]道路修建

  • P1967 货车运输

Kruskal 求最大瓶颈生成森林,然后树剖处理路径上最小边的询问

20/11/03

  • P1983 车站分级

建图,拓扑排序找层数即可

  • P2597 [ZJOI2012]灾难

一道紫题,思路比较巧妙。

首先对图拓扑排序,建出的拓扑序列保证后面的不是前面的猎物。然后尝试建一棵树,保证根节点灭绝后整个子树会跟着灭绝。考虑按照拓扑序列给树加点,每次将一个点加到其所有食物的 LCA 上(拓扑序保证了这些食物已经被加进树里面),求 LCA 的过程使用倍增维护。然后 dfs 一遍求出所有节点的子树大小即可。总时间复杂度 O(m\log n+n\log n)

20/11/04

  • P3478 [POI2008]STA-Station

换根 dp 板子题,考虑当前节点的贡献以及父亲节点的贡献即可。

  • P2986 [USACO10MAR]Great Cow Gathering G

还是换根 dp,ans 初始值要赋超级大(1e18)

  • P3047 [USACO12FEB]Nearby Cows G

换根 dp,f_{i,k} 为答案,g_{i,k} 表示点 i 的儿子中到 i 的距离不超过 k 的权值和,则 f_{v,k}=f_{u,k-1}+g_{v,k}-g_{v,k-2}

  • CF1187E Tree Painting

题意:给定一棵n个点的树 初始全是白点

要求你做n步操作,每一次选定一个与一个黑点相隔一条边的白点,将它染成黑点,然后获得该白点被染色前所在的白色联通块大小的权值。

第一次操作可以任意选点。

求可获得的最大权值

f_u 为先选 u 号点获得的最大答案,g_u 为先选 u 点在子树中的最大答案,则 g_u=size(u)+\sum g_v,然后通过换根求出 f_u 即可。

20/11/07 csp 爆炸

20/11/09

  • P4427 [BJOI2018]求和

复习树剖模板

  • P1944 最长括号匹配

线性 dp,使用 dp 解决括号串匹配问题,找准转移关键即可。

20/11/10

  • P2572 [SCOI2010]序列操作

sb 题,区间推平的时候要清空反转标记,维护区间和,前缀 0/1,后缀 0/1,最大连续 0/1 和两个懒标记即可。

20/11/11

  • P1772 [ZJOI2006]物流运输

比较巧的线性 dp,设 f_i 为到第 i 天为止的最少花费。转移时对于第 i 天,倒序枚举天数 j,意思为从第 j 天开始改线路,同时记录 [j,i] 天不可用的点,跑最短路即可。

f_i=\min\lbrace f_{j-1}+k+\operatorname{dis}(1,m)\cdot (j-i+1)\rbrace,即改了线之后的最短路乘以改线后的天数,并寻找最佳改线的时间点。

f[0]=-k;//边界条件
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            now[j]=0;//now[u] 维护在 [j,i] 天区间内点 u 是否可用
        for(int j=i;j>=1;j--)
        {
            for(int u=1;u<=m;u++)
                if(avl[u][j])
                    now[u]=1;
            ll dis=dij();
            if(dis>=0x3f3f3f3f)//如果已经无法继续到达就可以直接结束
                break;
            f[i]=std::min(f[i],f[j-1]+(i-j+1)*dis+k);//状态转移
        }
    }

20/11/12

  • P5490 【模板】扫描线

扫描线求面积并模板

  • P1856 [USACO5.5]矩形周长Picture

扫描线求周长并模板

20/11/13

  • P1502 窗口的星星

转化成扫描线问题

  • P2146 [NOI2015]软件包管理器

树剖,对于每个安装操作,统计从根到该节点上的和并全部赋 1,对于每个卸载操作,统计这个节点的子树大小并全部赋 0 即可。

20/11/14

  • P1608 路径统计

最短路计数问题,注意判断重边(当然如果从 ij 存在 w_1<w_2 的话显然选 w_1,所以不能直接简单的 bool 数组判重)。跑 dij 的时候再记录 f_i 表示到 i 的最短路条数,恰当转移即可

  • P1144 最短路计数

无需思考重边和自环

20/11/15

  • CF915E Physical Education Lessons

动态开点线段树

  • P5459 [BJOI2016]回转寿司

问有多少组 (l,r) 满足 L\le\sum_{i=l}^ra_i \le R(l,r) 对数。

预处理前缀和 sum(i),变换式子后不难发现变为 sum(y)-R\le S_{x-1}\le sum(y)-L,使用权值线段树维护即可。

20/11/17

  • P1955 [NOI2015]程序自动分析

离散化+并查集

  • P2279 [HNOI2003]消防局的设立

树形dp,https://imyangty.com/oi/1216

20/11/18

  • UVA1347 旅行 Tour/P1523 旅行商简化版

dp

20/11/19

  • UVA12563 劲歌金曲 Jin Ge Jin Qu hao

转化后即为 0-1 背包

  • UVA11400 照明系统设计 Lighting System Design

前缀和+线性dp

  • UVA11584 划分成回文串 Partitioning by Palindromes

划分为回文串的最小分割数,dp

20/11/21

  • P3376 【模板】网络最大流

EK dinic

  • P2170 选学霸

并查集+ 0-1 背包

  • P2359 三素数数

比较神奇的 dp

  • P1799 数列

线性 dp

  • P1343 地震逃生

裸的最大流,AC400 祭

20/11/22

  • P1453 城市环路

基环树 dp,考虑使用并查集找环然后暴力断环跑两次没有上司的舞会

  • P2607 [ZJOI2008]骑士

基环森林 dp,可以使用有向图,把 i 讨厌的人 j 设成 i 的父亲,然后连边 (j,i)。这样的话只有“根节点”有机会形成环,这样就可以很容易的断环为链跑两次 dp 统计每个连通块的答案。

  • P5144 蜈蚣

水,线性 dp

20/11/23

  • P3153 [CQOI2009]跳舞

最大流 + 二分答案

  • P3381 【模板】最小费用最大流

EK+SPFA

20/11/24

  • P3853 [TJOI2007]路标设置

二分答案

  • P3743 kotori的设备

二分答案,对于每个使用时间考虑每个设备需要充的总电量充电宝能不能提供,如果 \sum a_i\le p 则输出 -1 即可

  • P1850 换教室

期望 dp

20/11/25

  • P1281 书的复制

dp+贪心输出

  • P2370 yyy2015c01 的 U 盘

二分答案套背包

  • P1577 切绳子

二分答案

20/11/26

  • UVA11582 巨大的斐波那契数! Colossal Fibonacci Numbers!

斐波那契数列在模 n 的意义下必然会出现循环节(如果 f_i=f_{i-1}=1i>2,则周期为 i-2),注意到这一点之后打一个快速幂取模即可

  • UVA12169 不爽的裁判 Disgruntled Judge

  • UVA10375 选择与除法 Choose and divide

考虑给答案乘上 p^1q^{-1}(p-q)^{-1}r^{-1}s^1(r-s)^1,对答案的质因数分解进行处理即可

  • UVA10791 最小公倍数的最小和 Minimum Sum LCM

注意到 n=\prod p_i^{a_i},所以每个数分别为 p_i^{a_i} 时可以有最优解,注意 n=1 时以及 n=p_i^{a_i} 时的特判即可。

  • UVA12716 GCD等于XOR GCD XOR

比较巧的结论题,利用了 gcd 和异或的性质 https://imyangty.com/oi/1222

20/11/27

  • P1593 因子和

唯一分解定理,等比数列求和以及费马小定理求逆元的综合应用https://imyangty.com/oi/1223

20/11/28

  • P1156 垃圾陷阱

类背包的 dp,坑点较多

  • P3957 跳房子

二分答案套单调队列优化 dp

坑点:入队/出队顺序,二分上下界,答案初始化为-1,该状态无法被转移到时不能直接终止 dp

  • P3195 [HNOI2008]玩具装箱

斜率优化模板

  • P2365 任务安排

O(n^2) 可过,但可斜率优化

20/11/29

  • P5520 [yLOI2019] 青原樱

考虑种下的 m 棵树之间必须要有至少 m-1 个空位,将其空出来之后发现还有 n-m+1 个位置可以种树,因此答案为 A_{n-m+1}^m=\frac{(n-m+1)\times(n-m)\times\cdots\times1}{(n-2m+1)\times(n-2m)\times(n-2m-1)\times\cdots\times1}=(n-m+1)\times(n-m)\times\cdots\times(n-2m+2)

  • P3197 [HNOI2008]越狱

考虑补集思想,所有的犯人状态有 m^n 种,减去两两不相邻的 m(m-1)^{n-1} 种即为答案,输出加上 mod 再取模。

  • P7076 动物园

CSP2020 赛题,要特判 n=0k=64 的情况,输出 2^{64}

20/11/30

  • P7077 函数调用

CSP2020 赛题,拓扑排序讨论乘法对加法产生的贡献

  • P5022 旅行

NOIP2018,考虑直接枚举基环树环上的边然后暴力断边

最后修改日期:2020年12月18日

作者

留言

撰写回覆或留言

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