首页 > 其他分享 >ACM模板

ACM模板

时间:2024-06-01 20:44:41浏览次数:20  
标签:return Point int ACM Vector mod 模板 define

主席树区间修改

#define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#define bug(x) cout<<#x<<" is "<<x<<endl

#include <bits/stdc++.h>

#define iter ::iterator

using namespace  std;

typedef long long ll;

typedef pair<int,int>P;

#define pb push_back

#define mk make_pair

#define se second

#define fi first

const ll mod=1e9+7;

const int N=1e5+5;

int n,q;

int a[N],rt[N*32],ls[N*32],rs[N*32];

ll sum[N*32],add[N*32];

int cnt;

void build(int &o,int l,int r){

    o=++cnt;

    if(l==r){

        sum[o]=a[l];

        return;

    }

    int m=(l+r)/2;

    build(ls[o],l,m);

    build(rs[o],m+1,r);

    sum[o]=sum[ls[o]]+sum[rs[o]];

}

void up(int &o,int pre,int l,int r,int ql,int qr,int val){

    o=++cnt;

    ls[o]=ls[pre];

    rs[o]=rs[pre];

    add[o]=add[pre];

    sum[o]=sum[pre]+1ll*val*(min(r,qr)-max(l,ql)+1);

    if(l>=ql&&r<=qr){

        add[o]+=val;

        return;

    }

    int m=(l+r)/2;

    if(ql<=m)up(ls[o],ls[pre],l,m,ql,qr,val);

    if(qr>m)up(rs[o],rs[pre],m+1,r,ql,qr,val);

}

ll qu(int o,int l,int r,int ql,int qr){

    if(l>=ql&&r<=qr)return sum[o];

    ll res=add[o]*(min(r,qr)-max(l,ql)+1);

    int m=(l+r)/2;

    if(ql<=m)res+=qu(ls[o],l,m,ql,qr);

    if(qr>m)res+=qu(rs[o],m+1,r,ql,qr);

    return res;

}

int main(){

    while(~scanf("%d%d",&n,&q)){

        for(int i=1;i<=n;i++)scanf("%d",&a[i]);

        cnt=0;

        build(rt[0],1,n);

        int time=0;

        while(q--){

            char op;

            int L,R,val;

            scanf(" %c",&op);

            if(op=='Q'){

                scanf("%d%d",&L,&R);

                ll ans=qu(rt[time],1,n,L,R);

                printf("%lld\n",ans);

            }

            else if(op=='C'){

                scanf("%d%d%d",&L,&R,&val);

                ++time;

                up(rt[time],rt[time-1],1,n,L,R,val);

 

            }

            else if(op=='H'){

                scanf("%d%d%d",&L,&R,&val);

                ll ans=qu(rt[val],1,n,L,R);

                printf("%lld\n",ans);

            }

            else{

                scanf("%d",&val);

                time=val;

            }

        }

        printf("\n");

    }

}

 

带权并查集

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int parent[N];

int value[N];  ///记录当前结点到根结点的距离

int FindSet(int x) {

    if (x == parent[x])

        return x;

    else {

        int t = parent[x]; //记录原父节点编号

        parent[x] = FindSet(parent[x]); //父节点变为根节点,此时value[x]=父节点到根节点的权值

        value[x] += value[t]; //当前节点的权值加上原本父节点的权值

        return parent[x];

    }

}

int main(){

    int n, m;

    while (scanf("%d%d", &n, &m) != EOF) {

        for (int i = 0; i <= n; i++) {

            parent[i] = i;

            value[i] = 0;

        }

        int ans = 0;

        while (m--) {

            int a, b, v;

            scanf("%d%d%d", &a, &b, &v);

            a--;

            int roota = FindSet(a);

            int rootb = FindSet(b);

            if (roota == rootb) {

                if (value[a] - value[b] != v) ans++;  ///精华部分1

            }

            else {

                parent[roota] = rootb;

                value[roota] = -value[a] + value[b] + v; ///精华部分2

            }

        }

        printf("%d\n", ans);

    }

}

树剖

#define IO std::ios::sync_with_stdio(0);

#include <bits/stdc++.h>

#define iter ::iterator

using namespace  std;

typedef long long ll;

typedef pair<ll,ll>P;

#define pb push_back

#define se second

#define fi first

#define rs o<<1|1

#define ls o<<1

#define inf 0x3f3f3f3f

const int N=1e5+5;

int n,q,rt,mod;

int a[N],b[N];

vector<int>g[N];

int deep[N],fa[N],id[N],son[N],siz[N],top[N];

int sumv[N*4],add[N*4];

int L[N*4],R[N*4];

void dfs1(int u,int f){

    deep[u]=deep[f]+1;

    fa[u]=f;

    siz[u]=1;

    int mx=-1;

    for(int i=0;i<g[u].size();i++){

        int v=g[u][i];

        if(v==f)continue;

        dfs1(v,u);

        siz[u]+=siz[v];

        if(siz[v]>mx){

            mx=siz[v];

            son[u]=v;

        }

    }

}

int tim;

void dfs2(int u,int topf){

    id[u]=++tim;

    a[tim]=b[u];

    top[u]=topf;

    if(!son[u])return;

    dfs2(son[u],topf);

    for(int i=0;i<g[u].size();i++){

        int v=g[u][i];

        if(v==fa[u]||v==son[u])continue;

        dfs2(v,v);

    }

}

void push(int o){

    sumv[o]=(sumv[ls]+sumv[rs])%mod;

}

void down(int o){

    if(add[o]){

        add[o]%=mod;

        sumv[ls]+=add[o]*(R[ls]-L[ls]+1);

        sumv[ls]%=mod;

        sumv[rs]+=add[o]*(R[rs]-L[rs]+1);

        sumv[rs]%=mod;

        add[ls]+=add[o];

        add[ls]%=mod;

        add[rs]+=add[o];

        add[rs]%=mod;

        add[o]=0;

    }

}

void build(int o,int l,int r){

    if(l==r){

        sumv[o]=a[l]%mod;

        L[o]=R[o]=l;

        return;

    }

    int m=(l+r)/2;

    build(ls,l,m);

    build(rs,m+1,r);

    L[o]=L[ls];

    R[o]=R[rs];

    push(o);

}

int qu(int o,int l,int r,int ql,int qr){

    if(l>=ql&&r<=qr){

        return sumv[o]%mod;

    }

    down(o);

    int m=(l+r)/2;

    int res=0;

    if(ql<=m)res+=qu(ls,l,m,ql,qr)%mod;

    res%=mod;

    if(qr>m)res+=qu(rs,m+1,r,ql,qr)%mod;

    res%=mod;

    return res;

}

void up(int o,int l,int r,int ql,int qr,int v){

    if(l>=ql&&r<=qr){

        v%=mod;

        add[o]+=v;

        add[o]%=mod;

        sumv[o]+=v*(r-l+1);

        sumv[o]%=mod;

        return;

    }

    down(o);

    int m=(l+r)/2;

    if(ql<=m)up(ls,l,m,ql,qr,v);

    if(qr>m)up(rs,m+1,r,ql,qr,v);

    push(o);

}

void qu1(int x,int y){//x节点到y节点的路径和

    int res=0;

    while(top[x]!=top[y]){

        if(deep[top[x]]<deep[top[y]])swap(x,y);

        res+=qu(1,1,n,id[top[x]],id[x]);

        res%=mod;

        x=fa[top[x]];

    }

    if(deep[x]>deep[y])swap(x,y);

    res+=qu(1,1,n,id[x],id[y])%mod;

    res%=mod;

    printf("%d\n",res);

}

