如题。

山东省第三轮省队集训题目现只对潍坊一中内部用户开放。

本机

import os

WYOJ_HOST = "192.168.137.4"

print ("上传 PDF 题面。")
print ("原有的题面会完全丢失！！！")
print ("不能使用网页端更改题面！！！")
pidst = int (input ("题目编号起始值（含）："))
pided = int (input ("题目编号终止值（含）："))
lpath = input ("PDF 题面路径：")
if not os.path.exists (lpath):
    raise Exception ("没有这个文件，唐氏儿")

def execute (s):
    print ("运行本机命令：%s" % s)
    if os.system (s):
        raise Exception ("本机命令运行错误")

for pid in range (pidst, pided + 1):
    rpath = "pdfstat%d.pdf" % pid
    execute ("scp %s ryp@%s:/home/ryp/%s" % (lpath, WYOJ_HOST, rpath))
    execute ("ssh ryp@%s ./pdf-update %d %s" % (WYOJ_HOST, pid, rpath))

远端

#!/bin/python3
import os
import sys

if len (sys.argv) != 3:
    raise Exception ("参数数量错误")

pid = int (sys.argv[1])
lpath = sys.argv[2]
if not os.path.exists (lpath):
    raise Exception ("文件未找到")

def execute (s):
    print ("执行远端命令：%s" % s, file=sys.stderr)
    if os.system (s):
        raise Exception ("远端命令运行失败", file=sys.stderr)

rpath = "/opt/uoj/web/upload/statement%s.pdf" % pid
execute ("sudo docker cp %s uoj-web:%s" % (lpath, rpath))
execute ("sudo docker exec uoj-db mysql -proot app_uoj233 -e \"update problems_contents set statement_md = "
         "'<iframe src=\"/upload/statement%d.pdf\" width=\"100%%\" height=\"1000\"></iframe>' where id = %d;\"" % (pid, pid))
execute ("sudo docker exec uoj-db mysql -proot app_uoj233 -e \"update problems_contents set statement = statement_md where id = %d;\"" % pid)
execute ("rm %s" % lpath)

自动配置 problem.conf

自动将 subXX_XX.in/out 转化为 subtaskX/X.in 格式脚本

WyOJ 快速数据上传脚本

WyOJ PDF 题面上传脚本

带有 WyOJ 前缀的，是只有在机房的路由机器（也就是那台 Windows 10）上才可以运行的。

import re
import os

# 输入、输出文件后缀。可更改
insuf, outsuf = "in", "out"

print ("problem.conf 自助配置")
path = input ("输入数据目录：")
os.chdir (path)

spjp, stdp, valp, subtaskp = False, False, False, False

def continuep ():
    s = input ("要继续吗？（y/N）")
    if s != "y":
        exit (1)

for s in os.listdir ("."):
    if s == 'problem.conf':
        print ("警告：problem.conf 已存在，将会被覆盖")
        continuep ()

    if s == 'chk.cpp':
        spjp = True
    if s == 'std.cpp':
        stdp = True
    if s == 'val.cpp':
        valp = True
    if os.path.isdir (s) and re.match ("subtask[0-9]*", s):
        subtaskp = True

output = open ("problem.conf", "w")
chker = None
if spjp:
    print ("识别到 chk.cpp，已启用 Special Judge")
else:
    chker = input ("未识别到 chk.cpp，请输入自定义校验器类型：")
print ("use_builtin_judger on", file=output)
if chker:
    print ("use_builtin_checker %s" % chker, file=output)

if subtaskp:
    print ("识别到 subtaskX 目录，自动识别 Subtask 中")
else:
    print ("未识别到 subtaskX 目录，自动尝试普通配置（如果你认为 Subtask 存在，但文件名格式为 subXX_XX.in/out，尝试使用 subxx2datax.py 脚本）")


tlim = int (input ("时间限制（秒）："))
mlim = int (input ("空间限制（MB）："))
print ("time_limit %d\nmemory_limit %d" % (tlim, mlim), file=output)
patt = re.compile ("([A-Z]*[a-z]*[A-Z]*)([0-9]+).(%s|%s)" % (insuf, outsuf))

