10.20 一点考前复习-1

Posted on By 张, 高畅 10.20 一点考前复习-1无评论

太菜了，什么都不会了。

那就根据大纲重新复习一下吧。
(悲伤)。

ST表/倍增求LCA

ST表原题/或这里

#include
using namespace std;
const int N=2e5+5,M=25;
int n,m;
int f[N][M];
void init()
{
    for(int i=1;i<=n;i++)scanf("%d",&f[i][0]);
    for(int j=1;j<=20;j++)
    {
        for(int i=1;(i+(1<<j)-1)<=n;i++)f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
    }
}
int query(int l,int r)
{
    int len=r-l+1;
    int k=log(len)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d",&n);
    init();
    scanf("%d",&m);
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r));
    }
    return 0;
}

倍增求LCA

#include
using namespace std;
const int N=500005;
int n,m,root,d[N],fa[N][25];
vectorG[N];
void dfs(int u,int father)
{
    d[u]=d[father]+1;
    fa[u][0]=father;
    for(int j=1;j<=20;j++)fa[u][j]=fa[fa[u][j-1]][j-1];
    for(int j:G[u])
    {
        if(j==father)continue;
        dfs(j,u);
    }
}
int LCA(int a,int b)
{
    if(d[a]=d[b])a=fa[a][i];
    }
    if(a==b)return a;
    for(int i=20;~i;i--)
    {
        if(fa[a][i]!=fa[b][i])
        {
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
int main()
{
    scanf("%d%d%d",&n,&m,&root);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(root,0);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",LCA(a,b));
    }
    return 0;
}

KMP

这个可能是在PJ/TG级唯一一个比较需要理解的算法了。
（注：AC自动机/后缀数组SA/exKMP(Z函数)等是NOI级考点，考完之后没回归WHK就写）
原题链接/或这里

#include
using namespace std;
const int N=1e6+5;
int n,m,ne[N];
char s[N],p[N];
int main()
{
    scanf("%d%s%d%s",&n,p+1,&m,s+1);
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&p[i]!=p[j+1])j=ne[j];
        if(p[i]==p[j+1])j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&s[i]!=p[j+1])j=ne[j];
        if(s[i]==p[j+1])j++;
        if(j==n)
        {
            printf("%d ",i-n);
            j=ne[j];
        }
    }
    return 0;
}

树状数组/线段树/分块/Trie树

Trie树模板/或这里
LUOGU你怎么卡常数呢？？？

