Olympiad in Informatics

根据左孩子又兄弟的规则，可以得到如下的代码段。 
1
2
3
4
5
6

fillchar(last,sizeof(last),0);
for i:=1 to n do begin
  readln(a,b);{其中a是b的孩子}
  if last[b]=0 then tree[b].left:=a else tree[last[b]].right:=a;
  last[b]:=a;
end;

last[i]表示i的孩子的最后一个兄弟。 十分简短，留作纪念。

Olympiad in Informatics

少说多做- -||

1.笨小猴

送分，略…… 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

var i,maxn,minn:longint;
    s:string;
    c:char;
    a:array['a'..'z']of longint;
begin
  readln(s);
  for i:=1 to length(s) do inc(a[s[i]]);
  minn:=maxlongint;
  maxn:=0;
  for c:='a' to 'z' do if a[c]<>0 then begin
    if a[c]>maxn then maxn:=a[c];
    if a[c]<minn then minn:=a[c];
  end;
  dec(maxn,minn);
  for i:=2 to trunc(sqrt(maxn)) do if maxn mod i=0 then begin
    c:=#32;
    break;
  end;
  if (c=#32)or(maxn<2) then begin
    writeln('No Answer');
    writeln(0);
  end else begin
    writeln('Lucky Word');
    writeln(maxn);
  end;
end.

2.火柴棒等式

题目火柴棒的数量n最大等于24，扣掉加号、等号只剩下20根。20根显然不可能有五位数（最好情况都是1，但即使如此组成的等式不成立，11111+1=1111）。而如果组成了一个四位数加数，则另一个加数必定<=11。其他情况最多A,B都是3位数。 因此可以先预处理算出组成x（x<10000）需要多少根火柴棒，然后枚举加数A和B。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

const MAT:array[0..9]of integer=(6,2,5,5,4,5,6,3,7,6);
var i,ans,a,b,n:longint;
    need:array[0..9999]of longint;
begin
  for i:=0 to 9 do need[i]:=MAT[i];
  for i:=10 to 99 do need[i]:=need[i mod 10]+need[i div 10];
  for i:=100 to 999 do need[i]:=need[i mod 10]+need[i div 10];
  for i:=1000 to 9999 do need[i]:=need[i mod 10]+need[i div 10];
  readln(n);
  dec(n,4);
  ans:=0;
  for a:=0 to 999 do
    for b:=0 to 999 do if need[a]+need[b]+need[a+b]=n then inc(ans);
  for a:=1000 to 9999 do
    for b:=0 to 11 do if (a+b<=9999)and(need[a]+need[b]+need[a+b]=n) then inc(ans);
  writeln(ans);
end.
Read on →
Olympiad in Informatics

少说多做- -||

1.潜伏者

简单的字符替换，需要注意的是，‘A’..’Z’需要建立一一对应的关系，而不是映射的关系（因为这点错了1个数据，可见数据弱爆了）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

var i:longint;
    c:char;
    code,conv:array['A'..'Z']of char;
    e,d,s:string[100];
begin
  fillchar(code,sizeof(code),' ');
  fillchar(conv,sizeof(conv),' ');
  readln(e);
  readln(d);
  for i:=1 to length(e) do
    if ((code[e[i]]=' ')or(code[e[i]]=d[i]))and((conv[d[i]]=' ')or(conv[d[i]]=e[i])) then begin
      code[e[i]]:=d[i];
      conv[d[i]]:=e[i];
    end else begin
      writeln('Failed');
      close(input);close(output);
      halt;
    end;
  for c:='A' to 'Z' do if code[c]=' ' then begin
    writeln('Failed');
    close(Input);close(output);
    halt;
  end;
  readln(s);
  for i:=1 to length(s) do write(code[s[i]]);
end.

2.Hankson的趣味题

其实这题朴素做法也可以过，甚至比普及组相对应的那题更简单。朴素做法如下： 题目求方程组：gcd(a0,x)=a1 && lcm(b0,x)=b1 由于lcm(a,b)=ab/gcd(a,b)，所以方程组化为： gcd(a0,x)=a1 && gcd(b0,x)b1=b1*x 并且题目已知b1，x必定小于b1，并且b1能够整除x。因此可以考虑枚举x，枚举范围就是1..sqrt(b1)，之所以只枚举到sqrt(b1)，是因为另一半必定为b1 div x，这样可以减少很多没必要的浪费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

{$inline on}
var a0,a1,b0,b1,x,tmp,T,ans:longint;
function gcd(a,b:longint):longint;
  var r:longint;
  begin
    if a<b then begin r:=a;a:=b;b:=r; end;
    r:=a mod b;
    while r<>0 do begin
      a:=b;b:=r;r:=a mod b;
    end;
    exit(b);
  end;
begin
  readln(T);
  while T>0 do begin
    dec(t);
    ans:=0;
    readln(a0,a1,b0,b1);
    for x:=1 to trunc(sqrt(b1)) do if b1 mod x=0 then begin
      if (gcd(a0,x)=a1)and(gcd(b0,x)*b1=b0*x) then inc(ans);
      tmp:=b1 div x;
      if (tmp<>x)and(gcd(a0,tmp)=a1)and(gcd(b0,tmp)*b1=b0*tmp) then inc(ans);
    end;
    writeln(ans);
  end;
end.
Read on →
Olympiad in Informatics

少说多做～！

1.机器翻译

略微思索即可得到O(n)算法，略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var n,m,i,x,head,ans,tail:longint;
    q:array[1..1000]of longint;
    b:array[1..1000]of boolean;
begin
  fillchar(b,sizeof(b),0);
  readln(m,n);
  head:=0;tail:=0;
  ans:=0;
  for i:=1 to n do begin
    read(x);
    if not b[x] then begin
      if tail-head=m then begin
        inc(head);
        b[q[head]]:=false;
      end;
      inc(tail);
      q[tail]:=x;
      b[x]:=true;
      inc(ans);
    end;
  end;
  writeln(ans);
end.

2.乌龟棋

四维动规，用f[k1,k2,k3,k4]表示用了k1张走1格的卡、k2张走2格的卡……那么，此时的位置tmp=1+k1+2k2+3k3+4*k4。走到f[k1,k2,k3,k4]有四种选择：用一张走1格的卡；用一张走2格的卡…… 由于题目规定了用完所有的卡正好走到最后一格，所以答案就是f[b[1],b[2],b[3],b[4]]（b[i]为走i格的卡片的总数）

1
2
3
4
5
6
7
8
9
10
11
12
13

{$inline on}
var i,j,tmp,k1,k2,k3,k4,n,m:longint;
    a:array[0..350]of longint;
    b:array[1..4]of longint;
    f:array[0..40,0..40,0..40,0..40]of longint;
function max(a,b:longint):longint;inline;begin if(a0 then j:=max(j,f[k1-1,k2,k3,k4]);
    if k2>0 then j:=max(j,f[k1,k2-1,k3,k4]);
    if k3>0 then j:=max(j,f[k1,k2,k3-1,k4]);
    if k4>0 then j:=max(j,f[k1,k2,k3,k4-1]);
    f[k1,k2,k3,k4]:=j+a[tmp];
  end;
  writeln(f[b[1],b[2],b[3],b[4]]);
end.
Read on →
Life

新生报到了，新班级，新名字，新妹子(*^__^*)……我发现我们班“晓某”以及“某萍”很多，似乎能把全班都串起来了。于是我就有种冲动，把名字转成有向图！比方说我叫做甲乙丙，那么就有：甲→乙→丙。当然如此艰巨的任务就得交给Mathematica啦，不过我们需要的首先是一份名表（囧啊，名表是我用手机拍下来，然后自己打的，中间少拍了一段，结果还有10多个人不在名表中- -||）

我把名表保存为.csv文件，简单，易导入。我.csv的格式是：第一行是标题，然后从第二行开始，第一列是号数，第二列是名字。这么说来，在导入Mathematica的时候，就要把第一行和第一列去掉。另外Mathematica导入csv会产生二维List，第一维根据行，第二维根据每行的逗号分隔，比方说：{ {1,甲乙丙},{2,乙丙丁}……}。去掉第一列后变成{ {甲乙丙},{乙丙丁}……}，显然我们需要把内括号去掉（也就是把二维降成一维）。导入并处理方法如下：

1
2
3

A = Flatten[
  Drop[Import["C:\Users\Administrator\Desktop\names.csv",
    CharacterEncoding -> "UTF-8"], 1, 1]]

解释一下，Import用来导入文件，其中CharacterEncoding根据你的文件修改（我乱码了N次）。Import后会产生二维List，用Drop[…,1,1]可以删除第一行和第一列。接着再用Flatten[…]把多维提出来变成一维。现在就把名字存在了A中了。 然后我们要创建一个List B，记录有向图的边，也就是甲→乙→丙。两个For搞定：

1
2
3
4

B = List[];
For[row = 1, row  For[char = 1, char < StringLength[A[[row]]], ++char,   B = Append[B,      StringTake[A[[row]], {char}] -> StringTake[A[[row]], {char + 1}]]
  ]
 ]

最后就是画图了，VertexLabeling显示标签，AspectRatio是宽高比，PlotRangePadding是图的内边距，Method是画图算法，DirectedEdges是否显示有向边，MultiedgeStyle是否显示重边，PackingMethod也是画图算法，PlotStyle用来控制点和边的样式：

1
2
3
4
5

GraphPlot[B, VertexLabeling -> True, AspectRatio -> 0.618,
 PlotRangePadding -> 0, Method -> "SpringEmbedding",
 DirectedEdges -> True, MultiedgeStyle -> True,
 PackingMethod -> "ClosestPackingCenter",
 PlotStyle -> {FontFamily -> "Microsoft YaHei", FontSize -> 13}]

合起来就是这样：

1
2
3
4
5
6
7
8
9
10
11
12

A = Flatten[
  Drop[Import["C:\Users\Administrator\Desktop\names.csv",
    CharacterEncoding -> "UTF-8"], 1, 1]]
B = List[];
For[row = 1, row  For[char = 1, char < StringLength[A[[row]]], ++char,   B = Append[B,      StringTake[A[[row]], {char}] -> StringTake[A[[row]], {char + 1}]]
  ]
 ]
GraphPlot[B, VertexLabeling -> True, AspectRatio -> 0.618,
 PlotRangePadding -> 0, Method -> "SpringEmbedding",
 DirectedEdges -> True, MultiedgeStyle -> True,
 PackingMethod -> "ClosestPackingCenter",
 PlotStyle -> {FontFamily -> "Microsoft YaHei", FontSize -> 13}]

This is it~! 下面偷偷展出我们班的名表有向图(*^__^*) ： Read on →

Programming Studies

最近在看MIT OCW的线性代数，本来想自己写个Gauss_Jordan消元法的程序，结果前几天上维基百科的时候碰巧看到了，拷贝过来（Python2）： [python] def gauss_jordan(m, eps = 1.0/(10**10)): “”“Puts given matrix (2D array) into the Reduced Row Echelon Form. Returns True if successful, False if ‘m’ is singular. NOTE: make sure all the matrix items support fractions! Int matrix will NOT work! Written by J. Elonen in April 2005, released into Public Domain”“” (h, w) = (len(m), len(m[0])) for y in range(0,h): maxrow = y for y2 in range(y+1, h): # Find max pivot if abs(m[y2][y]) > abs(m[maxrow][y]): maxrow = y2 (m[y], m[maxrow]) = (m[maxrow], m[y]) if abs(m[y][y]) <= eps: # Singular? return False for y2 in range(y+1, h): # Eliminate column y c = m[y2][y] / m[y][y] for x in range(y, w): m[y2][x] -= m[y][x] * c for y in range(h-1, 0-1, -1): # Backsubstitute c = m[y][y] for y2 in range(0,y): for x in range(w-1, y-1, -1): m[y2][x] -= m[y][x] * m[y2][y] / c m[y][y] /= c for x in range(h, w): # Normalize row y m[y][x] /= c return True [/python] 需要注意的是，由于Python2中整数除法返回整数，所以对于整数矩阵该程序不一定能正常工作，解决办法有：使用浮点数，或者改用Python3。因为Python3中/操作符固定返回浮点数。 下面有个调用的示例： Read on →

Web Design

经常我们都要从表中随机选出一行（或者几行），但是怎么选才会快点呢？这个囧，下面我特地做了个实验：

准备：

生成100,000条数据到speed.t3表中，包括两列，第一列AI不多说，第二列是md5(i)。用PHP生成：

1
2
3
4
5
6
7
8
9
10

<?php
set_time_limit(0);
$conn=mysql_connect("localhost","username","userpwd");
mysql_select_db("speed",$conn);
define("MAXN",1000000);
for ($i=1;$i<MAXN;++$i) {
    mysql_query("insert into `t3` (data) values('".md5($i)."')");
}
mysql_close($conn);
?>

法一： 

1

SELECT * FROM `t3` ORDER BY RAND() LIMIT 0,1;
优点：易于理解，简单，纯SQL语句，不需要有ID列 缺点：可想而知，速度不会快

法二： 

1
2
3
4

$range_result = mysql_query( " SELECT MAX(`id`) AS max_id , MIN(`id`) AS min_id FROM `t3` ");
$range_row = mysql_fetch_object( $range_result );
$random = mt_rand( $range_row->min_id , $range_row->max_id );
$result = mysql_query( " SELECT * FROM `t3` WHERE `id` >= $random LIMIT 0,1 ");
原理：从列中找出ID的最大值和最小值，然后用PHP得到一个[最小,最大]区间内的随机值。由于通过delete，ID可能不连续，所以选取>=该随机值的第一行 优点：比较好理解，速度还不错 缺点：非纯SQL，依赖于外部，需要有ID列

法三： 

1
2
3
4

$offset_result = mysql_query( " SELECT FLOOR(RAND() * COUNT(*)) AS `offset` FROM `t3` ");
$offset_row = mysql_fetch_object( $offset_result );
$offset = $offset_row->offset;
$result = mysql_query( " SELECT * FROM `t3` LIMIT $offset, 1 " );
表示不懂，大概是先得到偏移量然后取偏移量后第一条

法四： 

1

SELECT * FROM `t3` WHERE id >= (SELECT FLOOR( MAX(id) * RAND()) FROM `t3` ) ORDER BY id LIMIT 1
表示完全不懂，用到了一个子查询。

法五： 

1

SELECT t3.* FROM (SELECT FLOOR (RAND() * (SELECT count(*) FROM t3)) num ,@num:=@num+1 from (SELECT @num:=0) a , t3 LIMIT 1) b ,  t3 WHERE b.num=t3.id
有点囧了，更看不懂了

测试

经测试，法四速度极慢，所以注释掉。下面先给出PHP代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

<?php
class runtime
{
    var $StartTime = 0;
    var $StopTime = 0;

    function get_microtime()
    {
        list($usec, $sec) = explode(' ', microtime());
        return ((float)$usec + (float)$sec);
    }

    function start()
    {
        $this->StartTime = $this->get_microtime();
    }

    function stop()
    {
        $this->StopTime = $this->get_microtime();
    }

    function spent()
    {
        return round(($this->StopTime - $this->StartTime) * 1000, 1);
    }

};
function show()
{
    global $result;
    while($row = mysql_fetch_array($result))
    {
        echo $row[0] . " " . $row[1];
        echo "<br />";
    }
}
set_time_limit(0);
date_default_timezone_set("Asia/Shanghai");
$runtime=new runtime;
$conn=mysql_connect("localhost","username","userpwd");
mysql_select_db("speed",$conn);

/*
 * 法一
 */
$runtime->start();
$result=mysql_query("SELECT * FROM `t3` ORDER BY RAND() LIMIT 0,1");
show();
$runtime->stop();
echo "Time: ".$runtime->spent()." ms<br /><br /><br />";

/*
 * 法二
 */
$runtime->start();
$range_result = mysql_query( " SELECT MAX(`id`) AS max_id , MIN(`id`) AS min_id FROM `t3` ");
$range_row = mysql_fetch_object( $range_result );
$random = mt_rand( $range_row->min_id , $range_row->max_id );
$result = mysql_query( " SELECT * FROM `t3` WHERE `id` >= $random LIMIT 0,1 ");
show();
$runtime->stop();
echo "Time: ".$runtime->spent()." ms<br /><br /><br />";

/*
 * 法三
 */
$runtime->start();
$offset_result = mysql_query( " SELECT FLOOR(RAND() * COUNT(*)) AS `offset` FROM `t3` ");
$offset_row = mysql_fetch_object( $offset_result );
$offset = $offset_row->offset;
$result = mysql_query( " SELECT * FROM `t3` LIMIT $offset, 1 " );
show();
$runtime->stop();
echo "Time: ".$runtime->spent()." ms<br /><br /><br />";

/*
 * 法四
 */
/*$runtime->start();
$result = mysql_query( "SELECT * FROM `t3` WHERE id >= (SELECT FLOOR( MAX(id) * RAND()) FROM `t3` ) ORDER BY id LIMIT 1" );
show();
$runtime->stop();
echo "Time: ".$runtime->spent()." ms<br /><br /><br />";*/

/*
 * 法五
 */
$runtime->start();
$result = mysql_query( "SELECT t3.* FROM (SELECT FLOOR (RAND() * (SELECT count(*) FROM t3)) num ,@num:=@num+1 from (SELECT @num:=0) a , t3 LIMIT 1) b ,  t3 WHERE b.num=t3.id" );
show();
$runtime->stop();
echo "Time: ".$runtime->spent()." ms<br /><br /><br />";
?>

得出的结果是：

[plain] 88443 dbb7f0097fe15075a19396229957e7a7 Time: 3625.1 ms

90233 0fd7b7d88bf1d997aec06d8d800bee5a Time: 1.1 ms

514251 9846559706dac43ac7f0546a292be1b5 Time: 847.9 ms

29668 4db3b4270aca22aa23c78c4acf712915 Time: 3.6 ms [/plain] 看来对于有ID的数据，法二和法五还是比较方便的。

Linux Studies, Olympiad in Informatics

背景

由于现在学校的电脑不是特别好（当然也不至于特别烂），运行起Ubuntu有点卡，加上Lazarus watch数组的时候总是以字符数组显示（也就是a = #0#0#0#0之类的），因此决定果断放弃Lazarus，直接用gdb。当然，抛弃了Lazarus，就得用记事本了，我早就想试试vim了，所以vim+gdb已成定局。另外我发先，在窗口模式下切换窗口有点慢（- -||），因此console+vim+gdb的组合就出现啦～！

本文是我一个多星期以来使用console+vim+gdb的心得体会，要获得各个部分的完整指南可以参照各个软件的说明书以及Google之。

console

Ubuntu默认开了6个tty，用Ctrl+Alt+Fx（x=1..6）切换，其中Ctrl+Alt+F7切换到X Window。我的习惯是tty1开vim，tty2开gdb。你可以试试，console的切换是很快的。

Ubuntu 10.04以上（貌似9.10开始就有了）进入系统后，console的分辨率会自动调整到显示器的最佳分辨率，这点很方便，我们一般就不用操心了。之前还要在grub中加vga参数，而且弄得很乱。

另外，要显示中文的话可以安装zhcon，对于Ubuntu 10.04以上，源里面的zhcon还是很好用的。安装好了可以直接输入zhcon进去，一般不会乱码之类的（我记得以前还得加上–dev和–utf8选项，现在就不用那么麻烦了）。zhcon中还有中文输入法，按Ctrl+0~9切换。

vim Read on →

Linux Studies

我学校的电脑上运行着Ubuntu 10.04 LTS，装有firefox3.6，感觉有点老想更新一下。因为是LTS版本，所以软件源更新的不是很快，apt-get没办法升级（显示已经是最新版本）……既然如此，那咱就只好手动升级了，步骤如下：

先下载对应平台的firefox二进制压缩包（x86_64的朋友一定要注意找到正确版本，直接下载基本上都是x86的，否则会导致各种问题，你懂的）。然后就是命令行（这里以firefox-5.0.1为例）：

1
2
3
4
5
6

abcdabcd987@stu36:~/Download$ tar xf firefox-5.0.1.tar.bz2
abcdabcd987@stu36:~/Download$ sudo mv firefox /usr/local/lib/firefox-5.0.1
[sudo] password for abcdabcd987:
abcdabcd987@stu36:~/Download$ sudo rm /usr/bin/firefox
abcdabcd987@stu36:~/Download$ sudo ln -s /usr/local/lib/firefox-5.0.1/firefox /usr/bin/firefox
abcdabcd987@stu36:~/Download$

然后重新运行firefox就好了～！ 至于/usr/local/lib/firefox-5.0.1这个路径则不是乱写的，要跟你解压出来的firefox文件夹中的firefox文件里面的moz_libdir变量的值相同！

其实firefox本来就是绿色的，放到随便一个目录下运行firefox都是可以的，但是按照如上方法更新可以将更新应用于整个系统，而且运行firefox也比较方便。

Olympiad in Informatics

[RQNOJ 29][stupid]愚蠢的组合数这题看一眼就知道是求C(n,k)的奇偶性，其实貌似这题只不过是PKU3219的包装版本……由C(n,k)=n!/(k!*(n-k)!)可以知道，只要能够算出n!, k!, (n-k)!中因子2的个数就能够得出答案。关键就在于如何计算n!中因子2的个数。

那天请教了下lzc，发现一个很快速的方法。计算n!中2因子的个数=[n/21]+[n/22]+[n/23]+…+[n/2[lg(n)]]其中lg(n)表示log2(n)，[x]表示下取整。原理也很简单：

[n/21]，统计了1~n中2的倍数的个数，也就是先统计了一部分的2因子。

[n/22]，又统计了4的倍数的个数，由于4=2*2，之前去掉一个2了，所以这一遍就加上剩下的这个2，不多不少。

……

直到[n/2[lg(n)]]。这样就把12…*n中所有的2因子都取出来了。

在写程序的时候，就是不断的x/=2;ans+=x;直到x=0。另外，由于计算机计算除法的时间是乘法的五六倍，而位运算则和加减乘速度相同，所以除以2可以直接看成是向右移动一位，这样效率就高多了（常数级的优化）。

代码如下： Read on →