首页 > 其他分享 >写板子的时候发现的易错点

写板子的时候发现的易错点

时间：2023-11-14 21:58:26浏览次数：28  
标签：发现 易错 ch tag1 int tr 板子 rd define

KMP

void get_nt(){
    int j=0;
    for(int i=2;i<=tl;++i){
        while(j&&t[i]!=t[j+1])j=nt[j];
        if(t[j+1]==t[i])j+=1;
        nt[i]=j;
    }
    
}
void KMP(){
    int j=0;
    F(i,1,sl){
        while(j&&s[i]!=t[j+1])j=nt[j];
        if(s[i]==t[j+1])j+=1;
        if(j==tl){
            cout<<i-tl+1<<'\n';
            j=nt[j];
        }
    }
}

错一位求nt和j+1来匹配

manacher

void prew(){
    s[++sl]='@';
    s[++sl]='#';
    F(i,1,tl){
        s[++sl]=t[i];
        s[++sl]='#';
    }
    s[++sl]='%';
}
int p[N];
int manacher(){
    int ans=0;
    for(int i=1,r=0,mid=0;i<=sl;++i){
        if(i<=r)p[i]=min(r-i+1,p[(mid<<1)-i]);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])++p[i];
        if(i+p[i]>r){
            r=i+p[i]-1;
            mid=i;
        }
        ans=max(ans,p[i]);
    }
    return ans;
}
signed main(){
    scanf("%s",t+1);
    tl=strlen(t+1);
    prew();
//  F(i,1,sl)cout<<s[i]<<' ';cout<<'\n';
    cout<<manacher()-1<<'\n';
    return 0;
}

第一位是"@",最后一位是"%",中间是"#",用以区分
求出来的回文半径是变化后的,具体的要具体分析

点双

#include<bits/stdc++.h>
#define int long long
#define F(i,i0,n) for(int i=(i0);i<=(n);i++)
#define D(i,n,i0) for(int i=(n);i>=i0;--i)
#define pii pair<int,int>
#define fr first
#define sc second
#define pb push_back
using namespace std;
inline int rd(){
    int f=0,x=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return f?-x:x;
}
const int N=2e6+5,mod=1e9+7;
int n,m;
struct Id{
    int v,nt;
}e[N<<1];
int p[N],id=1;
void add(int x,int y){
    e[++id]={y,p[x]};p[x]=id;
} 
int dfn[N],low[N],Tim;
int st[N],top;
vector<int>dcc[N];
int tot;
void Tarjan(int x,int ffa){
    dfn[x]=low[x]=++Tim;
    
    int cnt=0;
    if(!p[x]&&ffa==0){
        dcc[++tot].pb(x);
        return ;
    }
    st[++top]=x;
    for(int i=p[x];i;i=e[i].nt){
        int v=e[i].v;
        if(!dfn[v]){
            cnt++;
            Tarjan(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]){
                tot++;
                int y;
                dcc[tot].pb(x);
                do{
                    y=st[top--];
                    dcc[tot].pb(y);
                }while(y!=v);
            }
        }
        else low[x]=min(low[x],dfn[v]);
    }
}
signed main(){
    n=rd(),m=rd();
    F(i,1,m){
        int x=rd(),y=rd();
        if(x==y)continue;
        add(x,y);add(y,x);
    }
    F(i,1,n)if(!dfn[i]){
        Tarjan(i,0);
    }
    cout<<tot<<'\n';
    F(i,1,tot){
        cout<<dcc[i].size()<<' ';
        for(auto v:dcc[i])cout<<v<<" ";cout<<'\n';
    }
    return 0;
}

注意出栈方式,以及点双不用判父亲

欧拉路径