void up1(int x,int y,int z){//把x节点到y节点的路径所有点加z

    while(top[x]!=top[y]){

        if(deep[top[x]]<deep[top[y]])swap(x,y);

        up(1,1,n,id[top[x]],id[x],z);

        x=fa[top[x]];

    }

    if(deep[x]>deep[y])swap(x,y);

    up(1,1,n,id[x],id[y],z);

}

int main(){

    scanf("%d%d%d%d",&n,&q,&rt,&mod);

    for(int i=1;i<=n;i++){

        scanf("%d",&b[i]);

        b[i]%=mod;

    }

    for(int i=1;i<n;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        g[x].pb(y);

        g[y].pb(x);

    }

    dfs1(rt,0);

    dfs2(rt,rt);

    build(1,1,n);

    while(q--){

        int op,x,y,z;

        scanf("%d",&op);

        if(op==1){//把x节点到y节点的路径所有点加z

            scanf("%d%d%d",&x,&y,&z);

            up1(x,y,z);

        }

        else if(op==2){//查询x节点到y节点的路径和

            scanf("%d%d",&x,&y);

            qu1(x,y);

        }

        else if(op==3){////把x节点的所有子孙加y

            scanf("%d%d",&x,&y);

            up(1,1,n,id[x],id[x]+siz[x]-1,y);

        }

        else{//查询x节点的子孙和

            scanf("%d",&x);

            printf("%d\n",qu(1,1,n,id[x],id[x]+siz[x]-1)%mod);

        }

    }

}

LCA

#define dbg(x) cout<<#x<<" = "<< (x)<< endl

#define IO std::ios::sync_with_stdio(0);

#include <bits/stdc++.h>

#define iter ::iterator

using namespace  std;

typedef long long ll;

typedef pair<ll,ll>P;

#define pb push_back

#define se second

#define fi first

#define rs o<<1|1

#define ls o<<1

const ll inf=0x7fffffff;

const int N=5e5+10;

int n,m,s;

vector<int>g[N];

int d[N],lg[N],p[N][22];

void dfs(int u,int fa){

    p[u][0]=fa;

    d[u]=d[fa]+1;

    for(int i=1;(1<<i)<=d[u];i++){

        p[u][i]=p[p[u][i-1]][i-1];

    }

    for(int i=0;i<g[u].size();i++){

        int v=g[u][i];

        if(v==fa)continue;

        dfs(v,u);

    }

}

 

 

 

 

void init(){

    for(int i=1;i<=n;i++){

        lg[i]=lg[i-1]+((1<<lg[i-1])==i);

    }

 

}

int lca(int x,int y){

    if(d[x]<d[y])swap(x,y);

    while(d[x]>d[y]){

        x=p[x][lg[d[x]-d[y]]-1];

    }

    if(x==y)return x;

    for(int i=lg[x];i>=0;i--){

        if(p[x][i]!=p[y][i]){

            x=p[x][i];

            y=p[y][i];

        }

    }

    return p[x][0];

}

int main(){

    //IO;

    cin>>n>>m>>s;

    for(int i=1;i<n;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        g[x].pb(y);

        g[y].pb(x);

    }

    init();

    dfs(s,0);

    while(m--){

        int x,y;

        scanf("%d%d",&x,&y);

        //cout<<lca(x,y)<<endl;

        printf("%d\n",lca(x,y));

    }

}

并查集、倍增

#include <cmath>

#include <cstdio>

#include <iostream>

using namespace std;

const int maxn = 100005, mod = 1000000007;

int n, m, fa[maxn][18], ans;

int find(int x, int k) {

    return fa[x][k] == x ? x : fa[x][k] = find(fa[x][k], k);

}

void merge(int x, int y, int k) {

    x = find(x, k), y = find(y, k);

    if(x != y) fa[x][k] = y;

}

int main() {

    scanf("%d %d", &n, &m);

    const int maxk = floor(log2(n));

    for(int i = 1; i <= n; ++i)

        for(int k = 0; k <= maxk; ++k)

            fa[i][k] = i;          

    for(int i = 1, l1, r1, l2, r2; i <= m; ++i) {

        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);

        for(int k = maxk; ~k; --k)

            if(l1+(1<<k)-1 <= r1) merge(l1, l2, k), l1 += 1<<k, l2 += 1<<k;

    }  

    for(int k = maxk; k; --k)

        for(int i = 1; i+(1<<k)-1 <= n; ++i) {

            int pos = find(i, k);

            merge(i, pos, k-1), merge(i+(1<<k-1), pos+(1<<k-1), k-1);

        }

    for(int i = 1; i <= n; ++i)

        if(fa[i][0] == i) ans = !ans ? 9 : ans * 10ll % mod;

    printf("%d\n", ans);

    return 0;

}

 


 

笛卡尔树

#define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#define bug(x) cout<<#x<<" is "<<x<<endl

#include <bits/stdc++.h>

#define iter ::iterator

using namespace  std;

typedef long long ll;

const int N=1e5+5;

int n;

ll a[N],b[N];

int st[N],ls[N],rs[N];

ll ans;

ll dfs(int u){

    if(!u)return 0;

    ll res=dfs(ls[u])+dfs(rs[u])+b[u];

    ll res1=min(res,a[u]);

    res1*=res1;

    ans=max(ans,res1);

    return res;

}

int main(){

    IO;

    cin>>n;

    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];

    int h=0;

    for(int i=1;i<=n;i++){

        int k=h;

        while(k>0&&a[st[k]]>a[i])k--;

        if(k>0)rs[st[k]]=i;

        if(k<h) ls[i]=st[k+1];

        st[++k]=i;

        h=k;

    }

    ans=0;

    dfs(st[1]);

    cout<<ans<<endl;

 

}

/*

11

9 3 7 1 8 12 10 20 15 18 5

*/

JAVA大数

import java.math.RoundingMode;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.Scanner;

import java.util.*;

import java.io.*;

public class Main {

    public static long mod=(long)(1e9+7);//1e9会被java看作double

    public static long fastpow(long x, long y) {//快速幂

        long res=1;

        while(y>0) {

            if((y&1)==1) {

                res=(res*x)%mod;

            }

            x=(x*x)%mod;

            y>>=1;

        }

        return res;

    }

    public static int N=200005;

    public static long[] b=new long[N];//声明数组

    public static void init(int n){//求n的阶乘

        b[0]=1;

        for(int i=1;i<=n;i++){

            b[i]=(b[i-1]*i)%mod;

        }

    }

