首页 > 其他分享 >1.19闲话

1.19闲话

时间：2024-01-19 21:25:48浏览次数：33  
标签：int 闲话 top son dfn text inline 1.19

推歌：凉雨/洛天依 by COPY

今天中午看了一中午之前买的天依的珍藏色纸，腿看起来肉肉的好想捏一下诶但是非常伤心捏不到呜呜呜

图论复习篇？加个字符串吧

  • 最短路

    • ﹣洛依の (Floyd，最前面的是个负号)

      这个的名字我比较喜欢，但是复杂度\(O(n^3)\)不太好，所以我想要尝试对其优化

      原版就是一DP，没啥意义，但是能一次求出来任意两点的最短路

      for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            d[i][j]=min(d[i][k]+d[k][j],d[i][j]);

      首先考虑一下能不能用除了邻接矩阵以外的比较好的存图方法

      众所周知，﹣洛依の要求\(O(1)\)查询，好像只能用邻接矩阵，那非常不好啊

      所以我去查了资料，查了半天也没查出来啥

      然后疑似优化比较有效的版本大概打了一份

      memset(d,0x7f,sizeof(d));
for(int k=1;k<=n;k++){
    for(int i=s;i<=n;i++){
        if(k==i) continue;
        const int t((k<i)?d[i][k]:d[k][i]);
        if(t==0x7f7f7f7f) continue;
        for(int j=t;j<=min(i,k);j++){
            d[i][j]=min(t+d[k][j],d[i][j]);
        }    
        for(int j=k+1;j<=i;j++){
            d[i][j]=min(t+d[j][k],d[i][j]);
        }    
    }
}

      对于最上面那个，如果是求固定两点的距离其实可以是这样的

      for(int k=1;k<=n;k++)
    for(int i=s;i<=n;i++){
        if(k==i) continue;
        const int t((k<i)?d[i][k]:d[k][i]);
        if(t==INF) continue;
        for(int j=t;j<=n;j++)
            d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
    }

      但是这都是一些比较无意义的

    • dijskrua

      只适用于没有负环的图

      可以堆优化，如下

      void dij(int s){
    memset(v,0,sizeof(v));
    for(int i=1;i<=n;i++)
        d[i]=2147483647;
    d[s]=0;
    q.push(make_pair(0,s));
    while(q.size()){
        int x=q.top().second;
        q.pop();
        if(v[x])
            continue;
        v[x]=1;
        for(int i=head[x];i;i=t[i].Next){
            int y=t[i].ver,z=t[i].edge;
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
    }
}

    • SPFA

      真不会，有负环就上﹣洛依の得了

  • 树链剖分(重)

    这个感觉非常好用，就是有点难背过

    两个DFS，一颗线段树，还有树剖自带的几个东西，代码量直接增加\(1\sim 2\text k\)起步

    还有一些不好的概念

    重儿子：子树结点数目最多的结点

    轻儿子：除了重儿子以外的结点

    重边：父亲结点和重儿子连成的边

    轻边：父亲节点和轻儿子连成的边

    重链：由多条重边连接而成的路径

    轻链：由多条轻边连接而成的路径

    但是反正是复习，就直接放代码了

    • 第一个DFS

      这个主要就是找出每个结点的父节点、深度、子树大小、重子节点

      这里的son就是重子节点啦，当son跑完还是-1那就是没有重子节点惹

      inline void Dfs1(int q){
    T[q].son=-1;
    T[q].siz=1;
    for(int j=head[q];j;j=NEXT[j]){
        if(T[TO[j]].dep) continue;
        T[TO[j]].dep=T[q].dep+1;
        T[TO[j]].fa=q;
        Dfs1(TO[j]);
        T[q].siz+=T[TO[j]].siz;
        if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) 
            T[q].son=TO[j];
    }
}

      注意：使用前需要把\(root\)的深度初始化为\(1\)哦

      伪代码如下

      \[\begin{array}{l} \text{DFS1 }(u){} \\ \begin{array}{ll} 1 & u.hson\gets -1 \\ 2 & u.size\gets 1 \\ 3 & \textbf{for }\text{each }u\text{'s son }v \\ 4 & \qquad v.dep\gets u.dep+1\\ 5 & \qquad v.father\gets u \\ 6 & \qquad \text {DFS}1(v)\\ 7 & \qquad u.size\gets u.size+v.size \\ 8 & \qquad \textbf{if }v.size> (u.hson).size \\ 9 & \qquad \qquad u.hson\gets v \\ \end{array} \end{array} \]

    • 第二个DFS

      这里是记录所在链的链顶，DFS序，对应的rank

      这里的top是链顶,dfn是DFS序,rnk是对应的rank

      inline void Dfs2(int q,int v){
    T[q].top=v;
    T[q].dfn=++cnt;
    T[cnt].rnk=q;
    if(T[q].son==-1)
        return;
    Dfs2(T[q].son,v);
    for(int j=head[q];j;j=NEXT[j]){
        if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
            Dfs2(TO[j],TO[j]);
    }
}

      伪代码如下

      \[\begin{array}{l} \text{DFS2 }(u,v){} \\ \begin{array}{ll} 1 & u.top\gets v \\ 2 & cnt\gets cnt+1\\ 3 & u.dfn\gets cnt \\ 4 & cnt.rnk=q \\ 5 & \textbf{if } u.son=-1\\ 6 & \qquad \text{return}\\ 7 & \text{DFS2}(u.son,v)\\ 8 & \textbf{for }\text{each }u\text{'s son }j \\ 9 & \qquad \textbf{if }(j \ne u \textbf{ and }j \ne u.son)\\ 10 & \qquad \qquad \text{DFS2}(j,j) \\ \end{array} \end{array} \]

    两个DFS写完，接下来就简单啦

    • 线段树部分

      没啥重要的，就一普通线段树，建树改一下就行了

      inline void build(int q,int l,int r){
    t[q].l=l,t[q].r=r;
    t[q].siz=r-l+1;
    if(l==r){
        t[q].dat=a[T[l].rnk];
        return;
    }
    build(lC,l,mid);
    build(rC,mid+1,r);
    t[q].dat=t[lC].dat+t[rC].dat;
}

      其他和普通的线段树一样

    • 两点之间路径修改/查询

      呃呃呃，有一个显然的结论QAQ

      \(x\) 到 \(x.top\) 中的节点在线段树上是连续的

      那么一个非常显然的思路

      每次都让查询中两个点里 \(dep\) 较低的向上跳到其的 \(top\) 的父节点,同时线段树上更新

      最后两个点会处于同一重链，直接修改就行了

      inline void TreeAdd(int x,int y,int val){
    while(T[x].top!=T[y].top){
        if(T[T[x].top].dep<T[T[y].top].dep) 
            std::swap(x,y);
        ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
        x=T[T[x].top].fa;
    }
    if(T[x].dep>T[y].dep) 
        std::swap(x,y);
    ST::change(1,T[x].dfn,T[y].dfn,val);
}
inline int TreeSum(int x,int y){
    int ans=0;
    while(T[x].top!=T[y].top){
        if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
        ans=ans+ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
        x=T[T[x].top].fa;
    }
    if(T[x].dep>T[y].dep) std::swap(x,y);
    return ans+ST::asksum(1,T[x].dfn,T[y].dfn);
}

      伪代码如下

      \[\begin{array}{l} \text{TreeAdd }(x,y,val){} \\ \begin{array}{ll} 1 & \textbf{while }x.top \ne y.top \\ 2 & \qquad \textbf{if }[x.top].dep < [y.top].dep\\ 3 & \qquad \qquad \text{swap}(x,y)\\ 4 & \qquad \text {change }(1,[x.top].dfn,x.dfn,val) \\ 5 & \qquad x=[x.top].fa\\ 6 & \qquad \text{return}\\ 7 & \textbf{if }x.dep>y.dep\\ 8 & \qquad \text{swap}(x,y)\\ 9 & \text {change }(1,[x.top].dfn,x.dfn,val)\\ \end{array} \end{array} \]

    • 子树修改/查询

      这个比较好，因为简单

      一棵树的子树在线段树上是连续的,所以直接线段树修改就行啦QWQ

      inline void AddTree(int x,int val){
    ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
}
inline int AskTree(int x){
    return ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
}

      伪代码如下

      \[\begin{array}{l} \text{TreeAdd }(x,y,val){} \\ \begin{array}{ll} 1 & \text{change}(1,x.dfn,x.dfn+x.siz-1,val)\\ \end{array} \end{array} \]

    • 完整代码

      点击查看代码 
      #include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM];
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=t[lC].dat+t[rC].dat;
        #ifdef debug
            std::cout<<t[q].dat<<std::endl;
        #endif
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=(t[lC].siz)*t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=(t[rC].siz)*t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=t[q].siz*v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=t[lC].dat+t[rC].dat;
    }
    long long asksum(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy!=0) 
            lazy(q);
        return asksum(lC,l,r)+asksum(rC,l,r); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans=ans+ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return ans+ST::asksum(1,T[x].dfn,T[y].dfn);
    }
    inline void AddTree(int x,int val){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
    }
    inline int AskTree(int x){
        return ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif 
    int N=read(),M=read(),R=read();
    for(int i=1;i<=N;i++)
        a[i]=read();
    for(int i=1;i<N;i++){
        int u=read(),v=read();
        Grape::add(u,v);
        Grape::add(v,u);
    }
    T[R].dep=1;
    killTree::Dfs1(R);
    killTree::Dfs2(R,R);
    ST::build(1,1,N);
    for(int i=1;i<=M;i++){
        int q=read();
        if(q==1){
            int x=read(),y=read();
            killTree::AddTree(x,y);
        }
        else{
            int x=read();
            std::cout<<killTree::AskTree(x)<<std::endl;
        }
    }
}

  • \(\text{tarjan}\)

    看起来好像比较无意义？肯定不考吧估计

  • 二分图

    真不会，唯一打的一道题还是用dinic打的

  • 字符串

    • 字符串hash

      傻逼哈希我每次都因为模数而死

      选个模数，选个进制数，乱搞就行，我个人比较推荐用pair<ll,ull>来搞双模数hash，最开始记得预处理那个倍数

      点击查看代码 
      #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e4+5,M=205,B=1009;
const int P1=1000000000039;
namespace IO{
    inline void close(){
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
        std::cout.tie(0);
    }
    inline void Fire(){
        freopen("data.in","r",stdin);
        freopen("data.out","w",stdout);
    }
    inline int read(){
        int s = 0,w = 1;char ch = getchar();
        while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}
        while(ch>='0'&&ch<='9'){ s=(s<<3)+(s<<1)+ch-'0';ch = getchar();}
        return s*w;
    }
    inline void write(int x){
        char F[200];int tmp=x>0?x:-x,cnt=0;
        if(x<0)putchar('-');while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}
        if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');
    }
}   
using namespace IO;
struct HASH{
    int hash1,hash2;
};
inline bool cmp(register HASH a,register HASH b){
    return a.hash1<b.hash1;
}
int ans;
pair<int,unsigned long long> Hash[N][M],po[M];;
HASH a[N];
char s[M];
signed main(){
    register int n(read()),m(read());read();
    po[0].first=po[0].second=1;
    for(register int i(1);i<=m;++i) {
        po[i].first=(B*po[i-1].first)%P1;
        po[i].second=B*po[i-1].second;
    }
    for(register int i(1);i<=n;++i){
        scanf("%s",s+1);
        for(register int j(1);j<=m;j++) {
            Hash[i][j].first=(Hash[i][j-1].first*B+s[j])%P1;
            Hash[i][j].second=Hash[i][j-1].second*B+s[j];
        }
    }
    for(register int j(1);j<=m;++j){
        for(register int i(1);i<=n;++i){
            a[i].hash1=((Hash[i][m].first-Hash[i][j].first*po[m-j].first+Hash[i][j-1].first*po[m-j+1].first)+P1)%P1;
            a[i].hash2=Hash[i][m].second-Hash[i][j].second*po[m-j].second+Hash[i][j-1].second*po[m-j+1].second;
        }
        sort(a+1,a+1+n,cmp);
        register int cnt(0);
        for(register int i(2);i<=n;++i){
            ans+=((a[i].hash2==a[i-1].hash2)&&(a[i].hash1==a[i-1].hash1))?++cnt:cnt=0;
        }
    }
    write(ans);
}

    • kmp

      kmp主要那个失配指针，然后找broder（是叫这个吧？），一般感觉纯kmp用处没有hash更大

      int N=a.size()-1,M=b.size()-1;
