• 在排列中求lcs

    ​

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

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

    之前做过一道类似的题目

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

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

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. const ll MAX=1e6+5;
    6. const ll mod=998244353;
    7. ll n,k,a[6][1005],b[6][1005],dp[10005];
    8. bool check(ll x,ll y){
    9.     for(int i=2;i<=k;i++)
    10.     if(b[i][x]>b[i][y]) return false;
    11.     return true;
    12. }
    13. int main(){ 
    14.     scanf("%lld%lld",&n,&k);
    15.     for(int i=1;i<=k;i++)
    16.     for(int j=1;j<=n;j++){
    17.         scanf("%lld",&a[i][j]);
    18.         b[i][a[i][j]]=j;
    19.     }
    20.     ll ans=0;
    21.     for(int i=1;i<=n;i++) dp[i]=1;
    22.     for(int i=1;i<=n;i++)
    23.     for(int j=i+1;j<=n;j++){
    24.         if(check(a[1][i],a[1][j]))
    25.         dp[j]=max(dp[j],dp[i]+1);
    26.     }
    27.     for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    28.     printf("%lld\n",ans);
    29.     system("pause");
    30.     return 0;
    31. }

    D - Color with Occurrences dp记录路径

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

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

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 1e3+100;
    5. ll q,n,dp[105],len[15],w[105],f[105],g[105];
    6. char s[15][15],t[105];
    7. int main(){
    8.     scanf("%lld",&q);
    9.     while(q--){
    10.         scanf("%s%lld",t+1,&n);
    11.         ll m=strlen(t+1);
    12.         for(int i=1;i<=n;i++){
    13.             scanf("%s",s[i]+1);
    14.             len[i]=strlen(s[i]+1);
    15.         }
    16.         for(int i=1;i<=100;i++) dp[i]=1e18;
    17.         dp[0]=0;
    18.         for(int i=1;i<=m;i++){
    19.             for(int j=1;j<=n;j++){
    20.                 ll flag=1;
    21.                 for(int k=len[j],p=i;k;k--,p--){
    22.                     if(s[j][k]!=t[p]){
    23.                         flag=0;break;
    24.                     }
    25.                 }
    26.                 if(!flag) continue;
    27.                 for(int k=len[j],p=i;k;k--,p--){
    28.                     if(dp[p-1]+1
    29.                         dp[i]=dp[p-1]+1;
    30.                         w[i]=j;f[i]=i-len[j]+1;g[i]=p-1;
    31.                     }
    32.                 }
    33.             }
    34.         }
    35.         if(dp[m]>m){printf("-1\n");continue;}
    36.         printf("%lld\n",dp[m]);
    37.         vector>v;
    38.         for(int i=m;i;i=g[i]){
    39.             v.push_back({w[i],f[i]});
    40.         }
    41.         reverse(v.begin(),v.end());
    42.         for(auto [x,y]:v) printf("%lld %lld\n",x,y);
    43.     }
    44.     system("pause");
    45.     return 0;
    46. }

    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的情况特判一下就行

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 1e3+100;
    5. ll t,n,a[200005];
    6. ll b[10]={0,1,0,9,18,0,6,25,14,23};
    7. int main(){
    8.     scanf("%lld",&t);
    9.     while(t--){
    10.         scanf("%lld",&n);
    11.         ll maxx=0;
    12.         for(int i=1;i<=n;i++){
    13.             scanf("%lld",&a[i]);
    14.             a[i]+=b[a[i]%10];
    15.             maxx=max(maxx,a[i]);
    16.         }
    17.         ll flag=1;
    18.         for(int i=1;i<=n;i++){
    19.             ll x=maxx-a[i];
    20.             if(x==0) continue;
    21.             if(a[i]%10==0||a[i]%10==5){
    22.                 if(x!=5&&x!=0){
    23.                     flag=0;break;
    24.                 }
    25.                 if(x==5&&a[i]%10!=5){flag=0;break;}
    26.                 continue;
    27.             }
    28.             if(x%20!=0){
    29.                 ll y=x%20;
    30.                 if(y==2||y==6||y==14) continue;
    31.                 flag=0;break;
    32.             }
    33.         }
    34.         if(flag) printf("YES\n");
    35.         else printf("NO\n");
    36.     }
    37.     system("pause");
    38.     return 0;
    39. }

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

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

    开数组大小时一般开 2*maxm*log2(maxn)

    maxm为最大询问次数，maxn为线段树最大大小

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

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 2e5+5;
    5. struct node{
    6.     ll l,r,val;//val是[l,r]中有多少数
    7. }t[N*40];
    8. ll cnt,rt[N];
    9. void pushup(ll p){t[p].val=t[t[p].l].val+t[t[p].r].val;}
    10. void update(ll l,ll r,ll &p,ll k,ll x){//单点修改，p的位置上加上x，空间复杂度O(logn)
    11.     if(!p) p=++cnt;
    12.     //t[p].val+=x;
    13.     if(l==r){t[p].val+=x;return;}
    14.     ll m=l+r>>1;
    15.     if(k<=m) update(l,m,t[p].l,k,x);
    16.     else update(m+1,r,t[p].r,k,x);
    17.     pushup(p);
    18. }
    19. void merge(ll &x,ll y){//将y节点的内容合并到x节点上
    20.     if(!(x&&y)) x|=y;
    21.     else{
    22.         t[x].val+=t[y].val;
    23.         merge(t[x].l,t[y].l);
    24.         merge(t[x].r,t[y].r);
    25.     }
    26. }
    27. ll split(ll l,ll r,ll &p,ll x,ll y){//从p节点中分出[x,y]并返回新节点编号，空间复杂度O(2logn)
    28.     ll nn=++cnt;
    29.     if(x<=l&&y>=r){
    30.         t[nn]=t[p];
    31.         p=0;
    32.     }
    33.     else{
    34.         ll m=l+r>>1;
    35.         if(x<=m) t[nn].l=split(l,m,t[p].l,x,y);
    36.         if(y>m) t[nn].r=split(m+1,r,t[p].r,x,y);
    37.         pushup(nn);pushup(p);
    38.     }
    39.     return nn;
    40. }
    41. ll query(ll l,ll r,ll p,ll x,ll y){//查询[x,y]这个区间中一共有多少数
    42.     if(x<=l&&y>=r) return t[p].val;
    43.     ll m=l+r>>1;
    44.     ll sum=0;
    45.     if(x<=m) sum+=query(l,m,t[p].l,x,y);
    46.     if(y>m) sum+=query(m+1,r,t[p].r,x,y);
    47.     return sum;
    48. }
    49. ll query(ll l,ll r,ll p,ll k){//查询这个集合中第k小的数
    50.     if(l==r) return l;
    51.     ll m=l+r>>1;
    52.     if(k<=t[t[p].l].val) return query(l,m,t[p].l,k);
    53.     else return query(m+1,r,t[p].r,k-t[t[p].l].val);
    54. }
    55. ll n,q;
    56. int main(){
    57.     scanf("%lld%lld",&n,&q);
    58.     for(int i=1;i<=n;i++){
    59.         ll x;scanf("%lld",&x);
    60.         update(1,n,rt[1],i,x);
    61.     }
    62.     ll last=1;
    63.     while(q--){
    64.         ll op,x,y,p;
    65.         scanf("%lld%lld%lld",&op,&p,&x);
    66.         if(op==0){
    67.             scanf("%lld",&y);
    68.             rt[++last]=split(1,n,rt[p],x,y);
    69.         }
    70.         else if(op==1){
    71.             merge(rt[p],rt[x]);
    72.         }
    73.         else if(op==2){
    74.             scanf("%lld",&y);
    75.             update(1,n,rt[p],y,x);
    76.         }
    77.         else if(op==3){
    78.             scanf("%lld",&y);
    79.             printf("%lld\n",query(1,n,rt[p],x,y));
    80.         }
    81.         else{
    82.             if(x>t[rt[p]].val) printf("-1\n");
    83.             else printf("%lld\n",query(1,n,rt[p],x));
    84.         }
    85.     }
    86.     system("pause");
    87.     return 0;
    88. }

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

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

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 1e5+5;
    5. //链式前向星
    6. ll head[N*2],ct;
    7. struct Edge{
    8.     ll from,to,next;
    9. }edge[N*2];
    10. void addedge(ll from, ll to){
    11.     edge[++ct].from = from;
    12.     edge[ct].to = to;
    13.     edge[ct].next =head[from];
    14.     head[from] = ct;
    15. }
    16. //lca
    17. ll dep[N],son[N],siz[N],f[N];
    18. void dfs1(ll u,ll fa){
    19.     siz[u]=1;dep[u]=dep[fa]+1;f[u]=fa;
    20.     for(int i=head[u];i;i=edge[i].next){
    21.         ll j=edge[i].to;
    22.         if(j==fa) continue;
    23.         dfs1(j,u);
    24.         siz[u]+=siz[j];
    25.         if(siz[j]>siz[son[u]]) son[u]=j;
    26.     }
    27. }
    28. ll top[N];
    29. void dfs2(ll u,ll fa,ll topx){
    30.     top[u]=topx;
    31.     if(son[u]) dfs2(son[u],u,topx);
    32.     for(int i=head[u];i;i=edge[i].next){
    33.         ll j=edge[i].to;
    34.         if(j!=fa&&j!=son[u]) dfs2(j,u,j);
    35.     }
    36. }
    37. ll lca(ll x,ll y){
    38.     while(top[x]!=top[y]){
    39.         if(dep[top[x]]swap(x,y);
    40.         x=f[top[x]];
    41.     }
    42.     return dep[x]
    43. }
    44. //线段树
    45. struct node{
    46.     ll l,r;
    47.     pairval;
    48. }t[N*70];
    49. ll cnt,rt[N];
    50. pair& max(pair& x,pair& y){
    51.     if(x.first>y.first) return x;
    52.     else if(x.first==y.first) return x.second
    53.     else return y;
    54. }
    55. void pushup(ll p){t[p].val=max(t[t[p].l].val,t[t[p].r].val);}
    56. void update(ll l,ll r,ll &p,ll k,ll x){
    57.     if(!p) p=++cnt;
    58.     if(l==r){
    59.         t[p].val.first+=x;
    60.         t[p].val.second=k;
    61.         return;
    62.     }
    63.     ll mid=l+r>>1;
    64.     if(mid>=k) update(l,mid,t[p].l,k,x);
    65.     else if(midupdate(mid+1,r,t[p].r,k,x);
    66.     pushup(p);
    67. }
    68. void merge(ll &x,ll y,ll l=1,ll r=N){//用于判断l和r是否是到了叶子节点
    69.     if(!x||!y) x|=y;
    70.     else if(l==r){
    71.         t[x].val.first+=t[y].val.first;
    72.     }
    73.     else{
    74.         ll mid=l+r>>1;
    75.         merge(t[x].l,t[y].l,l,mid);
    76.         merge(t[x].r,t[y].r,mid+1,r);
    77.         pushup(x);
    78.     }
    79. }
    80. ll ans[N];
    81. void dfs(ll u,ll fa){//类似于序列求前缀和获得原数组一样，树上差分也是做类似的操作统计出答案
    82.     for(int i=head[u];i;i=edge[i].next){
    83.         ll j=edge[i].to;
    84.         if(j==fa) continue;
    85.         dfs(j,u);
    86.         merge(rt[u],rt[j]);
    87.     }
    88.     if(t[rt[u]].val.first) ans[u]=t[rt[u]].val.second;
    89. }
    90. ll n,m;
    91. int main(){
    92.     scanf("%lld%lld",&n,&m);
    93.     for(int i=1;i
    94.         ll u,v;
    95.         scanf("%lld%lld",&u,&v);
    96.         addedge(u,v);addedge(v,u);
    97.     }
    98.     dfs1(1,0);dfs2(1,0,0);
    99.     while(m--){
    100.         ll x,y,z;
    101.         scanf("%lld%lld%lld",&x,&y,&z);
    102.         //树上差分，x到y上都加上一个z，那就是要在x，y上加上一个z，lca(x,y)和lca(x,y)
    103.         //的父亲上加上一个z
    104.         update(1,N,rt[x],z,1);
    105.         update(1,N,rt[y],z,1);
    106.         update(1,N,rt[lca(x,y)],z,-1);
    107.         update(1,N,rt[f[lca(x,y)]],z,-1);
    108.     }
    109.     dfs(1,0);
    110.     for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    111.     system("pause");
    112.     return 0;
    113. }

  • 相关阅读:
    xss-labs/level15
    解决Windows 10更新安装失败的问题
    Java__Eclipse中开发Servlet及其访问浏览器常见的错误类型
    10月13日上课内容 Ansible 的脚本 --- playbook 剧本
    字节秋招高频算法汇总（基础篇）
    go语言 leetcod1 两数之和
    【再探】设计模式—中介者模式、观察者模式及模板方法模式
    phpinfo为关键的getshell方法
    Lua中pair和ipair的区别
    【从零开始学习 SystemVerilog】3.8、SystemVerilog 控制流—— Tasks（任务）
  • 原文地址：https://blog.csdn.net/weixin_52621204/article/details/126115631