当前位置: 首页 > news >正文

LGP9120 [NOIP 2022.5] 密码锁 学习笔记

LGP9120 [NOIP 2022.5] 密码锁 学习笔记

洛谷链接

前言

这道 \(\text{LOCK}\) 是二三年春测的最后一道题。作为一道 \(\texttt{CNDS}\),因为随机化算法的存在而显得有点黯然失色。然而,将这道题对扫描线的(相对)复杂应用彻底消化吸收,也能让自己在数据结构能力上收获不少经验。

7R3WG1.png

这也是 \(\text{LOCK}\)。在邦多利第二季到第三季的动画中,从岐阜到东京,她(此处省略细节,详见萌娘百科或者哔站剧情解析)最终登上了武道馆,成功圆梦。希望我和你(如果有朋友在看的话)也可以。

真的能金牌吗。

题意简述

给定一个 \(m\)\(n\) 列的方阵 \(A\)。你可以任意次执行操作:将任意列循环位移若干格(对应原题面中密码锁的拨圈)。定义第 \(i\) 行的松散度 \(c_i=\max_{j=1}^n a_{i,j}-\min_{j=1}^n a_{i,j}\)。问 \(\max c_i\) 最小值(就是请最小化所有行的极差的最大值)。

多测。\(m\le 4\)\(\sum n\le 3\times 10^4\)\(1\le a_{i,j}\le 3\times 10^4\)。另外 \(m\le 3\)\(\sum n\le 1.5\times 10^5\)

做法解析一

首先,我们先来学习一下随机化做法。毕竟考场遇到这种骗分性价比高的还是应该骗一下。更何况这道题短短的随机化可以直接 \(\texttt{AC}\)

首先我们有一个显然假的贪心:从 \(1\)\(n\) 考虑每个拨圈,枚举出转多少格能最小化总答案。因为后效性,所以它大概率是错的。

不过,这个假贪心做一次的时间复杂度是 \(O(nk)\) 的。你发现 \(k\) 几乎可以视作常数,而 \(10^5\) 左右的数量级再乘点常数显然也能接受。那我一个随机化你不炸了?

的确如此,随机化真就可以把这题直接过掉。这玩意放 \(\texttt{T4}\) 多少沾点组题失误了。

代码实现一

本人写的时候犯了一堆堂食错误,详见错因总结,若可能。

随机化种子:\(114514\)

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1.5e6+5,Inf=0x3f3f3f3f;
int M,N,A[MaxN][5],tim;
int T[5],fmx[5],fmn[5],cmx[5],cmn[5],ans;
void mian(){readi(N),ans=Inf;for(int i=1;i<=M;i++)for(int j=1;j<=N;j++)readi(A[j][i]);for(int t=1,tres;t<=tim;t++){shuffle(A+1,A+N+1,mrnd);tres=0;for(int i=1;i<=M;i++)fmx[i]=fmn[i]=A[1][i];for(int i=2,ires,p;i<=N;i++){ires=Inf;for(int j=0,jres;j<M;j++){jres=0;for(int k=1,jj;k<=M;k++){T[k]=A[i][(k+j-1)%M+1];maxxer(jres,max(fmx[k],T[k])-min(fmn[k],T[k]));}if(jres<ires)ires=jres,p=j;}int tst=0;for(int j=1,jj;j<=M;j++){jj=(j+p-1)%M+1;maxxer(fmx[j],A[i][jj]);minner(fmn[j],A[i][jj]);maxxer(tst,fmx[j]-fmn[j]);}tres=ires;if(ans<=tres)break;}minner(ans,tres);}writil(ans);
}
int Tcn;
int main(){readis(Tcn,M);tim=(M>3?600:300);while(Tcn--)mian();return 0;
}

做法解析二

这个做法的代码篇幅还是比较长的。但如果你有想在 \(\texttt{CNOI}\) 上取得一番成就的决心,那么,你就应当至少有能迈过这道槛的实力。相信自己可以!

正经做法:从 \(m=1\) 推到 \(m=4\)

\(m=1\) 没有任何好说的。最大值减最小值即可。

\(m=2\) 时?你发现每个拨圈就两种方法,并且每个拨圈较大的那个居于同一行,较小的那个居于另一行一定最优(显然)。时间复杂度 \(O(1)\)

\(m=3\) 时?简单的贪心再也撑不动了,最小化最大值考虑二分,设二分出的值为 \(C\)。我们让全局的最大值与最小值不居于同一行仍然是必要的,所以我们不妨钦定全局最大值在第一行,然后全局最小值无非有两种选择,不妨分别把在第二行或第三行的情况都考虑一遍。