    public static void main(String [] args){

        Scanner cin = new Scanner(System.in);

        int T = cin.nextInt();

        while (T-- > 0) {

            BigInteger x = cin.nextBigInteger();//输入大数

            BigInteger y = cin.nextBigInteger();

            BigInteger z = BigInteger.valueOf(123456789L);//L标记是long类型

            BigInteger k = BigInteger.ZERO;//赋值k为大数类型的0

            System.out.println(k);

            System.out.println(fastpow(2L,x.longValue()));//快速幂输出2的x次方

 

            if(x.compareTo(y)==0)System.out.println("x=y");//大数的比较函数

            else if(x.compareTo(y)<0)System.out.println("x<y");

            else if(x.compareTo(y)>0)System.out.println("x>y");

            String s=x.toString(2);//把十进制大数转化为二进制数存入字符串。

            int n=s.length();//获取字符串长度

            for (int i = 0; i < n; i++) {

                System.out.print(s.charAt(i) + " ");//空格隔开输出字符.

            }

            System.out.println();

 

            BigInteger sum = x.add(y);

            BigInteger difference = x.subtract(y);

            BigInteger product = x.multiply(y);

            BigInteger quotient = x.divide(y);  // 假设y不为0

            BigInteger remainder = x.remainder(y);  // 假设y不为0

 

            BigInteger gcd = x.gcd(y); // 最大公约数

            BigInteger modInverse = (y.signum() > 0 && x.gcd(y).equals(BigInteger.ONE)) ? x.modInverse(y) : null; //求逆元

            BigInteger power = x.pow(2); // x的2次幂

            BigInteger shiftedLeft = x.shiftLeft(1); // x左移1位

            BigInteger shiftedRight = x.shiftRight(1); // x右移1位

            BigInteger andResult = x.and(y); // 位与

            BigInteger orResult = x.or(y); // 位或

            BigInteger xorResult = x.xor(y); // 位异或

 

            System.out.println("x + y = " + sum);

            System.out.println("x - y = " + difference);

            System.out.println("x * y = " + product);

            System.out.println("x / y = " + quotient);

            System.out.println("x % y = " + remainder);

            System.out.println("gcd(x, y) = " + gcd);

            System.out.println("x modInverse y = " + (modInverse != null ? modInverse : "undefined (no inverse)"));

            System.out.println("x^2 = " + power);

            System.out.println("x << 1 = " + shiftedLeft);

            System.out.println("x >> 1 = " + shiftedRight);

            System.out.println("x & y = " + andResult);

            System.out.println("x | y = " + orResult);

            System.out.println("x ^ y = " + xorResult);

 

            BigDecimal x1 = new BigDecimal(cin.next()); // 读取高精度小数

            BigDecimal y1 = new BigDecimal(cin.next());

 

            BigDecimal sum1 = x1.add(y1);

            BigDecimal difference1 = x1.subtract(y1);

            BigDecimal product1 = x1.multiply(y1);

            BigDecimal quotient1 = x1.divide(y1, 10, RoundingMode.HALF_UP); // 设置结果精度为10位小数并使用四舍五入

 

            System.out.println("x + y = " + sum1);

            System.out.println("x - y = " + difference1);

            System.out.println("x * y = " + product1);

            System.out.println("x / y = " + quotient1); // 假设y不为0

 

            BigDecimal original = new BigDecimal("123.456789");

            BigDecimal result1 = original.setScale(3, RoundingMode.HALF_UP);// 小数点后保留3位,采用四舍五入

            System.out.println(result1);  // 输出:123.457

            BigDecimal dividend1 = new BigDecimal("10");

            BigDecimal divisor1 = new BigDecimal("3");

            // 指定精度为10位小数,使用四舍五入模式

            result1 = dividend1.divide(divisor1, 10, RoundingMode.HALF_UP);

            System.out.println(result1);  // 输出: 3.3333333333

        }

        cin.close();

    }

}

/*

c=a.max(b);           //  取a,b中较大的,a.min(b)就是取较小的

d=a.compareTo(b);    //比较a与b的大小 d=-1小于d=0等于 d=1大于  d为int型

a.equals(b);       //  判断a与b是否相等    相等返回true  不相等返回false

d=a.intValue();      //       将大数a转换为 int 类型赋值给 d

e=a.longValue();     //       将大数a转换为  long 类型赋值给 e

f=a.floatValue();    //       将大数a转换为  float 类型赋值给 f

g=a.doubleValue();   //       将大数a转换为  double 类型赋值给 g

s=a.toString();      //     将大数a转换为 String 类型赋值给 s

s=a.toPlainString();  //将大数a转换为String类型赋值给s,且不表示为科学计数法

a=BigInteger.valueOf(e);  // 将 e 以大数形式赋值给大数 a   e只能为long或int

a=newBigInteger(s, d);  // 将s数字字符串以d进制赋值给大数a如果d=s字符数字的进制则等同于将数字字符串以大数形式赋值给大数a

String st = Integer.toString(num, base); //把int型num当10进制的数转成base进制数存入st中(base <= 35).

int num = Integer.parseInt(st, base); //把st当做base进制,转成10进制的int

(parseInt有两个参数,第一个为要转的字符串,第二个为说明是什么进制).

BigInter m = new BigInteger(st, base); // st是字符串,base是st的进制.

a=cin.nextBigInteger(b);   //以b进制读入一个大数赋值给a

c=a.toString(b);          // 将大数a以b进制的方式赋给字符串c

a=newBigInteger(c, b);  //把c 当做“b进制“转为十进制大数赋值给a

*/

 

计算几何
链接:https://ac.nowcoder.com/acm/contest/1112/J
来源:牛客网

Bobo 有一个三角形和一个矩形,他想求他们交的面积。
具体地,三角形和矩形由 8 个整数 x1,y1,x2,y2,x3,y3,x4,y4x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4x1​,y1​,x2​,y2​,x3​,y3​,x4​,y4​ 描述。
表示三角形的顶点坐标是 (x1,y1),(x1,y2),(x2,y1)(x_1, y_1), (x_1, y_2), (x_2, y_1)(x1​,y1​),(x1​,y2​),(x2​,y1​),
矩形的顶点坐标是 (x3,y3),(x3,y4),(x4,y4),(x4,y3)(x_3, y_3), (x_3, y_4), (x_4, y_4), (x_4, y_3)(x3​,y3​),(x3​,y4​),(x4​,y4​),(x4​,y3​)

 

把三角形的顶点里在矩形里面的点放进数组;

把矩形的顶点里在三角形里面的点放进数组;

把三角形三条边和矩形四条边的交点放进数组(规范相交);

对这个数组去重并求凸包然后求凸包面积就是答案。

#include <bits/stdc++.h>

using namespace  std;

#define ll long long

const int N=1e3+10;

double eps=1e-8;

double pi=acos(-1);

struct Point{

    double x,y;

    Point(double x=0,double y=0):x(x),y(y){};

};

typedef Point Vector;

Vector operator +(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator -(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}

Vector operator *(Vector A,double B){return Vector(A.x*B,A.y*B);}

Vector operator /(Vector A,double B){return Vector(A.x/B,A.y/B);}

int dcmp(double x){

    if(fabs(x)<eps)return 0;

    return x<0?-1:1;

}

bool operator<(const Point&a,const Point&b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}

bool operator == (const Point &a,const Point &b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}

double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}

double Length(Vector A){return sqrt(Dot(A,A));}

double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}

double Angle(Vector A) {return atan2(A.y, A.x);}

 

struct Circle{    //圆

    Point c;

    double r;

    Circle(Point c = Point(0, 0), double r = 0):c(c),r(r){}

    Point point(double a){

        return Point(c.x+cos(a)*r,c.y+sin(a)*r);

    }

};

double dis(Point A,Point B){

    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));

}

int circle_circle(Circle C1,Circle C2,vector<Point>&sol){//返回圆与圆的交点个数

    double d=Length(C1.c-C2.c);

    if(dcmp(d)==0){

        if(dcmp(C1.r-C2.r)==0)return -1;

        return 0;

    }

    if(dcmp(C1.r+C2.r-d)<0)return 0;

    if(dcmp(fabs(C1.r-C2.r)-d)>0)return 0;

    double a=Angle(C2.c-C1.c);

    double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*d*C1.r));

    Point p1=C1.point(a-da),p2=C1.point(a+da);

    sol.push_back(p1);

    if(p1==p2)return 1;

    sol.push_back(p2);

    return 2;

}

 

Point line_point(Point p,Vector v,Point q,Vector w){//直线交点

    Vector u=p-q;

    double t=Cross(w,u)/Cross(v,w);

    return p+v*t;

}

bool onsegment(Point p,Point a1,Point a2){

    if(p==a1||p==a2)return true;

    return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;

}

