萌新在线模板--keyboarder_zsq

夏侯承恩

2023-12-01

好像马上就要出去打铁了QAQ，所以是不是要做个模板带过去也玩一玩？
那就做吧。。。
标题就设为萌新模板吧。。。各种萌新讲解对吧。。。。

快速输入

template <class T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if(c=getchar(),c==EOF) return 0; //EOF
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
inline void out(int x)
{
    if(x>9) out(x/10);
    putchar(x%10+'0');
}

图论

拓扑排序

最短路

最小生成树

二分匹配

强连通Tarjan

最近公共祖先LCA

在线ST表，RMQ维护求LCA

// 注意Maxn 和 25  !!!
int deep[Maxn<<1], first[Maxn], tot, id[Maxn<<1];
int dp[Maxn<<1][25];         
void _DFS(int u, int dep, int fa){
    int v;
    id[++tot] = u;
    deep[tot] = dep;
    first[u] = tot;
    for(int i=head[u]; ~i; i = edge[i].nex){
        v = edge[i].v;
        if(v == fa) continue;
        _DFS(v, dep+1, u);
        id[++tot] = u;
        deep[tot] = dep;
    }
}
void ST(){
    for(int i=1;i<=tot;i++) dp[i][0] = i;
    for(int j=1;(1<<j) <= tot;j++){
        for(int i=1;i+(1<<j)-1<=tot;i++){
            int a = dp[i][j-1], b = dp[i+(1<<(j-1))][j-1];
            dp[i][j] = deep[a] < deep[b] ? a : b;
        }
    }
}
int RMQ(int Left, int Right){
    int k = 0;
    while(1<<(k+1) <= (Right - Left + 1)) k++;
    int a = dp[Left][k], b = dp[Right-(1<<k)+1][k];
    return deep[a] < deep[b] ? a : b;
}
int LCA(int u, int v){
    int x = first[u], y = first[v];
    if(x > y){
        x = x ^ y;
        y = x ^ y;
        x = x ^ y;
    }
    int res = RMQ(x, y);
    return id[res];
}
void solve(){
    tot = 0;
    _DFS(root, 1, -1);
    ST();
}

二分

算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)

算法返回一个非递减序列[first, last)中第一个大于val的位置。

upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)

其实如果是一个二分搜索答案，完全可以加一个判断条件就是正确答案直接return正确答案，避免之后判断，最后写个return 特殊标记

0000001111111，寻找一个满足条件的最左；

int binary_find(int Left,int Right)  
{    
    while(Left<Right)  
    {  
        int mid=Left+(Right-Left)/2;  
        if(Judge(mid))  
            Right=mid;  
        else  
            Left=mid+1;  
    }  
    return Left;  
}

对于1111000000，寻找一个满足条件的最右；

int binary_find(int Left,int Right)  
{
    while(Left<Right)  
    {
        int mid=Left+(Right-Left+1)/2;  
        if(Judge(mid))  
            Left=mid;  
        else  
            Right=mid-1;  
    }  
    return Left;  
}

浮点数二分
惨痛的教训：浮点数最好转化成整数再算，不然精度有问题。

double Solve(double L, double R)
{
    double M;
    for( int i = 0; i < 100; ++ i)
    {
        M = (L + R) / 2;
        if (Judge(M))
            R = M;
        else
            L = M;
    }
    return R;
}

三分

凸性函数:
Mid = (Left*2.0+Right)/3.0;
Midmid = (Left + Right*2.0)/3.0;
如果 cal(Mid) > cal(MidMid), 意味着 Mid 更靠近极值点 => Right = MidMid;
否则，意味着 MidMid 更靠近极值点 => Left = Mid;

#define g 9.8
#define PI 3.141592653589732384626433832795
const double eps = 1e-8;

double Cal(double x){
    /****计算需求****/

}
double SanfenTu(double Left, double Right){
    double Mid, Midmid, cMid, cMidmid;
    while(Left + eps < Right){
        Mid = (Left*2.0+Right)/3.0;
        Midmid = (Left + Right*2.0)/3.0;
        cMid = Cal(Mid);
        cMidmid = Cal(Midmid);
        if(cMid > cMidmid) Right = Midmid;
        else Left = Mid;
    }
    /***注意返回什么**/
//    return Cal(Left);
//    
//    return Left;
}

凹性函数:
Mid=(Left*2.0 + Right)/3;
Midmid=(Right*2.0 + Left)/3;
如果 cal(Mid) > cal(MidMid) 意味着 MidMid 更靠近极值点 => Left = Mid;
否则，意味着 Mid 更靠近极值点 => Right = MidMid;

