在排列中求lcs

​

活动地址：CSDN21天学习挑战赛

463D - Gargari and Permutations 在排列中求lcs

之前做过一道类似的题目

但是上一个是求两个排列的lcs，这次是求多个的，但总归求得思路还是没有很大的变化，都是在转化为求最长递增子序列lis，不过这个不能nlog(n)了，因为需要判断多个子序列的递增情况

D. Gargari and Permutations[求最长公共字序列]_z听歌的小孩z的博客-CSDN博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll n,k,a[6][1005],b[6][1005],dp[10005];
bool check(ll x,ll y){
    for(int i=2;i<=k;i++)
    if(b[i][x]>b[i][y]) return false;
    return true;
}
int main(){ 
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=k;i++)
    for(int j=1;j<=n;j++){
        scanf("%lld",&a[i][j]);
        b[i][a[i][j]]=j;
    }
    ll ans=0;
    for(int i=1;i<=n;i++) dp[i]=1;
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++){
        if(check(a[1][i],a[1][j]))
        dp[j]=max(dp[j],dp[i]+1);
    }
    for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

D - Color with Occurrences dp记录路径

每次都是暴力的比对然后更新计数，要注意是要从后往前来，这样便于更新状态，记录路径还是掌握的不好，，，

Codeforces Round #811 (Div. 3) A - G - 知乎 (zhihu.com)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e3+100;
ll q,n,dp[105],len[15],w[105],f[105],g[105];
char s[15][15],t[105];
int main(){
    scanf("%lld",&q);
    while(q--){
        scanf("%s%lld",t+1,&n);
        ll m=strlen(t+1);
        for(int i=1;i<=n;i++){
            scanf("%s",s[i]+1);
            len[i]=strlen(s[i]+1);
        }
        for(int i=1;i<=100;i++) dp[i]=1e18;
        dp[0]=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                ll flag=1;
                for(int k=len[j],p=i;k;k--,p--){
                    if(s[j][k]!=t[p]){
                        flag=0;break;
                    }
                }
                if(!flag) continue;
                for(int k=len[j],p=i;k;k--,p--){
                    if(dp[p-1]+1<dp[i]){
                        dp[i]=dp[p-1]+1;
                        w[i]=j;f[i]=i-len[j]+1;g[i]=p-1;
                    }
                }
            }
        }
        if(dp[m]>m){printf("-1\n");continue;}
        printf("%lld\n",dp[m]);
        vector<pair<ll,ll>>v;
        for(int i=m;i;i=g[i]){
            v.push_back({w[i],f[i]});
        }
        reverse(v.begin(),v.end());
        for(auto [x,y]:v) printf("%lld %lld\n",x,y);
    }
    system("pause");
    return 0;
}

E - Add Modulo 10

可以发现除了5，每一个加到最后都会是2，4，8，6这样的循环，

比如

1,2,4,8,6

2,4,8,6

3,6,2,4,8

4,8,6,2,4,8,6

5,0(例外情况)

6,2,4,8,6

7,4,8,6,2,4,8,6

8,6,2,4,8,6

9,8,6,2,4,8,6

所以我们一开始输入的时候就加上一个值,使得这个数下一步就会进入2，4，8，6循环，比如如果个位是1就加上1，如果是3就加上9，，然后我们找出最大值，重新遍历一遍数组如果最大值与a[i]的差值不是2，4，8，6循环和的话那就不符合条件，5和0的情况特判一下就行

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e3+100;
ll t,n,a[200005];
ll b[10]={0,1,0,9,18,0,6,25,14,23};
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        ll maxx=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            a[i]+=b[a[i]%10];
            maxx=max(maxx,a[i]);
        }
        ll flag=1;
        for(int i=1;i<=n;i++){
            ll x=maxx-a[i];
            if(x==0) continue;
            if(a[i]%10==0||a[i]%10==5){
                if(x!=5&&x!=0){
                    flag=0;break;
                }
                if(x==5&&a[i]%10!=5){flag=0;break;}
                continue;
            }
            if(x%20!=0){
                ll y=x%20;
                if(y==2||y==6||y==14) continue;
                flag=0;break;
            }
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    system("pause");
    return 0;
}

P5494 【模板】线段树分裂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

可以解决与区间拆分相关的问题，，但现在还是不知道具体是用来做什么，，，

