十年

mybirth:Lu/OedGYle3k+AFDx3t9MA==:mAkL0iU+fnr92EOe6O6L3Q==:fmAxcSqzDeG8XYea7l4oT/Re1lCJXERQ/hSTEsrlOPJwYaDpRUR0Ed+G8lVlP1sU+594QgeJlpMEum7IJUJEkDcn1zqo+S9X4qnXA+Y7m8UQDb3AoEqQ5lEuecI34iH4KPJlE4fE5vUUk6had+/b7fjAHFmsnXcRM60g7/XQMj/pj8pglXbJnbNjFCmMmHsAR0GouDrCvi+KMRMSM1yAwh0lgtmDiLk2bgvC0MbHZEyhjvcjSiPcyZsgzj3p7mM9S6medr7+Tochwigm91TkY8TYNzQ4yETurIJ2+aymS0A/pCgNsUp+b1gVOsy0a91NcdqeA5esYl2s9f2gkEgxrtW/lm2RY07KDmLKQxRrJp/APmUOsGij7CYGBr64tFOYJSn912qn+ZbcBYKUhbJmfVQCF0aa/9G6kiVfGHo+qd+Heksj8OA5Q/nwg52zGBDRZS87RT0w1l+4xm6sNH2CphS7oAUb+pecwSJIP9P1dfSSB/TX7KOUSLACRllw6eKPn/xpKeaUra3s/g6Aelb3+PaNQm0X/KMA1zgrxo2mXr8TvTDCLvpdKAXwq3RsuW7bMBLSBG6gn5D20WincehA2FBPszDpQU3b4Vt2TXTd9ewb7ykbAZsx6Vyx1RiXSe7/SiNO0E/zzTTsZ10dslJBmXhITWD9D3CSjRS1CK2HlXDaL1YQB+KmeJ9l3DEDmrmRVvb6TdPEuiYGZyLUrjv8dbzZpjynMf5PO/8eAAu/i3RyDPOIoB3YXtAWtoLTbiNzZ4bcwyrlUbJDNyhiqpHUCLgA/SlmRnFPO+5A2xGOozlbSw79cG2qQ/gB+xJshGwL6oj80AGKWYxT4V7SZQgYIyL3S3qCA10QO51Tztg+SZvDQJIbd0Vmoq3x6QasPX6KwybJlF5BwKp/PEK4NjVNFuWxG0kHt162mWD/YZJHOq819wGZtTy0VZce0z9ApVtzcGxPjdgQkcS6iPnBPrQ8jFf/h5YATALGjpy/tpBGMUPYUEMoWUWtIQuXep3StgA3stEN5rFNtR6veodIrtsP12f4tiA1pb9yY4AAMc0Fp5UmhVtNi0cjAD+AEd8NSbnIqM31zIL4rKY/WTY0EsNNy8sbd0lkEoANq5rMC0yLqxHSPFY8i5hCXb+9uVZQkCBlBDcomJFBc0VaF8ne8aQv2RT0RqKobarhpkvNxbbcRCjf7Mg1iErxohFv+z6lcpnx2bMle5t1fskrMc/ZOQTBnCLsbazSYR8UfD7gKnrYHyW0j/iB8RuaUHmJPgfHx88NWr+xV/v/PnxZjZninyyiDz4HQ3+15tetJB5crLrwrPOOm3JrkDedbLkFznLmHVYFHpNU6oX7kJPrK02R3RE/EaGd/L/uwRg5+cbRWmVPfMN0fEJ4JpwgBB4hoj6w3kvB0b+NTVxl0VFHGovHMfsbUo6xo2UOtOD1atBFVZGHLHJB0fr4xeYW3F/8wLk+sm9AR9MJQhYxZZzoZ9Ey2j6B+d4p9CZ5UAPCBUYAXzNDavNzKa4pD6RSA/pBnc/oQAscnGZqmpkxcoDU9OeaMBYgsbVZwhomRYY3Ag0JhYML0f+kw7xT4ujk4lGICRaqKGyFs37FdgZL/f+Q1nOr6PjhHKa30++se1pb5t6c7saA/6pVf/mOebgDA6qZf5d1enF3PlZyuFTLWDo+W9/saGtNl8d6oB5PhoUr/bRWWE1/xOGNCfjiYXVM6MnRMTNR+7YFPO00S9IEGkehe5fIrTQSL+ORTWhZvNvfC4XzkP9r2xXqm8a8hgjlgYlZZ8ix0czW7zSW+4hozwZMHnAh9oWv7CTmK7wCIxKpG5LNFaEPql4T1B1cCv/eZ085P0O/JYXFEaANnRHYw5tBeb+yKIw+uIkdki6jLNCnnRoByvL6WGoOYyWR0ZvIzwjtsb5pe+y5gsWRPzuyslwco7ZHtUaCTY6Yls/3pX3MK+2RGq13PIQ+KP97OEJmz/AMW2c9WbbrgSCzy9pbtKhwsUV0n4JZ4MVDixAqlhbBv5pADRen/U2rChtVTf45O6Atn9bgWF5h1DdW6VVT8Zx13erT5fMTbrX9PVu38h9waNK9NDu9dLWPXsDcIQUEBoOWzS7s64e+f5Fokz+tFpMP4cEZB0HFT5TXCtkluXFY+PPCLM7QrCeRauid1/i2ye73fLL6WtoSkd7TkuE63LwMcQvN2TCkW2vK2NRpw7o93WPNyf97y8GgYCe49VBOOzvwC3mGvfBA45oqM5tNZonbb1DDjcC4eRfm0iewV38G6siWMkGeH7pxl5U9qmU2CEdINF/9xoXufHbP6O8u4d7XOeYKyYfYtk78MtCSipjIM1AImaG73MndpF3CIOYNr1EA/6sDvJt2e4WotvLbFASKEjRTWBWT5T8KgXi5AGXGD6QVZEYyNNSNIpNz/5mB1CfluJOH77NtTgWoZ/2FSPOEKbdcBs3tMir4valu+GRmeyApKGGuvm8v1RL/DenxclAVzFTywORZJXrgJjXafc0BZDaRLJXTGg7SGaXUCfrdXDn1dhqMI/c5p4AtnnO2QTN4ida5eQ1bK3XWbTXC3JYbADujPf0yTqoZCyXX8nmqO8/5RF6Clom87jPJxKs5rAD7BImDJP+TOMF569zEgZWK005y6GfhbPm9nvExueTyIn/HKeARjZyGihWjxaANmbaYj9iF8Uy7ykuXodzriaCcwhHw11nv8ZO7qtZgHGTJ+29iBeWXcT/WgBVop3hUjeAS6gs3ZcerpZ/5VNgVW7bMj7u2YZLTcI2zxXH0V/fLQL/9zJa3737Or50IqCdd+PXPt+FbceMAK3+sbrXKEMo7IY3EtzL8tHHVIBUrCIsiJVSHbNh2opanTqC1d54B+hVsg5rA4xH+RVZb6Lc2wKNYQfsiMfNUDhLg9bpclSUAX3vTa/W9LXqkeUm4WdCxxJOe2qM9/BSa04EwhKAInp3plGH7Y1JKbNxkWoVcN8djDPYkX5xKhLxUu5ANA0U+IP194mSRrGZs9SYB9t4qq5Xfb4E7RSmkRhRdgE5uHD1q5lQwrqyFzkmTF1NNRzH/EPmY8jJKiKCw+okINltc2ZM+Cco082+0gog1/+FrCCw88KNj9scOv3hbqpN9HjCwvS+xtQdyNv185aAPqMxZjRPQVXRlUIT4VwXRYU/2KgwjTNs6R7eNFS2Xd0gNcyqXJVKz6kVO8Jo2eCwYTUVIzyYcPzvPm3JCvPA8p5Es9MeDMrUlDXNWhdn3dA5KUcxUMfWkQXteUyXDNo+kMaUq07K7899nsDqCWwXLi65204QlhloZ7L4KwmlW1sgC18BFZeGWCa+qymaN4X99VG5Qfk8PRoVdm0aUAKBtIsXpQlxiJMNNUnSnWguGVso5wW/MoxbYuHwRfSDYovLNWuaPPTkFefs7z/xOREPfoGymYxtZvEYPeLagE0fHLpmsBXo8VJBsycIy7TssY2T6H18OIbPMit1xEMUo8kRDdO+4r95mxNmecAY2wTYrKla+IdApTD/bcmt1wbp3ZPNb+djHeuusvXGoEMYo0SUV8l1jCJJUbLfRJwLVc8ADBrwpVWj77Y2+H6camjUYZqBukQmi3LkoiYbNPFzM7lLSZfYNpi9aICJ78ZO9wBmjE9mz1vF+fl8qE5ebsaMPQGAquQSWZ7WgV/oR0ovbS81mw+qrYnneuxkb+DP1c6yyO51c8D8JpoOs61hQouPdfpTJRj4cNsxGH+iwJEt+vd7gO5gNdaN48KC3tyersYnuI1+R1J1N/xlxKYfPqP0wpPGFctnVSuwd9E2ZVsKJlnKISLrHIPpD5y8FTm8CfKeTzQ10M7RJzbGF5nMECM/BKX8RpoUsXg2VKrQ/7FLs2cWCvdC7vAV1SQ6qxfolgBGDb31ioFTOO/BgUJ38SF4+O4ojwrvCB8h8SHTbv+vfhgeZqAwbEX8w8r9ZXnGdIuJKxutkKQDuzD65VPbWXEvdxyO2mzIncLZuFW6TD7CaHOzvDm8xtKBmuAVyG/1IzbBtW4eTE+vZRSOCftdGlhsf9kOcLUS6P7zZh2UYDiM5PShT0f2Hs0slPREUbh//qlEDSEEZSgRyOeUgso5boL4rStK/DlFLFwXUPIkBA+R+4jntNxZztoUQZ7EHALvZtfodIurEHgwIYszuWngQqCtlQ3EhdOmrrF/K9nz9trgt3zBg47NT4gzbmthtI1gabjw=
**THIS CONTENT IS ENCRYPTED**
 
