如何用python寫NOIP的數據生成器來對拍？

01-08

想要學會對拍

當然是CYaRon

你是否遇到以下情況：

希望在5分鐘內寫出一組隨機數據，並方便地使用它們對拍幾個程序
希望生成一個合適的隨機圖或者樹，且有一定強度
希望生成一組隨機數列或者向量，且不能重複。

那麼，你可以藉助 CYaRon 和 Python ，來快速生成一組數據。目前支持的特性有：

建一個隨機圖（簡單圖或者非簡單圖，有向圖或無向圖，帶權圖或者無權圖）
建一個隨機樹（鏈狀、隨機樹、或者菊花圖，而且可以設定樹的強弱）
生成一組允許相同或者互相不同的多維向量（可以較快速度生成10^6組、範圍到10^9的向量或者數列）
根據函數解析式生成數列
生成一些隨機多邊形，並且可以求面積、周長等
從字典生成隨機字元串、單詞、句子、段落
使用以上功能生成的數據和您其他地方下載的測試數據方便地進行程序對拍

使用pip即可安裝

pip install cyaron

之後直接在生成器中import即可，Github倉庫wiki中有詳細的使用文檔。

對拍，其實就是自己的數據生成器 -&> 很慢很慢的暴力、不一定快的程序 -&> 校驗運行的過程。

其實對拍有兩種方式。一種是要求在考場上儘快地寫出來的對拍器，不一定要求功能多，但要求一定要能夠快點寫得出來然後檢驗自己的程序到底對不對；另一種是平常在自己電腦上訓練時寫的程序，這時我們就希望功能什麼的越實用越好，軟體複雜度並不是問題。

我們來舉個例子。

#!/bin/bash flags="-O0"; g++ $2.cpp $flags -o ./$2; g++ $3.cpp $flags -o ./$3; python $1.py &> $1-data.in; cat ./prob.in | ./$2 &> $1-data.ans; cat ./prob.in | ./$3 &> $1-data.out; rm ./$2 ./$3; diff $1-data.ans $1-data.out

比如上面這個程序，在考場上一到兩分鐘就能寫出來，運行時候執行 pai.sh gen std my 就行了。對應的文件分別是 gen.py std.cpp 和 my.cpp。

當然如果貴方有更快的做法當然更好，在下洗耳恭聽。

接下來到了安利本地對拍器的時候了。想當年無聊時寫的數據生成器的基於 Python 的描述語言，雖然無聊但是用處其實很大。基本上一個生成器在 10 行內就能搞定，而且邏輯十分清晰。

比如這一段代碼（bzoj1177: [Apio2009]Oil）

from pydatagen import * _, m, n = rand(list, 2, int, 5, 10) k = rand(int, 1, min(m, n)) a = rand(list, m, list, n, int, 1, 500) printf(" ".join((" ".join(str(i) for i in j[1:]) for j in a[1:])))

是不是很明了？（並不，其實老版本是有直接輸出數組（二維也算）的，但是後來在 refactor 時扔掉了，應該是為了強制規範使用 for 的緣故）

但是不管您用不用 pydatagen（jeffswt/pydatagen），這都沒有關係，因為：

您都可以自由地使用離線評測姬！

也是曾經無聊的時候寫的評測姬，支持多種類型的輸入，諸如已經造好的數據、輸出，或者是自己寫的數據生成器。不管什麼語言（您用的是 Java、Python、C++ 還是 Pascal）都可以輕鬆用 pyjudge 進行對拍。

例如，我有一個數據生成器，要測試 5 次：

pyjudge -i input.py -o std.cpp -c my.cpp -x 5

後來又寫了個超慢的程序，結果不停 TLE：

pyjudge -i input.py -o std.cpp -c my.cpp -t 2 -x 5

然後你果斷地發現需要標準數據，然後就：

pyjudge -i magic/magic.in* -o magic/magic.out* -c my.cpp -t 2 -x 10

諸如此類的用法...（magic 就是ネタ某年北京冬令營 Hockey 出題公然[政治敏感]）

而且，不僅如此，pyjudge 還能以更好的圖形輸出使你更快速地查錯：

pyjudge -v results.json # 一定要先跑一遍然後查看結果

是不是很好用？

但是話說在前頭，MB 級的數據就不要用 -v 了，除非你相信 Chrome 不會搞炸你的電腦

關於我自己的安利就說這麼多。

其實業界還有很多良 (wu) 心 (liang) 的離線測評，例如 Cena 和 Lemon，也有很多很良心的離線測評機，比如 @xmcp 的 xmcp/pyMatcher，在易用性上雖然不及 pyjudge，但是針對大數據的優化很好（畢竟用的 tkinter）。

當然，熟悉一個 20 行內的對拍腳本才是最重要的，同時還要考慮有些省在 Windows 上比賽的情況所以要用 C++ 對拍...（沒錯，說的就是我省）

蛤？

如果只是用py寫數據生成器的話……跟cpp沒什麼兩樣吧

仿照題中的數據格式和要求生成數據，然後輸出到文件里

應該只需要用到兩個除了基礎語句以外的操作

一個是生成隨機數

首先要引用random模塊：

import random

然後使用裡邊的randint函數，有兩個參數，分別是下限和上限：

print random.randint(a, b)

（其中a和b分別表示下限和上限

其次就是輸出到文件

我一般直接重定向標準輸出流（需要引用sys模塊

import sys sys.stdout = open("input.in","w")

最好在最後把文件關掉：

sys.stdin.close()

如果要寫（用來）對拍（的）程序的話就是另一回事了

有點跑題不過以下策略感覺通用

寫gen，進行對拍實際上c c++ py 這些oi中能用語言都能實現

事實上你需要掌握的是以下三個方面的內容

一、如何操作文件(命令行，py，c/c++

)，並進行diff

二、如何生成數據（合法，有強度，有測試重心）

三、寫一個正確的暴力

至於每一步 Google or Baidu基本有滿意的答案

學一學random庫

學一學各種圖怎麼構建

學一學文件讀寫（open函數）

就ok咯