测试位置：WikiOI1078
type
TEdge = record
start, terminal: longint;
weight: int64;
end;
TEdgeArr = array of TEdge;
operator (e1, e2: TEdge)res: Boolean;
begin
res := e1.weight > e2.weight;
end;
procedure SortEdge(A: TEdgeArr; l, r: longint);
var
i, j: longint;
t, m: TEdge;
begin
继续阅读 »
题目
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：$\sum_{i=1}^{n}{(a_i-b_i)^2}$
，其中 ai表示第一列火柴中第 i 个火柴的高度，bi表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。
分析
这真是一道好题——断断续续想了几天才完全AC。
事实上，由排序不等式可知：
当$a_i, b_i$从小到大排序时，距离
继续阅读 »
题目大意
输入a, b, k, n, m，计算$a^n\times b^m\times C_k^n$模10007的余数。
分析
对于幂数的计算并不难，关键在于对组合数$C_n^k$的计算。
通常来说，组合数的计算一般是这样的：$$C_n^k=\frac{n}{k}\times\frac{n-1}{k-1}\times\ldots\times\frac{n-k+1}{1}$$ 这对于单精度的计算来说是十分快捷的，但如果要对结果取模的话就不起作用了——取模运算对于除法不成立。因此只能另辟蹊径了。
注意到加减乘法对于取模都是成立的，从而想到：能否将组合数转化成加法？
自然而然，想到了组合恒等式：$$C_n^k=C_{n-1}^{k}
继续阅读 »
链接：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
继续阅读 »
鉴于U盘中Sublime的配置常常莫名其妙地消失，在此将其记录一下。
Code
{
"cmd": ["fpc", "-S2", "${file}", "-o${file_path}/${file_base_name}.exe"],
"file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
"working_dir": "${file_path}",
"selector": "source.pascal",
"variants": [
{
"name": "Run",
"c
继续阅读 »
链接：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 状态：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 耗时：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',
继续阅读 »
从今天起至10月11日，持续连载。
关于计算机
ENIAC
出现于1946年。
是最早的计算机。
是电子管计算机。
其他
阶码，即浮点数的指数部分。
IPv6是128位的。
求补码：二进制下：各位取反再加1 或 把原码减1再取反。
关于算法
各种排序的时间复杂度
快速排序：$O(nlogn)$，最坏为$O(n^2)$。
冒泡排序：$O(n^2)$。
归并排序：$O(nlogn)$。
计数排序：$O(n)$。
插入排序：$O(n^2)$。
关于树
完全二叉树 vs 满二叉树：完全二叉树最后一层不一定满。
前序遍历：中左右；中序遍历：左中右；后序遍历：左右中。
节点数
继续阅读 »
链接：Link 状态：Runtime Error
前言
这题做的可真够久的，整整三个小时。但即便如此，还是只过了一部分的点，另一部分报运行时错误——估计是哈希表设计的不太好。但这确实是一道好题，因此，在睡觉前决定记录一下。
分析
很容易便想到：用一个三元组$(x,y,z)$表示节点，表示内容为x的节点下跟着标号为y和z的左右子树。这样一来，一类相同的子树便可以唯一确定了，而不必每构造一棵子树就把整棵树遍历一遍。
对于三元组的储存，刚开始图方便，用了数组。查找也是用了$O(n)$的线性查找。磕磕碰碰写了两个多小时然后兴冲冲地提交，结果TLE了…………没办法，只好又花了半个小时写了一个哈希表，然后就是上文说过的情况了：Runti
继续阅读 »