bool segmentcross(Point a1,Point a2,Point b1,Point b2){

    double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),

           c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);

    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;

}

Point line_line(Point A,Point B,Point C,Vector D){//线段交点

    if(segmentcross(A,B,C,D)){

        return line_point(A,B-A,C,D-C);

    }

    return Point(123.456,0);

}

int tubao(Point *p,int n,Point *ch){

    sort(p,p+n);

    n=unique(p,p+n)-p;

    int m=0;

    for(int i=0;i<n;i++){

        while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;

        ch[m++]=p[i];

    }

    int k=m;

    for(int i=n-2;i>=0;i--){

        while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;

        ch[m++]=p[i];

    }

    if(n>1)m--;

    return m;

}

double tubaos(Point *p,int n){

    double area=0;

    for(int i=1;i<n-1;i++){

        area+=Cross(p[i]-p[0],p[i+1]-p[0]);

    }

    return area/2;

}

int intubao(Point *ch,int n,Point p){

    Vector A,B;

    int flag=0;

    for(int i=0;i<n;i++){

        A=ch[(i+1)%n]-ch[i];

        B=p-ch[i];

        if(onsegment(p,ch[i],ch[(i+1)%n])){

            flag=-1;

            break;

        }

        else if(Cross(A,B)>0){

            flag++;

        }

    }

    if(flag==-1||flag==n)return 1;

    return 0;

}

double x[N],y[N];

Point p[N],q[N],ch[N],ans[N];

int main(){

    while(~scanf("%lf%lf",&x[1],&y[1])){

        scanf("%lf%lf",&x[2],&y[2]);

        scanf("%lf%lf",&x[3],&y[3]);

        scanf("%lf%lf",&x[4],&y[4]);

        int n=0;

        p[n++]=Point(x[3],y[3]);

        p[n++]=Point(x[4],y[3]);

        p[n++]=Point(x[4],y[4]);

        p[n++]=Point(x[3],y[4]);

 

        int m=0;

        q[m++]=Point(x[1],y[1]);

        q[m++]=Point(x[1],y[2]);

        q[m++]=Point(x[2],y[1]);

 

        tubao(q,m,ch);

        int cnt=0;

        for(int i=0;i<n;i++){

            if(intubao(ch,m,p[i])){

                ans[cnt++]=p[i];

            }

        }

        for(int i=0;i<m;i++){

            if(intubao(p,n,q[i])){

                ans[cnt++]=q[i];

            }

        }

        p[n]=p[0];

        q[m]=q[0];

        for(int i=0;i<n;i++){

            for(int j=0;j<m;j++){

                Point A=line_line(p[i],p[i+1],q[j],q[j+1]);

                if(dcmp(A.x-123.456)!=0)ans[cnt++]=A;

            }

        }

        int n1=tubao(ans,cnt,ch);

        if(n1<=2)printf("%.8lf\n",0.0);

        else printf("%.8lf\n",tubaos(ch,n1));

    }

}

字符串双哈希

https://codeforc.es/contest/1200/problem/E

题意:给定一堆字符串,依次插入答案串尾部,每次删掉答案串的后缀 与 待插入串的前缀的最大匹配串

思路:hash匹配后缀和前缀,不断更新hash值

 

#define bug(x) cout<<#x<<" is "<<x<<endl

#define IO std::ios::sync_with_stdio(0)

#include <bits/stdc++.h>

#define iter ::iterator

#define pa pair<int,int>

using namespace  std;

#define ll long long

#define mk make_pair

#define pb push_back

#define se second

#define fi first

#define ls o<<1

#define rs o<<1|1

const int N=1e6+5;

int n;

ll mod[5]={1000000009,998244353};

ll base[5]={666127,777131};

ll p[N][2];

ll h[N][2];

void init(){

    for(int i=0;i<2;i++)p[0][i]=1;

    for(int i=1;i<=N-2;i++){

        for(int j=0;j<2;j++){

            p[i][j]=p[i-1][j]*base[j]%mod[j];

        }

    }

}

ll cal(int l,int r,int t){

    return (h[r][t]-h[l-1][t]*p[(r-l+1)][t]%mod[t]+mod[t])%mod[t];

}

ll get(char c){

    if('a'<=c&&c<='z')return c-'a';

    if('A'<=c&&c<='Z')return c-'A'+26;

    if('0'<=c&&c<='9')return c-'0'+52;

}

string s,t;

int main(){

    IO;

    cin>>n;

    cin>>s;

    int pre=1;

    init();

    for(int g=1;g<n;g++){

        cin>>t;

        int ns=s.length();

        for(int i=pre;i<=ns;i++){

            ll c=get(s[i-1]);

            for(int j=0;j<2;j++){

                h[i][j]=(h[i-1][j]*base[j]%mod[j]+c)%mod[j];

            }

        }

        int nt=t.length();

        ll H[2]={0};

        pre=ns+1;

        int id=0;

        for(int i=1;i<=nt;i++){

            int f=0;

            ll c=get(t[i-1]);

            for(int j=0;j<2;j++){

                H[j]=(H[j]*base[j]%mod[j]+c)%mod[j];

                if(cal(ns-i+1,ns,j)==H[j])f++;

            }

            if(f==2){

                id=i;

            }

            if(i==ns)break;

        }

        s+=t.substr(id,nt-id);

    }

    cout<<s<<endl;

}

/*

7

RAtONC14epz KfIenADgDKDci OMmOOQOc yVrfGLV49fW1 xntodZLM5 2f7LXdzX xIhm

5

I want to order pizza

*/


 

离散化和部分常用STL操作
sort(a,a+n);

int m=unique(a,a+n)-a;

for(int i=0;i<n;i++) b[i]=lower_bound(a,a+m,b[i])-a+1;

lower_bound(v.begin(), v.end(), x)//vector的lower_bound用法

multiset<int>s;

s.insert(x);

s.erase(x)//既可以删除与x相等的所有元素,也可以删除单个迭代器

s.erase(L,R)//删除迭代器[L,R)内的所有元素,是左闭右开区间。

auto id=s.lower_lound(x);

auto id=s.upper_bound(x);

List双向链表

#include <bits/stdc++.h>

using namespace std;

int main() {

    list<int> list1 = {1, 2, 3, 4, 5}; // 创建两个 list

    list<int> list2 = {10, 20, 30, 40, 50};

 

    list1.splice(list1.begin(), list2); // 1. 使用 splice 移动整个 list2 到 list1 的开始位置

 

    //list1: 10 20 30 40 50 1 2 3 4 5

    //list2: 为空

   

    auto it=find(list1.begin(),list2.end(),3);//指定list1某个位置移动到list1最前面

    list1.splice(list1.begin(),list1,it);

    //3 10 20 30 40 50 1 2 4 5

 

    // 3. 使用 splice 移动 list1 中的一段元素 [20, 40] 到 list2 的结束位置

    auto first = find(list1.begin(), list1.end(), 20);

    auto last = find(list1.begin(), list1.end(), 40);

    if (first != list1.end() && last != list1.end()) {

        last = next(last); // 使 last往后移动一次,再将[fisrt,last)区间内的数移到指定位置

        list2.splice(list2.end(), list1, first, last);//将list1的[first,last]中元素移动到list2末尾

    }

    // list1: 3 10 50 1 2 4 5

    // list2: 20 30 40

    it = find(list1.begin(), list1.end(), 50);

    auto it1=next(it);  // 得到it的下一个迭代器,指向的数为1

    auto it2=prev(it); // 得到it的上一个迭代器,指向的数为10

    cout<<*it1<<" "<<*it2<<endl;

}

   

