polygon

教程

testlib 库，其中的文件夹中有示例程序。

具体教程

polygon

oi-wiki

polygon 题面支持语法

polygon

速通 generator

  1. https://oi-wiki.org/tools/testlib/
  2. https://oi-wiki.org/tools/testlib/generator/

示例

命令行参数 + 分组数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * gen-array-with-opt   -test-count <num>
 *                      -sum-n <num>
 *                      [-min-n <num>]
 *                      [-min-value <num>] [-max-value <num>]
 *                      [-value-bias <num>]
 * 
 * Generate a test with `test-count` test cases, each test case is an
 * array. The sum of lengths of all arrays will equal `sum-n`.
 * 
 * Arguments:
 * -test-count: specify the number of test cases. Required.
 * -sum-n: specify the sum of array lengths over all test cases. Required.
 * -min-n: specify the minimum array length for all test cases. Default: 1.
 * -min-value: specify the minimum value for the array element. Default: 1.
 * -max-value: specify the maximum value for the array element. Default: 10^9.
 * -value-bias: specify the bias for generating the value. The bigger the
 *  _positive_ value-bias, the closer the element to max-value. The smaller the
 *  _negative_ value-bias, the closer the element to min-value. See rnd.wnext()
 *  function. Default: 0 (no bias).
 */
#include "testlib.h"
#include <vector>
using namespace std;

int main(int argc, char** argv) {
    registerGen(argc, argv, 1);
    
    int test_count = opt<int>("test-count");
    int sum_n = opt<int>("sum-n"); // 必选参数
    int min_n = opt<int>("min-n", 1); // 可选参数，默认 1
    
    int min_value = opt<int>("min-value", 1);
    int max_value = opt<int>("max-value", 1000 * 1000 * 1000);
    int value_bias = opt<int>("value-bias", 0);
    
    vector<int> n_list = rnd.partition(test_count, sum_n, min_n);
    
    println(test_count);
    for (int test_case = 0; test_case < test_count; ++test_case) {
        int n = n_list[test_case];
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            arr[i] = rnd.wnext(min_value, max_value, value_bias); // 不用担心 value_bias 过大导致过慢，过大时会采用另一种生成方式
        }
        println(n);
        println(arr);
    }
}

二分图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "testlib.h"

#include <vector>
#include <set>

using namespace std;

int main(int argc, char *argv[]) {
    registerGen(argc, argv, 1);

    int n = opt<int>(1);
    int m = opt<int>(2);
    size_t k = opt<int>(3);

    int t = rnd.next(-2, 2);

    set<pair<int, int>> edges;

    while (edges.size() < k) {
        int a = rnd.wnext(n, t); // 0 ~ n - 1
        int b = rnd.wnext(m, t);
        edges.insert(make_pair(a, b));
    }

    vector<pair<int, int>> e(edges.begin(), edges.end());
    shuffle(e.begin(), e.end());

    vector<int> pa = rnd.perm(n, 1); // 产生从 1 开始的长度为 n 的随机排列
    vector<int> pb = rnd.perm(m, 1);

    println(n, m, e.size()); // 以空格间隔，\n 为结尾打印，推荐以此打印，防止忘记行末 \n
    for (auto edge: e)
        println(pa[edge.first], pb[edge.second]);
}

输出重定向 + 一次性生成多个数据文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
 * It is another type of generators. It writes several files named 
 * as test indices. 
 *
 * For example, this generator writes 10 files (tests) from 1 to 10.
 * This type of generators is supported by Polygon too, but
 * stdout-generators are more preferred.
 *
 * The generator is for A+B problem, generates 10 tests where each 
 * number is between 1 and 100, and tests grow with indices.
 */

#include "testlib.h"

using namespace std;

void writeTest(int test) {
    startTest(test); // 输出重定向到文件名为 test 对应值的文件中

    int a = rnd.next(1, test * test);
    int b = rnd.next(1, test * test);
    println(a, b);
}

int main(int argc, char *argv[]) {
    registerGen(argc, argv, 1);

    for (int i = 1; i <= 10; i++)
        writeTest(i);
}

以 1 为根的有根树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "testlib.h"

#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
    registerGen(argc, argv, 1);

    int n = opt<int>(1);
    int t = opt<int>(2);

    vector<int> p(n);
    // p[i] is the parent of i-th vertex in 0-numeration without shuffling
    for (int i = 1; i < n; i++)
        p[i] = rnd.wnext(i, t);

    vector<int> perm(n);
    for (int i = 0; i < n; i++)
        perm[i] = i;
    shuffle(perm.begin() + 1, perm.end());

    vector<int> pp(n - 1);
    // pp[i] is the parent of (i+2)-nd vertex in 1-numeration after shuffling
    for (int i = 1; i < n; i++)
        pp[perm[i] - 1] = perm[p[i]] + 1;

    println(n);
    println(pp);
}

无根树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "testlib.h"

#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
    registerGen(argc, argv, 1);

    int n = opt<int>(1);
    int t = opt<int>(2);

    vector<int> p(n);
    for (int i = 1; i < n; i++)
        p[i] = rnd.wnext(i, t); // t 越大越趋近于链，越小越趋近于菊花图

    vector<int> perm = rnd.perm(n);

    vector<pair<int, int>> edges;
    for (int i = 1; i < n; i++)
        if (rnd.next(2))
            edges.push_back(make_pair(perm[i], perm[p[i]]));
        else
            edges.push_back(make_pair(perm[p[i]], perm[i]));

    shuffle(edges.begin(), edges.end());

    println(n);
    for (auto edge: edges)
        println(edge.first + 1, edge.second + 1);
}

连通图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include "testlib.h"

#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
    registerGen(argc, argv, 1);

    int n = opt<int>(1);
    int m = opt<int>(2);
    int t = opt<int>(3, 0);

    vector<int> p(n);
    for (int i = 1; i < n; i++)
        p[i] = rnd.wnext(i, t); // t 越大越趋近于链，越小越趋近于菊花图

    vector<int> perm = rnd.perm(n);

    vector<pair<int, int>> edges;
    set<pair<int, int>> s;
    for (int i = 1; i < n; i++){
        if (rnd.next(2)) {
            edges.push_back(make_pair(perm[i], perm[p[i]]));
        }
        else {
            edges.push_back(make_pair(perm[p[i]], perm[i]));
        }
        s.emplace(perm[i], perm[p[i]]);
        s.emplace(perm[p[i]], perm[i]);
    }
    for (int i = 0; i < m - n + 1; ++i) {
        while (true) {
            int x = rnd.next(n), y = rnd.next(n);
            if (x != y && s.find({x, y}) == s.end()) {
                s.emplace(x, y);
                s.emplace(y, x);
                edges.emplace_back(x, y);
                break;
            }
        }
    }

    shuffle(edges.begin(), edges.end());

    println(n, m);
    for (auto edge: edges)
        println(edge.first + 1, edge.second + 1);
}

其他示例

其他示例

注意事项

generators

option println partition

推荐 println 打印，防止遗忘行末 \n

println 函数，还能传入一个 vector

rnd.partition(test_count, sum_n, min_n);

rnd.perm()

multigen

一些高级语法

validators

read

用来规范数据输入，不能有行末空格，这里也不能有行末换行（标答要有）。

以 inf.readEof() 结束

inf.readString 是读入一整行，包括换行。

inf.readEoln 在 Linux 下读入 LF，在 Windows 下读入 CR LF

inf.readStrictReal 可以限制小数位数

inf.readWord() a word that doesn’t contain any whitespaces

interactors

checkers

即 special judge，应该用一个函数 int readAns(InStream& stream) 来读入选手和标程的答案，在这个函数中只是用来获取答案和检查答案的合法性，然后在主函数中比对选手和标程的答案

fcmp 是答案行完全匹配。

lcmp line 是需要每行的每一项匹配上。一般选择这种或下一种。

wcmp word 只需要每项匹配，不要求在同一行。

rcmp9 精度比较，匹配类似于 wcmp，但是每一项具体比较是靠误差在 1E-9 以内

因为上面这些程序都是根据标准答案的行数来循环的，所以似乎如果选手输出多出几行也是无影响的。这也是标答以换行结尾的原因（就可以检测出是否多输出了）。

program
#program #problem
polygon
https://lllei.top/2023/10/15/polygon/
作者
Lei
发布于
2023年10月15日
许可协议