算法模版-杂类

杂类

对拍模板

数据生成器

#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;
}

对拍程序

#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;
}

windows 环境

// BAD.cpp, 存放待寻找错误的代码
freopen("A.txt","r",stdin);
freopen("BAD.out","w",stdout);

// 1.cpp, 存放暴力或正确的代码
freopen("A.txt","r",stdin);
freopen("1.out","w",stdout);

// Ask.cpp
freopen("A.txt", "w", stdout);

• C++ 版 bat

int main() {
    int T = 1E5;
    while(T--) {
        system("BAD.exe");
        system("1.exe");
        system("A.exe");
        if (system("fc BAD.out 1.out")) {
            puts("WA");
            return 0;
        }
    }
}

__int128 输入/输出

输入

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<<"";
}

输出

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\)

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";

三分（实数域）

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";

Python常用语法

读入与定义

• 读入多个变量并转换类型：X, Y = map(int, input().split())
• 读入列表：X = eval(input())
• 多维数组定义：X = [[0 for j in range(0, 100)] for i in range(0, 200)]

格式化输出

• 保留小数输出：print("{:.12f}".format(X)) 指保留 \(12\) 位小数
• 对齐与宽度：print("{:<12f}".format(X)) 指左对齐，保留 \(12\) 个宽度

排序

• 倒序排序：使用 reverse 实现倒序 X.sort(reverse=True)

• 自定义排序：下方代码实现了先按第一关键字降序、再按第二关键字升序排序。

  X.sort(key=lambda x: x[1])
  X.sort(key=lambda x: x[0], reverse=True)

文件IO

• 打开要读取的文件：r = open('X.txt', 'r', encoding='utf-8')
• 打开要写入的文件：w = open('Y.txt', 'w', encoding='utf-8')
• 按行写入：w.write(XX)

增加输出流长度

import sys
sys.set_int_max_str_digits(200000)

自定义结构体

自定义结构体并且自定义排序

class node:
    def __init__(self, A, B, C):
        self.A = A
        self.B = B
        self.C = C

w = []
for i in range(1, 5):
    a, b, c = input().split()
    w.append(node(a, b, c))
w.sort(key=lambda x: x.C, reverse=True)
for i in w:
    print(i.A, i.B, i.C)

数据结构

• 模拟于 \(C^{map}_{++}\) ，定义：dic = dict()
• 模拟栈与队列：使用常见的 \(\tt list\) 即可完成，list.insert(0, X) 实现头部插入、list.pop() 实现尾部弹出、list.pop(0) 实现头部弹出

其他

• 获取ASCII码：ord() 函数
• 转换为ASCII字符：chr() 函数

OJ测试

对于一个未知属性的OJ，应当在正式赛前进行以下全部测试：

GNU C++ 版本测试

for (int i : {1, 2}) {} // GNU C++11 支持范围表达式

auto cc = [&](int x) { x++; }; // GNU C++11 支持 auto 与 lambda 表达式
cc(2);

tuple<string, int, int> V; // GNU C++11 引入
array<int, 3> C; // GNU C++11 引入

auto dfs = [&](auto self, int x) -> void { // GNU C++14 支持 auto 自递归
    if (x > 10) return;
    self(self, x + 1);
};
dfs(dfs, 1);

vector in(1, vector<int>(1)); // GNU C++17 支持 vector 模板类型缺失

map<int, int> dic;
for (auto [u, v] : dic) {} // GNU C++17 支持 auto 解绑
dic.contains(12); // GNU C++20 支持 contains 函数

constexpr double Pi = numbers::pi; // C++20 支持

编译器位数测试

using i64 = __int128; // 64 位 GNU C++11 支持

评测器环境测试

Windows 系统输出 -1 ；反之则为一个随机数。

#define int long long
map<int, int> dic;
int x = dic.size() - 1;
cout << x << endl;

编译器设置

g++ -O2 -std=c++20 -pipe 
-Wall -Wextra -Wconversion /* 这部分是警告相关，可能用不到 */
-fstack-protector 
-Wl,--stack=268435456