此时,我们称没有全局最值的行为剩余行。我们考察对于每一列,枚举它转了多少行,如果当前转法保证非剩余行合法,那么当前剩余行里的数就是“可选的”。最后存在合法方案等价于,存在一个值域上长为 \(C+1\) 的区间(因为 \([p,p+C]\) 的长度为 \(C+1\)),使得每一列剩余行的可选元素至少有一个坐落在此区间内。然后有经典转化:一个区间匹配若干种点等价于若干种区间匹配一个点。这都用不到线段树,直接把整个值域数轴扫一遍就行了。时间复杂度 \(O(n\log V)\)

\(m=4\) 时?与 \(m=3\) 相比,\(m=4\) 多了一个剩余行。这意味着剩余行的状态变成了一个数对,我们的判定也升到了二维:“存在一个以两维值域为平面上的,边长为 \(C+1\) 的正方形,使得每一列都存在一个数对落在里面”。

同样地,“用一个矩形覆盖一堆点”可以直接转化为“用一堆矩形覆盖一个点”,例如 \(\texttt{LGP1502}\)。然后,“使得每一列都存在一个”实际上等价于:把每列看作一种颜色之后,能集齐所有颜色。

不过,同颜色的矩形得避免算重。这个可以用容斥拆拼出来。因为 \(m=4\),所以最多一个颜色有四个点,所以暴力容斥最多产生 \(2^4-1=15\) 个矩形。

那这题就做完了?不不不,这题把暴力容斥卡了,评测机拒绝接受我们的 \(15\) 倍常数,想暴力卡过去最后一个点很麻烦(至少对于此刻的我来说)。

我们只能老老实实地写“扫描线”做法。就是对于同一个颜色的所有矩形我们把它重合在一起,然后按某一维剖开成若干条矩形。我代码的实现非常的暴力,没有用 multiset

不过有一点是对于卡常提速来说最重要的:

void aclear(int u){if(!mx[u])return;mx[u]=tag[u]=0;if(cl[u]==cr[u])return;aclear(ls(u)),aclear(rs(u));
}

这个 if(!mx[u])return; 可以用极简的方式来优化每次清空线段树的过程。

此做法的复杂度为 \(O(n\log V\log n)\) 带一些关于 \(m\) 的“常数”。

代码实现二

这道题写的时候虽然比较考研耐心与耐力,但是写完的时候还是很有成就感的。

然而这个题本身还是有其恶心之处的:这道题对非最优实现的容忍度太低了。你在 \(m=3\) 写线段树会被卡爆,\(m=4\) 暴力容斥也会被卡掉,这种低容忍度在同级别的赛题中疑似鲜有题出其右。

不过,你调这道题的时候会发现它的样例质量相当不错,这还算是一个优点。

