{"id":55,"date":"2009-12-26T12:19:00","date_gmt":"2009-12-26T04:19:00","guid":{"rendered":"http:\/\/localhost\/?p=55"},"modified":"2015-04-25T05:21:04","modified_gmt":"2015-04-25T05:21:04","slug":"pku_2008_individual_practice_1_1","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=55","title":{"rendered":"PKU 2008 Individual Practice 1 (1)"},"content":{"rendered":"

  3612 Problem A<\/strong> Telephone Wire<\/a>   3613 Problem B<\/strong> Cow Relays<\/a>   3614 Problem C<\/strong> Sunscreen<\/a>   3615 Problem D<\/strong> Cow Hurdles<\/a>   3616 Problem E<\/strong> Milking Time<\/a>   3617 Problem F<\/strong> Best Cow Line<\/a>   3618 Problem G<\/strong> Exploration<\/a>   3619 Problem H<\/strong> Speed Reading<\/a>   3620 Problem I<\/strong> Avoid The Lakes<\/a>
\u8fd9\u4e2a\u4ec0\u4e48Individual Practice\u7684\u611f\u89c9\u8fd8\u4e0d\u9519,\u786e\u5b9e\u6ee1\u53ef\u4ee5prrctice\u7684\u3002\u3002
3612 Problem A<\/strong> Telephone Wire<\/a>
\u5927\u610f\uff1a
\u4e00\u6392N(1<N<100000)\u8ddf\u7535\u7ebf\u6746,\u6bcf\u6839\u7684\u9ad8Hi<=100,\u76f8\u90bb\u4e24\u4e2a\u63a5\u7ebf\u7684\u94b1\u662f\u4ed6\u4eec\u9ad8\u5ea6\u5dee*C,
\u4e3a\u4e86\u7701\u94b1\uff0c\u53ef\u4ee5\u628a\u4e00\u4e9b\u7535\u7ebf\u6746\u53d8\u9ad8\uff0c\u4e00\u6839\u7535\u7ebf\u6746\u53d8\u9ad8X\u8981\u82b1X^2\u7684\u94b1\u3002\u3002\u6c42\u6700\u5c11\u82b1\u591a\u5c11\u94b1\u3002\u3002
\u5206\u6790\uff1a
\u8bbeDP[i][H]\u4e3a1..i\u7b2ci\u4e2a\u957f\u4e3aH\u65f6\u7684\u6700\u5c0f\u4ef7\u683c\u3002\u3002
\u90a3\u4e48DP[i][H](H>=Hi)=(H-Hi)^2+min(DP[i-1][k]+C*abs(k-H))
(k<=100)
\u662fO(N*maxH^2)\u7684\u3002\u3002\u5fc5\u8d85\u3002\u3002
\u4f18\u5316\u4e00\u4e0b\uff0cDP[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) )
\u6545\u8bbeA[i]=min(DP[i-1][k]-C*k)(k<i)
B[i]=min(DP[i-1]+C*k)(k>=i)
A\u548cB\u53ef\u4ee5\u7ebf\u6027\u63a8\u51fa\u6765\u3002\u3002
\u4ece\u800c\u590d\u6742\u5ea6\u5c31\u964d\u5230\u3002\u3002
O(N*maxH)\u4e86\u3002\u3002
\u542f\u793a\uff1a
\u6709abs\u8fd9\u79cd\u5206\u6bb5\u51fd\u6570\u7684\u65f6\u5019\u53ef\u4ee5\u5206\u961f\u8003\u8651\u6700\u4f18\u503c\u3002\u3002\u3002
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<\/strong> Cow Relays<\/a>
\u5927\u610f\uff1a
\u4e00\u4e2a\u56fe\uff0c\u8fb9\u6570\u5c0f\u4e8e100\uff0c\u6c42S\u5230E\u7684\u7ecf\u8fc7N\u6761\u8fb9\u7684\u6700\u77ed\u8def\u3002\u3002
\u5206\u6790\uff1a
\u8fd9\u662f\u5f88\u7ecf\u5178\u7684\u77e9\u9635\u4e58\u6cd5\u7684\u9898\u76ee\uff0c
\u5927\u5bb6\u90fd\u77e5\u9053\u8ddd\u79bb\u77e9\u9635\u81ea\u4e58N\u6b21\u5c31\u662f\u957f\u5ea6\u4e3aN\u7684\u6700\u77ed\u8def\uff0c\u90a3\u4e48\u53ea\u8981\u7528\u4e8c\u5206\u7b97\u77e9\u9635\u7684N\u6b21\u65b9\u5c31OK\u4e86\u3002\u3002
\u542f\u793a\uff1a
\u77e9\u9635\u4e58\u6cd5\u975e\u5e38NB\u963f\u3002\u3002
Code\uff1a<\/p>\n

\r\n#include<iostream>\r\n#include<algorithm>\r\n#include<cstring>\r\n#include<utility>\r\n#include<stack>\r\n#define Renew(x,c) x=min(x,c)\r\n#define x first\r\n#define y second\r\n#define ss x.x\r\n#define tt x.y\r\n#define cc y\r\nusing namespace std;\r\nconst int maxt=1000+10,maxn=100+1,inf=~0U>>1;\r\ntypedef long long Board[maxn][maxn];\r\ntypedef pair<int,int> pi;\r\ntypedef pair<pi,int> edge;\r\nstruct Matrix\r\n{\r\n    Board M;int n;\r\n    Matrix(int n):n(n)\r\n    {\r\n        for(int i=0;i<n;i++)\r\n            for(int j=0;j<n;j++)\r\n                M[i][j]=inf;\r\n    }\r\n    Matrix operator*(const Matrix&o)\r\n    {\r\n        Matrix ans(n);\r\n        for(int i=0;i<n;i++)\r\n            for(int j=0;j<n;j++)\r\n                for(int k=0;k<n;k++)\r\n                    Renew(ans.M[i][j],M[i][k]+o.M[k][j]);\r\n        return ans;\r\n    }\r\n    void operator=(const Matrix&o)\r\n    {\r\n        memmove(M,o.M,sizeof(M));\r\n        n=o.n;\r\n    }\r\n}*dist;\r\nint Map[maxt]={0},N,s,t,cnt;\r\ninline int get(int a)\r\n{\r\n    if(Map[a]==-1) Map[a]=cnt++;\r\n    return Map[a];\r\n}\r\nvoid init()\r\n{\r\n    for(int i=1;i<maxt;i++)\r\n        Map[i]=-1;\r\n    int m;\r\n    cin>>N>>m>>s>>t;cnt=0;\r\n    stack<edge> S;\r\n    while(m--)\r\n    {\r\n        int a,b,c;cin>>c>>a>>b;\r\n        a=get(a);b=get(b);\r\n        S.push(edge(pi(a,b),c));\r\n    }\r\n    dist=new Matrix(cnt);\r\n    while(S.size())\r\n    {\r\n        edge i=S.top();S.pop();\r\n        dist->M[i.ss][i.tt]=dist->M[i.tt][i.ss]=i.cc;\r\n    }\r\n    s=get(s);t=get(t);\r\n}\r\nMatrix Power(int n)\r\n{ \r\n    if(n==1){return *dist;}\r\n    Matrix ans=Power(n\/2);\r\n    ans=ans*ans;\r\n    if(n%2==1)\r\n        ans=ans*(*dist);\r\n    return ans;\r\n}\r\nvoid solve()\r\n{\r\n    Matrix ans=Power(N);\r\n    cout<<ans.M[s][t]<<endl;\r\n}\r\nint main()\r\n{\r\n    init();\r\n    solve();\r\n}\r\n<\/pre>\n
3614 Problem C<\/strong> Sunscreen<\/a>
\u5927\u610f\uff1a\u6539\u7684XX\u70b9\u7b97\u4e86\u3002\u3002
\u6bcf\u4e2a\u7537\u751f\u7684\u5e05\u6c14\u503c\u57281\u52301000\u4e4b\u95f4\uff0c\uff0c
N\u4e2a\u5973\u751f\uff08N<=2500\uff09\u7b2ci\u4e2a\u559c\u6b22\u5e05\u6c14\u503cLowi\u5230Upi\u4e4b\u95f4\u7684\u7537\u751f\u3002\u3002
M\u79cd\u7537\u751f\uff08M<=2500\uff09\u7b2ci\u4e2a\u6709Numi\u4eba\uff0c\u5e05\u6c14\u503c\u4e3aHandsomei\u3002\u3002
\u8fd9\u65f6\u7537\u751f\u5f97\u77e5WJMZBMR\u6765\u4e86\uff0c\u4e3a\u4e86\u4e0d\u8ba9\u5e05\u5e05\u7684WJMZBMR\uff08\u5e05\u6c14\u503c>2^128\uff09
\u62a2\u8d70\u5973\u751f\u7684\u5fc3\u3002\u3002\u4ed6\u4eec\u9a6c\u4e0a\u5f00\u59cb\u884c\u52a8\u4e86\u3002\u3002
\u95ee\u6700\u591a\u6709\u591a\u5c11\u4e2a\u5973\u751f\u53ef\u4ee5\u6709\u7537\u670b\u53cb\u5462\uff1f\uff08\u4e0d\u5305\u62ecWJMZBMR\u3002\u3002\u3002\uff09
\u5206\u6790\uff1a
\u628a\u7537\u751f\u6309handsomei\u6392\u5e8f\u3002\u3002
\u4e00\u4e2a\u4e2a\u626b\u63cf\u8fc7\u53bb\uff0c\u6bcf\u4e2a\u7537\u751f\u5c3d\u91cf\u5339\u914dUpi\u5c0f\u7684\u5973\u751f\uff08\u592a\u5c0f\u7684\u5148\u8e22\u6389\uff09\u3002\u3002
\u7528\u4e00\u4e2aheap\u7ef4\u62a4\u5c31\u53ef\u4ee5\u4e86\u3002\u3002
\u542f\u793a\uff1a
\u5f88\u591a\u65f6\u5019\u60f3\u8d2a\u5fc3\u4e5f\u662f\u6709\u65b9\u6cd5\u7684\u3002\u3002\u6700\u91cd\u8981\u7684\u662f\u964d\u7ef4\u548c\u66ff\u4ee3\u6cd5\u3002\u3002
Code\uff1a
#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;
}<\/p>\n
\u7531\u4e8e\u767e\u5ea6\u7bc7\u5e45\u95ee\u9898
\u53ea\u80fd\u5f00\u5f88\u591a\u7ae0\u4e86\u3002\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
  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 \u8fd9\u4e2a\u4ec0\u4e48Individual […]<\/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\/55"}],"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=55"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/55\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=55"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=55"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=55"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}