{"id":56,"date":"2009-12-26T12:40:00","date_gmt":"2009-12-26T04:40:00","guid":{"rendered":"http:\/\/localhost\/?p=56"},"modified":"2009-12-26T12:40:00","modified_gmt":"2009-12-26T04:40:00","slug":"pku_2008_individual_practice_1_2","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=56","title":{"rendered":"PKU 2008 Individual Practice 1 (2)"},"content":{"rendered":"\n

3615 Problem D<\/strong> Cow Hurdles
<\/a><\/p>\n<\/p>\n

\u5927\u610f\uff1a<\/p>\n

N\uff081<=300\uff09\u4e2a\u9876\u70b9\u7684\u56fe\uff0c\u6709T\uff08<=40000\uff09\u4e2a\u8be2\u95ee\uff0c<\/p>\n

\u6bcf\u6b21\u8be2\u95ee\u4eces\u5230e\u7684\u6240\u6709\u8def\u5f84\u4e2d\uff0c\u6700\u5927\u8fb9\u6700\u5c0f\u662f\u591a\u5c11\u3002\u3002<\/p>\n

\u5206\u6790\uff1a<\/p>\n

\u5f88\u660e\u663eN\u5f88\u5c0fT\u5f88\u5927\u66b4\u529b\u4e0d\u53ef\u884c\u3002\u3002<\/p>\n

\u4e8e\u662f\u60f3\u5230floyd\u3002\u3002\u53d1\u73b0\u6269\u5c55\u4e00\u4e0b\u6ca1\u6709\u95ee\u9898\uff0c\u4e0d\u8fc7\u662f\u6539\u6210\u4e86\u3002\u3002<\/p>\n

D[i,j]=min(D[i,j],max(D[i,k],D[k,j]) );\u800c\u5df2<\/p>\n

\u542f\u793a\uff1a<\/p>\n

\u5f88\u591a\u65f6\u5019floyd\u662f\u5f88\u6709\u7528\u7684\u3002\u3002<\/p>\n

Code\uff1a<\/p>\n<\/p>\n

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=300,inf=~0U>>1;
int d[maxn][maxn];
int n,m,ti;
int main()
{
freopen("in","r",stdin);
cin>>n>>m>>ti;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=inf;
int s,t,c;
while(m–)
{
scanf("%d %d %d",&s,&t,&c);s–;t–;
d[s][t]=min(d[s][t],c);
}
for(int k=n-1;k>=0;k–)
for(int i=n-1;i>=0;i–)if(i!=k&&d[i][k]!=inf)
for(int j=n-1;j>=0;j–)
d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
while(ti–)
{
scanf("%d %d",&s,&t);s–;t–;
printf<\/a>("%dn",(d[s][t]==inf?-1:d[s][t]));
}
}<\/p>\n

3616 Problem E<\/strong> Milking Time<\/a><\/p>\n

\u5927\u610f\uff1aM\u4e2a\u533a\u95f4\uff0c\u6bcf\u4e2a\u6709\u4e2a\u6548\u7387\u503c\uff0c\u53d6\u4e00\u4e9b\u533a\u95f4\uff0c\u8ba9\u6240\u6709\u533a\u95f4\u4e0d\u91cd\u53e0\u5e76\u524d\u76f8\u90bb\u7684\u4e24\u4e2a\u4e2d\u7a7a\u5f00R\u683c\u4ee5\u4e0a\u3002\u3002<\/p>\n

\u5206\u6790\uff1a\u8bbeP[n]\u4e3a\u6700\u540e\u4e00\u4e2a\u533a\u95f4\u5728n\u7ed3\u675f\u65f6\u6700\u5927\u6548\u7387\u548c\uff0c\u5219P[n]=max(P[k])(k<=n-R)\u3002\u3002<\/p>\n

\u90a3\u4e48\u7528\u6570\u72b6\u6570\u7ec4\u7ef4\u62a4\u4e00\u4e0b\u5c31OK\u4e86\u3002\u3002<\/p>\n

\u542f\u793a\uff1a<\/p>\n

\u533a\u95f4\u95ee\u9898\u5982\u679c\u957f\u5ea6\u4e0d\u662f\u592a\u5927\u7684\u5316\u9b3c\u624d\u79bb\u6563\u5316\u3002\u3002\u3002<\/p>\n

Code\uff1a<\/p>\n

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#define low(x) (x&(-x))
#define Renew(x,c) x=max(x,c)
using namespace std;
typedef pair<int,int> pi;
typedef pair<pi,int> inter;
const int maxn=1000000+100,maxm=1000+100,inf=~0U>>2;
int N,M,R,A[maxn];
int Max(int l)
{
int ans=0;
for(;l>0;l-=low(l))
Renew(ans,A[l]);
return ans;
}
void Change(int l,int d)
{
for(;l<=N;l+=low(l))
Renew(A[l],d);
}
inter I[maxm];
void init()
{
cin>>N>>M>>R;N++;
for(int i=1;i<=N;i++) A[i]=-inf;
int s,t,e;
for(int i=0;i<M;i++)
{
scanf("%d %d %d",&s,&t,&e);
I[i]=inter(pi(s,t),e);
}
sort(I,I+M);
}
void solve()
{
int ans=-inf,get;
for(inter*i=I;i!=I+M;i++)
{
get=Max(i->first.first-R);
get+=i->second;
Change(i->first.second,get);
}
ans=Max(N);
cout<<ans<<endl;
}
int main()
{
init();
solve();
}<\/p>\n

3617 Problem F<\/strong> Best Cow Line<\/a><\/p>\n

\u5927\u610f\uff1a<\/p>\n

\u957f\u5ea6\u4e3aN\u7684\u4e00\u4e32\u5b57\u7b26\uff0c\u6bcf\u6b21\u4ece\u4e24\u7aef\u53d6\u4e00\u4e2a\uff0c\u653e\u5165\u65b0\u7684\u5b57\u7b26\u4e32\u5c3e\u90e8\uff0c\u90a3\u4e48N\u6b21\u540e\u5b57\u7b26\u4e32\u5e8f\u6700\u5c0f\u7684\u5b57\u7b26\u4e32\u662f\u4ec0\u4e48\uff1f<\/p>\n

\u5206\u6790\uff1a<\/p>\n

\u5982\u679c\u4e24\u7aef\u4e0d\u4e00\u6837\u7684\u8bdd\u5c31\u53d6\u5c0f\u70b9\u7684\u3002\u3002\u5982\u679c\u4e00\u6837\u7684\u8bdd\u53ef\u4ee5\u5ffd\u7565\u770b\u518d\u91cc\u9762\u4e00\u4e2a\u4e48\uff1f<\/p>\n

\u4e0d\u662f\u5f88\u6e05\u695a\u4e3a\u4ec0\u4e48\u3002\u3002\u4e0d\u8fc7A\u6389\u4e86\u3002\u3002\u5c31\u662f\u8bf4\u5982\u679c\u5b57\u7b26\u4e32\u6b63\u8fc7\u6765\u770b\u6bd4\u8f83\u5c0f\uff0c\u5c31\u9009\u5de6\u8fb9\u7684\uff0c\u5982\u679c\u5012\u8fc7\u6765\u770b\u6bd4\u8f83\u5c0f\uff0c\u5c31\u9009\u53f3\u8fb9\u7684\u3002\u3002<\/p>\n

\u542f\u793a\uff1a<\/p>\n

\u76f4\u89c9\u963f\u3002\u3002\u4e0d\u8bc1\u660e\u3002\u3002<\/p>\n

Code\uff1a<\/p>\n

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<string>
using namespace std;
typedef string::iterator it;
typedef string::reverse_iterator rit;
const int maxn=2000;
int n,limit=5000000;
string a,ans;
bool cmp(it a,it b,rit c,rit d)
{
for(;a!=b;a++,c++)
{
if(*a<*c) return true;
if(*a>*c) return false;
}
return false;
}
int main()
{
scanf("%d",&n);char c;
for(int i=0;i<n;i++)
scanf("n%c",&c),a+=c;
it l=a.begin(),r=a.end();
rit rl=a.rbegin(),rr=a.rend();
while(l!=r)
{
if(cmp(l,r,rl,rr))
{
ans+=*l;
l++;rr–;
}
else
{
r–;rl++;
ans+=*r;
}
}
int now=0;
for(int i=0;i<n;i++)
{
now++;
printf<\/a>("%c",ans[i]);
if(now==80) printf<\/a>("n"),now=0;
}
if(now) printf<\/a>("n");
}<\/p>\n

3618 Problem G<\/strong> Exploration<\/a><\/p>\n

\u6c34\u9898\u3002\u3002\u4e0d\u5206\u6790\u3002\u3002<\/p>\n

Code\uff1a<\/p>\n

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<string>
using namespace std;
const int maxn=50000;
typedef pair<int,int> pi;
inline int abs(int x){return x>0?x:-x;}
int t,n,x;
pi X[maxn];
int main()
{
cin>>t>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
X[i]=pi(abs(x),x);
}
sort(X,X+n);int last=0;
for(int i=0;i<n;i++)
{
t-=abs(last-X[i].second);
if(t<0){cout<<i<<endl;return 0;}
last=X[i].second;
}
cout<<n<<endl;
}<\/p>\n

3619 Problem H<\/strong> Speed Reading<\/a><\/p>\n

\u6c34\u9898\u3002\u3002\u76f4\u63a5\u6570\u5b66\u8ba1\u7b97\u3002\u3002<\/p>\n

Code\uff1a<\/p>\n

#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
using namespace std;
const int maxk=1000;
int n,k;
int time(int s,int t,int r)
{
int p=n\/(s*t),ans;
if(p*s*t==n)
return (p-1)*(t+r)+t;
ans=p*(t+r);
int e=n-p*s*t;
ans+=((e-1)\/s)+1;
return ans;
}
int main()
{
cin>>n>>k;
int s,t,r;
while(k–)
{
cin>>s>>t>>r;
cout<<time(s,t,r)<<endl;
}
}<\/p>\n

3620 Problem I<\/strong> Avoid The Lakes<\/a><\/p>\n

\u4e00\u4e2a\u7f51\u683c\u3002\u3002\u6c42\u6700\u5927\u7684\u8fde\u7eed\u7a7a\u683c\u5757\u7684\u5927\u5c0f<\/p>\n

\u76f4\u63a5DFS\u3002\u3002\u3002<\/p>\n

Code\uff1a<\/p>\n

#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
#define Renew(x,c) x=max(x,c)
using namespace std;
const int maxn=100+10;
const int di[]={-1,0,1,0},dj[]={0,1,0,-1};
bool map[maxn][maxn]={0};
int n,m,k;
int dfs(int i,int j)
{
map[i][j]=false;int ans=1;
for(int ii,jj,d=0;d<4;d++)
{
ii=i+di[d];jj=j+dj[d];
if(map[ii][jj])
ans+=dfs(ii,jj);
}
return ans;
}
int main()
{
freopen("in","r",stdin);
cin>>n>>m>>k;int s,t;
while(k–)
{
cin>>s>>t;
map[s][t]=true;
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j])
Renew(ans,dfs(i,j));
cout<<ans<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"

3615 Problem D Cow Hurdles \u5927\u610f\uff1a N\uff081<=300\uff09\u4e2a\u9876\u70b9\u7684\u56fe\uff0c\u6709T\uff08<=40000\uff09\u4e2a\u8be2\u95ee\uff0c \u6bcf\u6b21\u8be2\u95ee\u4eces\u5230e\u7684\u6240\u6709\u8def\u5f84\u4e2d\uff0c\u6700\u5927\u8fb9\u6700\u5c0f\u662f\u591a\u5c11\u3002\u3002 \u5206\u6790\uff1a \u5f88\u660e\u663eN\u5f88\u5c0fT\u5f88\u5927\u66b4\u529b\u4e0d\u53ef\u884c\u3002\u3002 \u4e8e\u662f\u60f3\u5230floyd\u3002\u3002\u53d1\u73b0\u6269\u5c55\u4e00\u4e0b\u6ca1\u6709\u95ee\u9898\uff0c\u4e0d\u8fc7\u662f\u6539\u6210\u4e86\u3002\u3002 D[i,j]=min(D[i,j],max(D[i,k],D[k,j]) );\u800c\u5df2 \u542f\u793a\uff1a \u5f88\u591a\u65f6\u5019floyd\u662f\u5f88\u6709\u7528\u7684\u3002\u3002 Code\uff1a #include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn=300,inf=~0U>>1;int d[maxn][maxn];int n,m,ti;int main(){ freopen("in","r",stdin); cin>>n>>m>>ti; for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]=inf; int s,t,c; while(m–) { scanf("%d %d %d",&s,&t,&c);s–;t–; d[s][t]=min(d[s][t],c); } for(int k=n-1;k>=0;k–) for(int i=n-1;i>=0;i–)if(i!=k&&d[i][k]!=inf) for(int j=n-1;j>=0;j–) d[i][j]=min(d[i][j],max(d[i][k],d[k][j])); while(ti–) { scanf("%d %d",&s,&t);s–;t–; printf("%dn",(d[s][t]==inf?-1:d[s][t])); }} 3616 Problem […]<\/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\/56"}],"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=56"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/56\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=56"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=56"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=56"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}