def processdir (path):
    tcases = 0
    pre = None

    for s in os.listdir (path):
        if os.path.isdir (s):
            continue
        q = re.findall (patt, s)
        if len (q) != 1:
            continue
        print ("识别到数据文件 %s" % s)
        q = q[0]
        if not pre:
            pre = q[0]
        elif pre != q[0]:
            raise Exception ("数据文件前缀不相同！同时找到了 %s 与 %s，自动配置失败。" % (pre, q[0]))
        if int (q[1]) > tcases:
            tcases = int (q[1])
    if tcases == 0 or not pre:
        raise Exception ("无法自动识别数据文件")
    return (tcases, pre)

if not subtaskp:
    tcases, pre = processdir (".")
    print ("找到 %d 个测试点" % tcases)
    print ("n_tests %d" % tcases, file=output)
    print ("n_ex_tests 0\nn_sample_tests 0", file=output)
    print ("input_pre %s\ninput_suf %s" % (pre, insuf), file=output)
    print ("output_pre %s\noutput_suf %s" % (pre, outsuf), file=output)
    print ("自动配置结束！")
else:
    tcases, subs = 0, 0
    pre = None
    subtptt = re.compile ("subtask([0-9]*)")
    end = {  }

    for s in os.listdir ("."):
        if os.path.isdir (s):
            q = re.findall (subtptt, s)
            if len (q) != 1:
                print ("忽略非 Subtask 目录 %s" % s)
                continue
            print ("找到 subtask 目录 %s" % s)
            subs += 1
            nc, spre = processdir (s)
            if not pre:
                pre = spre
            elif pre != spre:
                raise Exception ("Subtask 间文件前缀不同！同时找到了 %s 与 %s，自动配置失败。" % (pre, spre))
            end[int (q[0])] = nc
            if nc > tcases:
                tcases = nc
    print ("n_tests %d\nn_ex_tests 0\nn_sample_tests 0" % tcases, file=output)
    print ("input_pre %s\ninput_suf %s" % (pre, insuf), file=output)
    print ("output_pre %s\noutput_suf %s" % (pre, outsuf), file=output)
    print ("找到 %d 个 Subtask，共 %d 个测试点" % (subs, tcases))

    scs = 100.0 / subs
    print ("正在按照每个 Subtask 等分配置（%.2f 分）" % scs)
    print ("n_subtasks %d" % subs, file=output)
    for i in range (1, subs + 1):
        print ("subtask_end_%d %d" % (i, end[i]), file=output)
        print ("subtask_score_%d %.2f" % (i, scs), file=output)

output.close ()

本机：

import os
import random

rhost = "ryp@192.168.137.4"

def upload (pid, path):
    if not os.path.exists (path):
        raise Exception ("文件不存在。")

    rpath = "upload%d-%d.zip" % (pid, random.randint (1, 32767))
    print ("上传数据中")
    if os.system ("scp %s %s:%s" % (path, rhost, rpath)):
        raise Exception ("上传数据失败")
    print ("数据上传完毕。正在处理")
    if os.system ("ssh %s ./upload %d %s" % (rhost, pid, rpath)):
        raise Exception ("解压失败")
    print ("完毕！现在请在网页端题目管理界面单击 校验配置并同步数据。")
    os.system ("pause")

print ("选项（1：上传单个数据；2：上传一组数据（要求题目编号连续、ZIP 存档名称格式为 题目编号.zip））：")
opt = int (input ())

if opt == 1:
    pid = int (input ("题目 ID："))
    path = input ("数据存档（必须是包含 problem.conf 的 ZIP 存档；子文件夹中的文件将会被移动到根，其中的同名文件会随机覆盖，）：")
    upload (pid, path)
