{"id":158,"date":"2010-03-17T12:54:00","date_gmt":"2010-03-17T04:54:00","guid":{"rendered":"http:\/\/localhost\/?p=158"},"modified":"2010-03-17T12:54:00","modified_gmt":"2010-03-17T04:54:00","slug":"pku_1743_muscial_theme","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=158","title":{"rendered":"PKU 1743 Muscial Theme"},"content":{"rendered":"\n

\u8fd9\u662f\u4e00\u9053\u5f88\u7ecf\u5178\u7684\u9898\u76ee\u4e86\u3002\u3002\u9898\u76ee\u5728\uff1ahttp:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=1743<\/a>
USACO\u4e0a\u9762\u7684\u90a3\u6b21\u6211\u662f\u7528DP\u8fc7\u7684\uff0c\u73b0\u5728\u4e0d\u80fdDP\u4e86\u3002\u6211\u5b66\u4e86\u4e00\u4e0bSA\u3002\u8fc7\u6389\u4e86\u3002\u4e0d\u8fc7\u53c8\u60f3\u5230\u4e86\u4e00\u4e2a\u7528Hash\u7684\u505a\u6cd5\u6bd4\u8f83NB\u3002\u3002
\u9996\u5148\u628a\u539f\u7cfb\u5217\u6362\u6210\u5dee\u7cfb\u5217\u3002\u3002
\u65b9\u6cd5\u8fd8\u662f\u4e8c\u5206\uff0c\u56e0\u4e3a\u957f\u5ea6\u4e3al\u7684\u91cd\u590d\u5b57\u4e32\u5b58\u5728\u90a3\u4e48l-1\u7684\u80af\u5b9a\u4e5f\u5b58\u5728\uff0c\u6240\u4ee5\u95ee\u9898\u53d8\u6210\u5224\u65ad\u6240\u6709\u957f\u5ea6\u4e3al\u7684\u5b57\u4e32\u4e2d\u6709\u6ca1\u6709\u76f8\u540c\u4e14\u4e0d\u76f8\u4ea4\u7684\uff0c\u8fd9\u53ef\u4ee5\u7528Hash\u6765\u89e3\u51b3\uff0c\u7b97\u51fa\u6bcf\u4e2a\u5b57\u4e32\u7684Hash\u503c\u7136\u540e\u7528\u4e00\u4e2aHash\u8868\u6765\u4fdd\u5b58\uff0c\u6709\u70b9\u7c7b\u4f3cRabin-Karp\u7b97\u6cd5\u3002\u3002\u7136\u540e\u4e8c\u5206\u5c31OK\u4e86\u3002\u3002\u4e3a\u4e86\u8c03\u8bd5\u6211\u8fd8\u53bbUSACO\u4e86\u4e00\u4e0b\u3002\u3002\u597d\u4e45\u6ca1\u53bb\u4e86\u3002\u6709\u70b9\u6000\u5ff5\u997f\u3002\u3002
Code\uff1a<\/p>\n

\/* PROG: theme LANG: C++ ID: Tom Chen*\/#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1;typedef unsigned int uint;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;const int maxn=20000,seed[]={131,1331,10007,133331},size=17771;int A[maxn],n,Len;struct Hash{ struct node { node*next; uint h[4]; int Max,Min; void Renew(int x) { Max=max(Max,x); Min=min(Min,x); } bool Legal() { return Max-Min>Len; } bool equals(uint _h[4])const { for(int i=0;i<4;i++) if(h[i]!=_h[i])return false; return true; } }Data[maxn],*Now,*H[size]; void Clear() { Now=Data; rep(i,size) H[i]=0; } node* new_node(uint h[4],int start,node*next) { memcpy(Now->h,h,sizeof(Now->h)); Now->Max=Now->Min=start; Now->next=next; return Now++; } bool Insert(uint h[4],int start) { int t=h[0]%size; for(node*i=H[t];i;i=i->next) if(i->equals(h)) { i->Renew(start); return i->Legal(); } H[t]=new_node(h,start,H[t]); return false; }}H;bool Check(int l){ H.Clear(); Len=l;uint e[4]={1,1,1,1}; rep(i,4)rep(j,l-1)e[i]*=seed[i]; uint h[4]={0}; rep(i,l)rep(j,4) h[j]*=seed[j],h[j]+=A[i]; H.Insert(h,0); for(int i=1;i+l<=n;i++) { rep(j,4) { h[j]-=A[i-1]*e[j]; h[j]*=seed[j]; h[j]+=A[i+l-1]; } if(H.Insert(h,i)) return true; } return false;}bool Init(){ cin>>n;if(!n)return false;rep(i,n)scanf("%d",A+i); rep(i,n-1) A[i]=A[i+1]-A[i]+90; –n; return true;}void Work(){ int l=0,r=n\/2+2; while(l+1<r) { int m=(l+r)\/2; if(Check(m))l=m; else r=m; } ++l; if(l<5)cout<<0<<endl; else cout<<l<<endl;}bool Solve(){ if(!Init())return false; Work(); return true;}int main(){ \/\/freopen("in","r",stdin); \/\/freopen("theme.in","r",stdin); \/\/freopen("theme.out","w",stdout); while(Solve());} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u8fd9\u662f\u4e00\u9053\u5f88\u7ecf\u5178\u7684\u9898\u76ee\u4e86\u3002\u3002\u9898\u76ee\u5728\uff1ahttp:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=1743USACO\u4e0a\u9762\u7684\u90a3\u6b21\u6211\u662f\u7528DP\u8fc7\u7684\uff0c\u73b0\u5728\u4e0d\u80fdDP\u4e86\u3002\u6211\u5b66\u4e86\u4e00\u4e0bSA\u3002\u8fc7\u6389\u4e86\u3002\u4e0d\u8fc7\u53c8\u60f3\u5230\u4e86\u4e00\u4e2a\u7528Hash\u7684\u505a\u6cd5\u6bd4\u8f83NB\u3002\u3002\u9996\u5148\u628a\u539f\u7cfb\u5217\u6362\u6210\u5dee\u7cfb\u5217\u3002\u3002\u65b9\u6cd5\u8fd8\u662f\u4e8c\u5206\uff0c\u56e0\u4e3a\u957f\u5ea6\u4e3al\u7684\u91cd\u590d\u5b57\u4e32\u5b58\u5728\u90a3\u4e48l-1\u7684\u80af\u5b9a\u4e5f\u5b58\u5728\uff0c\u6240\u4ee5\u95ee\u9898\u53d8\u6210\u5224\u65ad\u6240\u6709\u957f\u5ea6\u4e3al\u7684\u5b57\u4e32\u4e2d\u6709\u6ca1\u6709\u76f8\u540c\u4e14\u4e0d\u76f8\u4ea4\u7684\uff0c\u8fd9\u53ef\u4ee5\u7528Hash\u6765\u89e3\u51b3\uff0c\u7b97\u51fa\u6bcf\u4e2a\u5b57\u4e32\u7684Hash\u503c\u7136\u540e\u7528\u4e00\u4e2aHash\u8868\u6765\u4fdd\u5b58\uff0c\u6709\u70b9\u7c7b\u4f3cRabin-Karp\u7b97\u6cd5\u3002\u3002\u7136\u540e\u4e8c\u5206\u5c31OK\u4e86\u3002\u3002\u4e3a\u4e86\u8c03\u8bd5\u6211\u8fd8\u53bbUSACO\u4e86\u4e00\u4e0b\u3002\u3002\u597d\u4e45\u6ca1\u53bb\u4e86\u3002\u6709\u70b9\u6000\u5ff5\u997f\u3002\u3002Code\uff1a \/* PROG: theme LANG: C++ ID: Tom Chen*\/#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1;typedef unsigned int uint;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;const int maxn=20000,seed[]={131,1331,10007,133331},size=17771;int A[maxn],n,Len;struct Hash{ struct node { node*next; uint h[4]; int Max,Min; void Renew(int x) { Max=max(Max,x); Min=min(Min,x); } bool […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/158"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=158"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/158\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=158"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=158"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=158"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}