字符串乘方(KMP)

字符串乘方

对问题的分析设计过程

该题要求询问字符串的最小循环节,为KMP算法的经典应用

对样例求出其next数组,有:

s abcd aaaa ababab
next 0000 0123 001234

易猜出如下结论:

若$n$能被$n-next[n]$整除,则答案为$\frac{n}{n-next[n]}$ ,易证明该结论正确

程序中用到的数据机构和算法

程序使用KMP算法求出next数组后即得

程序的运行情况

该程序提交了五次才通过,具体原因如下:

  • 结束信号为” . “而不是EOF
  • f数组类型定义为char

在实习过程中得到的经验和体会

要认真注意程序的读入格式

Code:

 

牛奶模式(后缀数组)

牛奶模式

对问题的分析设计过程

题目要求序列中的最长的重复k次子序列,为一道经典的后缀数组+height数组例题

将序列求出其后缀数组即其h数组后,我们有$ans=max(RMQ(h[i],h[i+1],…,h[i+k]))$ 为了快速的进行上诉计算,可以考虑随着i的增大来维护一个数据结构,有下列两种方式:

  • 优先队列(堆)
  • 单调队列

程序中用到的数据机构和算法

本程序使用优先队列实现。

在初始化程序时使用离散化来避免初始时的桶排出现桶太大的情况。

程序的运行情况

一共提交了四次才通过,在提交时出现了下列问题:

  • 下标为1为0分不清楚
  • 在初始化时的离散化直接在s数组上修改出现问题

在实习过程中得到的经验和体会

  1. 在打程序时就要考虑到各种各样的边界问题
  2. 改变数组功能需要考虑是否会对后续操作出现冲突
  3. 后缀数组是解决字符串问题的一种利器

Code:

 

Tree(点分治)

Tree

对问题的分析设计过程

该题要求求出树上路径长度$\leq K$的路径总数,为点分治经典题目

程序中用到的数据机构和算法

程序使用点分治实现,点分治的思想为将一颗树通过重心分割成多棵树来分治求解。即答案=路径通过重心的合法数目+子树答案。求解路径通过重心的合法数目可以通过容斥原理在$O(n\log n)$的时间内得出,可以证明,在用重心进行分割的前提下,时间复杂度为$O(n\log^2 n)$

程序的运行情况

该程序提交了两次才通过,具体情况如下:

321509264477_.pic

311509264471_.pic

在实习过程中得到的经验和体会

要对程序的初始值有足够的细心

Code:

 

Black Box(堆)

Black Box

对问题的分析设计过程

题目要求实现一个支持插入序列和在第$i$次查询序列第$i$小的数的算法,经过思考得到如下算法:

  1. 可以考虑直接用动态开节点的线段树或者BST来进行在线查询
  2. 若将序列分成前$i$小和其他,可以通过两个堆实现单次操作在$O(\log n)$的时间内的在线查询和修改
  3. 若使用时间倒流方法,将插入和删除离线从后向前处理,可以只使用两个栈实现上述操作

程序中用到的数据机构和算法

综合考虑到实现难度和时间空间复杂度,考虑用第二种方法实现。通过维护一个大根堆存储前i小的元素以及一个小根堆存储其他元素。对操作有如下实现方法:

  • 添加元素$x$
    • 元素$x$小于第$i$个元素:将元素$x$插入大根堆中,并将大根堆堆顶元素插入小根堆中。
    • 元素$x$大于第$i$个元素:将元素$x$插入小根堆中。
  • 查询输出大根堆堆顶元素,将小根堆堆顶元素插入大根堆中

程序的运行情况

提交一次即通过,提交情况如下:

在实习过程中得到的经验和体会

  1. 使用STL库将会大大减少代码复杂度
  2. 注意初始化问题

Code:

 

Apple Tree(树状数组+dfs序)

Apple Tree

对问题的分析设计过程