代码里面还有各种为了加速而搞的提前 break 之类的东西。

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1.5e5+5,MaxV=6e4+5,Inf=0x3f3f3f3f;
int M,N,A[MaxN][5],T[5],B[MaxN][5],amn,amx,ans,V;
void toggle(int a[],int k,int b[]){for(int j=1;j<=M;j++)T[(j+k-1)%M+1]=a[j];for(int j=1;j<=M;j++)b[j]=T[j];
}
struct SegTree{int cl[MaxN<<2],cr[MaxN<<2],cmid[MaxN<<2];int mx[MaxN<<2],tag[MaxN<<2];int ls(int u){return u<<1;}int rs(int u){return (u<<1)|1;}void build(int u,int l,int r){mx[u]=tag[u]=0;cl[u]=l,cr[u]=r;if(l==r)return;int mid=(l+r)>>1;cmid[u]=mid;build(ls(u),l,mid),build(rs(u),mid+1,r);}void aclear(int u){if(!mx[u])return;mx[u]=tag[u]=0;if(cl[u]==cr[u])return;aclear(ls(u)),aclear(rs(u));}void pushup(int u){mx[u]=max(mx[ls(u)],mx[rs(u)]);}void maketag(int u,int x){mx[u]+=x,tag[u]+=x;}void pushdown(int u){if(tag[u])maketag(ls(u),tag[u]),maketag(rs(u),tag[u]),tag[u]=0;}void modify(int u,int dl,int dr,int k){if(dl<=cl[u]&&cr[u]<=dr){maketag(u,k);return;}pushdown(u);if(dl<=cmid[u])modify(ls(u),dl,dr,k);if(dr>cmid[u])modify(rs(u),dl,dr,k);pushup(u);}
}SgT;
vector<pii> hvec;
struct anob{int c,p,k;};vector<anob> C;
bool cmp1(anob a,anob b){return a.p<b.p;}
void cadd(int c,int l,int r){C.push_back({c,l,1}),C.push_back({c,r+1,-1});}
int mxc,mnc,buc[MaxV],csum;
void updbuc(int c,int k){csum-=(buc[c]>0);buc[c]+=k;csum+=(buc[c]>0);}
bool solve1(int lim){for(auto [nh,tm] : hvec){toggle(A[mnc],tm,B[mnc]);int rh=(nh==2?3:2),flg=0;C.clear(),csum=0;for(int i=1;i<=V;i++)buc[i]=0;fill(buc,buc+V+1,0);for(int i=1;i<=N;i++){flg=0;if(mxc==i||mnc==i){if(amx-B[i][1]>lim)break;if(B[i][nh]-amn>lim)break;flg=1;int pos=B[i][rh];cadd(i,pos,pos+lim);continue;}for(int k=0,pos;k<M;k++){toggle(A[i],k,B[i]);if(amx-B[i][1]>lim)continue;if(B[i][nh]-amn>lim)continue;flg=1,pos=B[i][rh];cadd(i,pos,pos+lim);}if(!flg)break;}if(!flg)continue;sort(C.begin(),C.end(),cmp1);for(int j=0;j<C.size();j++){if(j>0&&C[j-1].p!=C[j].p&&csum==N)return true;auto [cc,cp,ck]=C[j];updbuc(cc,ck);}}return false;
}
struct bnob{int l,r,p,k;};vector<bnob> S;
bool cmp2(bnob a,bnob b){return a.p<b.p;}
void sadd(int lx,int rx,int ly,int ry,int k){if(lx>rx||ly>ry)return;S.push_back({lx,rx,ly,k});S.push_back({lx,rx,ry+1,-k});
}
struct cnob{int x,y;};
vector<cnob> D;
int cxa[10],cxn,cya[10],cyn;
vector<pii> sgp[10];int xcc[10],xcs[10];
bool solve2(int lim){for(auto [nh,tm] : hvec){toggle(A[mnc],tm,B[mnc]);int rh1,rh2,flg=0;if(nh==2)rh1=3,rh2=4;if(nh==3)rh1=2,rh2=4;if(nh==4)rh1=2,rh2=3;S.clear();for(int i=1,cz;i<=N;i++){D.clear();flg=0;if(mxc==i||mnc==i){if(amx-B[i][1]>lim)break;if(B[i][nh]-amn>lim)break;flg=1;int pos1=B[i][rh1],pos2=B[i][rh2];sadd(pos1,pos1+lim,pos2,pos2+lim,1);continue;}for(int k=0;k<M;k++){toggle(A[i],k,B[i]);if(amx-B[i][1]>lim)continue;if(B[i][nh]-amn>lim)continue;flg=1;D.push_back({B[i][rh1],B[i][rh2]});}cz=D.size();if(!flg)break;for(int j=0;j<cz;j++)cxa[j]=D[j].x,cxa[j+cz]=D[j].x+lim+1;sort(cxa,cxa+cz*2),cxn=unique(cxa,cxa+cz*2)-cxa;for(int j=0;j<cz;j++)cya[j]=D[j].y,cya[j+cz]=D[j].y+lim+1;sort(cya,cya+cz*2),cyn=unique(cya,cya+cz*2)-cya;for(int j=0;j<cyn;j++)sgp[j].clear();for(int j=0;j<cz;j++){int lx=lower_bound(cxa,cxa+cxn,D[j].x)-cxa;int rx=lower_bound(cxa,cxa+cxn,D[j].x+lim+1)-cxa;int ly=lower_bound(cya,cya+cyn,D[j].y)-cya;int ry=lower_bound(cya,cya+cyn,D[j].y+lim+1)-cya;sgp[ly].push_back({lx,1}),sgp[ly].push_back({rx,-1});sgp[ry].push_back({lx,-1}),sgp[ry].push_back({rx,1});}for(int j=0;j<cxn;j++)xcc[j]=0;for(int j=0;j<cyn;j++){for(auto &[p,w] : sgp[j])xcc[p]+=w;for(int k=0,l=0;k<cxn;k++){xcs[k]=(k?xcs[k-1]:0)+xcc[k];if(!xcs[k]){if(l!=k)sadd(cxa[l],cxa[k]-1,cya[j],cya[j+1]-1,1);l=k+1;}}}}if(!flg)continue;flg=0;sort(S.begin(),S.end(),cmp2);for(int j=0;j<S.size();j++){if(j>0&&S[j-1].p!=S[j].p&&SgT.mx[1]==N){flg=1;break;}auto [cl,cr,cp,ck]=S[j];if(cp>amx)break;SgT.modify(1,cl,cr,ck);}SgT.aclear(1);if(flg)return true;}return false;
}
bool check(int lim){if(M==3)return solve1(lim);else return solve2(lim);
}
void mian(){readi(N);amx=0,amn=Inf;for(int j=1;j<=M;j++){for(int i=1;i<=N;i++){readi(A[i][j]);maxxer(amx,A[i][j]);minner(amn,A[i][j]);}}if(N==1){writil(0);return;}if(M==1){writil(amx-amn);return;}if(M==2){int nmx=0,xmn=Inf;for(int i=1;i<=N;i++){maxxer(nmx,min(A[i][1],A[i][2]));minner(xmn,max(A[i][1],A[i][2]));}writil(max(amx-xmn,nmx-amn));return;}V=amx*2-amn;SgT.build(1,1,V);hvec.clear();for(int i=1,cmx,p;i<=N;i++){cmx=0;for(int j=1;j<=M;j++)if(A[i][j]>cmx)cmx=A[i][j],p=j;if(cmx!=amx)continue;mxc=i;int k=(M+1-p)%M;toggle(A[i],k,A[i]);break;}for(int i=1,cmn,p;i<=N;i++){cmn=Inf;for(int j=1;j<=M;j++)if(A[i][j]<cmn)cmn=A[i][j],p=j;if(cmn!=amn)continue;mnc=i;if(mnc==mxc)hvec.push_back({p,0});else{int k=(M+1-p)%M;toggle(A[i],k,A[i]);for(int j=2;j<=M;j++)hvec.push_back({j,j-1});}break;}for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)B[i][j]=A[i][j];int sl=0,sr=amx-amn,smid;for(int i=0;sl<=sr;i++){smid=(sl+sr)>>1;if(check(smid))ans=smid,sr=smid-1;else sl=smid+1;}writil(ans);
}
int Tcn;
int main(){readis(Tcn,M);while(Tcn--)mian();return 0;
}

