Rewinner

分类

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16) 未归档(70)

/ 注册

全部文章（共136篇）

HDU 4417 Super Mario 可持久化线段树

题意：询问区间[ L , R] 中比 H 小的数的个数，注意题目中给的区间是从0下标开始的。思路：用upper_bound跑出 H 的相对大小，去查找 L-1 和 R 时间戳小于H的的改变数量注意点：如果找到的H相对大小为0，就不用去寻找（否则会T），可以直接输出0即可。 ///#inc...

2019-01-24

0 600

2017 四川省省赛 Clannad AC自动机+DP

题目传送门这道题和 Remember the Word 【UVALive - 3942 】题意基本一致，只是让你输入每个前缀的方案数（mod 1e9+7） UVALive - 3942 这道题可以字典树DP能过，AC自动机（未优化）+DP也能过。但是这道题数据范围比 3942 这道...

2019-01-24

0 463

UVALive - 3942 Remember the Word

第一道AC自动机+DP，自己好菜连一个线性DP都不会，还得去看博客。大佬 Orz <一蒟蒻（我）题意：给你一个文本串，再给你几个单词，用单词组成文本串的方案数（单词不能重叠）。我的思路：用AC自动机跑出文本串中出现单词区间[s,e](我的代码中的e表示单词结束位置的后一位，为...

2019-01-23

0 473

AC自动机的学习

花了一天把AC最基础的东西弄明白了，想弄清楚AC自动机就得学会KMP和字典树，因为这个算法是这个两个算法的基础上建立的。我们得明白字典树如何建立的和得深度理解KMP中next数组得含义。AC自动机中的fail指针和KMP中的next数组有异曲同工之处。fail指针的作用：在失配时能够跳转到合适的位置...

2019-01-22

0 487

树形DP求树的直径讲解+例题

例题：HDU 2196 Computer（树形dp经典）传送门证明：原文：https://blog.csdn.net/shuangde800/article/details/9732825 把无根树转化成有根树分析，对于上面那棵树，要求距结点2的最长距离，那么，就需要知道以2...

2019-01-21

0 620

树形DP求树的直径【模板】

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int const MAX = 100005; int head[MAX], dp[MAX][2]...

2019-01-21

0 432

POJ - 1177 矩形周长并

参考博客：http://www.cnblogs.com/scau20110726/archive/2013/04/13/3018687.html 方法：把矩形分成横线和竖线去处理，可知是完全相同的操作，我们来讲下怎么算出横线部分，竖线部分就是照搬即可。将横线保存在一个表中，按横线所处的竖直位...

2019-01-21

0 593

HDU 4419 扫描线+线段树

自己的思路：题目给了三种颜色 R G B，能够组成7种颜色，我想到用状态压缩（R =1,G=2,B=4），因为他的颜色是由他的种类数决定的，所以我用异或来表示他的覆盖情况（这是我***的地方，我没理解基础的 +1，-1 为什么），后面debug发现我的覆盖情况出现的负值的情况，然后就没有思路了。 ...

2019-01-21

0 374

数位DP HDU 4507 求满足条件的平方和

这跟我的上一篇数位DP博客，有点相似，仔细想一下就能明白：博客：https://blog.csdn.net/qq_42211531/article/details/86307936 ///#include<bits/stdc++.h> ///#include<unorder...

2019-01-21

0 465

线段树+扫描线

看了一天才明白了参考博客：https://blog.csdn.net/otowa/article/details/50695401 看完参考博客在看看我对这个的理解。我的理解：扫描线是一种想法，方便我们去理解，线段的作用：维护我们所需要的值。比我们要求上图的面积，我们可以将图...

2019-01-20

0 603