可以使用本文中提到的数据生成器生成OJ中的测试数据，对自己代码进行测试对拍，或对OJ后台数据进行补充。
先序二叉树生成器
基于Python的cyaron库实现。可以生成若干个二叉树的先序序列。
from cyaron import * global tree global ans def outPut(i): if i > len(tree) or tree[i] == -1: ans.append(0) return ans.append(tree[i]) outPut(i * 2 + 1) outPut(i * 2 + 2) if __name__ == '__main__': _n = [20, 21, 22, 23, 24, 25, 26] _m = ['A'] for ii in range(1, 5): print("working on %d" % ii) io = IO(file_prefix="test", data_id=ii) n = _n[ii % len(_n)] nn = randint(20, 50) io.input_writeln(nn) for j in range(nn): binary_tree = Graph.binary_tree(n) ans = [] tree = [-1] * pow(2, n) tree[0] = 1 for edge in binary_tree.iterate_edges(): i = 0 for i in range(0, len(tree)): if tree[i] == edge.start: break if tree[i * 2 + 1] == -1: tree[i * 2 + 1] = edge.end else: tree[i * 2 + 2] = edge.end outPut(0) res = "" for i in ans: if i == 0: res += "0" else: res += chr(ord(_m[j % len(_m)]) + i - 1) io.input_writeln(res) io.output_gen("ans.exe")
哈夫曼树生成器
基于C++实现，便于生成多组测试数据，本生成器可完美适配赫夫曼树的构建与编码，经过修改后可以适配多种题目。为了避免导致因相同权值造成的多解问题导致的可能答案错误，添加了保证哈夫曼树唯一性的检测函数。
#include <iostream> #include <queue> #include <random> #include <vector> #include <random> #include <ctime> #include <set> #include <algorithm> #include <map> using namespace std; bool checkOnlySolution(vector<int> const v, int const newNumber) { set<int> s; priority_queue<int, vector<int>, greater<>> pq; for (int i = 0; i < v.size(); i++) { s.insert(v[i]); pq.push(v[i]); } pq.push(newNumber); s.insert(newNumber); while (pq.size() > 1) { int a = pq.top(); pq.pop(); s.erase(a); int b = pq.top(); pq.pop(); s.erase(b); if (s.find(a + b) != s.end()) { return false; } s.insert(a + b); pq.push(a + b); } return true; } int main() { srand(time(NULL) * rand() * (time(NULL) % 10)); freopen("5.in", "w", stdout); int totalCases = rand() % 10 + 20; cout << totalCases << endl; while (totalCases--) { int totalNumbers = rand() % 80 + 30; cout << totalNumbers; vector<int> numbers; set<int> s; for (int i = 0; i < totalNumbers; i++) { int newNumber = rand() % 200 + 1; if (s.find(newNumber) == s.end() && checkOnlySolution(numbers, newNumber)) { s.insert(newNumber); numbers.push_back(newNumber); } else { i--; continue; } } for (int i = 0; i < numbers.size(); i++) { cout << " " << numbers[i]; } cout << endl; } return 0; }
哈夫曼树解码生成器
基于C++实现，便于生成多组测试数据，本生成器可完美适配赫夫曼树解码，经过修改后可以适配多种题目。为了避免导致因相同权值造成的多解问题导致的可能答案错误，添加了保证哈夫曼树唯一性的检测函数，并使用随机数函数生成有解或无解的测试序列。
#include <iostream> #include <queue> #include <random> #include <vector> #include <random> #include <ctime> #include <set> #include <algorithm> #include <map> using namespace std; class huffman_tree { public: struct node { int freq; string ch; node *left, *right; node(int freq, string ch, node *left, node *right) : freq(freq), ch(ch), left(left), right(right) {} }; node *root; vector<pair<string, string>> codes; huffman_tree(const vector<pair<string, int>> &freq) { auto cmp = [](node *a, node *b) { return a->freq > b->freq; }; priority_queue<node *, vector<node *>, decltype(cmp)> q(cmp); for (auto &p: freq) { q.push(new node(p.second, p.first, nullptr, nullptr)); } while (q.size() > 1) { node *a = q.top(); q.pop(); node *b = q.top(); q.pop(); q.push(new node(a->freq + b->freq, "0", a, b)); } root = q.top(); q.pop(); dfs(root, ""); } void dfs(node *root, string s) { if (root->left == nullptr && root->right == nullptr) { codes.push_back({root->ch, s}); return; } dfs(root->left, s + "0"); dfs(root->right, s + "1"); } }; bool checkOnlySolution(vector<int> const v, int const newNumber) { set<int> s; priority_queue<int, vector<int>, greater<>> pq; for (int i = 0; i < v.size(); i++) { s.insert(v[i]); pq.push(v[i]); } pq.push(newNumber); s.insert(newNumber); while (pq.size() > 1) { int a = pq.top(); pq.pop(); s.erase(a); int b = pq.top(); pq.pop(); s.erase(b); if (s.find(a + b) != s.end()) { return false; } s.insert(a + b); pq.push(a + b); } return true; } vector<string> solve(vector<int> v) { vector<int> temp(v); sort(temp.begin(), temp.end()); vector<pair<string, int>> freq; for (int i = 0; i < v.size(); i++) { freq.emplace_back(to_string(temp[i]), temp[i]); } huffman_tree tree(freq); vector<string> res; for (int i = 0; i < v.size(); i++) { res.push_back(tree.codes[i].second); } return res; } int main() { srand(time(NULL) * rand() * (time(NULL) % 10)); int totalCases = rand() % 10 + 10; cout << totalCases << endl; vector<char> encodeChars; for (int i = 0; i < 26; i++) { encodeChars.push_back('a' + i); encodeChars.push_back('A' + i); } while (totalCases--) { shuffle(encodeChars.begin(), encodeChars.end(), default_random_engine(rand())); int totalNumbers = rand() % 35 + 15; cout << totalNumbers; vector<int> numbers; set<int> s; for (int i = 0; i < totalNumbers; i++) { int newNumber = rand() % 200 + 1; if (s.find(newNumber) == s.end() && checkOnlySolution(numbers, newNumber)) { s.insert(newNumber); numbers.push_back(newNumber); } else { i--; continue; } } for (int i = 0; i < numbers.size(); i++) { cout << " " << numbers[i]; } cout << endl; for (int i = 0; i < numbers.size(); i++) { if (i) { cout << " "; } cout << encodeChars[i]; } cout << endl; int totalQueries = rand() % 10 + 5; cout << totalQueries << endl; while (totalQueries--) { bool hasSolution = rand() % 5 != 0; if (hasSolution) { vector<string> solutions(solve(numbers)); shuffle(solutions.begin(), solutions.end(), default_random_engine(rand())); for (int i = 0; i < rand() % 30 + 20; i++) { cout << solutions[rand() % solutions.size()]; } } else { for (int i = 0; i < rand() % 50 + 50; i++) { cout << rand() % 2; } } cout << endl; } } return 0; }
多叉树生成器
基于C++实现，便于生成多组测试数据，本生成器可完美适配DS森林叶子编码，经过修改后可以适配多种OJ题，便于生成测试数据进行对拍。
#include <iostream> #include <queue> #include <random> #include <vector> #include <random> #include <ctime> #include <set> #include <algorithm> #include <map> using namespace std; vector<int> getTree(int const numOfNodes, int const numOfBranch) { vector<int> res; map<int, int> m; vector<int> positions; positions.push_back(0); for (int i = 0; i < numOfNodes; i++) { for (int j = 0; j < positions.size(); j++) { swap(positions[rand() % positions.size()], positions[rand() % positions.size()]); } res.push_back(positions.front()); for (int j = 0; j < numOfBranch; j++) { positions.push_back(positions.front() * numOfBranch + j + 1); } positions.erase(positions.begin()); } sort(res.begin(), res.end()); return res; } void prePost(vector<int> &res, vector<int> tree, int numOfBranch, int node); vector<int> getPrePost(vector<int> tree, int const numOfBranch) { vector<int> res; prePost(res, tree, numOfBranch, 0); return res; } void prePost(vector<int> &res, vector<int> const tree, int const numOfBranch, int const node) { int i = 0; for (; i < tree.size() && node > tree[i]; i++) { if (tree[i] == node) { break; } } if (i == tree.size() || node != tree[i]) { res.push_back(-1); return; } res.push_back(node); for (int j = 0; j < numOfBranch; j++) { prePost(res, tree, numOfBranch, node * numOfBranch + j + 1); } } int main() { srand(time(NULL) * rand() * (time(NULL) % 10)); int numOfTrees = 4, numOfBranch = 6; cout << numOfTrees << " " << numOfBranch << endl; int cnt = 0; for (int i = 0; i < numOfTrees; i++) { int upper_bound = rand() % ((52 - cnt) / (numOfTrees - i) / 3) + (52 - cnt) / (numOfTrees - i) / 3; int lower_bound = numOfBranch + 1; int numOfNodes = 0; if (upper_bound <= lower_bound) { numOfNodes = upper_bound; } else { numOfNodes = rand() % (upper_bound - lower_bound) + lower_bound; } vector<int> res = getPrePost(getTree(numOfNodes, numOfBranch), numOfBranch); for (int j = 0; j < res.size(); j++) { if (j) { cout << " "; } if (res[j] >= 0) { if (cnt < 26) { cout << (char) ('A' + cnt); } else { cout << (char) ('a' + cnt - 26); } cnt++; } else { cout << "0"; } } cout << endl; } return 0; }
多叉树的孩子链表法表示生成器
基于C++实现，生成使用孩子链表法表示的多叉树，可以直接适配树的后根遍历（孩子链表法）
#include <iostream> #include <queue> #include <random> #include <vector> #include <random> #include <ctime> #include <set> #include <algorithm> #include <map> using namespace std; int main() { srand(time(NULL) * rand() * (time(NULL) % 10)); int numOfNodes = 50; int indexOfRoot = rand() % numOfNodes; set<int> s; vector<int> nodes; vector<vector<int>> graph(numOfNodes); s.insert(indexOfRoot); nodes.push_back(indexOfRoot); while (nodes.size() < numOfNodes) { int i = rand() % numOfNodes; while (s.find(i) != s.end()) { i = rand() % numOfNodes; } graph[nodes[rand() % nodes.size()]].push_back(i); s.insert(i); nodes.push_back(i); } for (int i = 0; i < numOfNodes; i++) { sort(graph[i].begin(), graph[i].end()); } cout << numOfNodes << " " << indexOfRoot << endl; for (int i = 0; i < numOfNodes; i++) { if (i < 26) { cout << (char) (i + 'A') << " "; } else { cout << (char) (i - 26 + 'a') << " "; } for (int j = 0; j < graph[i].size(); j++) { cout << graph[i][j] << " "; } cout << "-1" << endl; } return 0; }
多叉树的双亲表示法生成器
基于C++实现，生成使用双亲表示法表示的多叉树，可以直接适配树的先序遍历（双亲表示法）
#include <iostream> #include <queue> #include <random> #include <vector> #include <random> #include <ctime> #include <set> #include <algorithm> #include <map> using namespace std; int main() { srand(time(NULL) * rand() * (time(NULL) % 10)); int T = 100; cout << T << endl; while (T--) { int numOfNodes = rand() % 30 + 21; int indexOfRoot = rand() % numOfNodes; set<int> s; vector<int> nodes; vector<vector<int>> graph(numOfNodes); s.insert(indexOfRoot); nodes.push_back(indexOfRoot); while (nodes.size() < numOfNodes) { int i = rand() % numOfNodes; while (s.find(i) != s.end()) { i = rand() % numOfNodes; } graph[nodes[rand() % nodes.size()]].push_back(i); s.insert(i); nodes.push_back(i); } for (int i = 0; i < numOfNodes; i++) { sort(graph[i].begin(), graph[i].end()); } cout << numOfNodes << endl; cout << "A"; for (int i = 1; i < numOfNodes; i++) { if (i < 26) { cout << " " << (char) (i + 'A'); } else { cout << " " << (char) (i - 26 + 'a'); } } cout << endl; for (int i = 0; i < numOfNodes; i++) { if (i) { cout << " "; } if (i == indexOfRoot) { cout << "-1"; } else { for (int f = 0; f < nodes.size(); f++) { for (int j = 0; j < graph[f].size(); j++) { if (graph[f][j] == i) { cout << f; f = nodes.size(); break; } } } } } cout << endl; } return 0; }
图的邻接表表示生成器
基于Python实现，用于生成图的邻接表表示法的测试数据。
from cyaron import * if __name__ == '__main__': for ii in range(1, 6): print("working on %d" % ii) io = IO(file_prefix="", data_id=ii) T = randint(20, 30) io.input_writeln(T) for i in range(T): n = randint(20, 25) m = randint(3 * n, 6 * n) io.input_writeln(n, m) graph = Graph.graph(n, m, self_loop=False, repeated_edges=False) seq = [chr(ord('A') + i) for i in range(0, n)] ans = "" for i in seq: ans += str(i) + " " io.input_writeln(ans.strip()) edges = [] for edge in graph.iterate_edges(): edges.append(chr(ord('A') - 1 + edge.start) + " " + chr(ord('A') - 1 + edge.end)) edges.sort() for i in edges: io.input_writeln(i)
矩阵表示法的图
from cyaron import * if __name__ == '__main__': for ii in range(1, 6): print("working on %d" % ii) io = IO(file_prefix="", data_id=ii) T = randint(20, 30) io.input_writeln(T) for i in range(T): n = randint(20, 25) m = randint(3 * n, 6 * n) io.input_writeln(n) graph = Graph.graph(n, m, self_loop=False, repeated_edges=False) g = [[0 for ii in range(n)] for jj in range(n)] for edge in graph.iterate_edges(): g[edge.start - 1][edge.end - 1] = 1 g[edge.end - 1][edge.start - 1] = 1 ans = str(g).replace('[', '').replace(']', '\n').replace(',', '').replace('\n ', '\n').strip() io.input_writeln(ans)
图的最短路径（无框架）
from itertools import product from random import shuffle from cyaron import * if __name__ == '__main__': for ii in range(1, 6): print("working on %d" % ii) io = IO(file_prefix="", data_id=ii) T = randint(10, 20) io.input_writeln(T) letters = "abcdefghijklmnopqrstuvwxyz" letters += letters.upper() letters_combinations = ["".join(x) for x in product(letters, repeat=2)] for i in range(T): shuffle(letters_combinations) n = randint(20, 25) m = randint(2 * n, 10 * n) tmp = randint(1, 100) al = [n] for j in range(n): al.append(letters_combinations[j]) io.input_writeln(al) graph = Graph.graph(n, m, directed=True, self_loop=False, repeated_edges=False, weight_limit=(10, 100)) g = [[0 for ii in range(n)] for jj in range(n)] for edge in graph.iterate_edges(): g[edge.start - 1][edge.end - 1] = edge.weight matrix = str(g).replace('[', '').replace(']', '\n').replace(',', '').replace('\n ', '\n').strip() io.input_writeln(matrix) io.input_writeln(letters_combinations[randint(0, n)]) io.output_gen("ans.exe")
拓扑排序
from itertools import product from random import shuffle from cyaron import * from random import shuffle as sl from random import randint as rd def random_graph(node, edge): n = node node = range(0, n) node = list(node) sl(node) # 生成拓扑排序 m = edge result = [] # 存储生成的边，边用tuple的形式存储 appeared_node = [] not_appeared_node = node # 生成前n - 1条边 while len(result) != n - 1: # 生成第一条边 if len(result) == 0: p1 = rd(0, n - 2) p2 = rd(p1 + 1, n - 1) x = node[p1] y = node[p2] appeared_node.append(x) appeared_node.append(y) not_appeared_node = list(set(node).difference(set(appeared_node))) result.append((x, y)) # 生成后面的边 else: p1 = rd(0, len(appeared_node) - 1) x = appeared_node[p1] # 第一个点从已经出现的点中选择 p2 = rd(0, len(not_appeared_node) - 1) y = not_appeared_node[p2] appeared_node.append(y) # 第二个点从没有出现的点中选择 not_appeared_node = list(set(node).difference(set(appeared_node))) # 必须保证第一个点的排序在第二个点之前 if node.index(y) < node.index(x): result.append((y, x)) else: result.append((x, y)) # 生成后m - n + 1条边 while len(result) != m: p1 = rd(0, n - 2) p2 = rd(p1 + 1, n - 1) x = node[p1] y = node[p2] # 如果该条边已经生成过，则重新生成 if (x, y) in result: continue else: result.append((x, y)) mat = [[0] * n for i in range(n)] for i in range(len(result)): mat[result[i][0]][result[i][1]] = 1 return node, list(result), mat if __name__ == '__main__': for ii in range(1, 6): print("working on %d" % ii) io = IO(file_prefix="", data_id=ii) T = randint(10, 20) io.input_writeln(T) for i in range(T): n = randint(20, 25) m = randint(n, int(2 * n)) io.input_writeln(n) tp, edges, graph = random_graph(n, m) matrix = str(graph).replace('[', '').replace(']', '\n').replace(',', '').replace('\n ', '\n').strip() io.input_writeln(matrix) io.output_gen("ans.exe")