这道题需要对一颗树的节点进行如下操作:

  • 单点修改
  • 对子树节点求和

考虑到没有其他操作可以考虑使用dfs序和树状数组实现

程序中用到的数据机构和算法

该程序使用dfs序和树状数组。将树做一次dfs遍历,并记录每个节点的访问顺序,可以发现节点的子树都对应访问顺序上的一个子区间。该题可变为对序列的单点修改和区间求和,即可用树状数组解决

程序的运行情况

提交了三次才通过,提交情况如下:

在实习过程中得到的经验和体会

  1. 在提交时一定记得要把Debug信息给删除
  2. 树状数组在处理一系列简单的数列操作和询问时是一种非常简便的,可以替代线段树的视线方案

代码

Lost Cows(线段树)

3:Lost Cows

  1. 对问题的分析设计过程

    考虑拥有最小代号的奶牛所在的位置,可以发现其一定位于最右侧的计数器为0的位置上。然后考虑将其移出队列,位置比他大的位置的计数器都会减一,可以以此类推求出其他奶牛的代号。

    若将移出队列变成将其计数器变为$\infty$,则该题变成了支持序列的如下操作:

    • 找区间最小值所在位置
    • 区间减法
    • 单点修改

    即可用线段树来解决此问题。

  2. 程序中用到的数据机构和算法

    本程序使用带懒标记的线段树实现。详细原理请参考第一题。

  3. 程序的运行情况

    该程序提交了一次即通过

    1507796908309

  4. 在实习过程中得到的经验和体会

    线段树的写法需要形成自己的风格,才能提高速度与准确性。

Code:

 

K-th Number(主席树)

2:K-th Number

  1. 对问题的分析设计过程

    题目要求找区间第k大,是一道典型的可持久化权值线段树的例题。

  2. 程序中用到的数据机构和算法

    本程序使用可持久化权值线段树实现,在权值的离散化上直接使用动态申请权值线段树节点来解决该问题。可持久化权值线段树(又称主席树)的详细实现方法可自行百度或参考代码。

  3. 程序的运行情况

    该程序提交了一次即通过。0E0D469A-5839-4D00-A632-9AB4B92CAD25

  4. 在实习过程中得到的经验和体会

    可持久化权值线段树在维护某些区间信息上有很大的作用,是一种非常好的思路。

Code:

 

A Simple Problem with Integers(线段树)

题目链接

对问题的分析设计过程

题目要求对序列进行下列操作

  • 区间加法
  • 区间求和

因此可以考虑使用两个树状数组带懒标记维护的线段树来实现

程序中用到的数据机构和算法

该程序使用了带懒标记的线段树来实现上述操作。具体来说对线段树上的每个节点新增一个属性Lazy表示该区间被同时加上Lazy。在更新时若该节点区间被更新区间覆盖则直接更新Lazy,无需继续对其子节点进行修改。查询时在访问其儿子节点的同时将其Lazy下传至儿子节点。可证明单次修改以及查询其时间复杂度均为$O(\log n)$。总时间复杂度为$O(n+q\log n)$。 详细实现过程见代码。

程序的运行情况

该程序一共提交了3次,运行情况如下图所示:

错了两次的主要原因是因为对于lazy操作有点不太熟悉。

在实习过程中得到的经验和体会

线段树真的好用好写,在维护序列上强无敌。

Lazy操作需要考虑许许多多各种各样的方面需要小心一点

Code:

 

BZOJ 3208: 花神的秒题计划Ⅰ

这就是一道滑雪嘛= =

所有操作都爆力,求路径就dp,完了

CODE:

 

BZOJ 3404: [Usaco2009 Open]Cow Digit Game又见数字游戏(博弈论)

一开始被题意坑了= =,题目是说这个数字的最大和最小,不是个位的最大和最小= =

不知道怎么做只能递推了,必胜态就是存在能到达必败态的,必败态就是只能到达必胜态的

CODE: