{"id":61,"date":"2010-01-01T16:33:00","date_gmt":"2010-01-01T08:33:00","guid":{"rendered":"http:\/\/localhost\/?p=61"},"modified":"2010-01-01T16:33:00","modified_gmt":"2010-01-01T08:33:00","slug":"pku_2008_individual_practice_7_1","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=61","title":{"rendered":"PKU 2008 Individual Practice 7 (1)"},"content":{"rendered":"

PKU 2008 Individual Practice 7
<\/strong>   3666 Problem A<\/strong> Making the Grade<\/a> \u5927\u610f\u3002\u3002\u5c31\u662f\u7528\u6700\u5c0f\u7684\u4ee3\u4ef7\u628a\u4e00\u7fa4\u6570\u53d8\u6210\u5355\u8c03\u7684\u3002\u3002\u53d8\u5316\u4e00\u4e2a\u6570\u7684\u4ee3\u4ef7\u662f\u53d8\u5316\u7684\u7edd\u5bf9\u503c\u3002\u3002
\u9996\u5148\u5f88\u660e\u786e\u662f\u53ef\u4ee5\u79bb\u6563\u7684\uff0c\u5c31\u662f\u8bf4\u5982\u679c\u4e00\u4e2a\u6570\u4e0d\u8fd9N\u4e2a\u6570\u4e2d\uff0c\u4e5f\u6ca1\u6709\u5fc5\u8981\u628a\u5176\u4ed6\u7684\u6570\u53d8\u6210\u8fd9\u4e2a\u6570\u3002\u3002
\u6240\u4ee5\u5b9e\u9645\u4e0a\u6709\u7528\u7684\u6570\u53ea\u6709N\u4e2a\u3002\u3002\u8bbe\u8fd9\u4e9b\u6570\u4e3aA1..N
\u90a3\u4e48\u8bbeD[i][j]\u4e3a1..i,\u7b2ci\u4e2a\u6570\u4e3aAj\u8ba9\u6240\u6709\u6570\u9012\u589e\u7684\u6700\u5c0f\u4ee3\u4ef7\u3002\u3002
\u90a3\u4e48D[i][j]=|Ai-Aj|+min(D[i-1][k])(1<=k<=j)
\u90a3\u4e48\u7b54\u6848\u5c31\u662fmin(D[N][1..N])\u3002\u3002
\u5b9e\u9645\u4e0a\u8fd9\u662fBOI\u7684\u539f\u9898\u3002\u3002\u5f53\u65f6N<=100000\uff0c\u6240\u4ee5N^2\u53ea\u80fd\u89c1\u9b3c\u53bb\uff0c
\u4f46\u8fd9\u4e2aN\u53ea<=2000\u3002\u3002\u53ef\u4ee5\u8fc7\u3002\u3002\u3002
\u6709\u4e00\u4e2a\u7528\u5de6\u504f\u6811\u7684NLogN\u7684\u7b97\u6cd5\u3002\u3002\u4f46\u662f\u592a\u9ebb\u70e6\u4e86\u3002\u3002
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<string>
#include<cmath>
using namespace std;
const int maxn=2010,inf=~0U>>1;
int A[maxn],B[maxn],DP[maxn],n;
inline int cost(int i,int j){return i>j?(i-j):(j-i);}
int solve()
{
for(int i=0;i<n;i++)
DP[i]=cost(B[i],A[0]);
int tmp;
for(int i=1;i<n;i++)
{
tmp=inf;
for(int j=0;j<n;j++)
{
tmp=min(tmp,DP[j]);
DP[j]=tmp+cost(B[j],A[i]);
}
}
return *min_element(DP,DP+n);
}
int main()
{
freopen("in","r",stdin);
cin>>n;for(int i=0;i<n;i++) scanf("%d",A+i),B[i]=A[i];
sort(B,B+n);int ans=solve();
for(int l=0,r=n-1;l<r;l++,r–)
swap(A[l],A[r]);
ans=min(ans,solve());
cout<<ans<<endl;
}   3667 Problem B<\/strong> Hotel<\/a>
\u7528\u4e00\u4e2a\u7ebf\u6bb5\u6811\u7ef4\u62a4\u5c31OK\u4e86\u3002\u3002\u9700\u8981\u4f7f\u7528\u61d2\u6807\u8bb0\u3002\u3002
Code\uff1a
#include<iostream>
 
#include<algorithm>
 
#include<cstring>
 
#include<utility>
 
#include<cstdio>
 
#define Renew(x,c) x=max(x,c)
 
using namespace std;
 
struct Tree
 
{
 
bool sign,e;
 
int max,Lmax,Rmax,size,l,r;
 
Tree*Lch,*Rch;
 
}A[150000],*now,*root;
 
Tree* NewNode(int l,int r)
 
{
 
now->sign=false;
 
now->max=now->Lmax=now->Rmax=r-l+1;
 
now->size=r-l+1;
 
now->l=l;
 
now->r=r;
 
return now++;
 
}
 
void Update(Tree*Fa)
 
{
 
if(Fa->Lch->max==Fa->Lch->size)
 
Fa->Lmax=Fa->Lch->size+Fa->Rch->Lmax;
 
else
 
Fa->Lmax=Fa->Lch->Lmax;
 
if(Fa->Rch->max==Fa->Rch->size)
 
Fa->Rmax=Fa->Rch->size+Fa->Lch->Rmax;
 
else
 
Fa->Rmax=Fa->Rch->Rmax;
 
Fa->max=Fa->Lch->Rmax+Fa->Rch->Lmax;
 
Renew(Fa->max,max(Fa->Lch->max,Fa->Rch->max));
 
}
 
Tree* Build(int l,int r)
 
{
 
if(l==r)return NewNode(l,r);
 
int mid=(l+r)\/2;
 
Tree* T=NewNode(l,r);
 
T->Lch=Build(l,mid);
 
T->Rch=Build(mid+1,r);
 
return T;
 
}
 
void Set(Tree*T,bool e)
 
{
 
T->sign=true;
 
T->e=e;
 
T->Lmax=T->Rmax=T->max=e?T->size:0;
 
}
 
void Push(Tree*T)
 
{
 
if(T->sign)
 
{
 
if(T->size>1)
 
{
 
Set(T->Lch,T->e);
 
Set(T->Rch,T->e);
 
}
 
T->sign=false;
 
}
 
}
 
int l,r;
 
void set(Tree*T,bool e)
 
{
 
if(T->l>=l and T->r<=r)
 
{
 
Set(T,e);
 
return;
 
}
 
int mid=T->Lch->r;
 
Push(T);
 
if(mid>=l)
 
set(T->Lch,e);
 
if(r>mid)
 
set(T->Rch,e);
 
Update(T);
 
}
 
int len;
 
int Put(Tree*T)
 
{
 
Push(T);
 
if(T->Lch->max>=len)
 
return Put(T->Lch);
 
if(T->Lch->Rmax+T->Rch->Lmax>=len)
 
return T->Lch->r-T->Lch->Rmax+1;
 
if(T->Rch->max>=len)
 
return Put(T->Rch);
 
return 0;
 
}
 
void In(int D)
 
{
 
len=D;
 
int a=Put(root);
 
printf<\/a>("%dn",a);
 
if(a)
 
l=a,r=a+D-1,set(root,false);
 
}
 
void Out(int l,int r)
 
{
 
::l=l;::r=r;
 
set(root,true);
 
}
 
int n,m;
 
void init()
 
{
 
cin>>n>>m;
 
now=A;
 
root=Build(1,n);
 
}
 
void work()
 
{
 
int k,l,d;
 
while(m–)
 
{
 
scanf("%d",&k);
 
if(k==1)
 
scanf("%d",&d),In(d);
 
else
 
scanf("%d %d",&l,&d),Out(l,l+d-1);
 
}
 
}
 
int main()
 
{
 
init();
 
work();
 
}   3668 Problem C<\/strong> Game of Lines<\/a> \u5c31\u662f\u6240\u6709\u76f4\u7ebf\u4e2d\u4e0d\u540c\u659c\u7387\u7684\u4e2a\u6570\u3002\u3002\u76f4\u63a5set\u5c31\u53ef\u4ee5\u4e86\u3002\u3002
Code:
#include<iostream>
#include<cstdio>
#include<utility>
#include<set>
using namespace std;
typedef pair<int,int> pi;
int n;
pi A[300];
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
pi operator-(pi x,pi y)
{
return pi(x.first-y.first,x.second-y.second);
}
int main()
{
freopen("in","r",stdin);
cin>>n;
for(int i=0;i<n;i++)
cin>>A[i].first>>A[i].second;
set<pi> S;pi get;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
get=A[j]-A[i];
int d=gcd(get.first,get.second);
get.first\/=d;
get.second\/=d;
S.insert(get);
}
cout<<S.size()<<endl;
}   3669 Problem D<\/strong> Meteor Shower<\/a> BFS…
Code:
#include<iostream>
#include<cstdio>
#include<utility>
#include<queue>
#define Renew(x,c) x=min(x,c)
using namespace std;
typedef pair<int,int> pi;
const int maxn=310,inf=~0U>>1;
int T[maxn][maxn],D[maxn][maxn];
queue<pi> Q;
inline bool inarea(int x,int y)
{return x>=0 and y>=0 and x<maxn and y<maxn;}
int main()
{
freopen("in","r",stdin);
int m,x,y,t;cin>>m;
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
T[i][j]=D[i][j]=inf;
const int di[]={-1,0,1,0},dj[]={0,1,0,-1};
while(m–)
{
scanf("%d %d %d",&x,&y,&t);
Renew(T[x][y],t);
for(int ii,jj,d=0;d<4;d++)
{
ii=x+di[d];jj=y+dj[d];
if(inarea(ii,jj))
Renew(T[ii][jj],t);
}
}
D[0][0]=0;Q.push(pi(0,0));int c;
while(Q.size())
{
pi t=Q.front();Q.pop();c=D[t.first][t.second];
if(T[t.first][t.second]==inf)
{
cout<<c<<endl;
return 0;
}
for(int ii,jj,d=0;d<4;d++)
{
ii=t.first+di[d];jj=t.second+dj[d];
if(inarea(ii,jj) and D[ii][jj]==inf and T[ii][jj]>c+1)
D[ii][jj]=c+1,Q.push(pi(ii,jj));
}
}
cout<<-1<<endl;
}<\/p>\n","protected":false},"excerpt":{"rendered":"

PKU 2008 Individual Practice 7   3666 Problem A Making the Grade \u5927\u610f\u3002\u3002\u5c31\u662f\u7528\u6700\u5c0f\u7684\u4ee3\u4ef7\u628a\u4e00\u7fa4\u6570\u53d8\u6210\u5355\u8c03\u7684\u3002\u3002\u53d8\u5316\u4e00\u4e2a\u6570\u7684\u4ee3\u4ef7\u662f\u53d8\u5316\u7684\u7edd\u5bf9\u503c\u3002\u3002\u9996\u5148\u5f88\u660e\u786e\u662f\u53ef\u4ee5\u79bb\u6563\u7684\uff0c\u5c31\u662f\u8bf4\u5982\u679c\u4e00\u4e2a\u6570\u4e0d\u8fd9N\u4e2a\u6570\u4e2d\uff0c\u4e5f\u6ca1\u6709\u5fc5\u8981\u628a\u5176\u4ed6\u7684\u6570\u53d8\u6210\u8fd9\u4e2a\u6570\u3002\u3002\u6240\u4ee5\u5b9e\u9645\u4e0a\u6709\u7528\u7684\u6570\u53ea\u6709N\u4e2a\u3002\u3002\u8bbe\u8fd9\u4e9b\u6570\u4e3aA1..N\u90a3\u4e48\u8bbeD[i][j]\u4e3a1..i,\u7b2ci\u4e2a\u6570\u4e3aAj\u8ba9\u6240\u6709\u6570\u9012\u589e\u7684\u6700\u5c0f\u4ee3\u4ef7\u3002\u3002\u90a3\u4e48D[i][j]=|Ai-Aj|+min(D[i-1][k])(1<=k<=j)\u90a3\u4e48\u7b54\u6848\u5c31\u662fmin(D[N][1..N])\u3002\u3002\u5b9e\u9645\u4e0a\u8fd9\u662fBOI\u7684\u539f\u9898\u3002\u3002\u5f53\u65f6N<=100000\uff0c\u6240\u4ee5N^2\u53ea\u80fd\u89c1\u9b3c\u53bb\uff0c\u4f46\u8fd9\u4e2aN\u53ea<=2000\u3002\u3002\u53ef\u4ee5\u8fc7\u3002\u3002\u3002\u6709\u4e00\u4e2a\u7528\u5de6\u504f\u6811\u7684NLogN\u7684\u7b97\u6cd5\u3002\u3002\u4f46\u662f\u592a\u9ebb\u70e6\u4e86\u3002\u3002Code:#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<utility>#include<cstdlib>#include<string>#include<cmath>using namespace std;const int maxn=2010,inf=~0U>>1;int A[maxn],B[maxn],DP[maxn],n;inline int cost(int i,int j){return i>j?(i-j):(j-i);}int solve(){ for(int i=0;i<n;i++) DP[i]=cost(B[i],A[0]); int tmp; for(int i=1;i<n;i++) { tmp=inf; for(int j=0;j<n;j++) { tmp=min(tmp,DP[j]); DP[j]=tmp+cost(B[j],A[i]); } } return *min_element(DP,DP+n);}int main(){ freopen("in","r",stdin); cin>>n;for(int i=0;i<n;i++) scanf("%d",A+i),B[i]=A[i]; sort(B,B+n);int ans=solve(); for(int l=0,r=n-1;l<r;l++,r–) swap(A[l],A[r]); ans=min(ans,solve()); cout<<ans<<endl;}   […]<\/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\/61"}],"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=61"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/61\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=61"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=61"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=61"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}