主席树区间修改

#define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#define bug(x) cout<<#x<<" is "<<x<<endl

#include <bits/stdc++.h>

#define iter ::iterator

using namespace  std;

typedef long long ll;

typedef pair<int,int>P;

#define pb push_back

#define mk make_pair

#define se second

#define fi first

const ll mod=1e9+7;

const int N=1e5+5;

int n,q;

int a[N],rt[N*25],ls[N*25],rs[N*25];

ll sum[N*25],add[N*25];

int cnt;

void build(int &o,int l,int r){

    o=++cnt;

    if(l==r){

        sum[o]=a[l];

        return;

    }

    int m=(l+r)/2;

    build(ls[o],l,m);

    build(rs[o],m+1,r);

    sum[o]=sum[ls[o]]+sum[rs[o]];

}

void up(int &o,int pre,int l,int r,int ql,int qr,int val){

    o=++cnt;

    ls[o]=ls[pre];

    rs[o]=rs[pre];

    add[o]=add[pre];

    sum[o]=sum[pre]+1ll*val*(min(r,qr)-max(l,ql)+1);

    if(l>=ql&&r<=qr){

        add[o]+=val;

        return;

    }

    int m=(l+r)/2;

    if(ql<=m)up(ls[o],ls[pre],l,m,ql,qr,val);

    if(qr>m)up(rs[o],rs[pre],m+1,r,ql,qr,val);

}

ll qu(int o,int l,int r,int ql,int qr){

    if(l>=ql&&r<=qr)return sum[o];

    ll res=add[o]*(min(r,qr)-max(l,ql)+1);

    int m=(l+r)/2;

    if(ql<=m)res+=qu(ls[o],l,m,ql,qr);

    if(qr>m)res+=qu(rs[o],m+1,r,ql,qr);

    return res;

}

int main(){

    while(~scanf("%d%d",&n,&q)){

        for(int i=1;i<=n;i++)scanf("%d",&a[i]);

        cnt=0;

        build(rt[0],1,n);

        int time=0;

        while(q--){

            char op;

            int L,R,val;

            scanf(" %c",&op);

            if(op=='Q'){

                scanf("%d%d",&L,&R);

                ll ans=qu(rt[time],1,n,L,R);

                printf("%lld\n",ans);

            }

            else if(op=='C'){

                scanf("%d%d%d",&L,&R,&val);

                ++time;

                up(rt[time],rt[time-1],1,n,L,R,val);

 

            }

            else if(op=='H'){

                scanf("%d%d%d",&L,&R,&val);

                ll ans=qu(rt[val],1,n,L,R);

                printf("%lld\n",ans);

            }

            else{

                scanf("%d",&val);

                time=val;

            }

        }

        printf("\n");

    }

}

 

带权并查集

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int parent[N];

int value[N];  ///记录当前结点到根结点的距离

int FindSet(int x) {

    if (x == parent[x])

        return x;

    else {

        int t = parent[x]; //记录原父节点编号

        parent[x] = FindSet(parent[x]); //父节点变为根节点,此时value[x]=父节点到根节点的权值

        value[x] += value[t]; //当前节点的权值加上原本父节点的权值

        return parent[x];

    }

}

int main(){

    int n, m;

    while (scanf("%d%d", &n, &m) != EOF) {

        for (int i = 0; i <= n; i++) {

            parent[i] = i;

            value[i] = 0;

        }

        int ans = 0;

        while (m--) {

            int a, b, v;

            scanf("%d%d%d", &a, &b, &v);

            a--;

            int roota = FindSet(a);

            int rootb = FindSet(b);

            if (roota == rootb) {

                if (value[a] - value[b] != v) ans++;  ///精华部分1

            }

            else {

                parent[roota] = rootb;

                value[roota] = -value[a] + value[b] + v; ///精华部分2

            }

        }

        printf("%d\n", ans);

    }

}

树剖

#define IO std::ios::sync_with_stdio(0);

#include <bits/stdc++.h>

#define iter ::iterator

using namespace  std;

typedef long long ll;

typedef pair<ll,ll>P;

#define pb push_back

#define se second

#define fi first

#define rs o<<1|1

#define ls o<<1

#define inf 0x3f3f3f3f

const int N=1e5+5;

int n,q,rt,mod;

int a[N],b[N];

vector<int>g[N];

int deep[N],fa[N],id[N],son[N],siz[N],top[N];

int sumv[N*4],add[N*4];

int L[N*4],R[N*4];

void dfs1(int u,int f){

    deep[u]=deep[f]+1;

    fa[u]=f;

    siz[u]=1;

    int mx=-1;

    for(int i=0;i<g[u].size();i++){

        int v=g[u][i];

        if(v==f)continue;

        dfs1(v,u);

        siz[u]+=siz[v];

        if(siz[v]>mx){

            mx=siz[v];

            son[u]=v;

        }

    }

}

int tim;

void dfs2(int u,int topf){

    id[u]=++tim;

    a[tim]=b[u];

    top[u]=topf;

    if(!son[u])return;

    dfs2(son[u],topf);

    for(int i=0;i<g[u].size();i++){

        int v=g[u][i];

        if(v==fa[u]||v==son[u])continue;

        dfs2(v,v);

    }

}

void push(int o){

    sumv[o]=(sumv[ls]+sumv[rs])%mod;

}

void down(int o){

    if(add[o]){

        add[o]%=mod;

        sumv[ls]+=add[o]*(R[ls]-L[ls]+1);

        sumv[ls]%=mod;

        sumv[rs]+=add[o]*(R[rs]-L[rs]+1);

        sumv[rs]%=mod;

        add[ls]+=add[o];

        add[ls]%=mod;

        add[rs]+=add[o];

        add[rs]%=mod;

        add[o]=0;

    }

}

void build(int o,int l,int r){

    if(l==r){

        sumv[o]=a[l]%mod;

        L[o]=R[o]=l;

        return;

    }

    int m=(l+r)/2;

    build(ls,l,m);

    build(rs,m+1,r);

    L[o]=L[ls];

    R[o]=R[rs];

    push(o);

}

int qu(int o,int l,int r,int ql,int qr){

    if(l>=ql&&r<=qr){

        return sumv[o]%mod;

    }

    down(o);

    int m=(l+r)/2;

    int res=0;

    if(ql<=m)res+=qu(ls,l,m,ql,qr)%mod;

    res%=mod;

    if(qr>m)res+=qu(rs,m+1,r,ql,qr)%mod;

    res%=mod;

    return res;

}

void up(int o,int l,int r,int ql,int qr,int v){

    if(l>=ql&&r<=qr){

        v%=mod;

        add[o]+=v;

        add[o]%=mod;

        sumv[o]+=v*(r-l+1);

        sumv[o]%=mod;

        return;

    }

    down(o);

    int m=(l+r)/2;

    if(ql<=m)up(ls,l,m,ql,qr,v);

    if(qr>m)up(rs,m+1,r,ql,qr,v);

    push(o);

}

void qu1(int x,int y){//x节点到y节点的路径和

    int res=0;

    while(top[x]!=top[y]){

        if(deep[top[x]]<deep[top[y]])swap(x,y);

        res+=qu(1,1,n,id[top[x]],id[x]);

        res%=mod;

        x=fa[top[x]];

    }

    if(deep[x]>deep[y])swap(x,y);

    res+=qu(1,1,n,id[x],id[y])%mod;

    res%=mod;

    printf("%d\n",res);

}