后记

夢撃ち抜く瞬間に

キミは何を思うの?

http://www.hskmm.com/?act=detail&tid=25921

相关文章:

  • 深入解析:OpenCV CUDA模块图像处理------创建CUDA加速的Canny边缘检测器对象createCannyEdgeDetector()
  • 机器人技术奖学金项目助力STEM教育发展
  • SAP ABAP 事务码 RZ12 里的 Max Number of WPs Used 参数的作用介绍
  • busybox 没有 clear 命令吗
  • 实用指南:Hive SQL 中 BY 系列关键字全解析:从排序、分发到分组的核心用法
  • 经过基于流视频预测的可泛化双手运行基础策略
  • 每个JavaScript开发者都应掌握的33个核心概念
  • 解决Docker存储空间不足问题 - 指南
  • 完整教程:数据结构:递归的种类(Types of Recursion)
  • Nova Premier模型安全评估结果解析
  • Paypal 设置不自动换汇
  • 诺贝尔生理与医学奖颁给这项革命技术,多家中国公司已布局!(附名单)
  • 钱璐璐,唯一通讯发Nature,作者仅2人!
  • 华为员工工资待遇表:
  • 体验mcp服务的开发集成和演示过程 - 智慧园区
  • AI技术全景解析:从架构设计到社会影响
  • 对话系统中零样本与少样本学习技术解析
  • 随手记 | 关于AI最新趋势和未来发展方向探讨
  • 何夜无雨 - Ishar
  • 玩转树莓派屏幕之四:适配tslib增加触屏准确度
  • caddy搭建静态+PHP+伪静态Web服务器
  • 全自动 AI 视频创作与发布工具:LuoGen-agent
  • 静态库.a与.so库文件的生成与使用
  • CF2145D Inversion Value of a Permutation
  • 牛客刷题-Day8
  • Educational Codeforces Round 183 (Rated for Div. 2)
  • 高三闲话 #2
  • D. Inversion Value of a Permutation edu div2
  • 个人博客公告
  • 一个刚大一的普通大学生