题意:有\(2\)小写字符串\(s,t\),每次操作可以删掉一个字符串中的字符，或插入一个字符，或将某个上的字符换成另一个字符，求是否能在\(k\)步之内使两串相同。如能，输出最短步数
\(|s|,|t|\leq 5\cdot 10^5,k\leq 5000\)
我们不难得出一个结论，我们可以使得最短操作中不含删除
因而我们不难得到一个\(O(n^2)\)的\(dp\)
f[x+1][y+1]=max(f[x+1][y+1],f[x][y]+(str1[x+1]!=str2[x+1]));
f[x+1][y]=max(f[x+1][y],f[x][y]+1);
f[x][y+1]=max(f[x][y+1],f[x][y]+1);
直接搜索，时间复杂度\(O(3^k)\)
由于步数\(k\)较小，所以我们考虑利用\(\tt LCP\)跳过共同部分
定义\(f_{x,y}\)表示使用了\(x\)步,将\(t\)串比\(s\)串长\(y\)的前缀匹配起来，最多能使\(t\)串匹配到哪里
不难发现\(|y|\leq x\)
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;char k;bool vis=0;
do (k=getchar())==‘-‘&&(vis=1);while(‘0‘>k||k>‘9‘);
while(‘0‘<=k&&k<=‘9‘)t=(t<<3)+(t<<1)+(k^‘0‘),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int s,m,K;
char str[500005],str1[500005];
char sv[1000005];
int rk[1000005],sa[1000005],tp[1000005],tn[1000005],M,h[22][1000005],L;
void Rsort(int s){
for(int i=1;i<=M;++i)tn[i]=0;
for(int i=1;i<=s;++i)++tn[rk[i]];
for(int i=1;i<=M;++i)tn[i]+=tn[i-1];
for(int i=s;i;--i)sa[tn[rk[tp[i]]]--]=tp[i];
}
void make(int s){
for(int i=1;i<=s;++i)rk[i]=sv[i],tp[i]=i;
M=257;Rsort(s);
for(int i=1;i<=s;i<<=1){
M=0;
for(int j=1;j<=i;++j)tp[++M]=s-j+1;
for(int j=1;j<=s;++j)
if(sa[j]>i)tp[++M]=sa[j]-i;
Rsort(s);swap(rk,tp);
rk[sa[1]]=M=1;
for(int j=2;j<=s;++j)
rk[sa[j]]=(tp[sa[j]]^tp[sa[j-1]] or tp[sa[j]+i]^tp[sa[j-1]+i])?++M:M;
}
}
void make_h(int s){
for(int i=1,k=0;i<=s;++i){
if(rk[i]==1)continue;
if(k)--k;
int w=sa[rk[i]-1];
while(w+k<=s&&i+k<=s&&sv[w+k]==sv[i+k])++k;
h[0][rk[i]]=k;
}
for(int i=0;i<19;++i)
for(int j=1;j+(1<<i+1)-1<=s;++j)
h[i+1][j]=min(h[i][j],h[i][j+(1<<i)]);
}
int Log2(double x){return x==1?0:1+(*((unsigned ll*)&x)>>52&1023);}
int lcp(int x,int y){
x=rk[x+1];y=rk[y+s+2];
if(x>y)swap(x,y);++x;
int w=Log2(y-x+1);
return min(h[w][x],h[w][y-(1<<w)+1]);
}int f[5005][5005];
int main(){
s=read,m=read,K=read;
scanf("%s",str);
scanf("%s",str1);
memcpy(sv+1,str,s);
sv[s+1]=‘#‘;
memcpy(sv+s+2,str1,m);
L=s+m+1;
make(L);make_h(L);
f[0][K]=lcp(0,0);
for(int i=0;i<K;++i)
for(int j=-i;j<=i;++j){
int lx=f[i][j+K],rx=lx+j;
if(lx<s)f[i+1][j+K-1]=max(f[i+1][j+K-1],lx+1+lcp(lx+1,rx));
if(rx<m)f[i+1][j+K+1]=max(f[i+1][j+K+1],lx+lcp(lx,rx+1));
if(lx<s&&rx<m)f[i+1][j+K]=max(f[i+1][j+K],lx+1+lcp(lx+1,rx+1));
}
for(int i=0;i<=K;++i)
if(f[i][m-s+K]==s)
return printf("%d",i),0;
puts("-1");
return 0;
}
题意: 有\(n\)个人，一个人如果实力强于旁边的人，则可以杀死旁边的人，并且实力\(+1\),重复此过程直到只剩一人,问有哪些人可能成为最后剩下的人.
不会真有人会去打状压吧\(\tt \huge ?\)
我们不难发现，一个人如果想赢，肯定会一个劲地杀身旁的人.如果其他人没死光，则铁定赢不了，因为其他人中最强的人只会越来越强
所以我们直接打个\(n^2\)的暴力即可
我想着随便打个\(\tt ST\)表优化一下杀人过程，结果就\(\rm A\)了？
其实可以通过\(\text{"\__/"}\)型的数据卡掉
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;char k;bool vis=0;
do (k=getchar())==‘-‘&&(vis=1);while(‘0‘>k||k>‘9‘);
while(‘0‘<=k&&k<=‘9‘)t=(t<<3)+(t<<1)+(k^‘0‘),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int s,a[500005],ans[500005],St[500005][20];
int Log2(double x){return x==1?0:1+(*((unsigned ll*)&x)>>52&1023);}
int main(){
s=read;
for(int i=1;i<=s;++i)a[i]=read;
if(s<=2000){
for(int i=1;i<=s;++i){
int l=i-1,r=i+1,t=a[i];
while(0<l||r<=s){
if(0<l&&a[l]<=t){++t;--l;continue;}
if(r<=s&&a[r]<=t){++t;++r;continue;}
break;
}
if(!l&&r==s+1)ans[++ans[0]]=i;
}printf("%d\n",ans[0]);
for(int i=1;i<=ans[0];++i)
printf("%d ",ans[i]);
return 0;
}for(int i=1;i<=s;++i)St[i][0]=a[i];
for(int i=0;(1<<i+1)<=s;++i)
for(int j=1;j+(1<<i+1)-1<=s;++j)
St[j][i+1]=max(St[j][i],St[j+(1<<i)][i]);
for(int i=1;i<=s;++i){
int l=i-1,r=i+1,t=a[i];
while(0<l||r<=s){
if(0<l&&a[l]<=t){
for(int j=Log2(l);~j;--j)
if(l-(1<<j)+1>0&&St[l-(1<<j)+1][j]<=t){
l-=1<<j;
t+=1<<j;
}
continue;
}
if(r<=s&&a[r]<=t){
for(int j=Log2(s-r+1);~j;--j)
if(r+(1<<j)-1<=s&&St[r][j]<=t){
r+=1<<j;
t+=1<<j;
}
continue;
}
break;
}
if(!l&&r==s+1)ans[++ans[0]]=i;
}printf("%d\n",ans[0]);
for(int i=1;i<=ans[0];++i)
printf("%d ",ans[i]);
return 0;
}
正解好像是笛卡尔树，时间复杂度\(O(n)\)，也不是很难打
特地\(\rm \large \%\%\%\)\(\tt JZM\)巨佬，直接想出\(O(n\log_2n)\)的\(\tt cdq\)正解
题意:大小\(n\times m\)的矩阵\(A\)，求有多少个长宽均大于\(2\)的子矩阵满足边界只有一种颜色
\(n,m\leq 2000,0\leq A_{i,j}\leq 10^9\)
随便打个\(O(n^4)\)的暴力就能拿到的吧
预处理每个点向四个方向同色延伸的最远距离
然后枚举右下角，打个扫描线加树状数组就可以\(O(n^3\log_2n)\)了
我们考虑进行分治
我们每次计算\(x\in [l_1,r_1],y\in[l_2,r_2]\)时形成的矩阵内部的贡献
所以我们计算出\(x=mid\)横穿的矩阵个数，并递归计算\(x\in[l_1,mid],y\in[l_2,r_2]\)和\(x\in[mid+1,r_1],y\in[l_2,r_2]\)
我们考虑计算出中线两端的情况，再利用乘法原理合并
至于如何统计中线两端的情况，我们考虑枚举上边界，使用扫描线维护下边界
当然，如果我们真的这样弄，我们会收获一个最坏情况下\(O(n^3)\)的算法
所以我们每次应用中线较长的一条边，这样时间复杂度就是\(O(n^2\log n)\)
假设当前矩阵\(A\)的大小\(x\)
因为分割的为长边，所以枚举边界的数量\(\leq \sqrt x\)
则\(T(x)=2T(\frac{x}{2})+x=x\log x=n^2\log n\)
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;char k;bool vis=0;
do (k=getchar())==‘-‘&&(vis=1);while(‘0‘>k||k>‘9‘);
while(‘0‘<=k&&k<=‘9‘)t=(t<<3)+(t<<1)+(k^‘0‘),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int a[2005][2005],lx[2005][2005],rx[2005][2005],ly[2005][2005],ry[2005][2005],n,m,cntx[2005][2005],cnty[2005][2005];
int _tl[2005],_tr[2005];ll ans;
void solve(int l,int r,int L,int R){
if(L==R||l==r)return;
if(r-l<=R-L){int mid=L+R>>1,midx=mid+1;
solve(l,r,L,mid);solve(l,r,midx,R);
for(int i=l;i<=r;++i){
if(a[i][mid]!=a[i][midx])continue;
int Tl=max(mid-lx[i][mid]+1,L),Tr=min(midx+rx[i][midx]-1,R),tl=0,tr=0;
for(int j=Tl;j<=mid;++j)++tl,++_tl[min(i+ry[i][j]-1,r)];
for(int j=midx;j<=Tr;++j)++tr,++_tr[min(i+ry[i][j]-1,r)];
for(int j=i;j<=r;++j){
if(j!=i&&a[j][mid]==a[j][midx]&&a[j][mid]==a[i][mid]&&max(mid-lx[j][mid]+1,L)<=Tl)
cntx[i][j]+=tl;
tl-=_tl[j];_tl[j]=0;
}
for(int j=i;j<=r;++j){
if(j!=i&&a[j][mid]==a[j][midx]&&a[j][mid]==a[i][mid]&&min(midx+rx[j][midx]-1,R)>=Tr)
cnty[i][j]+=tr;
tr-=_tr[j];_tr[j]=0;
}
for(int j=Tl;j<=mid;++j)++tl,++_tl[max(i-ly[i][j]+1,l)];
for(int j=midx;j<=Tr;++j)++tr,++_tr[max(i-ly[i][j]+1,l)];
for(int j=i;j>=l;--j){
if(j!=i&&a[j][mid]==a[j][midx]&&a[j][mid]==a[i][mid]&&max(mid-lx[j][mid]+1,L)<Tl)
cntx[j][i]+=tl;
tl-=_tl[j];_tl[j]=0;
}
for(int j=i;j>=l;--j){
if(j!=i&&a[j][mid]==a[j][midx]&&a[j][mid]==a[i][mid]&&min(midx+rx[j][midx]-1,R)>Tr)
cnty[j][i]+=tr;
tr-=_tr[j];_tr[j]=0;
}
}
for(int i=l;i<r;++i)
for(int j=i+1;j<=r;++j)
ans+=cntx[i][j]*cnty[i][j],cntx[i][j]=cnty[i][j]=0;
}else{int mid=l+r>>1,midx=mid+1;
solve(l,mid,L,R);solve(midx,r,L,R);
for(int i=L;i<=R;++i){
if(a[mid][i]!=a[midx][i])continue;
int Tl=max(mid-ly[mid][i]+1,l),Tr=min(midx+ry[midx][i]-1,r),tl=0,tr=0;
for(int j=Tl;j<=mid;++j)++tl,++_tl[min(i+rx[j][i]-1,R)];
for(int j=midx;j<=Tr;++j)++tr,++_tr[min(i+rx[j][i]-1,R)];
for(int j=i;j<=R;++j){
if(j!=i&&a[mid][j]==a[midx][j]&&a[mid][j]==a[mid][i]&&max(mid-ly[mid][j]+1,l)<=Tl)
cntx[i][j]+=tl;
tl-=_tl[j];_tl[j]=0;
}
for(int j=i;j<=R;++j){
if(j!=i&&a[mid][j]==a[midx][j]&&a[mid][j]==a[mid][i]&&min(midx+ry[midx][j]-1,r)>=Tr)
cnty[i][j]+=tr;
tr-=_tr[j];_tr[j]=0;
}
for(int j=Tl;j<=mid;++j)++tl,++_tl[max(i-lx[j][i]+1,L)];
for(int j=midx;j<=Tr;++j)++tr,++_tr[max(i-lx[j][i]+1,L)];
for(int j=i;j>=L;--j){
if(j!=i&&a[mid][j]==a[midx][j]&&a[mid][j]==a[mid][i]&&max(mid-ly[mid][j]+1,l)<Tl)
cntx[j][i]+=tl;
tl-=_tl[j];_tl[j]=0;
}
for(int j=i;j>=L;--j){
if(j!=i&&a[mid][j]==a[midx][j]&&a[mid][j]==a[mid][i]&&min(midx+ry[midx][j]-1,r)>Tr)
cnty[j][i]+=tr;
tr-=_tr[j];_tr[j]=0;
}
}
for(int i=L;i<R;++i)
for(int j=i+1;j<=R;++j)
ans+=cntx[i][j]*cnty[i][j],cntx[i][j]=cnty[i][j]=0;
}
}
int main(){n=read,m=read;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
a[i][j]=read+1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
lx[i][j]=a[i][j]==a[i][j-1]?lx[i][j-1]+1:1;
ly[i][j]=a[i][j]==a[i-1][j]?ly[i-1][j]+1:1;
}
for(int i=n;i;--i)
for(int j=m;j;--j){
rx[i][j]=a[i][j]==a[i][j+1]?rx[i][j+1]+1:1;
ry[i][j]=a[i][j]==a[i+1][j]?ry[i+1][j]+1:1;
}
solve(1,n,1,m);cout<<ans;
return 0;
}
原文：https://www.cnblogs.com/SYDevil/p/14589929.html