日志 - ryp的博客

subxx2datax.py，将 subXXX_XXX.in/out 转化为 dataXXX.in/out 的脚本

2025-04-22 21:04:21 By ryp

import os
import re

patt = re.compile (r"sub([0-9]+)_([0-9]+).(in|out)")
cnt = {  }
print ("将 subXXX_XXX.in/out 转化为 dataXXX.in/out 的脚本")
path = input ("转化目录（如果是当前目录，输入 .）：")
os.chdir (path)

for i in os.listdir ("."):
    if os.path.isdir (i):
        print ("跳过子目录 %s" % i)
        continue
    q = re.findall (patt, i)
    if not q or len (q) != 1:
        print ("%s 不匹配格式 subXXX_XXX.in 或 subXXX_XXX.out，跳过" % i)
        continue
    q = q[0]
    subid = int (q[0])
    pid = int (q[1])
    suff = q[2]
    try:
        cnt[subid] += 1
    except KeyError:
        cnt[subid] = 1
cnt[0] = 0
for i in range (1, len (cnt)):
    try:
        cnt[i] += cnt[i - 1]
    except KeyError:
        raise Exception ("错误：subtask 编号不是连续的！自 %d 处断开" % i)
for i in range (1, len (cnt)):
    if cnt[i] % 2 == 1:
        raise Exception ("Subtask #%d 中 in/out 不配对（文件数量是奇数）" % i)
    cnt[i] /= 2

for i in range (1, len (cnt)):
    os.mkdir ("subtask%d" % i)
    print ("已创建子目录 subtask%d" % i)
copied = 0
covered = []

for i in os.listdir ("."):
    if os.path.isdir (i):
        continue
    q = re.findall (patt, i)
    if not q or len (q) != 1:
        continue
    q = q[0]
    subid = int (q[0])
    pid = int (q[1])
    suff = q[2]

    src = i
    newname = "data%d.%s" % (cnt[subid - 1] + pid, suff)
    dst = "subtask%d/" % subid + newname

    print ("%s -> %s" % (src, dst), end='')
    if os.path.exists (dst):
        print ("（覆盖！）")
        covered.append (dst)
    else:
        print ("")

    os.replace (src, dst)
    copied += 1
print ("已复制 %d 个文件，覆盖了 %d 个文件" % (copied, len (covered)))
print ("被覆盖文件：")
if len (covered) == 0:
    print ("（无）")
else:
    for i in covered:
        print ("--> \t", i)

阅读全文

谁不想搭一个自己的 OJ 呢？UOJ 简易搭建与其对 32 位系统的适配补丁

2025-04-22 21:03:43 By ryp

我相信许多 OIer 或者教练都曾有过搭一个自己的 OJ 的念头。但苦于 OI 并不包含有关服务器运维的任何内容，网络上有关的教程写的也比较简单，所以要么是外包，要么是鸽掉了。

然而，本 OJ，即WyOJ，山东省潍坊第一中学在线测评系统，就是一个非常好的例子。WyOJ 是一个基于 UOJ 的测评系统，利用了机房残留的四台机器搭建而成，总共耗费不到 100 元。如果不需要外网访问，可以做到完全免费搭建。同时，其性能也不错，根据一篇测评，完全可以胜任一般的校内或校级评测。

UOJ 官方要求使用 64 位机器，但实际上只需要做一些简单修改就可以支持 32 位机器。WyOJ 使用的四台机器中，一台是 i3-3240 @ 3.40GHz，另外三台都是 Pentium G2030 @ 3.00GHz。

阅读全文

再再再学红黑树

2025-04-18 23:32:07 By ryp

我已经是第三次学红黑树了。第一次只是把算法导论上头的代码给翻译过来抄了上去，还没调过；第二次囫囵吞枣学了学，大体上搞懂了这玩意儿为啥正确；第三次，也就是这一次，我觉得我才真正明白了这玩意儿的思路是什么样的。

首先红黑树有两条重要性质：

结点有红色黑色之分。红结点的儿子必须是黑的，黑结点的儿子任意。一个结点如果没有儿子，我们指定它的儿子连向一个特殊的黑色结点 NIL。
对于每个结点，它子树中任意一个叶子到它的路径上，经过的黑结点数量必须相同。如果我们定义黑高 $bh(x)$ 表示 $x$ 子树中叶子结点到它所经过的黑色结点数量，那么本条性质可以改写为：每个结点的黑高唯一确定。

事实上有一个不那么显然的性质：NIL 也是结点，所以根到所有 NIL 所经过的黑结点数量要相等。这几条限制共同限制了红黑树的树高是一定的。这个证明不难。可以像算法导论那样归纳证，也可以感性理解：因为最差情况也是红黑颜色交替，而黑高又要相等，因此

红黑树的插入比较简单。首先按照二叉树把新结点插入为一个红叶子。之所以为红，是为了防止调整黑高，不然很麻烦。然后我们需要处理的就是第一条性质。可以递归向上地处理。设当前处理的结点为 $x$，则有三种情况：

如果 $x$ 的父亲不是红色，维护完毕。否则，$x$ 的父亲是红色，$x$ 的祖父一定是黑色
如果 $x$ 的叔叔是红色的，那么我们可以直接把父亲和叔叔设为黑色，祖父变成红色，以在保证黑高不变的同时消除双红。随后，$x$ 更新到其祖父
如果 $x$ 的叔叔是黑色的，我们可以旋转父亲之后，把父亲设为红的，原祖父设为黑的，随后 $x$ 更新为父亲。

插入的核心思想就是消除双红的同时规避处理黑高。这还是比较简单的。

删除稍微麻烦一点儿。

删除一个结点，我们还是按照二叉树的方法。如果它左右儿子之一是空的，就用这个儿子替换它，随后向上更新。否则，找 $x$ 的后继 $y$，用这个后继替换 $x$ 的位置，$y$ 的位置用它的右儿子代替（因为它的左儿子一定空）。

这之后，我们要判断被移动的位置原来是不是个黑结点。把这个原位置叫做 $x$，那么如果 $x$ 原来是黑色的话，$x$ 及其上的所有点的黑高都不再平衡。

随后就是对黑高的修复。我们把当前 $x$ 的状态，看作是有两个黑结点的叠加态，也就是它对黑高的贡献为二，这样可以简单认为黑高没变。我们的任务是把这多余的一个贡献送给别人。

有两种基本情况，和另外两种转化为这两种基本情况的其他情况。

基本情况：

$x$ 的哥哥是黑色，他哥哥的两个儿子也是黑色。此时，我们把多余的黑高送给父亲。同时为了维护哥哥的黑高，我们让哥哥变成黑色。随后，让 $x$ 更新为其父亲。
$x$ 的哥哥是黑色，异向侄子是红色。此时，我们通过改变树的结构来把多余的黑高送出去。首先旋转叔叔，让他成为新的祖父。让原异向侄子变成黑的，以维护他的黑高。由于原哥哥变成了祖父，我们让父亲和它的颜色交换。

另两种情况的主要思路是转化为前两种：