首页 > 其他分享 >不带删尺取小记

不带删尺取小记

时间:2024-02-13 09:04:44浏览次数:29  
标签:10 不带 gcd int mid leq ans 删尺 小记

目录

前言

期末考考了,当时用倍增+ST表多了个 \(\log\) 做的

适用于双指针删除时复杂度很高,添加时复杂度很低的情形。

大概有两种类型,本质是一样的,只是写法有点区别。


双指针的移动与限制条件有关

CF1548B Integers Have Friends

洛谷传送门
CF1548B


分析

差分后转化为求区间 \(\gcd>1\) 的最长区间长度

有很多做法,带 \(\log n\) 的就是二分+ST表或者线段树+双指针

双指针就是只要区间 \(\gcd=1\) 左指针就不断右移。

继续考虑双指针,如果能将区间分成两段 \([l,mid],[mid+1,r]\)

前一段为后缀 \(\gcd\),后一段为前缀 \(\gcd\),然后就可以直接拼起来,双指针的移动也非常简单。

问题就是怎样判断后缀 \(\gcd\) 在什么时候计算,有一种办法,

就是当 \(l>mid\) 的时候直接将 \([l,r]\) 全部变成后缀 \(\gcd\),然后将 \(l,mid\) 全部赋值为 \(r\),

每个位置最多进行一次前缀 \(\gcd\) 和一次后缀 \(\gcd\),所以复杂度就是 \(O(n\log {a_i})\)


