从今天起至10月11日，持续连载。
关于计算机
ENIAC
出现于1946年。
是最早的计算机。
是电子管计算机。
其他
阶码，即浮点数的指数部分。
IPv6是128位的。
求补码：二进制下：各位取反再加1 或 把原码减1再取反。
关于算法
各种排序的时间复杂度
快速排序：$O(nlogn)$，最坏为$O(n^2)$。
冒泡排序：$O(n^2)$。
归并排序：$O(nlogn)$。
计数排序：$O(n)$。
插入排序：$O(n^2)$。
关于树
完全二叉树 vs 满二叉树：完全二叉树最后一层不一定满。
前序遍历：中左右；中序遍历：左中右；后序遍历：左右中。
节点数
继续阅读 »
现在算起来，至少有220分是不应该丢的——已经接近我的得分了，都是由各种脑残的错误引起的。总之，经历了这一切，我都早已习惯了。过去的事只能让它过去了，重要的是：经历了这一切，我总要明白一些什么。
生活大爆炸版剪刀石头布
题目链接：Link 得分：100
这题是真正的大水题，当然也是我唯一一道满分的题（欲哭无泪）。不说了，模拟就是了。
联合权值
题目链接：Link 得分：40
这题不难，关键是要将无根树转化成为有根树，做一次DFS。事实上，两个距离为2的节点，要么一个是另一个的祖父节点，要么两个节点是兄弟关系。一方面，我们在DFS时先求当前节点与祖父节点产生的联合权值（如果有的话）；另一方面，遍历当前节点的子节点。对于一个
继续阅读 »
题目大意
输入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}
继续阅读 »
题目
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：$\sum_{i=1}^{n}{(a_i-b_i)^2}$
，其中 ai表示第一列火柴中第 i 个火柴的高度，bi表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。
分析
这真是一道好题——断断续续想了几天才完全AC。
事实上，由排序不等式可知：
当$a_i, b_i$从小到大排序时，距离
继续阅读 »
记得11年的时候，觉得这道题爆难，根本无从下手。三年后再次回顾，终于AC了，就当是对表达式求值和动态规划的复习吧。
题目：Link
```cpp
// Accepted.
include <iostream>
define Mod 10007;
using namespace std;
typedef struct {
long long v0; //当前值为0的个数
long long v1; //当前值为1的个数
char ch; //当前字符
} vertex;
vertex f[100000];
void merge_sum(int p) {
int w0 = f[p-1
继续阅读 »
今天开始学习数论方面的算法。这部分在NOIP中并不常出现，即使出现了也不会像高联这么难（。。。）。
什么是扩展欧几里得算法
所谓欧几里得算法，实际上就是辗转相除法——求两个数最大公约数的一种高效算法。而扩展欧几里得算法则是来源于于一类方程的解决：
$$ax+by=gcd(a,b)$$
这有点像是裴蜀定理的一般形式。和裴蜀定理类似，这类方程也有无数多个整数解。如何高效率地求得它的一组特解呢？
代码
pascal
procedure gcd_ex(a, b: longint; var d: longint; var x, y: longint);
begin
if b = 0 then
begin
继续阅读 »
链接：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 耗时: 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 耗时：1.825s
这道题做的可真够久的：前前后后加起来将近有两个小时，因此当AC的那一刻，自己心中还是挺自豪的。
事实上，这是一道复杂一点的区间型动态规划，之所以说“复杂”，是因为它的状态转移是二维的：切蛋糕既可以横切，也可以纵切。由此我想到了分治算法：
假设一个矩形它所需要切的刀数是f，则f可以由组成该矩形的小矩形的f值决定。
因此，这个问题具有最优子结构。由于每个状态为一个矩形，因此需要4个维度来记录状态（及左上、右下两个顶点）。下面是横切时的状态转移方程，纵切时同理可得：
f(up, down, left, right) = min{f(up, i, left, right) + f(i, dow
继续阅读 »
链接：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
继续阅读 »