void up1(int x,int y,int z){//把x节点到y节点的路径所有点加z

    while(top[x]!=top[y]){

        if(deep[top[x]]<deep[top[y]])swap(x,y);

        up(1,1,n,id[top[x]],id[x],z);

        x=fa[top[x]];

    }

    if(deep[x]>deep[y])swap(x,y);

    up(1,1,n,id[x],id[y],z);

}

int main(){

    scanf("%d%d%d%d",&n,&q,&rt,&mod);

    for(int i=1;i<=n;i++){

        scanf("%d",&b[i]);

        b[i]%=mod;

    }

    for(int i=1;i<n;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        g[x].pb(y);

        g[y].pb(x);

    }

    dfs1(rt,0);

    dfs2(rt,rt);

    build(1,1,n);

    while(q--){

        int op,x,y,z;

        scanf("%d",&op);

        if(op==1){//把x节点到y节点的路径所有点加z

            scanf("%d%d%d",&x,&y,&z);

            up1(x,y,z);

        }

        else if(op==2){//查询x节点到y节点的路径和

            scanf("%d%d",&x,&y);

            qu1(x,y);

        }

        else if(op==3){////把x节点的所有子孙加y

            scanf("%d%d",&x,&y);

            up(1,1,n,id[x],id[x]+siz[x]-1,y);

        }

        else{//查询x节点的子孙和

            scanf("%d",&x);

            printf("%d\n",qu(1,1,n,id[x],id[x]+siz[x]-1)%mod);

        }

    }

}

LCA

#define dbg(x) cout<<#x<<" = "<< (x)<< endl

#define IO std::ios::sync_with_stdio(0);

#include <bits/stdc++.h>

#define iter ::iterator

using namespace  std;

typedef long long ll;

typedef pair<ll,ll>P;

#define pb push_back

#define se second

#define fi first

#define rs o<<1|1

#define ls o<<1

const ll inf=0x7fffffff;

const int N=5e5+10;

int n,m,s;

vector<int>g[N];

int d[N],lg[N],p[N][22];

void dfs(int u,int fa){

    p[u][0]=fa;

    d[u]=d[fa]+1;

    for(int i=1;(1<<i)<=d[u];i++){

        p[u][i]=p[p[u][i-1]][i-1];

    }

    for(int i=0;i<g[u].size();i++){

        int v=g[u][i];

        if(v==fa)continue;

        dfs(v,u);

    }

}

 

 

 

 

void init(){

    for(int i=1;i<=n;i++){

        lg[i]=lg[i-1]+((1<<lg[i-1])==i);

    }

 

}

int lca(int x,int y){

    if(d[x]<d[y])swap(x,y);

    while(d[x]>d[y]){

        x=p[x][lg[d[x]-d[y]]-1];

    }

    if(x==y)return x;

    for(int i=lg[x];i>=0;i--){

        if(p[x][i]!=p[y][i]){

            x=p[x][i];

            y=p[y][i];

        }

    }

    return p[x][0];

}

int main(){

    //IO;

    cin>>n>>m>>s;

    for(int i=1;i<n;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        g[x].pb(y);

        g[y].pb(x);

    }

    init();

    dfs(s,0);

    while(m--){

        int x,y;

        scanf("%d%d",&x,&y);

        //cout<<lca(x,y)<<endl;

        printf("%d\n",lca(x,y));

    }

}

并查集、倍增

#include <cmath>

#include <cstdio>

#include <iostream>

using namespace std;

const int maxn = 100005, mod = 1000000007;

int n, m, fa[maxn][18], ans;

int find(int x, int k) {

    return fa[x][k] == x ? x : fa[x][k] = find(fa[x][k], k);

}

void merge(int x, int y, int k) {

    x = find(x, k), y = find(y, k);

    if(x != y) fa[x][k] = y;

}

int main() {

    scanf("%d %d", &n, &m);

    const int maxk = floor(log2(n));

    for(int i = 1; i <= n; ++i)

        for(int k = 0; k <= maxk; ++k)

            fa[i][k] = i;          

    for(int i = 1, l1, r1, l2, r2; i <= m; ++i) {

        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);

        for(int k = maxk; ~k; --k)

            if(l1+(1<<k)-1 <= r1) merge(l1, l2, k), l1 += 1<<k, l2 += 1<<k;

    }  

    for(int k = maxk; k; --k)

        for(int i = 1; i+(1<<k)-1 <= n; ++i) {

            int pos = find(i, k);

            merge(i, pos, k-1), merge(i+(1<<k-1), pos+(1<<k-1), k-1);

        }

    for(int i = 1; i <= n; ++i)

        if(fa[i][0] == i) ans = !ans ? 9 : ans * 10ll % mod;

    printf("%d\n", ans);

    return 0;

}

 


 

笛卡尔树

#define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#define bug(x) cout<<#x<<" is "<<x<<endl

#include <bits/stdc++.h>

#define iter ::iterator

using namespace  std;

typedef long long ll;

const int N=1e5+5;

int n;

ll a[N],b[N];

int st[N],ls[N],rs[N];

ll ans;

ll dfs(int u){

    if(!u)return 0;

    ll res=dfs(ls[u])+dfs(rs[u])+b[u];

    ll res1=min(res,a[u]);

    res1*=res1;

    ans=max(ans,res1);

    return res;

}

int main(){

    IO;

    cin>>n;

    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];

    int h=0;

    for(int i=1;i<=n;i++){

        int k=h;

        while(k>0&&a[st[k]]>a[i])k--;

        if(k>0)rs[st[k]]=i;

        if(k<h) ls[i]=st[k+1];

        st[++k]=i;

        h=k;

    }

    ans=0;

    dfs(st[1]);

    cout<<ans<<endl;

 

}

/*

11

9 3 7 1 8 12 10 20 15 18 5

*/

JAVA大数

import java.math.RoundingMode;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.Scanner;

import java.util.*;

import java.io.*;

public class Main {

    public static long mod=(long)(1e9+7);//1e9会被java看作double

    public static long fastpow(long x, long y) {//快速幂

        long res=1;

        while(y>0) {

            if((y&1)==1) {

                res=(res*x)%mod;

            }

            x=(x*x)%mod;

            y>>=1;

        }

        return res;

    }

    public static int N=200005;

    public static long[] b=new long[N];//声明数组

    public static void init(int n){//求n的阶乘

        b[0]=1;

        for(int i=1;i<=n;i++){

            b[i]=(b[i-1]*i)%mod;

        }

    }