代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long lll;
const int N=200011;
int n,l,mid,ans; lll a[N],f[N];
lll iut(){
    lll ans=0,f=1; char c=getchar();
    while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans*f;
}
void print(int ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
lll gcd(lll x,lll y){return y?gcd(y,x%y):x;}
int main(){
    for (int T=iut();T;--T){
        n=iut(),l=mid=ans=0,f[0]=a[0]=1;
        for (int i=1;i<=n;++i) a[i]=iut();
        for (int i=1;i<n;++i)
        if (a[i]<a[i+1]) a[i]=a[i+1]-a[i];
            else a[i]-=a[i+1];
        --n;
        for (int i=1;i<=n;++i){
            f[i]=(i-1==mid)?a[i]:gcd(f[i-1],a[i]);
            while (l<=mid&&gcd(f[i],f[l])==1) ++l;//后缀与前缀拼接判断gcd
            if (l>mid){
                f[mid=i]=a[i];
                for (int j=mid-1;j>=l;--j) f[j]=gcd(f[j+1],a[j]);
                while (l<=mid&&f[l]==1) ++l;//重构之后只需要看f[l]
            }
            ans=max(ans,i-l+1);
        }
        print(ans+1),putchar(10);
    }
    return 0;
}

CF1547F Array Stabilization (GCD version)

洛谷传送门
CF1547F


分析

首先要断环为链,非常浅显的做法就是二分+ST表,判断当前判定的次数下是否能够使区间 \(\gcd\) 等于所有数的 \(\gcd\)

可以发现,还是可以用线段树+双指针做,指针移动就变成了不等于所有数的 \(\gcd\),

转化题意后和上一题本质是一样的,翻转数组就差不多了,可以利用不带删尺取


代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N=400011;
int n,l,mid,ans,a[N],f[N];
int iut(){
    int ans=0,f=1; char c=getchar();
    while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans*f;
}
void print(int ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main(){
    for (int T=iut();T;--T){
        n=iut(),l=mid=ans=0,a[0]=0;
        for (int i=1;i<=n;++i) a[i]=iut(),a[0]=gcd(a[0],a[i]);
        reverse(a+1,a+1+n),f[0]=a[0];
        for (int i=1;i<=n;++i) a[i+n]=a[i];
        for (int i=1;i<n*2;++i){
            f[i]=(i-1==mid)?a[i]:gcd(f[i-1],a[i]);
            while (l<=mid&&gcd(f[i],f[l])==a[0]) ++l;
            if (l>mid){
                f[mid=i]=a[i];
                for (int j=mid-1;j>=l;--j) f[j]=gcd(f[j+1],a[j]);
                while (l<=mid&&f[l]==a[0]) ++l;
            }
            ans=max(ans,i-l+1);
        }
        print(ans),putchar(10);
    }
    return 0;
}

JZOJ 6358 小ω的仙人掌

题目传送门

小ω有 \(s\) 个物品,每个物品有一定的大小和权值。

她可以从任意第 \(L\) 个物品走到第 \(R\) 个物品,这个区间内的物品可以选或者不选。

她取出的物品大小和必须为 \(w\),权值和必须小于等于 \(k\)。

她想知道这个区间最短是多少。如果无解,请输出“-1”,大样例来自 ?

对于 \(100\%\) 的测试点,保证 \(1\leq s\leq 10^4,1\leq b_i\leq 2\times 10^4,1\leq a_i\leq w\leq 5\times 10^3,1\leq k\leq 10^9\)


分析

还是一样考虑双指针,问题是背包删除不好弄,

那就用不带删尺取变成后缀背包和前缀背包的结合。

注意这里求的是最短区间所以要在指针移动时求最小值


代码

#include <cstdio>
#include <cctype>
using namespace std;
const int N=5011;
int dp[N<<1][N],w[N<<1],c[N<<1],n,m,k,l,mid,ans;
int iut(){
    int ans=0; char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans;
}
int min(int a,int b){return a<b?a:b;}
int main(){
    n=iut(),m=iut(),k=iut(),ans=n+1;
    dp[0][0]=0;
    for (int i=1;i<=m;++i) dp[0][i]=0x3f3f3f3f;
    l=mid=0;
    for (int i=1;i<=n;++i){
        w[i]=iut(),c[i]=iut();
        if (i-1==mid){
            dp[i][0]=0,dp[i][w[i]]=c[i];
            for (int j=1;j<w[i];++j) dp[i][j]=0x3f3f3f3f;
            for (int j=m;j>w[i];--j) dp[i][j]=0x3f3f3f3f;
        }else{
            for (int j=0;j<w[i];++j) dp[i][j]=dp[i-1][j];
            for (int j=w[i];j<=m;++j)
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
        }
        for (;l<=mid;++l){
            int flag=1;
            for (int j=0;j<=m&&flag;++j)
                if (dp[l][j]+dp[i][m-j]<=k) flag=0;
            if (flag) break;
            ans=min(ans,i-l+1);
        }
        if (l>mid){
            mid=i;
            dp[mid][0]=0,dp[mid][w[mid]]=c[mid];
            for (int j=1;j<w[mid];++j) dp[mid][j]=0x3f3f3f3f;
            for (int j=m;j>w[mid];--j) dp[mid][j]=0x3f3f3f3f;
            for (int _i=mid-1;_i>=l;--_i){
                for (int j=0;j<w[_i];++j) dp[_i][j]=dp[_i+1][j];
                for (int j=w[_i];j<=m;++j) dp[_i][j]=min(dp[_i+1][j],dp[_i+1][j-w[_i]]+c[_i]);
            }
            while (l<=mid&&dp[l][m]<=k) ans=min(ans,i-l+1),++l;
        }
    }
    if (ans==n+1) printf("-1");
        else printf("%d",ans);
    return 0;
}

双指针的移动与所求区间有关

OJ 1-F 矩阵滑窗

题目大意

给定 \(n\) 个 \(k\times k\) 的矩阵 \(A_i\),现在有 \(q\) 组询问,每组询问 \(\prod_{o=l_i}^{r_i}A_o\)

对于 \(100\%\) 的测试点满足 \(n\leq 10^5,k\leq 4,q\leq 10^5,\forall j\leq i,l_j\leq l_i,r_j\leq r_i\)


分析

由于区间是锁定的,所以两个指针有一点区别,\(_l,_mid\) 取代了原来的 \(mid,r\)

其实也差不多,\(l>_l\) 的时候就重构,\(_mid\) 就是右指针的移动

\([l,_l]\) 维护的是后缀矩阵积,\([_l,_mid]\) 维护的是前缀矩阵积


代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N=100011;
int n,m,Q,_l,_mid;
struct Matrix{
    int p[4][4];
    Matrix operator *(const Matrix &T)const{
        Matrix C;
        for (int j=0;j<4;++j)
        for (int k=0;k<4;++k) C.p[j][k]=0;
        for (int i=0;i<m;++i)
        for (int j=0;j<m;++j)
        for (int k=0;k<m;++k)
            C.p[i][j]=(C.p[i][j]+1ll*p[i][k]*T.p[k][j])%919260817;
        return C;
    }
}A[N],B[N],C;
int iut(){
    int ans=0; char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans;
}
void print(int ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
int main(){
    n=iut(),m=iut(),Q=iut();
    _l=_mid=0;
    for (int i=1;i<=n;++i){
        for (int j=0;j<m;++j)
        for (int k=0;k<m;++k)
            A[i].p[j][k]=iut();
    }
    for (int i=1;i<=Q;++i){
        int l=iut(),r=iut();
        Matrix C;
        if (l>_l){
            B[r]=A[r];
            for (int j=r-1;j>=l;--j) B[j]=A[j]*B[j+1];
            _l=r,_mid=r,C=B[l];
        }else{
            if (_l==_mid&&_mid<r)
                ++_mid,B[_mid]=A[_mid];
            while (_mid<r) ++_mid,B[_mid]=B[_mid-1]*A[_mid];
            C=B[l]*B[r];
        }
        for (int j=0;j<m;++j)
        for (int k=0;k<m;++k)
            print(C.p[j][k]),putchar(32);
        putchar(10);
    }
    return 0;
}

标签:10,不带,gcd,int,mid,leq,ans,删尺,小记
From: https://www.cnblogs.com/Spare-No-Effort/p/18014306

相关文章

  • 卡特兰数小记
    引入\(n\)个节点的二叉树个数。长度为\(2n\)的合法括号序列数量。不加说明的给出结论:上面两个问题的答案均为卡特兰数列\(H\)的第\(n\)项,\(H_n\)。暴力DP理解第一个问题设DP状态\(f(i)\)为\(i\)个节点的二叉树个数。求\(f(i)\)时,枚举左儿子节点数量\(j......
  • 耳分解小记
    EarDecomposition耳:对于无向图\(G=(V,E)\)和\(V\)的一个子集\(S\),定义一个耳为一个顶点序列\(a_1\sima_m\),满足\(a_2\sima_{m-1}\inV-S\)互不相同且和\(a_1,a_m\)不同,且\(a_i\)和\(a_{i+1}\)之间均有连边。其中\(a_1\neqa_m\)时称为开耳。耳分解......
  • Oracle-创建用户不带C##(19c)
    由于oracle从12c开始引入了容器(PDB和CDB)、租户的概念。直接连接sysdba用户创建新用户时,会默认在CDB中创建公有用户,用户名需要以“C##”或“c##”开头。如果用户名开头不想使用“C##”或“c##”,则需要做如下操作。 (1)使用sysdba管理员用户登录sqlplus/assysdba (2)查看数据......
  • Irrlicht 小记
    1.irrlicht名称空间下包含corescenevideoiogui2.irrlicht的事件可以监听页面事件、鼠标事件、按键事件——但是具体响应根据程序结构有所区分(例子中的按键响应处理部分扔到了引擎循环部分;而界面响应通过记录场景指针,直接在自定义场景响应类内进行的处理)3.irrlicht......
  • supervisor命令小记
    查看已启动服务状态supervisorctlstatus查看某个服务状态supervisorctlstatus进程名启动某个进程supervisorctlstart进程名重启某个进程supervisorctlrestart进程启动名停止某个进程supervisorctlstop进程名修改或添加某个服务配置文件后,使其......
  • 动态树直径小记
    本文采用BY-NC-SA协议发布。要求:给你一棵树,边带权,每次断边连边(保证合法且仍是树),在线求每次修改后的直径。LCT(咕)TopTree拆边,然后用negiizhao论文里的方法维护。实现时注意,翻转标记会影响合并的信息,要swap一下。#include<iostream>#include<unordered_map>#includ......
  • UTF-8格式编码的文件分为带BOM和不带BOM windows下编程,Linux下编程建议使用“UTF-8无
    UTF-8格式编码的文件分为带BOM和不带BOMwindows下编程,Linux下编程建议使用“UTF-8无BOM格式,“建议使用”UTF-8带BOM格式“Notepad++支持“UTF-8无BOM格式”和“UTF-8带BOM格式”两种UTF-8。一直以来不知道二者有什么区别。程序员它们的区别是:UTF-8带BOM格式,就是在文件头添加......
  • 【小记】Docker容器间SSH公钥自动交换实现免密登录的一次尝试
    咋想到这茬了最近开始忙毕设的事儿了,想部署个伪分布式的Spark+Hadoop集群来进行测试。思来考去,最终咱把目光放在了Docker上。盘了两天,发现这玩意意外的有趣,镜像构建好后开箱即用,省去了些配置环境的成本。不过呢,在配置Hadoop的时候我发现了一个问题——Hadoop分布式搭建要求各......
  • 在.framework框架下的winfrom中使用Castle.DynamicProxy实现AOP问题小记
    1.需求:为项目中通讯PLC模块实现AOP,实现统一的日志打印,参数校验,方法执行时间统计2.问题:①现有项目没有IOC容器,没法使用部分AOP库的方法注册到IOC,(注:如果要实现IOC对现有代码改动大,并且AOP只是针对部分模块实现)②要在尽量小的代码改动下实现针对以上问题选择使用Castle.DynamicProx......
  • 【小记】MSMF 框架开发 UVC 摄像头如何正确设置 MF_MT_SUBTYPE
    简单说一下:IMFSourceReader有两个可以获取 IMFMediaType对象的接口,分别是 GetNativeMediaType与 GetCurrentMediaType。初始化时调用 GetCurrentMediaType获得的IMFMediaType对象(此时为硬件默认情况下自动选择的对象)再进行修改是不能用于SetCurrentMediaType的,即......