GoldenPotato137的小屋

DAG DP
DAG DP

[SPOJ694] DISUBSTR - Distinct Substrings

题面 传送门:SPOJ 694 Solution 这题可以用SAM来搞,也可以用SA来搞。但无论是哪种搞法,都是基本操作。下面我们来分别讲解一下怎么搞。 SAM 这题用SAM来求就十分粗暴简单。不会SAM的小伙伴可以戳这里 首先,我们先把SAM建出来。根据SAM的性质,我们从出发点随着SAM任意走,走到哪里都是一个完全不同的子串。因此,我们只需要对SAM做一个拓扑序DP/记忆化搜索即可求出SAM上的路径总数,既不同子串的数量。 SA 这题我们显然还是要把后缀数组和height建出来的,不会SA的小伙伴可以戳这里 我…

2019年3月6日 0条评论 1015点热度 1人点赞 GoldenPotato137 阅读全文
DAG DP

[Luogu P3953] 逛公园

题面 蒟蒻博客:QAQ Solution 这是一道神题 首先,我们不妨想一下K=0,即求最短路方案数的部分分。 我们很容易可以想到一个做法,就是魔改迪杰斯特拉做法: 一个点可以更新到达其他点的距离,那个点的方案数就是这个点的方案数;如果一个点所更新出来的距离和之前的相等,那个点的方案数加等当前点的方案数。 用式子可以表现为: $$f[i]=f[i] (dis[j]>dis[i]+x)$$ $$f[j]+=f[i] (dis[j]==dis[i]+x)$$ (i表示当前点,j表示它更新的点,x为i到j那条路的距离) …

2019年2月22日 0条评论 1310点热度 0人点赞 GoldenPotato137 阅读全文
DAG DP

[Luogu P1613]跑路

题面 传送门:洛咕 Solution 挺有意思的一道题。 题面已经挺明显的描述出了这题的主要思想:倍增。 先这样想,我们可以把这题这样建模:有一堆点,若两个点之间的距离之和可以达到2的n次方,那么这两个点可以用1的时间相互到达。 也就是说,我们把距离能为2的n次方的点对用边权为1的边连上,再做一次最短路径,就可以求出答案了。 接下来问题就是如何求出每两个点是否能以2的n次方的时间相互到达。 考虑使用DP。 我们设$f[i][j][k]$ 表示 $i$到$j$是否能以$2$的$k$次方的距离相互到达。 转移的时候得运…

2019年2月22日 0条评论 1190点热度 0人点赞 GoldenPotato137 阅读全文
DAG DP

[Luogu P3119] [USACO15JAN]草鉴定Grass Cownoisseur

题面 传送门:洛谷 Solution 这题显然要先把缩点做了。 然后我们就可以考虑如何处理走反向边的问题。 像我这样的蒟蒻,当然是使用搜索,带记忆化的那种(滑稽)。 考虑设$f(i,j)$表示到达第i个点,还能走j次反向边,所能到达的最多的点的数量。 转移可以表示为: 如果x能到达1所在的强连通分量或max出来的值不为0,说明当前状态可行,否则不可行。 然后用记忆化搜索表达出来就OK了 Code #include<iostream> #include<cstdio> #include<…

2019年2月17日 0条评论 991点热度 0人点赞 GoldenPotato137 阅读全文

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

最近评论
hilaolu 发布于 2 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 2 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 2 年前(11月30日) 可以先不要告诉老师们吗(偷偷搞的
碱式碳酸希 发布于 2 年前(11月04日) %%%%Tql 请求搬运至NNEZ校内OJ公告中。 展示链接: 请在启天楼内网中访问! :razz:...
630分苦苦挣扎的菜鸡土豆 发布于 3 年前(05月01日) 肥肠抱歉,刚刚看见呢。 那个发送留言不能立刻看见源于我站挂了个腾讯云cdn,默认会返缓存的内容qwq...
分类
  • CDQ分治
  • DAG DP
  • DP+DP
  • FFT/NTT
  • Kruskal重构树
  • LCT
  • LUCAS
  • NNEZ
  • set
  • splay
  • 主席树
  • 二分/二分答案
  • 位运算
  • 倍增
  • 其他
  • 分块
  • 动态规划
  • 卷积
  • 反演
  • 同余
  • 后缀数组
  • 后缀自动机
  • 哈希
  • 图论
  • 圆方树
  • 堆
  • 多项式
  • 字符串
  • 学习笔记
  • 容斥
  • 容斥
  • 左偏树
  • 并查集
  • 数位DP
  • 数学
  • 数据结构
  • 整体二分
  • 斯特林数
  • 最小割
  • 最短路径
  • 未分类
  • 树套树
  • 树形DP
  • 模拟
  • 深度学习
  • 游记/自闭记/滚粗记
  • 点分治
  • 状压DP
  • 生涯纪录
  • 线段树
  • 组合数学
  • 缩点/强连通分量
  • 网格DP
  • 网络最大流
  • 网络流
  • 背包DP
  • 虚树
  • 贪心
  • 边双/点双
归档
  • 2022年1月
  • 2021年9月
  • 2021年3月
  • 2021年2月
  • 2019年11月
  • 2019年4月
  • 2019年3月
  • 2019年2月

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号