下一页 »Current position : 首页
打印所有虚拟页号（ICS Homework）
利用/proc/pid/mmap详情今后再补[crayon-5ade2a640da23993845288/]
字符串乘方（KMP）
字符串乘方对问题的分析设计过程该题要求询问字符串的最小循环节，为KMP算法的经典应用对样例求出其next数组，有：sabcdaaaaabababnext00000123001234易猜出如下结论：若$n$能被$n-next[n]$整除，则答案为$\frac{n}{n-next[n]}$，易证明该结论正确程序中用到的数据机构和算法程序使用KMP算法求出next数组后即得程序的运行情况该程序提交了五次才通过，具体原因如下：结束信号为"."而不是EOFf数组类型定义为char在实习过程...
牛奶模式(后缀数组)
牛奶模式对问题的分析设计过程题目要求序列中的最长的重复k次子序列，为一道经典的后缀数组+height数组例题将序列求出其后缀数组即其h数组后，我们有$ans=max(RMQ(h[i],h[i+1],…,h[i+k]))$为了快速的进行上诉计算，可以考虑随着i的增大来维护一个数据结构，有下列两种方式：优先队列（堆）单调队列程序中用到的数据机构和算法本程序使用优先队列实现。在初始化程序时使用离散化来避免初始时的桶排出现桶太大的情况。程序的运行...
Tree(点分治)
Tree对问题的分析设计过程该题要求求出树上路径长度$\leqK$的路径总数，为点分治经典题目程序中用到的数据机构和算法程序使用点分治实现，点分治的思想为将一颗树通过重心分割成多棵树来分治求解。即答案=路径通过重心的合法数目+子树答案。求解路径通过重心的合法数目可以通过容斥原理在$O(n\logn)$的时间内得出，可以证明，在用重心进行分割的前提下，时间复杂度为$O(n\log^2n)$程序的运行情况该程序提交了两次才通过，具体情...
Black Box（堆）
BlackBox对问题的分析设计过程题目要求实现一个支持插入序列和在第$i$次查询序列第$i$小的数的算法，经过思考得到如下算法：可以考虑直接用动态开节点的线段树或者BST来进行在线查询若将序列分成前$i$小和其他，可以通过两个堆实现单次操作在$O(\logn)$的时间内的在线查询和修改若使用时间倒流方法，将插入和删除离线从后向前处理，可以只使用两个栈实现上述操作程序中用到的数据机构和算法综合考虑到实现难度和时间空间复杂...
Apple Tree（树状数组+dfs序）
AppleTree对问题的分析设计过程这道题需要对一颗树的节点进行如下操作：单点修改对子树节点求和考虑到没有其他操作可以考虑使用dfs序和树状数组实现程序中用到的数据机构和算法该程序使用dfs序和树状数组。将树做一次dfs遍历，并记录每个节点的访问顺序，可以发现节点的子树都对应访问顺序上的一个子区间。该题可变为对序列的单点修改和区间求和，即可用树状数组解决程序的运行情况提交了三次才通过，提交情况如下：在实习过程中...
Lost Cows（线段树）
3:LostCows对问题的分析设计过程考虑拥有最小代号的奶牛所在的位置，可以发现其一定位于最右侧的计数器为0的位置上。然后考虑将其移出队列，位置比他大的位置的计数器都会减一，可以以此类推求出其他奶牛的代号。若将移出队列变成将其计数器变为$\infty$，则该题变成了支持序列的如下操作：找区间最小值所在位置区间减法单点修改即可用线段树来解决此问题。程序中用到的数据机构和算法本程序使用带懒标记的线段树实现。详细原理请...
K-th Number(主席树)
2:K-thNumber对问题的分析设计过程题目要求找区间第k大，是一道典型的可持久化权值线段树的例题。程序中用到的数据机构和算法本程序使用可持久化权值线段树实现，在权值的离散化上直接使用动态申请权值线段树节点来解决该问题。可持久化权值线段树（又称主席树）的详细实现方法可自行百度或参考代码。程序的运行情况该程序提交了一次即通过。在实习过程中得到的经验和体会可持久化权值线段树在维护某些区间信息上有很大的作用，是...
A Simple Problem with Integers(线段树)
题目链接对问题的分析设计过程题目要求对序列进行下列操作区间加法区间求和因此可以考虑使用两个树状数组或带懒标记维护的线段树来实现程序中用到的数据机构和算法该程序使用了带懒标记的线段树来实现上述操作。具体来说对线段树上的每个节点新增一个属性Lazy表示该区间被同时加上Lazy。在更新时若该节点区间被更新区间覆盖则直接更新Lazy，无需继续对其子节点进行修改。查询时在访问其儿子节点的同时将其Lazy下传至儿子节点。...
随笔
今天是5月1号。。接下来几天就是我的19岁生日了。。。这是步入大学的第一个生日，最近也在忙各种各样的事情，期中考，大作业，分专业种种事情，跟高中的生活相比截然不同同时也多了很多各种各样的感想。。。我觉得现在对我来说还是搞清楚我究竟想干什么，这几天在处理分专业的时候也想了很多，跟计算机在一起是没有多大问题，但更重要的自己想干什么方向的，科学方向还是工程方向，对于各种各样的事物有没有自己特别喜欢的东西，自...