PKU 2008 Individual Practice 1 (1)

  3612 Problem A Telephone Wire   3613 Problem B Cow Relays   3614 Problem C Sunscreen   3615 Problem D Cow Hurdles   3616 Problem E Milking Time   3617 Problem F Best Cow Line   3618 Problem G Exploration   3619 Problem H Speed Reading   3620 Problem I Avoid The Lakes
这个什么Individual Practice的感觉还不错,确实满可以prrctice的。。
3612 Problem A Telephone Wire
大意:
一排N(1<N<100000)跟电线杆,每根的高Hi<=100,相邻两个接线的钱是他们高度差*C,
为了省钱,可以把一些电线杆变高,一根电线杆变高X要花X^2的钱。。求最少花多少钱。。
分析:
设DP[i][H]为1..i第i个长为H时的最小价格。。
那么DP[i][H](H>=Hi)=(H-Hi)^2+min(DP[i-1][k]+C*abs(k-H))
(k<=100)
是O(N*maxH^2)的。。必超。。
优化一下,DP[i][H]=(H-Hi)^2+
min( min(DP[i-1][k]+C*k-C*H)(k>=H),min(DP[i-1][k]+C*H-C*k)(k<H) )
故设A[i]=min(DP[i-1][k]-C*k)(k<i)
B[i]=min(DP[i-1]+C*k)(k>=i)
A和B可以线性推出来。。
从而复杂度就降到。。
O(N*maxH)了。。
启示:
有abs这种分段函数的时候可以分队考虑最优值。。。
Code:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Renew(x,c) x=min(x,c)
using namespace std;
const int maxh=100,maxn=100000,inf=~0U>>2;
int n,c,x,best[2][maxh+1],now,old,low[maxh+2],up[maxh+2];
inline int abs(int x){return x<0?-x:x;}
int main()
{
freopen("in","r",stdin);
cin>>n>>c>>x;
for(int i=1;i<x;i++)
best[0][i]=inf;
for(int i=x;i<=maxh;i++)
best[0][i]=(x-i)*(x-i);
for(int t=1;t<n;t++)
{
now=t%2;old=1-now;
int get;scanf("%d",&x);
for(int i=1;i<=maxh;i++) best[now][i]=inf;
memset(low,127,sizeof(low));
memset(up,127,sizeof(up));
for(int i=1;i<=maxh;i++)
low[i]=min(low[i-1],best[old][i]-c*i);
for(int i=maxh;i>=1;i–)
up[i]=min(up[i+1],best[old][i]+c*i);
for(int i=x;i<=maxh;i++)
{
best[now][i]=(i-x)*(i-x);
best[now][i]+=min(low[i]+c*i,up[i]-c*i);
}
}
int ans=inf;
for(int i=1;i<=maxh;i++) Renew(ans,best[now][i]);
cout<<ans<<endl;
}3613 Problem B Cow Relays
大意:
一个图,边数小于100,求S到E的经过N条边的最短路。。
分析:
这是很经典的矩阵乘法的题目,
大家都知道距离矩阵自乘N次就是长度为N的最短路,那么只要用二分算矩阵的N次方就OK了。。
启示:
矩阵乘法非常NB阿。。
Code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
#include<stack>
#define Renew(x,c) x=min(x,c)
#define x first
#define y second
#define ss x.x
#define tt x.y
#define cc y
using namespace std;
const int maxt=1000+10,maxn=100+1,inf=~0U>>1;
typedef long long Board[maxn][maxn];
typedef pair<int,int> pi;
typedef pair<pi,int> edge;
struct Matrix
{
    Board M;int n;
    Matrix(int n):n(n)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                M[i][j]=inf;
    }
    Matrix operator*(const Matrix&o)
    {
        Matrix ans(n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    Renew(ans.M[i][j],M[i][k]+o.M[k][j]);
        return ans;
    }
    void operator=(const Matrix&o)
    {
        memmove(M,o.M,sizeof(M));
        n=o.n;
    }
}*dist;
int Map[maxt]={0},N,s,t,cnt;
inline int get(int a)
{
    if(Map[a]==-1) Map[a]=cnt++;
    return Map[a];
}
void init()
{
    for(int i=1;i<maxt;i++)
        Map[i]=-1;
    int m;
    cin>>N>>m>>s>>t;cnt=0;
    stack<edge> S;
    while(m--)
    {
        int a,b,c;cin>>c>>a>>b;
        a=get(a);b=get(b);
        S.push(edge(pi(a,b),c));
    }
    dist=new Matrix(cnt);
    while(S.size())
    {
        edge i=S.top();S.pop();
        dist->M[i.ss][i.tt]=dist->M[i.tt][i.ss]=i.cc;
    }
    s=get(s);t=get(t);
}
Matrix Power(int n)
{ 
    if(n==1){return *dist;}
    Matrix ans=Power(n/2);
    ans=ans*ans;
    if(n%2==1)
        ans=ans*(*dist);
    return ans;
}
void solve()
{
    Matrix ans=Power(N);
    cout<<ans.M[s][t]<<endl;
}
int main()
{
    init();
    solve();
}

3614 Problem C Sunscreen
大意:改的XX点算了。。
每个男生的帅气值在1到1000之间,,
N个女生(N<=2500)第i个喜欢帅气值Lowi到Upi之间的男生。。
M种男生(M<=2500)第i个有Numi人,帅气值为Handsomei。。
这时男生得知WJMZBMR来了,为了不让帅帅的WJMZBMR(帅气值>2^128)
抢走女生的心。。他们马上开始行动了。。
问最多有多少个女生可以有男朋友呢?(不包括WJMZBMR。。。)
分析:
把男生按handsomei排序。。
一个个扫描过去,每个男生尽量匹配Upi小的女生(太小的先踢掉)。。
用一个heap维护就可以了。。
启示:
很多时候想贪心也是有方法的。。最重要的是降维和替代法。。
Code:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
#include<queue>
using namespace std;
typedef pair<int,int> pi;
int Cover[1000+1]={0},C;
pi Cs[2500],Bs[2500];
priority_queue<int> Q;
inline void ins(int x)
{ Q.push(-x); }
inline int top()
{ return -Q.top(); }
inline void pop()
{ Q.pop(); }
int main()
{
int L;cin>>C>>L;
for(int i=0;i<C;i++)
{
cin>>Cs[i].first>>Cs[i].second;
}
for(int i=0;i<L;i++)
{
cin>>Bs[i].first>>Bs[i].second;
}
sort(Cs,Cs+C);
sort(Bs,Bs+L);
pi*s=Cs;int ans=0;
for(pi*i=Bs;i!=Bs+L;i++)
{
while(s!=Cs+C&&s->first<=i->first)
ins(s->second),s++;
while(Q.size()&&top()<i->first)
pop();
while(i->second&&Q.size())
{
pop(),i->second–,ans++;
}
}
cout<<ans<<endl;
}

由于百度篇幅问题
只能开很多章了。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>