描述

有一组数，你要把他分成若干连续段。每一段的值，定义为这一段 数中最大值与最小值的差。 求一种分法，使得这若干段的值的和最大。 \(n < 1e6, a_i < 1e9\)

播放器功能介绍

自适应窗口

在播放器的边缘，可以通过鼠标拉伸整个播放器窗口，大小随心

使用数据库管理数据

利用数据库的主键功能，实现了开发文档中所说的选座要求——歌单编号不得重复。

音乐播放控制

实现了开发文档中所说的选座要求——可以形成歌曲的上一首，下一首播放以及循环播放功能。

具备常规播放器具有的前进一首，后退一首，暂停，拖动进度条，调整音量的功能，并支持循环、单曲循环、随机播放的三种播放模式。

搜索

在搜索框输入内容后，会在下方显示搜索结果，包含两个信息，1）一共搜索到相关歌曲的数量，2）相关歌曲。点击歌曲名称的一行可以直接播放歌曲

添加歌单

在”我的歌单“右侧有一个加号的按钮，点击后会弹出添加歌单的对话框，其中歌单是必填项，简介为选填项，若无简介，歌单详情页也不会显示简介相关标签，同时会给歌单添加一张默认图片，添加完后自动加载新建的歌单。

加载歌单详细信息

点击歌单列表中的歌单名称，右侧详情页即会加载该歌单的相关信息。

前置知识

• KMP算法（之前写的一篇KMP解析博客：传送门）
• Trie树（推荐OI-Wiki上的文章：传送门）

AC自动机的定义与实现

定义

AC自动机是基于Trie树的数据结构利用KMP的思想进行多模式匹配的算法。

具体而言，建立一个AC自动机只需要完成两件事

1. 将所有模式串建立Trie树。
2. 构建失配指针。

粗略地理解，就是把本来要和原串匹配的一堆模式串合成一棵树，让原串和一棵树去匹配，来获得平均线性的复杂度。

目标

求出每个模式串在原串出现的次数。

BZOJ3916-Friends

描述

对于字符串\(S\)，先复制一遍接在\(S\)尾部，然后再在任意位置插入一个字符，给定构造好的字符串\(T\)，求原字符串\(S\)。

题解

首先设\(T\)长度为\(n\)，如果\(n\)为偶数，那么必然不存在原串，因为一个字符串长度乘二加一必然是奇数，然后，可以知道原串的长度一定是\(\frac n 2\)。

根据这两个结论，我们可以直接枚举每个位置是否是插入的字符，通过哈希去验证去除该字符后剩下的是否是两个完全相同的串，枚举复杂度为\(O(n)\)，验证复杂度为\(O(1)\)，总体复杂度为\(O(n)\)，符合题目要求。

CF985F-Isomorphic Strings

描述

给定一个字符串\(s\)，执行\(m\)次询问，每次询问判断\(s\)的两个子串是否同构。对于两个字符串同构的定义可以概括为：如果\(s\)中的字符可以被替换得到\(t\)，那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

KMP与前缀函数

前缀函数的定义

给定一个长度为\(n\)的字符串\(s\)（下标从\(1\)开始），约定\(s[l,r]\)表示从\(s[l]\)开始到\(s[r]\)结束的字符串，\(s\)的 前缀函数 被定义为一个长度为\(n\)的数组\(\pi\)。其中\(\pi[i]\)为既是字符串\(s[1,i]\)的前缀同时也是该字符串的后缀的 最长 真前缀字符串（真前缀字符串指不为这个字符串本身的前缀字符串）长度。

换言之，\(\pi[i]\)只关心字符串\(s[1,i]\)，且若\(\pi[i]=j\)，则有字符串\(s[1,j]=s[i-j+1,i]\)。抽象的数学定义即为：\(π(i)=max\{j|s[1,j]=s[i−j+1,i], j≤i\}\)

求解与优化

根据定义可以得出两个结论来帮助我们快速求解\(\pi\)函数。

题意

warma付钱的决策是多重背包模型，收银员找零是完全背包模型，先预处理，然后从w开始枚举S，求min即可

多重背包不开二进制优化应该会挂，开了优化可能没有推出结论也可以水过去

解法

20分

骗分大法直接输出-1

80分

写在前面

本题改编自USACO-The Fewest Coins，仅扩大了部分数据范围

题目描述

除夕之夜，warma唱完鼠来宝之后从国正中心出来，在寒风中瑟瑟发抖，于是乎决定去金拱门奢侈一把。

吃饭全靠赚赏（sang）钱的warma兜里只有硬币，为了快点吃上饭，她想让硬币转手的次数尽可能最少，即付出去的硬币数与找零得到的硬币数之和（S）最小。

市面上流通的硬币共有n（1<=N<=10000）种，面值分别为 \(v_1,v_2,...,v_n\) （ \(1<=V_i<=120\) )。对于面值为 \(v_i\) 的硬币，warma分别有 \(c_i\) 个（ \(0<=c_i<=10000\) ）。同时，出于囊中羞涩，warma只打算购买总价值为 \(w\) （1<=w<=10000）的食物和（谢拉）小伙伴们分享。

特别要注意的是，金拱门是国际品牌，各种硬币都很充足，可以满足任意的找零方案。收银员小姐姐也很善解人意，听到warma的要求后，决定用最少的硬币为warma找零

作为只会吹灭火器的音乐（le）人，warma找到了经验丰富的你（你也要过饭？），希望你能帮她算出付出去的硬币数与找零得到的硬币数之和（S）最小是多少。

前言

背包问题一直是DP的经典模型，但是像我这样的菜鸡总是学不会 （再聪明一点） 所以综合之前的做题和听课，把自己的一点感悟记录下来。（大部分与背包九讲一致）

01背包

01背包是背包模型的基础，也是我DP入门的噩梦，那就从这个问题入手吧。

题目

N件物品和一个容量为V的背包，每件物品有一个体积为c，有一个价值为v。求解背包能装入最大的价值总和。

思路

状态表示： \(f[i][j]\) 表示前i件物品放入容量为j的背包所能获得的最大价值和

状态计算：

• 状态转移方程： \(f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+v[i])\)
• 初始状态： \(f[i][0]=0,f[0][j]=0\)
• 边界条件： \(j<c[i]\) 时， \(f[i][j]=f[i-1][j]\)

写在前面

二分答案和差分构造上我一直是苦手，写这一篇存档记录一下可用的模板。

Problem1

描述：

给定升序排列数组 \(a[n]\) 以及 \(q\) 个查询，每次查询 \(k\) 在数组中的起始位置。

题解：

二分查找，贴一个模板还有一个暴力(前者45ms，后者39ms)