社区讨论

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 条回复,欢迎继续交流。

正在加载回复...