    public static void main(String [] args){

        Scanner cin = new Scanner(System.in);

        int T = cin.nextInt();

        while (T-- > 0) {

            BigInteger x = cin.nextBigInteger();//输入大数

            BigInteger y = cin.nextBigInteger();

            BigInteger z = BigInteger.valueOf(123456789L);//L标记是long类型

            BigInteger k = BigInteger.ZERO;//赋值k为大数类型的0

            System.out.println(k);

            System.out.println(fastpow(2L,x.longValue()));//快速幂输出2的x次方

 

            if(x.compareTo(y)==0)System.out.println("x=y");//大数的比较函数

            else if(x.compareTo(y)<0)System.out.println("x<y");

            else if(x.compareTo(y)>0)System.out.println("x>y");

            String s=x.toString(2);//把十进制大数转化为二进制数存入字符串。

            int n=s.length();//获取字符串长度

            for (int i = 0; i < n; i++) {

                System.out.print(s.charAt(i) + " ");//空格隔开输出字符.

            }

            System.out.println();

 

            BigInteger sum = x.add(y);

            BigInteger difference = x.subtract(y);

            BigInteger product = x.multiply(y);

            BigInteger quotient = x.divide(y);  // 假设y不为0

            BigInteger remainder = x.remainder(y);  // 假设y不为0

 

            BigInteger gcd = x.gcd(y); // 最大公约数

            BigInteger modInverse = (y.signum() > 0 && x.gcd(y).equals(BigInteger.ONE)) ? x.modInverse(y) : null; //求逆元

            BigInteger power = x.pow(2); // x的2次幂

            BigInteger shiftedLeft = x.shiftLeft(1); // x左移1位

            BigInteger shiftedRight = x.shiftRight(1); // x右移1位

            BigInteger andResult = x.and(y); // 位与

            BigInteger orResult = x.or(y); // 位或

            BigInteger xorResult = x.xor(y); // 位异或

 

            System.out.println("x + y = " + sum);

            System.out.println("x - y = " + difference);

            System.out.println("x * y = " + product);

            System.out.println("x / y = " + quotient);

            System.out.println("x % y = " + remainder);

            System.out.println("gcd(x, y) = " + gcd);

            System.out.println("x modInverse y = " + (modInverse != null ? modInverse : "undefined (no inverse)"));

            System.out.println("x^2 = " + power);

            System.out.println("x << 1 = " + shiftedLeft);

            System.out.println("x >> 1 = " + shiftedRight);

            System.out.println("x & y = " + andResult);

            System.out.println("x | y = " + orResult);

            System.out.println("x ^ y = " + xorResult);

 

            BigDecimal x1 = new BigDecimal(cin.next()); // 读取高精度小数

            BigDecimal y1 = new BigDecimal(cin.next());

 

            BigDecimal sum1 = x1.add(y1);

            BigDecimal difference1 = x1.subtract(y1);

            BigDecimal product1 = x1.multiply(y1);

            BigDecimal quotient1 = x1.divide(y1, 10, RoundingMode.HALF_UP); // 设置结果精度为10位小数并使用四舍五入

 

            System.out.println("x + y = " + sum1);

            System.out.println("x - y = " + difference1);

            System.out.println("x * y = " + product1);

            System.out.println("x / y = " + quotient1); // 假设y不为0

 

            BigDecimal original = new BigDecimal("123.456789");

            BigDecimal result1 = original.setScale(3, RoundingMode.HALF_UP);// 小数点后保留3位,采用四舍五入

            System.out.println(result1);  // 输出:123.457

            BigDecimal dividend1 = new BigDecimal("10");

            BigDecimal divisor1 = new BigDecimal("3");

            // 指定精度为10位小数,使用四舍五入模式

            result1 = dividend1.divide(divisor1, 10, RoundingMode.HALF_UP);

            System.out.println(result1);  // 输出: 3.3333333333

        }

        cin.close();

    }

}

/*

c=a.max(b);           //  取a,b中较大的,a.min(b)就是取较小的

d=a.compareTo(b);    //比较a与b的大小 d=-1小于d=0等于 d=1大于  d为int型

a.equals(b);       //  判断a与b是否相等    相等返回true  不相等返回false

d=a.intValue();      //       将大数a转换为 int 类型赋值给 d

e=a.longValue();     //       将大数a转换为  long 类型赋值给 e

f=a.floatValue();    //       将大数a转换为  float 类型赋值给 f

g=a.doubleValue();   //       将大数a转换为  double 类型赋值给 g

s=a.toString();      //     将大数a转换为 String 类型赋值给 s

s=a.toPlainString();  //将大数a转换为String类型赋值给s,且不表示为科学计数法

a=BigInteger.valueOf(e);  // 将 e 以大数形式赋值给大数 a   e只能为long或int

a=newBigInteger(s, d);  // 将s数字字符串以d进制赋值给大数a如果d=s字符数字的进制则等同于将数字字符串以大数形式赋值给大数a

String st = Integer.toString(num, base); //把int型num当10进制的数转成base进制数存入st中(base <= 35).

int num = Integer.parseInt(st, base); //把st当做base进制,转成10进制的int

(parseInt有两个参数,第一个为要转的字符串,第二个为说明是什么进制).

BigInter m = new BigInteger(st, base); // st是字符串,base是st的进制.

a=cin.nextBigInteger(b);   //以b进制读入一个大数赋值给a

c=a.toString(b);          // 将大数a以b进制的方式赋给字符串c

a=newBigInteger(c, b);  //把c 当做“b进制“转为十进制大数赋值给a

*/

 

计算几何
链接:https://ac.nowcoder.com/acm/contest/1112/J
来源:牛客网

Bobo 有一个三角形和一个矩形,他想求他们交的面积。
具体地,三角形和矩形由 8 个整数 x1,y1,x2,y2,x3,y3,x4,y4x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4x1​,y1​,x2​,y2​,x3​,y3​,x4​,y4​ 描述。
表示三角形的顶点坐标是 (x1,y1),(x1,y2),(x2,y1)(x_1, y_1), (x_1, y_2), (x_2, y_1)(x1​,y1​),(x1​,y2​),(x2​,y1​),
矩形的顶点坐标是 (x3,y3),(x3,y4),(x4,y4),(x4,y3)(x_3, y_3), (x_3, y_4), (x_4, y_4), (x_4, y_3)(x3​,y3​),(x3​,y4​),(x4​,y4​),(x4​,y3​)

 

把三角形的顶点里在矩形里面的点放进数组;

把矩形的顶点里在三角形里面的点放进数组;

把三角形三条边和矩形四条边的交点放进数组(规范相交);

对这个数组去重并求凸包然后求凸包面积就是答案。

#include <bits/stdc++.h>

using namespace  std;

#define ll long long

const int N=1e3+10;

double eps=1e-8;

double pi=acos(-1);

struct Point{

    double x,y;

    Point(double x=0,double y=0):x(x),y(y){};

};

typedef Point Vector;

Vector operator +(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator -(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}

Vector operator *(Vector A,double B){return Vector(A.x*B,A.y*B);}

Vector operator /(Vector A,double B){return Vector(A.x/B,A.y/B);}

int dcmp(double x){

    if(fabs(x)<eps)return 0;

    return x<0?-1:1;

}

bool operator<(const Point&a,const Point&b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}

bool operator == (const Point &a,const Point &b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}

double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}

double Length(Vector A){return sqrt(Dot(A,A));}

double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}

double Angle(Vector A) {return atan2(A.y, A.x);}

 

struct Circle{    //圆

    Point c;

    double r;

    Circle(Point c = Point(0, 0), double r = 0):c(c),r(r){}

    Point point(double a){

        return Point(c.x+cos(a)*r,c.y+sin(a)*r);

    }

};

double dis(Point A,Point B){

    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));

}

int circle_circle(Circle C1,Circle C2,vector<Point>&sol){//返回圆与圆的交点个数

    double d=Length(C1.c-C2.c);

    if(dcmp(d)==0){

        if(dcmp(C1.r-C2.r)==0)return -1;

        return 0;

    }

    if(dcmp(C1.r+C2.r-d)<0)return 0;

    if(dcmp(fabs(C1.r-C2.r)-d)>0)return 0;

    double a=Angle(C2.c-C1.c);

    double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*d*C1.r));

    Point p1=C1.point(a-da),p2=C1.point(a+da);

    sol.push_back(p1);

    if(p1==p2)return 1;

    sol.push_back(p2);

    return 2;

}

 

Point line_point(Point p,Vector v,Point q,Vector w){//直线交点

    Vector u=p-q;

    double t=Cross(w,u)/Cross(v,w);

    return p+v*t;

}

bool onsegment(Point p,Point a1,Point a2){

    if(p==a1||p==a2)return true;

    return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;

}

bool segmentcross(Point a1,Point a2,Point b1,Point b2){

    double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),

           c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);

    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;

}