【AgOHの数据结构】线段树分裂合并_哔哩哔哩_bilibili

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+5;
struct node{
    ll l,r,val;//val是[l,r]中有多少数
}t[N*40];
ll cnt,rt[N];
void pushup(ll p){t[p].val=t[t[p].l].val+t[t[p].r].val;}
void update(ll l,ll r,ll &p,ll k,ll x){//单点修改，p的位置上加上x，空间复杂度O(logn)
    if(!p) p=++cnt;
    //t[p].val+=x;
    if(l==r){t[p].val+=x;return;}
    ll m=l+r>>1;
    if(k<=m) update(l,m,t[p].l,k,x);
    else update(m+1,r,t[p].r,k,x);
    pushup(p);
}
void merge(ll &x,ll y){//将y节点的内容合并到x节点上
    if(!(x&&y)) x|=y;
    else{
        t[x].val+=t[y].val;
        merge(t[x].l,t[y].l);
        merge(t[x].r,t[y].r);
    }
}
ll split(ll l,ll r,ll &p,ll x,ll y){//从p节点中分出[x,y]并返回新节点编号，空间复杂度O(2logn)
    ll nn=++cnt;
    if(x<=l&&y>=r){
        t[nn]=t[p];
        p=0;
    }
    else{
        ll m=l+r>>1;
        if(x<=m) t[nn].l=split(l,m,t[p].l,x,y);
        if(y>m) t[nn].r=split(m+1,r,t[p].r,x,y);
        pushup(nn);pushup(p);
    }
    return nn;
}
ll query(ll l,ll r,ll p,ll x,ll y){//查询[x,y]这个区间中一共有多少数
    if(x<=l&&y>=r) return t[p].val;
    ll m=l+r>>1;
    ll sum=0;
    if(x<=m) sum+=query(l,m,t[p].l,x,y);
    if(y>m) sum+=query(m+1,r,t[p].r,x,y);
    return sum;
}
ll query(ll l,ll r,ll p,ll k){//查询这个集合中第k小的数
    if(l==r) return l;
    ll m=l+r>>1;
    if(k<=t[t[p].l].val) return query(l,m,t[p].l,k);
    else return query(m+1,r,t[p].r,k-t[t[p].l].val);
}
ll n,q;
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        ll x;scanf("%lld",&x);
        update(1,n,rt[1],i,x);
    }
    ll last=1;
    while(q--){
        ll op,x,y,p;
        scanf("%lld%lld%lld",&op,&p,&x);
        if(op==0){
            scanf("%lld",&y);
            rt[++last]=split(1,n,rt[p],x,y);
        }
        else if(op==1){
            merge(rt[p],rt[x]);
        }
        else if(op==2){
            scanf("%lld",&y);
            update(1,n,rt[p],y,x);
        }
        else if(op==3){
            scanf("%lld",&y);
            printf("%lld\n",query(1,n,rt[p],x,y));
        }
        else{
            if(x>t[rt[p]].val) printf("-1\n");
            else printf("%lld\n",query(1,n,rt[p],x));
        }
    }
    system("pause");
    return 0;
}

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道模板题真是煞我，需要lca，树上差分和线段树合并，怪不得是紫题，，，树上的每个点就是一个线段树，颁发一次救济粮就要利用树上差分，最后需要把线段树合并起来就是每个节点的答案，这个与序列的差分差不多，序列的差分也是求出前缀和得出答案

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
//链式前向星
ll head[N*2],ct;
struct Edge{
    ll from,to,next;
}edge[N*2];
void addedge(ll from, ll to){
    edge[++ct].from = from;
    edge[ct].to = to;
    edge[ct].next =head[from];
    head[from] = ct;
}
//lca
ll dep[N],son[N],siz[N],f[N];
void dfs1(ll u,ll fa){
    siz[u]=1;dep[u]=dep[fa]+1;f[u]=fa;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
        if(siz[j]>siz[son[u]]) son[u]=j;
    }
}
ll top[N];
void dfs2(ll u,ll fa,ll topx){
    top[u]=topx;
    if(son[u]) dfs2(son[u],u,topx);
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j!=fa&&j!=son[u]) dfs2(j,u,j);
    }
}
ll lca(ll x,ll y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
//线段树
struct node{
    ll l,r;
    pair<ll,ll>val;
}t[N*70];
ll cnt,rt[N];
pair<ll,ll>& max(pair<ll,ll>& x,pair<ll,ll>& y){
    if(x.first>y.first) return x;
    else if(x.first==y.first) return x.second<y.second?x:y;
    else return y;
}
void pushup(ll p){t[p].val=max(t[t[p].l].val,t[t[p].r].val);}
void update(ll l,ll r,ll &p,ll k,ll x){
    if(!p) p=++cnt;
    if(l==r){
        t[p].val.first+=x;
        t[p].val.second=k;
        return;
    }
    ll mid=l+r>>1;
    if(mid>=k) update(l,mid,t[p].l,k,x);
    else if(mid<k) update(mid+1,r,t[p].r,k,x);
    pushup(p);
}
void merge(ll &x,ll y,ll l=1,ll r=N){//用于判断l和r是否是到了叶子节点
    if(!x||!y) x|=y;
    else if(l==r){
        t[x].val.first+=t[y].val.first;
    }
    else{
        ll mid=l+r>>1;
        merge(t[x].l,t[y].l,l,mid);
        merge(t[x].r,t[y].r,mid+1,r);
        pushup(x);
    }
}
ll ans[N];
void dfs(ll u,ll fa){//类似于序列求前缀和获得原数组一样，树上差分也是做类似的操作统计出答案
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs(j,u);
        merge(rt[u],rt[j]);
    }
    if(t[rt[u]].val.first) ans[u]=t[rt[u]].val.second;
}
ll n,m;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<n;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v);addedge(v,u);
    }
    dfs1(1,0);dfs2(1,0,0);
    while(m--){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        //树上差分，x到y上都加上一个z，那就是要在x，y上加上一个z，lca(x,y)和lca(x,y)
        //的父亲上加上一个z
        update(1,N,rt[x],z,1);
        update(1,N,rt[y],z,1);
        update(1,N,rt[lca(x,y)],z,-1);
        update(1,N,rt[f[lca(x,y)]],z,-1);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    system("pause");
    return 0;
}