当前位置：首页 > news >正文

算法竞赛命题数据生成方法

news 2024/11/15 5:50:07

本文介绍在算法竞赛命题中题目造数据的方法，包括数据生成脚本以及数据正确性验证脚本，代码框架仅供参考。

本文以今年某校实验班考试题目为例，题目传送门，密码：24wksyb

写在前面

命题组在出好题目后，会由验题组进行后续题目验证。为了方便后续验题工作，建议命题人保留项目数据生成脚本，保证代码可读性和可维护性，以便验题组方便直观判断数据生成的质量。

环境准备

windows系统：win10/11

开发工具：Visual Studio Code 或 Sublime Text，本文使用 Sublime Text 3，配置环境 python 3.9.18 和 gcc 4.9.2。

项目准备

创建文件并加载到 sublime 中，建议项目文件目录如下：

其中 Data 文件中放置每个题目的数据，Problems 放置题目题面，README 为项目说明。

每个题目一般包括要素：题目描述，输入格式，输出格式，样例，提示，题解，验题意见。

一道题目的数据文件中，包括 data 文件存储本题的数据文件，标程ans.cpp，输入数据生成脚本 gen_in.py 和输出数据生成脚本 gen_out.py，以及验证脚本 check.bat。

比如下面是桨声灯影题目数据文件：

代码框架

输入数据生成脚本

最常用的就是随机数生成库 random，库中包括函数 randint(a, b) 表示生成 [a,b] 范围的随机整数； uniform(a, b) 表示生成 [a,b] 范围的随机浮点数；choices(seq, k=n) 表示从序列 seq 中随机选择 n 个元素等。

在文件输入输出时，可以采用输入输出重定向的方法。python 中可以使用 sys.stdin 和 sys.stdout 分别重定向标准输入输出到指定文件中。

下面的示例中，把数据生成实现方法写到 Random_data 函数中即可实现在 data 文件中生成编号 1 到 10 的输入文件。

import sys
import random
def Random_data():pass
if __name__ == '__main__':a,b=1,10for i in range(a,b+1):fname='data/'+str(i)+'.in'sys.stdout=open(fname,"w")Random_data()

例如美味生日茶这道题，题目输入要求是两个 $[0,10^{10}]$ 的整数用空格隔开，数据生成代码如下：

import sys
import random
def Random_data():n,m=random.randint(0,10**10),random.randint(0,10**10)print(n,m)
if __name__ == '__main__':a,b=1,10for i in range(a,b+1):fname='data/'+str(i)+'.in'sys.stdout=open(fname,"w")Random_data()

数据的生成需要根据具体题目输入要求来写，在 OI 或者 IOI 赛制中可能分为弱数据和强数据，例如10cm距离这道题目要求 30% 的弱数据，在代码中也可以采用各种方法增加数据的随机程度：

import sys
import randomdef Simple_data():n,l,r=20,0,1000print(n)for _ in range(n):print(random.randint(l,r),random.randint(l,r))
def Strong_data():n,l,r,k=10**6,0,10**9,10**8print(n)for _ in range(n):print(random.randint(l+random.randint(0,1)*k,r),random.randint(l+random.randint(0,1)*k,r))
if __name__ == '__main__':a,b=1,20for i in range(a,b+1):fname='data/'+str(i)+'.in'sys.stdout=open(fname,"w")if i<=6: Simple_data()else: Strong_data()

又如题目文件系统树中的生成随机树形结构，以及强数据生成链状树卡掉递归的方法：

import sys
import random
def Random_data(n=1000,mx=1000):print(n)nodes=[]fa=[-1]p=[i for i in range(n)]random.shuffle(p)for i in range(n):u=random.choice(fa)c=random.randint(0,mx)nodes.append((i,u,c))if i: fa.append(i)else: fa[0]=0for x in nodes:a,b,c=p[x[0]],x[1],x[2]if b!=-1: b=p[b]print(f"{a} {b} {c}")
def Strong_data(n=1000000,l=100000000,r=1000000000):print(n)nodes=[(0,-1,random.randint(l,r))]for i in range(1,n):nodes.append((i,i-1,random.randint(l,r)))p=[i for i in range(n)]random.shuffle(p)for x in nodes:a,b,c=p[x[0]],x[1],x[2]if b!=-1: b=p[b]print(f"{a} {b} {c}")if __name__ == '__main__':a,b=1,10for i in range(a,b+1):fname='data/'+str(i)+'.in'sys.stdout=open(fname,"w")if i==1: Random_data()elif i<=5: Random_data(1000000,1000000000)else: Strong_data()

输出数据生成脚本

根据生成好的输入数据，把题目正解实现好，对于第 i 个数据重定向标准输入到 data/i.in ，标准输出到 data/i.out 中即可。

代码示例如下：

import sysdef Solve():passdef Answer():t=1#t=int(input())while t:Solve()t-=1if __name__ == '__main__':a,b=1,10for i in range(a,b+1):fin='data/'+str(i)+'.in'fout='data/'+str(i)+'.out'sys.stdin=open(fin,"r")sys.stdout=open(fout,"w")Answer()

例如文件系统树题目数据生成代码：

import sysdef Solve():n=int(input())nodes=[tuple(map(int,input().strip().split())) for _ in range(n)]w={}fa=[0 for _ in range(n)]d=[0 for _ in range(n)]root=0for x in nodes:a,b,c=x[0],x[1],x[2]w[a]=cif b==-1: root=aelse:fa[a]=bd[b]+=1q=set()for i in range(n):if d[i]==0: q.add(i)while len(q)>0:v=q.pop()if v==root: continueu=fa[v]w[u]+=w[v]d[u]-=1if d[u]==0: q.add(u)for i in range(n): print(w[i],end=' ')
def Answer():t=1#t=int(input())while t:Solve()t-=1
if __name__ == '__main__':a,b=1,10for i in range(a,b+1):fin='data/'+str(i)+'.in'fout='data/'+str(i)+'.out'sys.stdin=open(fin,"r")sys.stdout=open(fout,"w")Answer()

标程

标程直接放题目正确解题代码即可，建议使用 c/c++，用两种语言验证题目。

数据验证脚本

原理就是用标程跑每一个测试点，结果与对应测试点的输出做对比。

@echo off
setlocal enabledelayedexpansionc++ ans.cpp -o ans.exeif errorlevel 1 (echo Compilation failed.pauseexit /b
)for /l %%i in (1,1,1000000) do (set fin=data\%%i.inset fout=data\%%i.outif not exist !fin! (goto :END)if not exist !fout! (goto :END)ans.exe < !fin! > temp.outfc temp.out !fout! > nulif errorlevel 1 (echo Incorrect for Test %%i) else (echo Correct for Test %%i)
)
:END
del temp.outpause

在文件目录下直接运行脚本：

可以改为测试指定范围的测试点：

@echo off
setlocal enabledelayedexpansion
if "%~1"=="" (echo Please provide the starting file range.exit /b
)
if "%~2"=="" (echo Please provide the ending file range.exit /b
)c++ ans.cpp -o ans.exeif errorlevel 1 (echo Compilation failed.pauseexit /b
)for /l %%i in (%1,1,%2) do (set fin=data\%%i.inset fout=data\%%i.outif not exist !fin! (goto :END)if not exist !fout! (goto :END)ans.exe < !fin! > temp.outfc temp.out !fout! > nulif errorlevel 1 (echo Incorrect for Test %%i) else (echo Correct for Test %%i)
)
:END
del temp.outpause

提供参数为测试点的开始结尾：