PKU 2008 Individual Practice 7 (1)

PKU 2008 Individual Practice 7
  3666 Problem A Making the Grade 大意。。就是用最小的代价把一群数变成单调的。。变化一个数的代价是变化的绝对值。。
首先很明确是可以离散的,就是说如果一个数不这N个数中,也没有必要把其他的数变成这个数。。
所以实际上有用的数只有N个。。设这些数为A1..N
那么设D[i][j]为1..i,第i个数为Aj让所有数递增的最小代价。。
那么D[i][j]=|Ai-Aj|+min(D[i-1][k])(1<=k<=j)
那么答案就是min(D[N][1..N])。。
实际上这是BOI的原题。。当时N<=100000,所以N^2只能见鬼去,
但这个N只<=2000。。可以过。。。
有一个用左偏树的NLogN的算法。。但是太麻烦了。。
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 Hotel
用一个线段树维护就OK了。。需要使用懒标记。。
Code:
#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("%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 Game of Lines 就是所有直线中不同斜率的个数。。直接set就可以了。。
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 Meteor Shower 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;
}

Page 2 of 212