#include <bits/stdc++.h>
#define F(i,i0,n) for(int i=i0;i<=n;i++)
#define mod 23333
#define ll long long
#define MAXN 100005
using namespace std;
inline int rd(){
    int 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-48;ch=getchar();}
    return x*f;
}
int n,m,du[MAXN][2],del[MAXN],cnt[MAXN]; //0 rudu 1 chudu
int vis[MAXN];
vector<int >p[MAXN];
stack<int >s;
void dfs(int x){
    for(int i=del[x];i<p[x].size();i=del[x]){
        del[x]=i+1;
        dfs(p[x][i]);
    }
    s.push(x);
}
int main() {
    n=rd(),m=rd(); 
    F(i,1,m){
        int a=rd(),b=rd();
        p[a].push_back(b);
        du[a][1]++;
        du[b][0]++;
    }
    F(i,1,n)sort(p[i].begin(),p[i].end());
    int flag=1;
    int st=1;
    F(i,1,n){
        if(du[i][0]!=du[i][1]){
            flag=0;
            if(du[i][1]-du[i][0]==1)cnt[1]++,st=i;
            else if(du[i][0]-du[i][1]==1)cnt[0]++;
            else {
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    if(!flag&&!(cnt[0]==cnt[1]&&cnt[0]==1)){
        cout<<"No"<<endl;
        return 0;
    }
    dfs(st);
    while(!s.empty()){
        cout<<s.top()<<' ';s.pop();
    }
    return 0;
}

注意是出的时候加入栈中以及倒序出栈

边双

#include<bits/stdc++.h>
#define int long long
#define F(i,i0,n) for(int i=(i0);i<=(n);i++)
#define D(i,n,i0) for(int i=(n);i>=i0;--i)
#define pii pair<int,int>
#define fr first
#define sc second
#define pb push_back
using namespace std;
inline int rd(){
    int f=0,x=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return f?-x:x;
}
const int N=2e6+5,mod=1e9+7;
int n,m;
struct Id{
    int v,nt;
}e[N<<1];
int p[N],id=1;
void add(int x,int y){
    e[++id]={y,p[x]};p[x]=id;
} 
int dfn[N],low[N],Tim;
vector<int>dcc[N];
int tot;
int cut[N<<1]; 
void Tarjan(int x,int fid){
    dfn[x]=low[x]=++Tim;
    int cnt=0;
    for(int i=p[x];i;i=e[i].nt){
        int v=e[i].v;
        if(!dfn[v]){
            Tarjan(v,i);
            low[x]=min(low[x],low[v]);
            if(low[v]>dfn[x])cut[i]=cut[i^1]=1;
        }
        else if(fid!=(i^1))low[x]=min(low[x],dfn[v]);
    }
}
int vis[N];
void dfs(int x,int ffa){
    vis[x]=1;
    dcc[tot].pb(x);
    for(int i=p[x];i;i=e[i].nt){
        int v=e[i].v;
        if(vis[v]||cut[i])continue;
        dfs(v,x);
    }
}
signed main(){
    n=rd(),m=rd();
    F(i,1,m){
        int x=rd(),y=rd();
        if(x==y)continue;
        add(x,y);add(y,x);
    }
    F(i,1,n)if(!dfn[i]){
        Tarjan(i,0);
    }
    F(i,1,n)if(!vis[i]){
        tot++;
        dfs(i,0);
    }
    cout<<tot<<'\n';
    F(i,1,tot){
        cout<<dcc[i].size()<<' ';
        for(auto v:dcc[i])cout<<v<<" ";cout<<'\n';
    }
    return 0;
}

记录父向边,不能用父向边更新low

线段树

乘法和加法的标记合并时
先pd乘法的标记
因为\((a+b)*c->a*c+b*c\)

void pd(int p,int l,int r){
    tr[ls].s=tr[ls].s*tr[p].tag2;
    tr[ls].tag2*=tr[p].tag2;
    tr[ls].tag1=tr[ls].tag1*tr[p].tag2;
    tr[ls].s+=(mid-l+1)*tr[p].tag1;
    tr[ls].tag1+=tr[p].tag1;
    
    tr[rs].tag2*=tr[p].tag2;
    tr[rs].s=tr[rs].s*tr[p].tag2;
    tr[rs].tag1=tr[rs].tag1*tr[p].tag2;
    tr[rs].s+=(r-mid)*tr[p].tag1;
    tr[rs].tag1+=tr[p].tag1;
    
    tr[p].tag2=1;
    tr[p].tag1=0;
}
void upd_sum(int p,int nl,int nr,int k,int l=1,int r=n){
    pd(p,l,r);
    if(nl<=l&&r<=nr){
        tr[p].s+=(r-l+1)*k;
        tr[p].tag1+=k;
        return ;
    }
}
void upd_mul(int p,int nl,int nr,int k,int l=1,int r=n){
    pd(p,l,r);
    if(nl<=l&&r<=nr){
        tr[p].s*=k;
        tr[p].tag2*=k;
        tr[p].tag1*=k;
        return ;
    }
}

KM

#include<bits/stdc++.h>
#define int long long
#define F(i,i0,n) for(int i=(i0);i<=(n);i++)
#define D(i,n,i0) for(int i=(n);i>=i0;--i)
#define pii pair<int,int>
#define fr first
#define sc second
#define pb push_back
using namespace std;
inline int rd(){
    int f=0,x=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return f?-x:x;
}
const int N=2e6+5,mod=1e9+7;
struct Id{
    int v,nt;
}e[N<<1];
int p[N],id=1;
void add(int x,int y){
    e[++id]={y,p[x]};p[x]=id;
} 
int n,m,E;
int mat[N];
int tim;
int vis[N];
bool km(int u){
    vis[u]=tim;
    for(int i=p[u];i;i=e[i].nt){
        int v=e[i].v;
        if(vis[v]!=tim){
            vis[v]=tim;
            if(!mat[v]||km(mat[v])){
                mat[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
signed main(){
    n=rd(),m=rd(),E=rd();
    F(i,1,E){
        int x=rd(),y=rd();
        add(x,y+n);
    }
    int ans=0;
    F(i,1,n){
        tim++; 
        ans+=km(i);
    }
    cout<<ans<<'\n';
    return 0;
}

总是忘记怎么写?怎么回事呢?

LIS LCS

二分的做法
LCS对于两个排列来说就是让两者产生映射关系，然后再来做LIS
相当于是保证了一维，做另一维

最大m段和

有点学不来

总而言之一句话：
优化到最后是\(dp[i][j][0/1]表示考虑前i个元素，选出了j个段，第i个元素是否选择的最大化和。\)
转移为：

\[dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0])+a[i];//接上或者新开 \]

\[dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]) \]

标签：发现,易错,ch,tag1,int,tr,板子,rd,define
From： https://www.cnblogs.com/ussumer/p/17832667.html

相关文章

  • RLHF · PBRL | 发现部分 D4RL tasks 不适合做 offline reward learning 的 benchmark
    论文题目：BenchmarksandAlgorithmsforOfflinePreference-BasedRewardLearning，TMLR20230103发表。openreview：https://openreview.net/forum?id=TGuXXlbKsnpdf版本：https://arxiv.org/pdf/2301.01392.pdfhtml版本：https://ar5iv.labs.arxiv.org/html/2301.01392目......
  • 大非质数取模算组合数板子
    constintN=1e5+10,M=13;intn,mod,l,r;llans,p[M],br[M],phi;inlinellksm(lla,llb){ lld=1; while(b){ if(b&1)d=d*a%mod; a=a*a%mod; b>>=1; } returnd;}namespacebig_mod{ structnum{ llx,r[M]; }fac[N],I,B; inlinenumoperat......
  • 写了个高精度加法板子
    #include<bits/stdc++.h>using namespace std;const int N=1e4+9;int a1[1000],b1[1000],ans[1000];void add(int a[],int b[],int na,int nb){int t=0;if(na<nb)return add(b,a,nb,na);for(int i=0;i<na;i++){t+=a[i];if(i<nb)t+=b[i];ans[i]=t%10;t/=10;}if(......
  • 开发现代化的.NetCore控制台程序：(3)将nuget包发布到GitHubPackages
    前言上一篇文章已经把项目模板的nuget包发布到了nuget的官方源了，其实还可以发布到其他源，比如GitHub，本文记录一下发布到GitHubPackages的过程。注意：本文建立在本系列第二篇文章的基础上，为了更好理解操作过程，请先熟悉本项目的代码结构创建GitHubtoken访问https://gith......
  • 几个易错的命令
    'echo’与'printf'和echo都是printf用于在shell中显示文本的命令，但它们有一些重要的区别。虽然echo只是输出提供给它的字符串，printf但允许对字符串、数字和其他数据类型进行更详细的格式化2.“>”与“&>”和>都&>用于Bash中的重定向，但它们之间有区别。仅重定向stdout到文件......
  • 关于从前端接收到整天时间，后端接收到后发现秒字段没了的问题
    1、问题：今天出现了比较奇怪的问题，使用mongo查询数据的时候，前端传来的是2023-11-0200:00:00但是后端接收到的是2023-11-02T00:00，使用的是LocalDateTime来接收，这出现秒丢失的问题就导致在进行mongo时间范围查询的时候，原本的时间范围是2023-11-02 00:00:00到 2023-11-0223:59......
  • 【板子申请】Ai-M61-32S开发环境搭建-wuboy19
    【板子申请】Ai-M61-32S开发环境搭建-wuboy19window10vscode环境安装vscode官网下载windows版本图1官网界面图图2安装成功图博主百度网盘下载百度网盘链接提取码：9jydgit安装git官网下载链接图3git安装过程图博主网盘下载git百度网盘链接提取码：n3z......
  • 开发现代化的.NetCore控制台程序：(2)创建一个C#项目模板
    前言上一篇文章（开发一个现代化的.NetCore控制台程序，包含依赖注入/配置/日志等要素）介绍了开发现代化的.NetCore控制台程序的细节，但这还不够，我又创建了一个脚手架模板，并命名为FluentConsole.Templates，可以方便的创建「现代化控制台应用」。源码地址:https://github.com/Deali-A......
  • 树套树板子，但是带修莫队+值域分块
    \(\text{Link-LuoguBlog}\)原题传送门没啥重要的事情，就是终于过了这题非常开心，发现自己是莫队的时间戳部分写错了调了114514年我也只能说是十分趣味。以及今天深刻地认识到了带修莫队应该len=pow(n,0.66);。就是裸的带修莫队+值域分块，就不说了，直接放代码了昂。如果有人......
  • 板子速查
    线性求逆元\[\begin{align*}i\cdotk+r&=0\pmodp\\k+r\cdoti^{-1}&=0\pmodp\\k\cdotr^{-1}+i^{-1}&=0\pmodp\\i^{-1}&=-k\cdotr^{-1}\pmodp\end{align*}\] inv[1]=1; for(inti=2;i<N;++i) ......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99