Next[1]=0;
ans=0;
for(int i=2,j=0;i<=N;i++){
    while(j>0 && a[i]!=a[j+1]) 
        j=Next[j];
    if(a[i]==a[j+1]) j++;
    Next[i]=j;
}
for(int i=1,j=0;i<=M;i++){
    while(j>0 && (j==N || b[i]!=a[j+1])) 
        j=Next[j];
    if(b[i]==a[j+1]) j++;
    f[i]=j;
    if(f[i]==N) ans++;
}

    • tire

      明天吧

标签：int,闲话,top,son,dfn,text,inline,1.19
From： https://www.cnblogs.com/Vsinger-LuoTianYi/p/17973407

相关文章

  • 南外集训 2024.1.19 T3
    给定正整数\(m,n\)使得\(m|n\)，求\([1,n]\cap\mathbbZ\)的所有子集中有多少和是\(m\)的倍数。\(1\leT\le10^4,1\lem\le10^7,1\len\le10^{18}\)相当于求\(F(z)=(1+z^0)(1+z^1)\dots(1+z^{n-1})\)的\(0,m,2m,\dots\)项之和。单位根反演可得\(Ans=......
  • 闲话1.19
    摆。上午模拟赛摆了，哈哈，交都没交......
  • 1.19 _fetchSql() 和 getLastSql() 的用法
    1fetchSql()的用法重要点：语法2getLastSql()的用法删除不掉的原因具有外键的那张表叫：主表，也就是details是主表，internet_bar这个是从表当使用:DELETEFROMbusiness_internet_barwhereid=34;删除表中的数据的时候,会发生下面的错误DELETEFROM`business_in......
  • 2024.1.19寒假每日总结10
    算法题：2809.使数组和小于等于x的最少时间-力扣（LeetCode）spark广播器场景:本地集合对象和分布式集合对象(RDD)进行关联的时候需要将本地集合对象封装为广播变量可以节省:1.网络IO的次数2.Executor的内存占用 ......
  • 1.19每日总结
    Python3解释器Linux/Unix的系统上，一般默认的python版本为2.x，我们可以将python3.x安装在 /usr/local/python3 目录中。安装完成后，我们可以将路径 /usr/local/python3/bin 添加到您的Linux/Unix操作系统的环境变量中，这样您就可以通过shell终端输入下面的命令来启动......
  • 2024.1.19
    9点26解决了一个第三方库require(xxxx)导致的vite4在build时报错Can'tfindvariable:requirehttps://github.com/vite-plugin/vite-plugin-commonjs《代码提取》三种等级，导出提取、函数提取和闭包提取。其中可以导出提取和闭包提取很有趣。其中导出提取解释了react-r......
  • 【2024.01.19】huginn爬取什么值得买的排行榜
    一句命令就行，主要是搭配RSS使用dockerrun-d-p3000:3000ghcr.io/yhdsl/huginn:latest这次主要是为了自定义爬取内容筛选掉一些我用不上的，比如说奶粉啥的{"schema_version":1,"name":"什么值得买榜单","description":"关键词里面自己修改","source_url&qu......
  • 1.19学习进度
    1.standalone是一个完整的分布式集群环境；standalone集群在进程上主要有三类进程：主节点master及昵称、从节点的worker进程、历史服务器哦historyserver（可选）2.4040：是一个运行的application在运行的过程中临时绑定的端口，用以查看当前任务的状态。4040被占用会顺延到4041、4042等。404......
  • 2024.1.19日报
    本质：启动一个JVMProcess进程（一个进程里有多个线程），执行任务TaskLocal模式可以限制模拟Spark集群环境的线程数量，即Local[N]或Local[*]其中N代表可以使用N个线程，每个线程拥有一个cpucore，如果不指定N，则默认是1个线程（该线程有一个core）。通常Cpu有几个core，就指定几个线程，最大化利用......
  • 1.18闲话
    同桌是弱智火p，天天启动，今天上英语课在哪里开局就是霸体加螺旋丸直接拿到你的先手替身我就飞雷神然后走过去捡标再次拿到先手哎呀我真是太有实力了然后被英语老师D了，鉴定为玩青水玩的推歌不想推太大众的，但是不大众的都想不起来了，只能想好久才想起来几个推歌：得过且过的勇者/洛天依......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99