double Cal(double x){
    /****计算需求****/
}
double SanfenAo(double Left, double Right){
    double Mid, Midmid, cMid, cMidmid;
    while(Left + eps < Right){
        Mid = (Left*2.0 + Right) / 3;
        Midmid = (Right*2.0 + Left) / 3;
        cMid = Cal(Mid);
        cMidmid = Cal(Midmid);
        if(cMid > cMidmid) Left = Mid;
        else Right = Midmid;
    }
    /***注意返回什么**/
//    return Cal(Left);
//    
//    return Left;
}

树状数组

线段树


/*
线段树模板
Author: Keyboarder_Zsq
Time: 2017/9/28/18:19
*/
const int Maxn = 1e5 + 10;      //线段树节点个数
#define elem LL     //区间数据类型
#define Elem LL     //数值数据类型
#define GetMid (node[num].Left+node[num].Right)>>1
#define Lson num<<1
#define Rson num<<1|1
Elem v[Maxn];
struct Seg{
    elem Left, Right;
    Elem Sum;   //区间和
    Elem Lazy;  //和标记
    Elem Max;   //区间最大值
    Elem Min;   //区间最小值
}node[Maxn<<2];
Elem Mmax(Elem va, Elem vb){
    return va > vb ? va : vb;
}
Elem Mmin(Elem va, Elem vb){
    return va < vb ? va : vb;
}
Elem ADD(Elem va, Elem vb){
    return va + vb;
}
void Push_Up(int num){
    node[num].Max = Mmax(node[Lson].Max, node[Rson].Max);
    node[num].Min = Mmin(node[Lson].Min, node[Rson].Min);
    node[num].Sum = ADD(node[Lson].Sum, node[Rson].Sum);
}

void Push_Down(int num){
    if(node[num].Lazy){
        node[Lson].Lazy = node[Lson].Lazy + node[num].Lazy;
        node[Lson].Sum = node[Lson].Sum + node[num].Lazy * (node[Lson].Right - node[Lson].Left + 1);

        node[Rson].Lazy = node[Rson].Lazy + node[num].Lazy;
        node[Rson].Sum = node[Rson].Sum + node[num].Lazy * (node[Rson].Right - node[Rson].Left + 1);

        node[num].Lazy = 0;
    }
}
//建树
void Build(int num, int Left, int Right){
    node[num].Left = Left;
    node[num].Right = Right;
////node[num].Lazy = 0;
    if(Left == Right){
////        node[num].Sum = node[num].Max = node[num].Min = v[Left];
////        scanf("%lld",&node[num].Sum);
//        node[num].Max = 0;
        return;
    }
    int Mid = GetMid;
    Build(Lson, Left, Mid);
    Build(Rson, Mid+1, Right);
    Push_Up(num);
}
//区间更新
void Update_Seg(int num, int s, int t, Elem val){
    if(node[num].Left >= s && node[num].Right <= t){
        node[num].Lazy = node[num].Lazy + val;
        node[num].Sum = node[num].Sum + val * (node[num].Right - node[num].Left + 1);
        return;
    }
    Push_Down(num);
    int Mid = GetMid;
    if(Mid >= t) Update_Seg(Lson, s, t, val);
    else if(Mid < s) Update_Seg(Rson, s, t, val);
    else{
        Update_Seg(Lson, s, Mid, val);
        Update_Seg(Rson, Mid+1, t, val);
    }
    Push_Up(num);
}
//区间求和
Elem Query_Sum(int num, int s, int t){
    if(node[num].Left >= s && node[num].Right <= t)
        return node[num].Sum;
    Push_Down(num);
    int Mid = GetMid;
    if(Mid >= t) return Query_Sum(Lson, s, t);
    else if(Mid < s) return Query_Sum(Rson, s, t);
    else{
        Elem x,y;
        x = Query_Sum(Lson, s, Mid);
        y = Query_Sum(Rson, Mid+1, t);
        return x + y;
    }
}
//点更新
void Update_One(int num, int pos, Elem val){
    if(node[num].Left == node[num].Right){
        if(node[num].Left == pos){
//            node[num].Sum = val;
//            node[num].Max = val;
//            node[num].Min = val;
        }
        return;
    }
    int Mid = GetMid;
    if(Mid >= pos) Update_One(Lson, pos, val);
    else Update_One(Rson, pos, val);
    Push_Up(num);
}
//区间求最大值
Elem Query_Max(int num, int s, int t){
    if(node[num].Left >= s && node[num].Right <= t)
        return node[num].Max;
    int Mid = GetMid;
    if(Mid >= t) return Query_Max(Lson, s, t);
    else if(Mid < s) return Query_Max(Rson, s, t);
    else{
        Elem x,y;
        x = Query_Max(Lson, s, Mid);
        y = Query_Max(Rson, Mid+1, t);
        return Mmax(x, y);
    }
}
//区间求最小值
Elem Query_Min(int num, int s, int t){
    if(node[num].Left >= s && node[num].Right <= t)
        return node[num].Min;
    int Mid = GetMid;
    if(Mid >= t) return Query_Min(Lson, s, t);
    else if(Mid < s) return Query_Min(Rson, s, t);
    else{
        Elem x,y;
        x = Query_Min(Lson, s, Mid);
        y = Query_Min(Rson, Mid+1, t);
        return Mmin(x, y);
    }
}

