{"id":238,"date":"2010-05-02T21:48:00","date_gmt":"2010-05-02T13:48:00","guid":{"rendered":"http:\/\/localhost\/?p=238"},"modified":"2010-05-02T21:48:00","modified_gmt":"2010-05-02T13:48:00","slug":"sgu_232","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=238","title":{"rendered":"SGU 232"},"content":{"rendered":"

acm.sgu.ru\/problem.php<\/a>
\u7b97\u6cd5\u4e0d\u96be\u60f3\u3002\u3002\u4f46\u56e0\u4e3a\u5404\u79cd\u5404\u6837\u7684SB\u539f\u56e0WA\u4e86N\u6b21\u3002\u3002\u4e3b\u8981\u662f\u6211\u662fSB\u3002\u3002
\u5f88\u663e\u7136\u8bbed=(N,K),\u90a3\u4e48\u6309\u9898\u76ee\u7684\u8bf4\u6cd5\u4e00\u5171\u6709d\u7c7b\u3002\u3002\u6bcf\u7c7b\u957f\u5ea6\u90fd\u662fN\/d\u3002\u3002\u90a3\u4e48\u53ea\u8981\u6c42\u51fa\u6bcf\u7c7b\u7684\u6700\u5927\u503c\u7136\u540e\u6bd4\u8f83\u4e00\u4e0b\u5c31\u53ef\u4ee5\u77e5\u9053\u5168\u90e8\u7684\u6700\u5927\u503c\u4e86\uff0c\u800c\u6bcf\u7c7b\u4e2d\u90a3\u4e2a\u5f88\u663e\u7136\u662f\u4e2a\u6700\u5927\u8868\u793a\u6cd5\u7684\u7ecf\u5178\u95ee\u9898\u3002\u3002\u6240\u4ee5\u5c31OK\u4e86\u3002\u3002\u4f46\u662fK\u592a\u6253\u4e86\u6240\u4ee5\u8981\u7528long long\u8fd9\u73a9\u610f\u641e\u7684\u6211\u7d2f\u6b7b\u3002\u3002\u6655\u554a\uff01
\u6211\u51b3\u5b9a\u4e86\u3002\u3002\u4ee5\u540e\u6211\u4e0d\u8bba\u4ec0\u4e48\u53d8\u91cf\u90fd\u7528long long\u3002\u3002TMD\u8001\u5b50\u4e0d\u8981\u6548\u7387\u4e86\u3002\u3002
Code\uff1a
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=150000+1;
using namespace std;
int A[maxn],n;
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int get(ll i){return A[i%n];}
int main()
{
\/\/freopen("in","r",stdin);
char c;int k,d,l;cin>>n>>k;k%=n;d=gcd(k,n),l=n\/d;
scanf("n");rep(i,n)scanf("%c",&c),A[i]=c-‘0’;
int m=-1;
rep(a,d)
{
int i=0,j=1;ll t=0;
while(i<l&&j<l&&t<l)
{
int A=get(a+(i+t)*k),B=get(a+(j+t)*k);
if(A==B)t++;
else
{
if(A<B){i+=t+1;t=0;}
else{j+=t+1;t=0;}
if(i==j)j++;
}
}
t=a+min(i,j)*ll(k);t%=n;bool c;
if(m<0)c=true;
else rep(i,l)
{
int A=get(t+ll(i)*k),B=get(m+ll(i)*k);
if(A<B){c=false;break;}
if(A>B){c=true;break;}
}
if(c)m=t;
}
rep(i,n)printf("%d",get(m+ll(i)*k));
printf("n");
} <\/p>\n","protected":false},"excerpt":{"rendered":"

acm.sgu.ru\/problem.php\u7b97\u6cd5\u4e0d\u96be\u60f3\u3002\u3002\u4f46\u56e0\u4e3a\u5404\u79cd\u5404\u6837\u7684SB\u539f\u56e0WA\u4e86N\u6b21\u3002\u3002\u4e3b\u8981\u662f\u6211\u662fSB\u3002\u3002\u5f88\u663e\u7136\u8bbed=(N,K),\u90a3\u4e48\u6309\u9898\u76ee\u7684\u8bf4\u6cd5\u4e00\u5171\u6709d\u7c7b\u3002\u3002\u6bcf\u7c7b\u957f\u5ea6\u90fd\u662fN\/d\u3002\u3002\u90a3\u4e48\u53ea\u8981\u6c42\u51fa\u6bcf\u7c7b\u7684\u6700\u5927\u503c\u7136\u540e\u6bd4\u8f83\u4e00\u4e0b\u5c31\u53ef\u4ee5\u77e5\u9053\u5168\u90e8\u7684\u6700\u5927\u503c\u4e86\uff0c\u800c\u6bcf\u7c7b\u4e2d\u90a3\u4e2a\u5f88\u663e\u7136\u662f\u4e2a\u6700\u5927\u8868\u793a\u6cd5\u7684\u7ecf\u5178\u95ee\u9898\u3002\u3002\u6240\u4ee5\u5c31OK\u4e86\u3002\u3002\u4f46\u662fK\u592a\u6253\u4e86\u6240\u4ee5\u8981\u7528long long\u8fd9\u73a9\u610f\u641e\u7684\u6211\u7d2f\u6b7b\u3002\u3002\u6655\u554a\uff01\u6211\u51b3\u5b9a\u4e86\u3002\u3002\u4ee5\u540e\u6211\u4e0d\u8bba\u4ec0\u4e48\u53d8\u91cf\u90fd\u7528long long\u3002\u3002TMD\u8001\u5b50\u4e0d\u8981\u6548\u7387\u4e86\u3002\u3002Code\uff1a#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backconst int inf=~0U>>1,maxn=150000+1;using namespace std;int A[maxn],n;typedef long long ll;int gcd(int a,int b){return b?gcd(b,a%b):a;}int get(ll i){return A[i%n];}int main(){ \/\/freopen("in","r",stdin); char c;int k,d,l;cin>>n>>k;k%=n;d=gcd(k,n),l=n\/d; scanf("n");rep(i,n)scanf("%c",&c),A[i]=c-‘0’; int m=-1; rep(a,d) { int i=0,j=1;ll t=0; while(i<l&&j<l&&t<l) { int A=get(a+(i+t)*k),B=get(a+(j+t)*k); if(A==B)t++; else { if(A<B){i+=t+1;t=0;} else{j+=t+1;t=0;} if(i==j)j++; } } […]<\/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\/238"}],"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=238"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/238\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=238"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=238"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=238"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}