Skip to content

Latest commit

 

History

History
378 lines (324 loc) · 9.25 KB

10-杂项.md

File metadata and controls

378 lines (324 loc) · 9.25 KB
Raw

杂项

重载哈希

// 重载哈希以支持 unordered_set & unordered_map
struct HashFunc {
    template<class T, class U>
    size_t operator() (const pair<T, U> &i) const {
        return hash<T>()(i.first) ^ hash<U>()(i.second);
    }
};
unordered_set<pll, HashFunc> st;
unordered_map<pll, int, Hash> mp;

随机

  • 标准库的rand()函数范围较小，仅$[0, 32768)$，容易被卡
  • 因此取随机数建议用下面这个

1-gon大爹的gen

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
ll rng(ll l, ll r) {
    uniform_int_distribution<ll> uni(l, r);
    return uni(mt);
}

对拍相关

windows下对拍 .bat文件

@echo off
:loop  
    rand.exe > rand.in
    std.exe < rand.in > std.out
    my.exe < rand.in > my.out
    fc my.out std.out 
if not errorlevel 1 goto loop
pause
goto loop

linux下对拍 .cpp文件

#include<bits/stdc++.h>

using namespace std;

int main() {
    int i;
    for (i = 1; ; i++) {
        printf("The result of No. %d Case is: ", i);
        system("./rand > rand.in");
        system("./std < rand.in > std.out");
        system("./my < rand.in > my.out");
        if (system("diff std.out my.out")) {
            printf("Wrong Answer\n");
            printf("rand:\n");
            system("cat rand.in");
            return 0;
        } else printf("Accepted\n");
    }
}

/*
linux下对拍
此文件为duipai.cpp

其余组件:
对拍程序my.cpp
标程std.cpp
数据rand.cpp
*/

rand.cpp

#include <sys/time.h>
#include<bits/stdc++.h>
#include <windows.h>

typedef long long ll;
using namespace std;

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
ll rng(ll l, ll r) {
    uniform_int_distribution<ll> uni(l, r);
    return uni(mt);
}

//rng(l, r)返回[min, max]区间值

int128输入输出

#include <bits/stdc++.h>

using namespace std;

inline __int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

inline void write(__int128 x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

/*
读入 x = read();
输出 write(x);
使用实例 a+b
*/

int main() {

    __int128 a = read();
    __int128 b = read();
    write(a + b);
    puts("");

    return 0;
}

分数模板

#include <bits/stdc++.h>
using namespace std;

#define _for(i,a,b) for(int i = (a);i < (b);i ++)
const int maxn = 50003;

int gcd(int a,int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}

class Fraction
{
    public:
        int a,b;
        int sign(int x) {return (x>0?1:-1);}
        Fraction():a(0),b(1){}
        Fraction(int x):a(x),b(1){}
        Fraction(int x,int y)
        {
            int m = gcd(abs(x),abs(y));
            a = x/m*sign(y);
            if(a==0)b=1;else b = abs(y/m);
        }
        int get_denominator() {return b;}
        int get_numerator() {return a;}
        Fraction operator+(const Fraction &f)
        {
            int m = gcd(b,f.b);
            return Fraction(f.b/m*a+b/m*f.a,b/m*f.b);
        }
        Fraction operator-(const Fraction &f)
        {
            int m = gcd(b,f.b);
            return Fraction(f.b/m*a-b/m*f.a,b/m*f.b);
        }
        Fraction operator*(const Fraction &f)
        {
            int m1 = gcd(abs(a),f.b);
            int m2 = gcd(b,abs(f.a));
            return Fraction((a/m1)*(f.a/m2),(b/m2)*(f.b/m1));
        }
        Fraction operator/(const Fraction &f)
            {return (*this)*Fraction(f.b,f.a);}
        friend ostream &operator << (ostream &out,const Fraction &f)
        {
            if(f.a==0) cout << 0;
            else if(f.b==1) cout << f.a;
            else cout << f.a << '/' << f.b;
            return out; 
        }
};

int main()
{
    Fraction p(18,10);
    Fraction o(11,17);
    cout << p*o << endl; 
    return 0;
}

快读

简易版

namespace FastIO {
#define BUF_SIZE 1000000
    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUF_SIZE, stdin), p1 == p2) ? EOF : *p1++;
    }
    inline int read() {
        char ch = nc();
        int sum = 0;

        while (!(ch >= '0' && ch <= '9')) ch = nc();
        while (ch >= '0' && ch <= '9') {
            sum = sum * 10 + ch - '0';
            ch = nc();
        }
        return sum;
    }

#undef BUF_SIZE
}

全家桶

namespace FastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    //fread->read
 
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
            //{printf("IO error!\n");system("pause");for (;;);exit(0);}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(double &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (ch=='.'){
            double tmp=1; ch=nc();
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if (sign)x=-x;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    //fwrite->write
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        void out(char ch){
            if (p1==pend){
                fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
            }
            *p1++=ch;
        }
        void print(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(double x,int y){
            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if (x<-1e-12)out('-'),x=-x;x*=mul[y];
            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
            if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
        }
        void println(double x,int y){print(x,y);out('\n');}
        void print(char *s){while (*s)out(*s++);}
        void println(char *s){while (*s)out(*s++);out('\n');}
        void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print_(int x){Ostream.print(x);Ostream.out(' ');}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print_(char x){Ostream.print(x);Ostream.out(' ');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print_(ll x){Ostream.print(x);Ostream.out(' ');}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print_(double x,int y){Ostream.print(x,y);Ostream.out(' ');}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};