#include
using namespace std;
const int N=3e6+5;
int n,son[N][80],cnt[N],idx;
char str[N];
void insert()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'0';
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
        cnt[p]++;
    }
}
int query()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'0';
        if(!son[p][u])return 0;
        p=son[p][u];
    }
    return cnt[p];
}
void work()
{
    for(int i=0;i<=idx;i++)cnt[i]=0;
    int n,q;
    scanf("%d%d",&n,&q);
    while(n--)
    {
        scanf("%s",str);
        insert();
    }
    while(q--)
    {
        scanf("%s",str);
        printf("%d\n",query());
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}

线段树今日不明题目(非模板)(带lazytag)

#include
using namespace std;
const int N=1e6+5;
typedef long long LL;
int n,m;
int w[N];
struct node
{
    LL sum,add;
}tr[N<<2];
void pushup(int u){tr[u].sum=min(tr[u<<1].sum,tr[u<<1|1].sum);}
void pushdown(int u)
{
    if(!tr[u].add)return;
    tr[u<<1].sum+=tr[u].add;
    tr[u<<1].add+=tr[u].add;
    tr[u<<1|1].sum+=tr[u].add;
    tr[u1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,int L,int R,LL x)
{
    if(L1;
    if(L<=mid)modify(u<<1,l,mid,L,R,x);
    if(mid<R)modify(u<<1|1,mid+1,r,L,R,x);
    pushup(u);
}
LL query(int u,int l,int r,int L,int R)
{
    if(L1;
    LL res=1e18;
    if(L<=mid)res=min(res,query(u<<1,l,mid,L,R));
    if(mid<R)res=min(res,query(u<<1|1,mid+1,r,L,R));
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int d,s,t;
        scanf("%d%d%d",&d,&s,&t);
        modify(1,1,n,s,t,-1LL*d);
        if(query(1,1,n,1,n)<0)
        {
            printf("-1\n%d",i);
            return 0;
        }
    }
    puts("0");
    return 0;
}

还是得请我们的老题这位
树状数组做法:

#include
using namespace std;
typedef long long LL;
const int N=100005;
int n,m,a[N];
LL tr1[N],tr2[N];
inline int lowbit(int x){return x&(-x);}
void add(LL tr[],int x,LL c)
{
    for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;
}
LL sum(LL tr[],int x)
{
    LL res=0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}
LL get(int x)
{
    return sum(tr1,x)*(x+1)-sum(tr2,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int b=a[i]-a[i-1];
        add(tr1,i,b);
        add(tr2,i,(LL)b*i);
    }
    while(m--)
    {
        char op[2];
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(*op=='C')
        {
            scanf("%d",&d);
            add(tr1,l,d);
            add(tr2,l,l*d);
            add(tr1,r+1,-d);
            add(tr2,r+1,(r+1)*-d);
        }
        else printf("%lld\n",get(r)-get(l-1));
    }
    return 0;
}

分块做法：

#include
using namespace std;
typedef long long LL;
const int N=1e5+5,M=355;
int n,m,len,w[N];
LL sum[M],flag[M];
int get(int x){return x/len;}
void modify(int l,int r,int d)
{
    if(get(l)==get(r))
    {
        for(int i=l;i<=r;i++)
        {
            w[i]+=d;
            sum[get(i)]+=d;
        }
    }
    else
    {
        int i=l,j=r;
        while(get(i)==get(l))
        {
            w[i]+=d;
            sum[get(i)]+=d;
            i++;
        }
        while(get(j)==get(r))
        {
            w[j]+=d;
            sum[get(j)]+=d;
            j--;
        }
        for(int k=get(i);k<=get(j);k++)
        {
            sum[k]+=len*d;
            flag[k]+=d;
        }
    }
}
LL query(int l,int r)
{
    LL res=0;
    if(get(l)==get(r))
    {
        for(int i=l;i<=r;i++)res+=w[i]+flag[get(i)];
    }
    else
    {
        int i=l,j=r;
        while(get(i)==get(l))
        {
            res+=w[i]+flag[get(i)];
            i++;
        }
        while(get(j)==get(r))
        {
            res+=w[j]+flag[get(j)];
            j--;
        }
        for(int k=get(i);k<=get(j);k++)res+=sum[k];
    }
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        sum[get(i)]+=w[i];
    }
    while(m--)
    {
        char op[2];
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(*op=='C')
        {
            scanf("%d",&d);
            modify(l,r,d);
        }
        else printf("%lld\n",query(l,r));
    }
    return 0;
}

线段树做法:

#include
using namespace std;
const int N=1e5+5;
typedef long long LL;
int n,m;
LL w[N];
struct node
{
    int l,r;
    LL sum,add;
}tr[N<<2];
void pushup(int u){tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;}
void pushdown(int u)
{
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,LL x)
{
    if(l1;
    if(l<=mid)modify(u<<1,l,r,x);
    if(mid<r)modify(u<<1|1,l,r,x);
    pushup(u);
}
LL query(int u,int l,int r)
{
    if(l1;
    LL sum=0;
    if(l<=mid)sum+=query(u<<1,l,r);
    if(mid<r)sum+=query(u<<1|1,l,r);
    return sum;
}
char op[5];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
    build(1,1,n);
    while(m--)
    {
        int l,r;
        LL x;
        scanf("%s%d%d",op,&l,&r);
        if(*op=='C')
        {
            scanf("%lld",&x);
            modify(1,l,r,x);
        }
        else if(*op=='Q')printf("%lld\n",query(1,l,r));
    }
    return 0;
}

(发现自己没有写过线段树做法，赶快补)

训练日志

发表回复