造题记录：如何出强制在线题

今天造了一个数据结构题，具体题面是什么就不说了，题目名称是 sosomst。输入格式是，第一行 \(n, typ\)，接下来两行的点权，然后是一棵树。输出 \(n-1\) 行的数字，树边强制在线。以下是我生成这题数据的方法。

std.cpp

肯定是自己写了，但是先不要实现强制在线。将 std.cpp 编译为可执行文件 main。

online.py

可以运行完 std 跑出 answer 之后，再对 input 进行加密。这里写一个程序 online.py，使用 python online.py in ans 将 in 进行加密。用到 sys.argv，表示命令行参数。程序首先读取了 in，然后根据 ans 加密了 in。

import os, sys

assert(len(sys.argv) >= 3)

inf = sys.argv[1]
ans = sys.argv[2]

with open(inf, "r") as file:
    readLn = file.readline
    n, typ = map(int, readLn().split())
    A = map(int, readLn().split())
    B = map(int, readLn().split())
    op = []
    for i in range(1, n):
        x, y = map(int, readLn().split())
        op.append((x, y))

with open(inf, "w") as file:
    with open(ans, "r") as outf:
        readLn = outf.readline
        print(n, typ, file=file)
        print(" ".join(map(str, A)), file=file)
        print(" ".join(map(str, B)), file=file)
        z = 0
        for x, y in op:
            if typ == 0:
                print(x, y, file=file)
            else:
                print(x ^ z, y ^ z, file=file)
            z = int(readLn())

mker.py

生成输入文件，然后跑出 ans，再对输入加密。

可以用形如 " ".join([f"{rnd(1, v)}" for i in range(n)]) 快速生成一行 \(n\) 个随机数，用到了 python 的列表推导 [func(i) for i in range(n)]，其中 func(i) 在这里是 f"{rnd(1, v)}" 相当于 str(rnd(1, v))。外面使用 str.join 方法，它接受一个 str 类型的列表，用分隔符连接，所以在生成随机数后马上将其转化为 str 类型。

print("\n".join([f"{per[rnd(0, i - 1)]} {per[i]}" for i in range(1, n)])) 这个就是随机了一棵树，每个点 \(i\) 随机 \([1, i-1]\) 中的一个点作为父亲，再随机打乱节点编号。生成一共 \(n-1\) 个 str，用换行链连接输出。

外部的 make 直接重写了 print 的默认输出文件，print 的文件可以通过 print(a, file=file) 重定向，默认是 file=sys.stdout。首先保存一份 sys.stdout，然后将 sys.stdout 赋值为 open("in", "w")，跑 makeIn，再将 sys.stdout 摁回去。然后进行 os.system 调用。

import sys, os, random
rnd = random.randint

def makeIn(n, typ, v = int(1e8), mode = 0):
    print(n, typ)
    print(" ".join([f"{rnd(1, v)}" for i in range(n)]))
    print(" ".join([f"{rnd(1, v)}" for i in range(n)]))
    if mode == 0:
        per = [i + 1 for i in range(n)]
        random.shuffle(per)
        print("\n".join([f"{per[rnd(0, i - 1)]} {per[i]}" for i in range(1, n)]))
    else:
        print("\n".join([f"{i} {i + 1}" for i in range(1, n)]))

def make(name, n, typ, v = int(1e8), mode = 0):
    name = "./data/sosomst" + name
    temp = sys.stdout
    with open(name + ".in", "w") as file:
        sys.stdout = file
        makeIn(n, typ, v, mode)
    sys.stdout = temp
    os.system(f"./main < {name}.in > {name}.ans")
    os.system(f"python3 online.py {name}.in {name}.ans")

造数据

使用 python 调出 python console，然后 from mker import * 将 mker.py 中的所有东西导入（import mker 的效果是 mker.make()，不好用）。然后直接在 console 中使用 make("0-0", n, 0, v = int(1e7), mode = -1) 之类的方法直接动态使用。

config.yml

编写 config.py，它应当对所有测试点，分好 subtask，调好对应的分数和时空限制。首先获取这些测试点的名字，使用 linux 下的 find（我是 windows.wsl 环境）找出名字，形如 find . -name 'sosomst{id}-?.in'，这里的单引号里面是正则表达式（支持简单的 * 和 ?）。因为 os.system 的返回值不是那个命令的返回值，因此可能需要将 find 的输出重定向到文件然后再读取。

def getTest(id):
    os.system(f"find . -name 'sosomst{id}-?.in' > __temp__")
    with open("__temp__", "r") as file:
        content = str(file.read())
    return content.split()

然后枚举 subtask 编号和分数进行赋分。

with open("./data/config.yml", "w") as file:
    for sid, score in [(i, 10 + (10 if i in [4, 5] else 0)) for i in range(8)]:
        for name in map(lambda s: s[7:], getTest(sid)):
            print(name + ":", file=file)
            print(f"  timeLimit: 2000", file=file)
            print(f"  memoryLimit: 512000", file=file)
            print(f"  score: {score}", file=file)
            print(f"  subtaskId: {sid}", file=file)