这是一道区间型DP，转移方程很简单，但在实现的过程中却遇见了很多坑，在此记录一下。 链接：Link 耗时：0.368s
容易想到，前i个数的划分情况可以由1,2,3...,i-1的划分情况来决定。因此很容易得到状态转移方程：
d[i] = min(d[i], d[j]+1) //j = 0, 1, 2...n-1 并且 s[j+1, i]为回文串，初始条件：d[i] = i。
d[i]表示前i项的最小划分。这样一来状态转移的复杂度就为O($n^2$)。
但状态转移的判断呢？“回文串”是一个复杂的条件，判断一个串是否为回文串需要将该串至少遍历一遍。这样一来时间复杂度就上升为O($n^3$)了。而事实上在这种算法中有许多无谓的计
继续阅读 »
链接：Link 耗时：1.825s
这道题做的可真够久的：前前后后加起来将近有两个小时，因此当AC的那一刻，自己心中还是挺自豪的。
事实上，这是一道复杂一点的区间型动态规划，之所以说“复杂”，是因为它的状态转移是二维的：切蛋糕既可以横切，也可以纵切。由此我想到了分治算法：
假设一个矩形它所需要切的刀数是f，则f可以由组成该矩形的小矩形的f值决定。
因此，这个问题具有最优子结构。由于每个状态为一个矩形，因此需要4个维度来记录状态（及左上、右下两个顶点）。下面是横切时的状态转移方程，纵切时同理可得：
f(up, down, left, right) = min{f(up, i, left, right) + f(i, dow
继续阅读 »
链接：Link 耗时：0.139s
前言
这道题的主要思路就是打表，看看Fibonacci数列模n几个一循环。但由于这题给的数太大了，从而在细节上耗了很久。在此记录一下：
var
x: qword;
y: longint;
begin
x := 1<<64-1;
y := 100;
x := x mod y; //报错201
x := x mod qword(y); //正确
end.
Code
var
a,b: qword;
_, n, i, k, cnt: longint;
f: array [1..1000000] of longint;
fun
继续阅读 »
链接：Link 状态：Runtime Error
前言
这题做的可真够久的，整整三个小时。但即便如此，还是只过了一部分的点，另一部分报运行时错误——估计是哈希表设计的不太好。但这确实是一道好题，因此，在睡觉前决定记录一下。
分析
很容易便想到：用一个三元组$(x,y,z)$表示节点，表示内容为x的节点下跟着标号为y和z的左右子树。这样一来，一类相同的子树便可以唯一确定了，而不必每构造一棵子树就把整棵树遍历一遍。
对于三元组的储存，刚开始图方便，用了数组。查找也是用了$O(n)$的线性查找。磕磕碰碰写了两个多小时然后兴冲冲地提交，结果TLE了…………没办法，只好又花了半个小时写了一个哈希表，然后就是上文说过的情况了：Runti
继续阅读 »
链接：Link 耗时: 0.012s
前言
真是疯玩了几天，脑袋都残了，一道弱智题做了近一个小时。
Code
var
pre, mid, s: string;
tree: array [1..50] of record
l, r: integer;
ch: char;
end;
cur: integer;
function init: integer;
var
m: integer;
begin
readln(s);
m := length(s) >> 1 + 1;
pre := Copy(s, 1, m-1);
mid
继续阅读 »
链接：Link 耗时：0.699s
思路
dfs(t, x, y, d, s)表示当前走了t步，在(x,y)，上一个方向为d，s为一个求和用的辅助变量。
当前位置无法走完剩下的路时直接回溯。可节省接近2s的时间。
ps: 这道题虽然没有明说每个城市只走一次，但它的确那样判了，这一点坑了我好久。
Code
//Accepted.
const
dx: array [1..4] of integer = (1, 0, 0, -1);
dy: array [1..4] of integer = (0, 1, -1, 0);
dir: array [1..4] of char = ('e', 'n', 's',
继续阅读 »
链接：Link 状态：WA
分析
做了两个小时，很可惜最终还是WA了。非常奇怪——和网上的C++代码运行结果完全一样，但却WA了。不过，在这里我还是记录一下解题的过程。
这道题数据量很小，直接爆搜每个空位，用*, +, -, #0来代表符号或不填。
Code
const
operators: array [1..4] of char = ('*', '+', '-', #0); //符号
var
s: string;
_, n: integer;
op: array [0..10] of char;
yes: Boolean;
function toValue(ch: char):
继续阅读 »
链接：Link 耗时：2.232s
分析
粗看题目，不过就是要求这样一个式子：$\sum_{i=1}^n{[\frac{n}{i}]}$的值。但注意到：题目给的数据范围极大，有$2^{31}-1$之多，若遍历计算，则时间复杂度为$O(n)$，将严重超时，不可取。
而事实上，通过尝试我们可以发现：$\sum_{i=1}^{n}{[\frac{n}{i}]}=2*\sum_{i=1}^{\sqrt n}{[\frac{n}{i}]}-{[\sqrt n]}^2$，这是一个重要的结论。因为这条式子一旦成立，时间复杂度即可从$O(n)$降为$O(\sqrt n)$，这是一个极为可观的改善。下面我们来证明一下这个结论：
事实上，$$\su
继续阅读 »
链接：Link 耗时：0.679s
分析
本质上，这是一道求数列通项的题目。我们列出前几个字符串：
$$01,$$
$$1001,$$
$$01101001,$$
$$1001011001101001,$$
$$\ldots$$
如果用$S_i$表示第i个字符串中“00”的个数，则有：
$$S_1=0,\ S_2=1,\ S_3=1,\ S_4=3,\ S_5=5,\ S_6=11,\ldots$$
经过观察可以发现有如下规律：
$$S_n=2\times S_{n-1}+{(-1)}^n$$
求通项就简单了，换个元即可：
$$S_n=\frac{1}{3}[{(-1)}^n+2^{n-1}]$$
程序采用高精度实现。
Cod
继续阅读 »
链接：Link 耗时：0.586s
昨晚做的太急了，没时间写总结，正好下午有空，补上。
这是一道典型的树形动态规划，不是很难，但十分坑语言。思路大致如下：
对于第i个节点，用d(i)表示其上诉所需的最小工人数。若i为叶节点，则d(i)=1；否则，遍历求出i的子节点所对应的d值，并由小到大排序，取出最小的几个相加，即为d(i)。
很容易想到用递归来实现。但对于“子节点的d值的排序”实现起来却十分困难：因为事先不知道有多少个数。当然啦，如果是C++组，用vector可以轻松搞定，可至于P党，实现起来却难上加难。思来想去，决定试试Pascal的动态数组。磕磕碰碰调了近1个小时，终于AC了。
Code:
```pascal
//
继续阅读 »