[Usaco2006 Dec]Milk Patterns<\/p>\n
Time Limit:5000MS Memory Limit:65536K
Total Submit:9 Accepted:6
Case Time Limit:1000MS<\/p>\n
Description <\/strong><\/p>\n \u519c\u592bJohn\u53d1\u73b0\u4ed6\u7684\u5976\u725b\u4ea7\u5976\u7684\u8d28\u91cf\u4e00\u76f4\u5728\u53d8\u52a8\u3002\u7ecf\u8fc7\u7ec6\u81f4\u7684\u8c03\u67e5\uff0c\u4ed6\u53d1\u73b0\uff1a\u867d\u7136\u4ed6\u4e0d\u80fd\u9884\u89c1\u660e\u5929 Input <\/strong><\/p>\n * Line 1: \u4e24\u4e2a\u6574\u6570 N,K\u3002 <\/p>\n * Lines 2..N+1: \u6bcf\u884c\u4e00\u4e2a\u6574\u6570\u8868\u793a\u5f53\u5929\u7684\u8d28\u91cf\u503c\u3002 <\/p>\n Output <\/strong><\/p>\n * Line 1: \u4e00\u4e2a\u6574\u6570\uff1aN\u5929\u4e2d\u6700\u957f\u7684\u51fa\u73b0\u4e86\u81f3\u5c11K\u6b21\u7684\u6a21\u5f0f\u7684\u957f\u5ea6 <\/p>\n <\/p>\n Sample Input <\/strong><\/p>\n 8 2 Sample Output <\/strong><\/p>\n 4<\/p>\n Source <\/strong><\/p>\n Gold<\/p>\n \u76f4\u63a5\u4e0aHash\u3002\u3002\u4e8c\u5206\u5224\u65ad\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u4ee3\u78010.7K\u56e7\u3002\u3002 #include <algorithm> [Usaco2006 Dec]Milk Patterns Time Limit:5000MS Memory Limit:65536KTotal Submit:9 Accepted:6 Case Time Limit:1000MS Description \u519c\u592bJohn\u53d1\u73b0\u4ed6\u7684\u5976\u725b\u4ea7\u5976\u7684\u8d28\u91cf\u4e00\u76f4\u5728\u53d8\u52a8\u3002\u7ecf\u8fc7\u7ec6\u81f4\u7684\u8c03\u67e5\uff0c\u4ed6\u53d1\u73b0\uff1a\u867d\u7136\u4ed6\u4e0d\u80fd\u9884\u89c1\u660e\u5929 \u4ea7\u5976\u7684\u8d28\u91cf\uff0c\u4f46\u8fde\u7eed\u7684\u82e5\u5e72\u5929\u7684\u8d28\u91cf\u6709\u5f88\u591a\u91cd\u53e0\u3002\u6211\u4eec\u79f0\u4e4b\u4e3a\u4e00\u4e2a\u201c\u6a21\u5f0f\u201d\u3002 John\u7684\u725b\u5976\u6309\u8d28\u91cf\u53ef\u4ee5\u88ab\u8d4b\u4e88\u4e00\u4e2a0\u52301000000\u4e4b\u95f4\u7684\u6570\u3002\u5e76\u4e14John\u8bb0\u5f55\u4e86N(1<=N<=20000)\u5929\u7684 \u725b\u5976\u8d28\u91cf\u503c\u3002\u4ed6\u60f3\u77e5\u9053\u6700\u957f\u7684\u51fa\u73b0\u4e86\u81f3\u5c11K(2<=K<=N)\u6b21\u7684\u6a21\u5f0f\u7684\u957f\u5ea6\u3002 \u6bd4\u59821 2 3 2 3 2 3 1 \u4e2d 2 3 2 3\u51fa\u73b0\u4e86\u4e24\u6b21\u3002\u5f53K=2\u65f6\uff0c\u8fd9\u4e2a\u957f\u5ea6\u4e3a4\u3002 Input * Line 1: \u4e24\u4e2a\u6574\u6570 N,K\u3002 * Lines 2..N+1: \u6bcf\u884c\u4e00\u4e2a\u6574\u6570\u8868\u793a\u5f53\u5929\u7684\u8d28\u91cf\u503c\u3002 Output * Line 1: \u4e00\u4e2a\u6574\u6570\uff1aN\u5929\u4e2d\u6700\u957f\u7684\u51fa\u73b0\u4e86\u81f3\u5c11K\u6b21\u7684\u6a21\u5f0f\u7684\u957f\u5ea6 Sample Input 8 212323231 Sample Output 4 Source Gold \u76f4\u63a5\u4e0aHash\u3002\u3002\u4e8c\u5206\u5224\u65ad\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u4ee3\u78010.7K\u56e7\u3002\u3002Code\uff1a […]<\/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\/216"}],"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=216"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/216\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=216"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=216"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=216"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u4ea7\u5976\u7684\u8d28\u91cf\uff0c\u4f46\u8fde\u7eed\u7684\u82e5\u5e72\u5929\u7684\u8d28\u91cf\u6709\u5f88\u591a\u91cd\u53e0\u3002\u6211\u4eec\u79f0\u4e4b\u4e3a\u4e00\u4e2a\u201c\u6a21\u5f0f\u201d\u3002
John\u7684\u725b\u5976\u6309\u8d28\u91cf\u53ef\u4ee5\u88ab\u8d4b\u4e88\u4e00\u4e2a0\u52301000000\u4e4b\u95f4\u7684\u6570\u3002\u5e76\u4e14John\u8bb0\u5f55\u4e86N(1<=N<=20000)\u5929\u7684
\u725b\u5976\u8d28\u91cf\u503c\u3002\u4ed6\u60f3\u77e5\u9053\u6700\u957f\u7684\u51fa\u73b0\u4e86\u81f3\u5c11K(2<=K<=N)\u6b21\u7684\u6a21\u5f0f\u7684\u957f\u5ea6\u3002
\u6bd4\u59821 2 3 2 3 2 3 1 \u4e2d 2 3 2 3\u51fa\u73b0\u4e86\u4e24\u6b21\u3002\u5f53K=2\u65f6\uff0c\u8fd9\u4e2a\u957f\u5ea6\u4e3a4\u3002 <\/p>\n
1
2
3
2
3
2
3
1<\/p>\n
Code\uff1a<\/p>\n
#include <cstdio>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
const int seed=1333331,maxn=20000;
using namespace std;
typedef unsigned long long ull;
ull P[maxn];
int n,k,A[maxn];
bool Check(int L)
{
ull ret=0;map<ull,int> M;
rep(i,L) ret*=seed,ret+=A[i];
M[ret]=1;
rep(i,n-L)
{
ret-=P[L-1]*A[i];ret*=seed;ret+=A[i+L];
int&x=M[ret];if(++x>=k)return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&k);rep(i,n)scanf("%d",A+i);
P[0]=1;rep(i,n-1)P[i+1]=P[i]*seed;
int l=0,r=n\/k+1;
while(l+1<r)
{
int m=(l+r)\/2;
if(Check(m)) l=m;
else r=m;
}
printf("%dn",l);
}<\/p>\n","protected":false},"excerpt":{"rendered":"