尺取

//尺取数组
    int Left, Right;
    Left = Right = 1;       //双指针初始化
    while(Left <= N){
        //先让右指针跑，并且保证右指针的情况都是合法的
        while(Right+1 <= N && Solution_Is_OK(Right+1)){
            Change_ADD();       //改变中间值，靠近约束条件
            Right++;            //如果(右指针+1)符合，右指针往后移
        }
        GetValue();             //得到需要求的最优值

        if(Right+1 == sz)       //break条件 具体看情况决定
            break;

        //由于添加(右指针+1)的位置会造成冲突，所以左指针往后移
        while(Left < sz && Right+1 < sz && Solution_Is_Not_OK(Right+1)){
            Change_Erase();      //改变中间值，变成符合条件
            Left++;              //如果(右指针+1)不符合，左指针往后移
        }
    }

组合数模板

const int N = 67;
LL C[N][N];
C[1][0] = C[1][1] = 1;
for (int i = 2; i < N; i++){
    C[i][0] = 1;
    for (int j = 1; j < N; j++){
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);
    }
}

exgcd模板

int exgcd(int a,int b,int &x,int &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a%b, x, y);
    int tmp = x;
    x = y;
    y = tmp - a/b*y;
    return d;
}

exgcd求逆元模板

Elem inv[Maxn]; ///逆元
Elem extend_gcd(Elem a,Elem b,Elem &x,Elem &y){
    if( b == 0 ) {
        x = 1;
        y = 0;
        return a;
    }
    else{
        Elem x1,y1;
        Elem d = extend_gcd (b,a % b,x1,y1);
        x = y1;
        y= x1 - a / b * y1;
        return d;
    }
}
Elem mod_reverse(Elem a,Elem n)
{
    Elem x,y;
    Elem d=extend_gcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}
void init(){
    inv[0] = 0,inv[1]=1;
    for(int i=2;i<=10000;i++){
        inv[i] = mod_reverse(i,9973);
    }
}

exgcd求不定方程ax+by=gcd(a, b)的解

Author: keyboarder_zsq
Time: 2017/10/22 18:53

typedef int Elem;
Elem exgcd(Elem a , Elem b, Elem &x, Elem &y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    Elem gcd = exgcd(b, a%b, x, y);
    Elem temp = x;
    x = y;
    y = temp - a/b*y;
    return gcd;
}
//求方程 a*x + b*y = c 的 x 的最小整数解.
//先利用 exgcd 求 a*x + b*y = gcd(a, b) 的x, y的最小整数解。
//然后再乘上去就好了;
Elem Cal(Elem a, Elem b, Elem c){
    Elem x, y, k, t;
    Elem gcd = exgcd(a, b, x, y);

    if(c%gcd!=0) return -1; //不存在解
    x = x * c/gcd;          //由a*x + b*y = gcd(a, b) 转化为 a*x + b*y = c 的解
    k = b/gcd;              //约去c后原来b就变为了b/gcd;
    if(k < 0) k = -k;       //如果b为负数就去绝对值

    x = (x%k + k) % k;      //最小非负整数解
    if(x <= 0) x = x + k;   //最小正整数解

    y = (c - a * x)/b;      //如果对y还有要求，先求出y值在进行判断

    while(y<0){
        x = x + k;
        y = (c - a * x)/b;
    }
    return x;
}

逆元预处理模板

typedef long long LL;
const int MAXN = 5e3+5;
const LL MOD = 1e9+7;
LL Inv[MAXN];
void Get_Inv()
{
    Inv[1] = 1;
    for(int i=2; i<MAXN; i++)
        Inv[i] = ( (MOD-MOD/i)*Inv[MOD%i] ) % MOD;
}

字符串hash模板

模板1. 字符串长度>=1e4/1e5 安全级别低/但是时间比较可观
$hash$ 函数可以理解为：
$hash[i]=(hash[i-1] \times p + s[i])\%(2^{64})$
求区间: $hash[L,R] = hash[R] - hash[L-1]*p^{(R-L+1)}$