DECRYPTING...


Ubuntu 安装 Sublime 2

sudo add-apt-repository ppa:webupd8team/sublime-text-2
sudo apt-get update
sudo apt-get install sublime-text-2

Ubuntu 加入自己的字体

假设字体文件夹为:~/Fonts。执行:

sudo mkdir -p /usr/share/fonts/myFonts
sudo cp ~/Fonts/*.ttf /usr/share/fonts/myFonts/
sudo chmod 644 /usr/share/fonts/myFonts/*.ttf
cd /usr/share/fonts/winFonts/
sudo mkfontscale #创建雅黑字体的fonts.scale文件,它用来控制字体旋转缩放
sudo mkfontdir #创建雅黑字体的fonts.dir文件,它用来控制字体粗斜体产生
sudo fc-cache -fv #建立字体缓存信息,也就是让系统认识雅黑



在 Ubuntu 下更改 MYSQL 的字符集

修改 /etc/mysql/my.cnf

[client]
default-character-set=utf8

[mysqld]
character_set_server=utf8

[mysql]
default-character-set=utf8

然后 sudo service mysql restart


LCA 之离线 Tarjan 算法

真是巧妙的算法!

比起树上倍增,Tarjan 算法实现起来更为简单,一个 DFS 加并查集即可。缺点便是:需要先把所有的查询都读进来,并且要储存结果。复杂度为 $O(n+q)$。

Code

var
sets: array [1..100] of longint;
visited: array [1..100] of Boolean;
a: array [1..100, 1..100] of Boolean;
questions: array [1..1000] of record
x, y: longint;
ans: longint;
end;
qn, n, i, m, x, y, root: longint;

function find(x: longint): longint;
begin
if x = sets[x] then exit(x);
sets[x] := find(sets[x]);
exit(sets[x]);
end;

procedure dfs(x: longint);
var
i: longint;
begin
visited[x] := true;
//对于两个节点都已访问到的询问,其结果已经出来了
for i := 1 to qn do
begin
if visited[questions[i].x] and visited[questions[i].y] then
if questions[i].x = x then
questions[i].ans := find(questions[i].y)
else if questions[i].y = x then
questions[i].ans := find(questions[i].x);
end;
for i := 1 to n do
begin
if not a[i, x] or visited[i] then continue;
dfs(i);
sets[find(i)] := x;
end;
end;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

read(n, m);
for i := 1 to n do
sets[i] := i;
for i := 1 to m do
begin
read(x, y);
a[x, y] := true;
a[y, x] := True;
end;
read(root);
qn := 0;
while not eof do
begin
inc(qn);
read(questions[qn].x, questions[qn].y);
end;
dfs(root);
for i := 1 to qn do
writeln(questions[i].ans);

close(input); close(output);
end.

LCA 树上倍增

var
a: array [1..100, 1..100] of boolean;
depth: array [1..100] of longint;
father: array [1..100, 0..16] of longint;
n, m, i, x, y: longint;
root: longint;

procedure dfs(x: longint);
var
i: longint;
j: longint;
begin
depth[x] := depth[father[x][0]]+1;
j := 1;
while 1<<j<=depth[x]-1 do
begin
father[x][j] := father[father[x][j-1]][j-1];
inc(j);
end;
for i := 1 to n do
begin
if not a[x][i] or (father[x][0] = i) then continue;
father[i][0] := x;
dfs(i);
end;
end;

procedure swap(var x, y: longint);
var
t: longint;
begin
t := x;
x := y;
y := t;
end;

function lca(x, y: longint): longint;
var
t, j: longint;
begin
if depth[x] < depth[y] then
swap(x, y);

t := depth[x] - depth[y];
for j := 0 to 15 do
if t and (1<<j) <> 0 then
x := father[x][j];
if x = y then
exit(x);
for j := 15 downto 0 do
if father[x][j] <> father[y][j] then
begin
x := father[x][j];
y := father[y][j];
end;
lca := father[x][0];
end;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

read(n, m);
for i := 1 to m do
begin
read(x, y);
a[x, y] := true;
a[y, x] := true;
end;
read(root);
father[root][0] := root;
dfs(root);
while not eof do
begin
read(x, y);
writeln(lca(x, y));
end;

close(input); close(output);
end.

RMQ(二进制方法)

问题描述

已知数组 a 以及若干个查询 $(x, y)$,求 $a[x..y]$ 之间的最小值。

分析

不难发现:若取 t 使得$2^t\leq y-x+1$且$2^{t+1}>y-x+1$,则有:

$$[x, x+t]\bigcup[y-t+1,y]=[x,y]$$

运用二进制的思想,我们只需预处理出 $i..i+2^k-1$ 之间的最小值,即可快速完成查询。设 $dp[i][j]$ 为 $i..i+2^j-1$ 之间的最小值,则有:

$$dp[i][j]=min(dp[i][j-1],dp[i+2^{j-1}][j-1])$$

Code

var
a: array [1..100000] of longint;
dp: array [1..100000, 0..20] of longint;
n, i: longint;

function min(x, y: longint): longint;
begin
if x < y then exit(x) else exit(y);
end;

procedure init;
var
i, j: longint;
begin
for i := 1 to n do dp[i, 0] := a[i];
j := 1;
while 1<<j-1<=n do
begin
for i := 1 to n-1<<(j-1) do
dp[i, j] := min(dp[i, j-1], dp[i+1<<(j-1), j-1]);
inc(j);
end;
end;

function query(x, y: longint): longint;
var
t: longint;
begin
t := 0;
while (1<<(t+1)<=y-x+1) do inc(t);
query := min(dp[x][t], dp[y-(1<<t)+1][t]);
end;

var
x, y: longint;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

readln(n);
for i := 1 to n do read(a[i]);
init;
while not eof do
begin
read(x, y);
writeln(query(X, y));
end;

close(input); close(output);
end.