elif opt == 2:
    fails = []
    st = int (input ("编号区间起始值（含）"))
    ed = int (input ("编号区间结束值（含）"))
    for i in range (st, ed + 1):
        if not os.path.exists ("%d.zip" % i):
            raise Exception ("未找到文件 %d.zip" % i)
    for i in range (st, ed + 1):
        print ("上传数据 %d 中" % i)
        try:
            upload (i, "%d.zip" % i)
        except Exception:
            print ("上传 %d 数据失败。尝试下一道题目……" % i)
            fails.append (i)
        else:
            print ("上传 %d 数据成功" % i)
    print ("上传结束。共有 %d 道题失败（%.3f%%）" % (len (fails), 100.0 * len (fails) / (ed - st + 1)))
    print ("失败题目：")
    if len (fails) == 0:
        print ("（无）")
    else:
        for i in fails:
            print (i, end="; ")
else:
    raise Exception ("无效选项")

远端：

#!/bin/python3
import os
import sys
import random

def exec (s):
    print ("执行远端命令：%s" % s, file=sys.stderr)
    if os.system (s):
        raise Exception ("远端命令执行失败！")
def info (s):
    print (s, file=sys.stderr)

if len (sys.argv) != 3:
    raise Exception ("参数数量错误")

pid = int (sys.argv[1])
lpath = sys.argv[2]
rpath = "data%d-%d.zip" % (pid, random.randint (1, 32767))
info ("正在复制到容器")
exec ("sudo docker cp %s uoj-web:/tmp/%s" % (lpath, rpath))
info ("正在清空原数据")
exec ("sudo docker exec uoj-web rm -rf /var/uoj_data/upload/%d" % pid)
exec ("sudo docker exec uoj-web rm -rf /var/uoj_data/%d" % pid)
info ("正在解压数据")
exec ("sudo docker exec uoj-web unzip -q /tmp/%s -d /var/uoj_data/upload/%d" % (rpath, pid))
exec ("sudo docker exec uoj-web unzip -q /tmp/%s -d /var/uoj_data/%d" % (rpath, pid))
exec ("sudo docker exec uoj-web rm /tmp/%s" % rpath)
info ("正在展开数据（第一次）")
exec ("sudo docker exec uoj-web bash -c \'"
      "cd /var/uoj_data/upload/%d; "
      "for f in `find -type f`; do mv $f `basename $f`; done;"
      "for f in `find -type f -maxdepth 1 ! -name '.'`; do rm -rfv $f; done;\'" % pid)

info ("正在展开数据（第二次）")
exec ("sudo docker exec uoj-web bash -c \'"
      "cd /var/uoj_data/%d; "
      "for f in `find -type f`; do mv $f `basename $f`; done;"
      "for f in `find -type f -maxdepth 1 ! -name '.'`; do rm -rfv $f; done;\'" % pid)
print ("删除临时数据包")
exec ("rm %s" % lpath)
print ("完毕！")

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)

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

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

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

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

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

• 结点有红色黑色之分。红结点的儿子必须是黑的，黑结点的儿子任意。一个结点如果没有儿子，我们指定它的儿子连向一个特殊的黑色结点 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$ 的哥哥是黑色，异向侄子是红色。此时，我们通过改变树的结构来把多余的黑高送出去。首先旋转叔叔，让他成为新的祖父。让原异向侄子变成黑的，以维护他的黑高。由于原哥哥变成了祖父，我们让父亲和它的颜色交换。

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

• $x$ 的哥哥是红色。

Special Judge 与 Hack 已可用！

WyOJ，代表山东省潍坊第一中学在线评测系统！

本 OJ 基于 UOJ 搭建。评测机利用了机房残留的两台奔腾机器，因此 评测机是 32 位的。支持 C++20 / C++14，暂不支持 __int128！！（希望不要因此被喷，然而不甚可能）

WyOJ 评测机性能简单测评 可见此。

另外，可以利用 【模板】后缀排序、【模板】普通平衡树 测试常数。

WyOJ 上我的普通平衡树记录, 325ms, 4592kb LibreOJ 上我的普通平衡树记录, 164ms, 2.5M

WyOJ 使用内存盘作为评测目录，因此 IO 速度不错：1e6 个 32 位正整数读入并输出，关同步流且用 '\n' 替换 endl，大约需要 230ms。使用 putchar 快读快写，大概需要 270ms。其他快读尚未测试。

普通快读快写暂不如 cin/cout 快！！

请不要使用 endl 作为换行。