USACO 2005 November Silver

http://acm.pku.edu.cn/JudgeOnline/problem?id=3044
http://acm.pku.edu.cn/JudgeOnline/problem?id=3045
http://acm.pku.edu.cn/JudgeOnline/problem?id=3046
@@@1@@@
考虑一块房子(就是两边都是地。。)
那么其中最矮的一块的高度必然是这一块中最矮的。。
那么贪心的选择自然是让它变得最宽。。然后再往上搭。。。
我直接暴力实现了。。平均是O(nlogn)。。最坏是O(n^2)。。幸好数据很厚道。。
暴力找最小值。。
官方程序只要栈扫描就OK了。。我SB阿。。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxy=500000,maxn=50000;
int w,n;
int H[maxn];
int cal(int i,int j)
{
if(i>j) return 0;
if(i==j) return H[i]>0;
int c=maxy;
for(int o=i;o<=j;o++)
c=min(H[o],c);
int a=i,ans=0;
for(int o=i;o<=j;o++)
if(H[o]==c)
ans+=cal(a,o-1),a=o+1;
ans+=cal(a,j);
if(c) ans++;
return ans;
}
int main()
{
cin>>n>>w;int x;
for(int i=0;i<n;i++)
{
scanf("%d %d",&x,H+i);
}
cout<<cal(0,n-1)<<endl;
}@@@@2@@@@
看两个牛i和i’。。设他们重量和力量分别为A,B,A’,B’..
他们上面的牛总重为S
假如A+B>A’+B’ 那么 A-B’>A’-B

A B
A‘ B’
max(S-B,S+A-B’) i在上面。。
max(S-B’,S+A’-B) i’在上面。。
那么总是i’在上面更好。。。
同理如果A+B=A’+B’。。
那么B大的在上面好。。。
直接排序就OK了。。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=50000,inf=~0U>>1;
int n;
struct node
{
int w,s;
bool operator<(const node&x) const
{
int a=w+s,b=x.w+x.s;
if(a!=b) return a<b;
return w<x.w;
}
}Q[maxn];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d %d",&Q[i].w,&Q[i].s);
}
sort(Q,Q+n);
int Sum=0,ans=-inf;
for(int i=0;i<n;i++)
{
ans=max(ans,Sum-Q[i].s);
Sum+=Q[i].w;
}
cout<<ans<<endl;
}@@@@3@@@@
这道题让我想到了母函数。。
然后我就直接上母函数了。。。
#include<iostream>
using namespace std;
const int maxn=1000,maxl=100000,Mod=1000000;
struct P
{
int *C;
int n;
P(int n):n(n)
{
C=new int[n+1];
for(int i=0;i<=n;i++)
C[i]=1;
}
int& operator[](int v){return C[v];}
void operator*=(P&x)
{
int*now=new int[n+x.n+1];
for(int i=0;i<=n+x.n;i++) now[i]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=x.n;j++)
{
now[i+j]+=C[i]*x[j];
now[i+j]%=Mod;
}
delete[] C;
C=now;n+=x.n;
}
};
int C[maxn]={0};
int T,A,S,B;
int main()
{
cin>>T>>A>>S>>B;
while(A–)
{
int t;cin>>t;
C[t-1]++;
}
P ans(0);
for(int i=0;i<T;i++)
{
P now(C[i]);
ans*=now;
}
int sum=0;
for(int i=S;i<=B;i++)
sum+=ans[i],sum%=Mod;
cout<<sum<<endl;
}

2 thoughts on “USACO 2005 November Silver

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>