Point line_line(Point A,Point B,Point C,Vector D){//线段交点

    if(segmentcross(A,B,C,D)){

        return line_point(A,B-A,C,D-C);

    }

    return Point(123.456,0);

}

int tubao(Point *p,int n,Point *ch){

    sort(p,p+n);

    n=unique(p,p+n)-p;

    int m=0;

    for(int i=0;i<n;i++){

        while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;

        ch[m++]=p[i];

    }

    int k=m;

    for(int i=n-2;i>=0;i--){

        while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;

        ch[m++]=p[i];

    }

    if(n>1)m--;

    return m;

}

double tubaos(Point *p,int n){

    double area=0;

    for(int i=1;i<n-1;i++){

        area+=Cross(p[i]-p[0],p[i+1]-p[0]);

    }

    return area/2;

}

int intubao(Point *ch,int n,Point p){

    Vector A,B;

    int flag=0;

    for(int i=0;i<n;i++){

        A=ch[(i+1)%n]-ch[i];

        B=p-ch[i];

        if(onsegment(p,ch[i],ch[(i+1)%n])){

            flag=-1;

            break;

        }

        else if(Cross(A,B)>0){

            flag++;

        }

    }

    if(flag==-1||flag==n)return 1;

    return 0;

}

double x[N],y[N];

Point p[N],q[N],ch[N],ans[N];

int main(){

    while(~scanf("%lf%lf",&x[1],&y[1])){

        scanf("%lf%lf",&x[2],&y[2]);

        scanf("%lf%lf",&x[3],&y[3]);

        scanf("%lf%lf",&x[4],&y[4]);

        int n=0;

        p[n++]=Point(x[3],y[3]);

        p[n++]=Point(x[4],y[3]);

        p[n++]=Point(x[4],y[4]);

        p[n++]=Point(x[3],y[4]);

 

        int m=0;

        q[m++]=Point(x[1],y[1]);

        q[m++]=Point(x[1],y[2]);

        q[m++]=Point(x[2],y[1]);

 

        tubao(q,m,ch);

        int cnt=0;

        for(int i=0;i<n;i++){

            if(intubao(ch,m,p[i])){

                ans[cnt++]=p[i];

            }

        }

        for(int i=0;i<m;i++){

            if(intubao(p,n,q[i])){

                ans[cnt++]=q[i];

            }

        }

        p[n]=p[0];

        q[m]=q[0];

        for(int i=0;i<n;i++){

            for(int j=0;j<m;j++){

                Point A=line_line(p[i],p[i+1],q[j],q[j+1]);

                if(dcmp(A.x-123.456)!=0)ans[cnt++]=A;

            }

        }

        int n1=tubao(ans,cnt,ch);

        if(n1<=2)printf("%.8lf\n",0.0);

        else printf("%.8lf\n",tubaos(ch,n1));

    }

}

字符串双哈希

https://codeforc.es/contest/1200/problem/E

题意:给定一堆字符串,依次插入答案串尾部,每次删掉答案串的后缀 与 待插入串的前缀的最大匹配串

思路:hash匹配后缀和前缀,不断更新hash值

 

#define bug(x) cout<<#x<<" is "<<x<<endl

#define IO std::ios::sync_with_stdio(0)

#include <bits/stdc++.h>

#define iter ::iterator

#define pa pair<int,int>

using namespace  std;

#define ll long long

#define mk make_pair

#define pb push_back

#define se second

#define fi first

#define ls o<<1

#define rs o<<1|1

const int N=1e6+5;

int n;

ll mod[5]={1000000009,998244353};

ll base[5]={666127,777131};

ll p[N][2];

ll h[N][2];

void init(){

    for(int i=0;i<2;i++)p[0][i]=1;

    for(int i=1;i<=N-2;i++){

        for(int j=0;j<2;j++){

            p[i][j]=p[i-1][j]*base[j]%mod[j];

        }

    }

}

ll cal(int l,int r,int t){

    return (h[r][t]-h[l-1][t]*p[(r-l+1)][t]%mod[t]+mod[t])%mod[t];

}

ll get(char c){

    if('a'<=c&&c<='z')return c-'a';

    if('A'<=c&&c<='Z')return c-'A'+26;

    if('0'<=c&&c<='9')return c-'0'+52;

}

string s,t;

int main(){

    IO;

    cin>>n;

    cin>>s;

    int pre=1;

    init();

    for(int g=1;g<n;g++){

        cin>>t;

        int ns=s.length();

        for(int i=pre;i<=ns;i++){

            ll c=get(s[i-1]);

            for(int j=0;j<2;j++){

                h[i][j]=(h[i-1][j]*base[j]%mod[j]+c)%mod[j];

            }

        }

        int nt=t.length();

        ll H[2]={0};

        pre=ns+1;

        int id=0;

        for(int i=1;i<=nt;i++){

            int f=0;

            ll c=get(t[i-1]);

            for(int j=0;j<2;j++){

                H[j]=(H[j]*base[j]%mod[j]+c)%mod[j];

                if(cal(ns-i+1,ns,j)==H[j])f++;

            }

            if(f==2){

                id=i;

            }

            if(i==ns)break;

        }

        s+=t.substr(id,nt-id);

    }

    cout<<s<<endl;

}

/*

7

RAtONC14epz KfIenADgDKDci OMmOOQOc yVrfGLV49fW1 xntodZLM5 2f7LXdzX xIhm

5

I want to order pizza

*/


 

离散化和部分常用STL操作
sort(a,a+n);

int m=unique(a,a+n)-a;

for(int i=0;i<n;i++) b[i]=lower_bound(a,a+m,b[i])-a+1;

lower_bound(v.begin(), v.end(), x)//vector的lower_bound用法

multiset<int>s;

s.insert(x);

s.erase(x)//既可以删除与x相等的所有元素,也可以删除单个迭代器

s.erase(L,R)//删除迭代器[L,R)内的所有元素,是左闭右开区间。

auto id=s.lower_lound(x);

auto id=s.upper_bound(x);

List双向链表

#include <bits/stdc++.h>

using namespace std;

int main() {

    list<int> list1 = {1, 2, 3, 4, 5}; // 创建两个 list

    list<int> list2 = {10, 20, 30, 40, 50};

 

    list1.splice(list1.begin(), list2); // 1. 使用 splice 移动整个 list2 到 list1 的开始位置

 

    //list1: 10 20 30 40 50 1 2 3 4 5

    //list2: 为空

   

    auto it=find(list1.begin(),list2.end(),3);//指定list1某个位置移动到list1最前面

    list1.splice(list1.begin(),list1,it);

    //3 10 20 30 40 50 1 2 4 5

 

    // 3. 使用 splice 移动 list1 中的一段元素 [20, 40] 到 list2 的结束位置

    auto first = find(list1.begin(), list1.end(), 20);

    auto last = find(list1.begin(), list1.end(), 40);

    if (first != list1.end() && last != list1.end()) {

        last = next(last); // 使 last往后移动一次,再将[fisrt,last)区间内的数移到指定位置

        list2.splice(list2.end(), list1, first, last);//将list1的[first,last]中元素移动到list2末尾

    }

    // list1: 3 10 50 1 2 4 5

    // list2: 20 30 40

    it = find(list1.begin(), list1.end(), 50);

    auto it1=next(it);  // 得到it的下一个迭代器,指向的数为1

    auto it2=prev(it); // 得到it的上一个迭代器,指向的数为10

    cout<<*it1<<" "<<*it2<<endl;

}

标签:return,Point,int,ACM,Vector,mod,模板,define
From: https://www.cnblogs.com/ccsu-kid/p/18226374

相关文章