Posts

Reincarnation 题意 区间查询不同字符串的数量。 题解 字符串hash+dp思想 我们从$1-len$枚举子串的长度，如果该区间内子串就加1。由于可能会有重复所以记录长度为$x$的子串最后一次出现的$L$。如果子串出现过那么$dp[L][R]-1$。 ...

Taotao Picks Apples 题意 一段序列，从中挑选的子序列是这样规定的 能取就取，而且取得数字一定要比上一次取得数字要大。 已知一段序列，问如果改变序列中的一个数字，那么取得数字的个数是多少。 ...

度度熊剪纸条 题意 将一段01的序列分成$k$段，将他们重新拼接，问拼接成的纸条中前导0最多有多少个。 拼接不可以改变方向。 题解 我模拟下来就是我们可以将这段序列分成三部分， ...

HDU - 6071 题意 将一个字符串每次减少一个子回文串，例子avdffd可以减少dd，就是subsequence。问最少减少几个回文子串可以使得字符串消失。 ...

树形dp，3天搞定 A - Information Disturbing 题意 对于一棵树，切断一些边使得每一个叶节点都无法连接到根节点，有两个要求 每条边带权重，切掉的边权重和不大于$m$ 切掉的每条边都不能大于一个$ans$ ...

Java大数模板 二、Java之输入输出处理由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。 ...

树链剖分学习笔记 题型 当一道题在询问两点之间修改后的权值或者是两点之间边修改后的权值。这类题目往往我们一开始就会思考用线段树来维护，但是线段树无法维护一颗树上的链，所以我们需要来将树上的链剖分下来。 ...

LCA专项练习 前提提要 由于A,B太水了，就不放了。 前几题先试试用trajan能不能全杀，之后再看在线算法。 易错点统计 如果两个点相同，那么他们的祖先节点居然会变成0。。可能是我的模板写法有点问题。可以在判断vis[u]=2的时候加上如果u=now也是找到了公共祖先。 ...

LCA学习笔记 祖先的定义 如果学习树结构就会明白除了根节点以外每个节点都有一个父节点，所以我们定义祖先为父节点的父节点，然后我们给出最近公共祖先的定义 一棵树祖先中到两个点距离最近的节点。 ...

Codeforces 833B - The Bakery 题意 将一段数字分成最多50个区间，每个区间的价值是区间内不同数字的个数，问怎么样分区间使得价值总和最大。 题解 $dp$加线段树。 $dp[i][j]$表示第$j$个坐标分成$i$块最大的价值。 ...