2020-10
最大公约数（GCD）与欧几里得算法 最大公约数（Greatest Common Divisor，GCD） 两个数最大公约数顾名思义，两个数的所有公约数中最大的。 若正整数 $a,b$ 的质因数分解为 $$a = \prod_{i} p_i ^ {e_{a,i}}$$ $$b = \prod_{i} p_i ^ {e_{b,i}}$$ 则其最大公
…
对拍程序 from os import system tc=0 while True: system("python data.py > data.in") system("std.exe < data.in > std.out") system("my.exe < data.in > my.out") # system("diff std.out my.out > diff.out"): if system("fc std.out my.out > diff.out"): print("WA") break else: tc += 1 print("AC #%d"%tc) print("-------------------- data.in --------------------") # system("cat data.in") system("type data.in") print("-------------------- std.out --------------------") system("type std.out") print("-------------------- my.out ---------------------") system("type my.out") Powershell #include <bits/stdc++.h>using namespace std; int main() { int tc=0; while(1) { system("./E_data > data.in"); system("cat data.in | ./E_std.exe > std.txt"); system("cat data.in | ./E.exe > my.txt"); if(system("diff std.txt my.txt > diff.txt")) { cout<<"WA"<<endl; break; } else
…
树状数组 Binary Index Tree/Fenwick Tree 1d 单点修改，区间询问 // T must + - // id 1~n template<typename T,size_t M,typename OpPlus=plus<T>,typename OpMinus=minus<T>> struct BIT { static int lowbit(int x) { return x&(-x); } constexpr static OpPlus opp{}; constexpr static OpMinus opm{}; static T tmp[M+1]; T tree[M+1]; // tree[i] -> sum of [i-lowbit(i)+1,i] int n; void init(int n_) { n=n_; for(int i=1;i<=n;i++) tree[i]=T(0); } void init(int n_,T v[]) // v[0 ~ n_-1] { n=n_; tmp[0]=T(0); for(int i=1;i<=n;i++) tmp[i]=opp(tmp[i-1],v[i]); for(int i=1;i<=n;i++) tree[i]=opm(tmp[i],tmp[i-lowbit(i)]); // for(int i=0;i<n;i++) add(i,v[i]); } void add(int p,T V) { for(;p<=n;p+=lowbit(p))
…
计时 Timing chrono class Timing { private: typedef chrono::time_point<std::chrono::high_resolution_clock> TP; TP current_time() { return chrono::high_resolution_clock::now(); } TP st,ed; public: void start() { st=current_time(); } void end() { ed=current_time(); } void print() { cout<<chrono::duration_cast<chrono::microseconds>(ed-st).count() <<"ms\n"; } }timing;
…