社区讨论

ODT一些警示后人,并提供C++20数据生成器

P5350序列参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mk0n86sr
此快照首次捕获于
2026/01/05 12:11
上个月
此快照最后确认于
2026/01/08 19:35
上个月
查看原帖
在多次 split 时,都要从大到小。所以在复制范围的时候需要判一下。
CPP
Ptr x1, y1, x2, y2;
if (l1 < l2) {
    y2 = split(r2);
    x2 = split(l2);
    y1 = split(r1);
    x1 = split(l1);
} else {
    y1 = split(r1);
    x1 = split(l1);
    y2 = split(r2);
    x2 = split(l2);
}
删除两个范围时,先删左边,因为如果左边的结尾是右边的开头,则删掉右边后左边的结尾失效。
复制范围时不能把靠左的区间作为 [l1,r1][l1, r1](应该只有我会这样吧)。
数据生成器(需 C++20)
CPP
#include <algorithm>
#include <array>
#include <bitset>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <thread>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#if __cplusplus >= 201703L
#include <any>
#include <filesystem>
#include <optional>
#include <string_view>
#include <variant>
#endif
#if __cplusplus >= 202002L
#include <bit>
#include <compare>
#include <concepts>
#include <format>
#include <numbers>
#include <ranges>
#include <span>
#endif
#if __cplusplus >= 202302L
#ifndef _MSC_VER
#include <flat_map>
#include <flat_set>
#endif
#include <print>
#include <generator>
#endif

#define assert(...)

#define FOR(i, a, b) for (ui i = a; i <= (b); ++i)
#define REP(i, a, b) for (ui i = a; i < (b); ++i)
#define RFOR(i, a, b) for (ui i = (a) + 1; i-- > (b); )
#define RREP(i, a, b) for (ui i = a; i > (b); --i)
using uc = unsigned char;
using ui = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using fp = double;
constexpr ui INF32 = ui(1e9);
constexpr u64 INF64 = u64(1e18);
template <typename T, typename U> inline bool ckmin(T& a, const U& b) {
    if (a < b) {

    }
    return b < a && (a = b, true);
}
template <typename T, typename U> inline bool ckmax(T& a, const U& b) {
    return a < b && (a = b, true);
}

#if __cplusplus < 202302L
#define print(...) std::cout << std::format(__VA_ARGS__)
#endif
using namespace std;
using namespace chrono;
using namespace literals;

mt19937_64 rng{static_cast<ui>(steady_clock::now().time_since_epoch().count())};

template <integral T> T random(T l, T r) {
    assert(l <= r, "randint out of range");
    static uniform_int_distribution<T> uid;
    return uid(rng, typename decltype(uid)::param_type(l, r));
}
template <floating_point T> T random(T l, T r) {
    assert(l <= r, "randfloat out of range");
    static uniform_real_distribution<T> urd;
    return urd(rng, typename decltype(urd)::param_type(l, r));
}

template <typename T>
    requires(integral<T> || floating_point<T>)
vector<T> make_seq(ui n, T l, T r) {
    vector<T> a(n);
    ranges::generate(a, [=]() { return random(l, r); });
    return a;
}

// make permutation
vector<ui> make_perm(ui n) {
    vector<ui> a(n);
    iota(a.begin(), a.end(), 1);
    ranges::shuffle(a, rng);
    return a;
}

// make permutation start at 0
vector<ui> make_perm_0(ui n) {
    vector<ui> a(n);
    iota(a.begin(), a.end(), 1);
    ranges::shuffle(a, rng);
    return a;
}

// make tree
vector<pair<ui, ui>> make_tree(ui n) {
    vector<ui> p = make_perm(n);
    vector<pair<ui, ui>> tree(n - 1);
    for (ui i = 2; i <= n; ++i) {
        tree[i - 2] = {p[random<ui>(1, i - 1) - 1], p[i - 1]};
    }
    ranges::shuffle(tree, rng);
    return tree;
}

// print integral sequence
template <integral T> void print_seq(const vector<T> &a) {
    ui n = ui(a.size());
    for (ui i = 0; i < n; ++i) {
        print("{}{}", a[i], " \n"[i == n - 1]);
    }
}

// print floating_point sequence with k 位
// template <floating_point T>
// void print_seq(const vector<T>& a) {
//
// }

// print tree
void print_tree(const vector<pair<ui, ui>> &a) {
    for (auto [x, y] : a) {
        print("{} {}\n", x, y);
    }
}

template <integral T>
pair<T, T> make_lr(T l, T r) {
    T x = random<T>(l, r), y = random<T>(l, r);
    if (x > y) {
        swap(x, y);
    }
    return {x, y};
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ui n = 10, m = 10, V = 1'000'000'007;
    print("{} {}\n", n, m);
    print_seq(make_seq(n, 0u, V - 1));
    REP(i, 0, m) {
        ui o = random(1u, 6u);
        auto [l, r] = make_lr(1u, n);
        if (o == 1 || o == 6) {
            print("{} {} {}\n", o, l, r);
        } else if (o == 2 || o == 3) {
            ui v = random(0u, V - 1);
            print("{} {} {} {}\n", o, l, r, v);
        } else {
            while (l == r) {
                tie(l, r) = make_lr(1u, n);
            }
            ui len = random(0u, (r - l - 1) / 2);
            ui x = l + len, y = r - len;
            swap(x, r);
            swap(x, y);
            if (random(0u, 1u)) {
                swap(l, x);
                swap(r, y);
            }
            print("{} {} {} {} {}\n", o, l, r, x, y);
        }
    }
}

回复

0 条回复,欢迎继续交流。

正在加载回复...