安全指数：三星（所以并不是很安全）
取膜利用 ULL 自动取膜（省时间）
大致满足字符串长度>1e4/1e5，因为相对于方法2，这个时间小。

//ULL printf()输出方式 %llu.
typedef unsigned long long ULL;
const int Maxn = 1e6 + 7;   // 字符串长度
const ULL p = 31;           // p 是字符串的种类
ULL f[Maxn], Has[Maxn];
char s1[Maxn], s2[Maxn];
//预处理 p的次数
void init(){
    f[0] = 1;
    for(int i=1;i<=1000000;i++) f[i] = f[i-1] * p;
}

//得到字符串区间 hash 值
ULL Get_Left_to_Right(int Left, int Right){
    return Has[Right] - Has[Left-1] * f[Right - Left + 1];
}

//用于 hash 单字符串
ULL Get_Hashval(char str[]){
    int len = strlen(str+1);
    ULL temp = 0;
    for(int i=1;i<=len;i++) temp = temp * p + str[i];
    return temp;
}
//对于一个字符串hash出 [1, pos] 的hash值
void _Hash(char str[]){
    Has[0] = 0;
    int len = strlen(str+1);
    for(int i=1;i<=len;i++) Has[i] = Has[i-1] * p + str[i];
}

模板2. 用于字符串长度<1e4/5e3的安全比较高/但是比较费时
$hash[i]=(hash[i-1] \times p+idx(s[i]))\%mod$
求区间：
$hash[L,R] = hash[R] - hash[L-1]*p^{(R-L+1)}$
取膜比较费时，注意时间.

const int Maxn = 1e4 + 10;
const LL p = 31;
const LL mod = 1e9 + 7;
char s1[Maxn], s2[Maxn*100];
LL h1[Maxn], h2[Maxn*100], f[Maxn*100];
void init(){
    h1[0] = h2[0] = 0;
    f[0] = 1;
    for(int i=1;i<=1000000;i++) f[i] = f[i-1] * p % mod;
}
LL idx(char x){
    return (long long)(x - 'A' + 1);
}

void Hash(char s[], LL has[]){
    int len = strlen(s+1);
    for(int i=1;i<=len;i++)
        has[i]=(has[i-1]*p+idx(s[i])) % mod;
}
LL get_L_to_R(int Left, int Right, LL has[]){
    return (has[Right] - has[Left-1]* f[Right - Left + 1] % mod + mod) % mod;
}

模板3.双hash，太费时；
模板2加强版，具体打法参照模板2.
mod1和mod2
hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1;
hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2;
mod1一般取1e9+7，mod2一般取1e9+9为什么这么取？
1000000007和1000000009是一对孪生素数，取它们，冲突的概率极低！
安全指数：五星！（非常稳！）(稳啊…稳T了…开玩笑)

打CF及一些在线比赛可以用的模板

矩阵相关

const int Maxn = 64;

struct Matrix{
    Matrix(){}
    Matrix(int R, int C, int M) : R(R), C(C), M(M){}

    void Clear()
    { memset(pData, 0, sizeof(pData)); }

    void init(int A, int B, int C){
        for(int i=1;i<Maxn;i++){
            pData[i][i-1] = A;
            pData[i][i] = B;
            pData[i][i+1] = C;
        }
    }

    Matrix operator + (Matrix& x) const
    {
        Matrix ans(R, C, M);
        for(int i=1;i<=R;i++)
            for(int j=1;j<=C;j++)
                ans.pData[i][j] = (pData[i][j] + x.pData[i][j]) % M;
        return ans;
    }
    Matrix operator * (Matrix& x) const
    {
        Matrix Tmp(R, x.C, M);
        Tmp.Clear();
        for(int k=1;k<=C;k++){
            for(int i=1;i<=Tmp.R;i++){
                for(int j=1;j<=Tmp.C;j++){
                    Tmp.pData[i][j] = (Tmp.pData[i][j] + pData[i][k] * x.pData[k][j] % M) % M;
                }
            }
        }
        return Tmp;
    }
    Matrix operator ^ (int x) const
    {
        Matrix ans(R, R, M), Tmp(R, R, M);
        memcpy(Tmp.pData, pData, sizeof(Tmp.pData));
        ans.Clear();
        for(int i=1;i<=ans.R;i++)
        { ans.pData[i][i] = 1; }
        while(x){
            if(x & 1) ans = ans * Tmp;
            x >>= 1;
            Tmp = Tmp * Tmp;
        }
        return ans;
    }

    int R, C, M;
    int pData[Maxn][Maxn];
};