算法模版-杂类

发表于 更新于 分类于 阅读次数： 本文字数： 3.1k
杂类模版，包括对拍、int128io等，慢慢更新。

杂类

对拍模版（Linux/MacOS）

数据生成器

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
50
51
52
53
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
int r(int a, int b) { return rnd() % (b - a + 1) + a; }

void graph(int n, int root = -1, int m = -1) {
    std::vector<std::array<int, 2>> t;
    for (int i = 2; i <= n; i++) {
        t.push_back({i, r(1, i - 1)});
    }
    std::vector<std::array<int, 2>> edge;
    std::set<std::array<int, 2>> uni;
    if (root == -1) {
        root = r(1, n);
    }
    for (auto [x, y] : t) {
        x = (x + root + n - 1) % n + 1;
        y = (y + root + n - 1) % n + 1;
        edge.push_back({x, y});
        uni.insert({x, y});
    }
    if (m != -1) {
        for (int i = n; i <= m; i++) {
            while (true) {
                int x = r(1, n), y = r(1, n);
                if (x == y) {
                    continue;
                }
                if (uni.count({x, y})) {
                    continue;
                }
                edge.push_back({x, y});
                uni.insert({x, y});
            }
        }
    }
    std::shuffle(edge.begin(), edge.end(), rnd);
    for (auto [x, y] : edge) {
        std::cout << x << " " << y << " " << r(0, 1) << std::endl;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    return 0;
}

对拍程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

void solve() {
    while (true) {
        system("./seed > in.txt");
        system("./baoli < in.txt > baoli.txt");
        system("./wrong < in.txt > wrong.txt");
        if (system("diff baoli.txt wrong.txt")) {
            puts("WA");
            return;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

__int128 输入/输出

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ostream& operator<<(ostream& os, __int128 t) {
    if (t==0) return os << "0";
    if (t<0) {
        os<<"-";
        t=-t;
    }
    int a[50],ai=0;
    memset(a,0,sizeof a);
    while (t!=0){
        a[ai++]=t%10;
        t/=10;
    }
    for (int i=1;i<=ai;i++) os<<abs(a[ai-i]);
    return os<<"";
}

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
istream & operator>>(istream& is, __int128 &t) {
    string s;
    bool f=0;
    is>>s;
    t=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='-'){
            f=1;
            continue;
        }
        t*=10;
        t+=s[i]-'0';
    }
    if(f)t=-t;
    return is;
}

三分（整数域）

最多次数是 \(2\lceil \log_\frac{3}{2}n\rceil\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lo = 1, hi = 1e5;
    while (lo < hi) {
        int lmid = lo + (hi - lo) / 3;
        int rmid = hi - (hi - lo) / 3;
        int lans = query(lmid), rans = query(rmid);
      	// 求凹函数的极小值
        if (lans <= rans) {
            hi = rmid - 1;
        } else {
            lo = lmid + 1;
        }
      	// 求凸函数的极大值
      	if(lans <= rans)  {
          	lo = lmid + 1;
        } else {
          	hi = rmid - 1;
        } 
    }
    std::cout << std::min(query(lo), query(hi)) << "\n";

三分（实数域）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 0; i < 300; i++) {
    double lmid = lo + (hi - lo) / 3;
    double rmid = hi - (hi - lo) / 3;
    auto check = [&](double x) {
        
    };
    double lans = check(lmid), rans = check(rmid);
    if (lans <= rans) {
        lo = lmid;
        ans = lmid;
    } else {
        hi = rmid;
    }
}
std::cout << std::fixed << std::setprecision(10) << ans << "\n";