社区讨论
0pts求条
P2463[SDOI2008] Sandy 的卡片参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mk3g0nrw
- 此快照首次捕获于
- 2026/01/07 11:12 上个月
- 此快照最后确认于
- 2026/01/07 20:04 上个月
CPP
/* ChongYun */
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define File(s,t) freopen(s".in","r",stdin),freopen(t".out","w",stdout)
#define Time() cerr<<fixed<<setprecision(6)<<1.*(double)(clock()-__st)/CLOCKS_PER_SEC<<"s\n"
#define Memory() cerr<<fixed<<setprecision(6)<<1.*fabs(&__t-&__s)/1024./1024.<<"MB\n"
char __s; clock_t __st;
#define ll long long
#define ldb long double
#define ull unsigned long long
#define reg register
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define _LIMIT(x) (x>='a'&&x<='z')
#define flush() fwrite(obuf,1,O-obuf,stdout)
#define putchar(x) ((O==obuf+(1<<21))&&(flush(),O=obuf)),*O++=x
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline char gc(){ reg char ch=getchar();while(!_LIMIT(ch))ch=getchar();return ch; }
inline int read(){
reg int x=0,f=1;
reg char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar(); }
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline int read(string &s){
s=""; reg char ch=getchar();
while(!_LIMIT(ch)) ch=getchar();
while(_LIMIT(ch)) s+=ch,ch=getchar();
return (int)s.size();
}
inline void write(int x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar((x%10)^48);
}
inline void write(int x,char ch){ write(x),putchar(ch); }
inline void write(string s){ for(reg int i=0;i<(int)s.size();++i) putchar(s[i]); }
struct Flush{ ~Flush(){ flush(); } }_;
const int N=4e5+5,inf=1865;
int n,ans=1,m[1005],a[1005][105],tot=1,lst=1,len[N],lnk[N],cnt[N],flg[N];
__gnu_pbds::gp_hash_table<int,int> ch[N];
void Ins(int x){
int cur=++tot,p=lst;
len[cur]=len[p]+1;
for(;p&&!ch[p][x];ch[p][x]=cur,p=lnk[p]);
if(!p) lnk[cur]=1;
else{
int q=ch[p][x];
if(len[q]==len[p]+1) lnk[cur]=q;
else{
len[++tot]=len[p]+1,lnk[tot]=lnk[q],ch[tot]=ch[q];
lnk[cur]=lnk[q]=tot;
for(;p&&ch[p][x]==q;ch[p][x]=tot,p=lnk[p]);
}
}
lst=cur;
}
namespace Tracy{
void Main(){
n=read();
for(int i=1;i<=n;++i){
m[i]=read();
for(int j=1,lst;j<=m[i];++j){
a[i][j]=read();
if(j^1) Ins(a[i][j]-a[i][j-1]);
}
}
for(int i=1;i<=n;++i){
for(int j=2,p=1;j<=m[i];++j){
p=ch[p][a[i][j]-a[i][j-1]];
int now=p;
while(flg[now]^i) flg[now]=i,++cnt[now],p=lnk[now];
}
}
for(int i=1;i<=tot;++i){
if(cnt[i]^n) continue;
ans=max(ans,len[i]+1);
}
write(ans,'\n');
}
char __t;
int Reznik(int T=1){
__st=clock();
while(T--) Main();
return /*Time(),Memory(),*/0;
}
}
signed main(){
// File("","");
return Tracy::Reznik();
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...