Rewinner

数据结构

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

/ 注册

全部文章 / 数据结构（共16篇）

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

扩展kmp(转载)

原文：https://blog.csdn.net/dyx404514/article/details/41831947 拓展kmp是对KMP算法的扩展，它解决如下问题：定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,exte...

2019-01-19

0 415

Gym 101889F — Fundraising 树状数组+离散化+带权上升子序列

题意:给你一些人，每个人有两个特性和一个价值，如果两个人的特性完全相等则可以合并，否则必须一个人的两个特性必须严格大于另一个人才能合并，问：最终可以的到的最大价值。解题思路：看到别人的博客里面有带权上升子序列，让我想起了最长上升子序列 nlogn 的解法：在数组下标 1—i中最长上升子序...

2019-01-02

0 477

Codeforces D. Monitor

二维线段树模板： ///#include<bits/stdc++.h> ///#include<unordered_map> ///#include<unordered_set> #include<iostream> #include<al...

2018-12-10

0 372