1691: [Usaco2007 Dec]挑剔的美食家

2013年4月01日 11:42

http://www.lydsy.com/JudgeOnline/problem.php?id=1691

RunID User Problem Result Memory Time Language Code_Length Submit_Time
380740 Liu_Ts 1691 Accepted 3924 kb 428 ms C++ 945 B 2013-03-31 17:18:47

 

题意

两个序列n和m,有权值a(钱),b(新鲜度)

求满足所有N序列与M序列匹配, 

M序列的元素可以匹配一个N中的元素,当且仅当M序列的值满足 m.a>=n.a && m.b>=n.b

求minΣm.a。

题解

把M和N按b排降序,

枚举N,用一个BST维护满足当前n.b的所有M中的元素。

每次去除BST中满足N.a的最小的M.a;

 

#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#define PB push_back
#define MP make_pair
using namespace std;
int n,m;
vector<pair<int,int> > cow,food;
multiset<int> s;
long long ans;
int main()
{
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        cow.PB(MP(b,a));
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        food.PB(MP(b,a));
    }
    sort(cow.begin(),cow.end());
    sort(food.begin(),food.end());
    bool flag=true;int j=m-1;
    for(int i=n-1;i>=0;i--)
    {
        for(;j>=0;)
            if(food[j].first>=cow[i].first)
                s.insert(food[j--].second);
            else    break;
        if(s.size()==0)
        {
            puts("-1");
            return 0;
        }
        multiset<int>::iterator p=s.lower_bound(cow[i].second);
        ans+=*p;s.erase(p);
    }
    printf("%lld\n",ans);
}

Tags: usaco bzoj
评论(0) 阅读(800)

1772: [Usaco2009 Nov]rescue 拯救奶牛貝希

2013年3月31日 14:56

http://www.lydsy.com/JudgeOnline/problem.php?id=1772

RunID User Problem Result Memory Time Language Code_Length Submit_Time
380234 Liu_Ts 1772 Accepted 884 kb 20 ms C++ 618 B 2013-03-30 15:10:53

 

题意

给定一个N行的三角形矩阵,如图

求一个点到另外几个给定的点的距离中,最短的距离。

题解

挺好玩的,重建三维坐标系

对于三角形(i,j)

x=i,y=(j+1)div 2,z=(i*2-1-j+1)div 2=i-j div 2

可以证明对于任意两个三角形,

他们的距离恰为|x1-x2|+|y1-y2|+|z1-z2|。

 

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<climits>
using namespace std;
const int N=10001;
int X[N],Y[N],n,m,sx,sy,sz,ax,ay,d;
 
int main()
{
    int a,b,x,y,z;
    scanf("%d%d%d%d",&n,&m,&a,&b);
    //x=i,y=(j+1)div 2,z=i-j div 2;
    sx=a;sy=(b+1)/2;sz=a-b/2;
    d=INT_MAX;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        x=a;y=(b+1)/2;z=a-b/2;
        int tmp=abs(x-sx)+abs(y-sy)+abs(z-sz);
        if((tmp<d)||(tmp==d && ax>a)||(tmp==d && ax==a && ay>b))
            ax=a,ay=b,d=tmp;
    }
    printf("%d %d\n",ax,ay);
    printf("%d\n",d+1);
}

 

 

 

Tags: bzoj usaco
评论(0) 阅读(1117)

1596: [Usaco2008 Jan]电话网络

2013年3月27日 15:40

http://www.lydsy.com/JudgeOnline/problem.php?id=1596

RunID User Problem Result Memory Time Language Code_Length Submit_Time
377097 Liu_Ts 1596 Accepted 3932 kb 16 ms C++ 944 B 2013-03-27 11:32:23

 

题意

一棵树,每个点可以支配直接与它相邻的点,求最小支配集。

题解

经典题目0.0

f[i][0]:以i为根的子树中均被覆盖且草地i上信号塔所需的最小塔数

f[i][1]:以i为根的子树中均被覆盖且草地i上信号塔所需的最小塔数

f[i][2]:以i为根的子树中除i点以外其余点均被覆盖所需的最小塔数

 转移方法:

f[i][1]=Σ(min(f[i.son][0..2]))

f[i][2]=Σ(f[i.son][0])

令sum=Σ(min(f[i.son][0..1]))

f[i][0]=min(f[i.son][1]+sum-min(f[i.son][0..1]))

i为叶节点时,f[i][0]显然是不合法的,所以应设为无穷大。 

 

#include<cstring>
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
const int N=100001,M=2*N;
int n,k,f[N][3],v[M],next[M],head[N];
 
void add(int x,int y)
{
    v[++k]=y;next[k]=head[x];head[x]=k;
}
 
void dfs(int x,int fa)
{
    int sum=0;
    f[x][1]=1;
    for(int i=head[x];i;i=next[i])
        if(v[i]!=fa)
        {
            dfs(v[i],x);
            f[x][1]+=min(f[v[i]][0],min(f[v[i]][1],f[v[i]][2]));
            f[x][2]+=f[v[i]][0];
            sum+=min(f[v[i]][0],f[v[i]][1]);
        }
    f[x][0]=N;
    if(x!=1&&!next[head[x]])    return;
    for(int i=head[x];i;i=next[i])
        if(v[i]!=fa)
            f[x][0]=min(f[x][0],f[v[i]][1]+sum-min(f[v[i]][0],f[v[i]][1]));
}
     
 
int main()
{
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    printf("%d\n",min(f[1][1],f[1][0]));
}

Tags: usaco bzoj
评论(0) 阅读(819)

1776: [Usaco2010 Hol]cowpol 奶牛政坛

2013年3月26日 17:21

http://www.lydsy.com/JudgeOnline/problem.php?id=1776

RunID User Problem Result Memory Time Language Code_Length Submit_Time
376495 Liu_Ts 1776 Accepted 26244 kb 1940 ms C++ 1693 B 2013-03-26 17:01:47

 

题意

一棵树,每个节点有一个编号,一共K种编号,输出每种编号的控制范围,即所有该编号的点,在树上的最远点对。

题解

对于每种编号,

最远点对中的其中一个点肯定离根最远,

所以先找出这个点,

枚举剩下的点,用lca算出每个点和找出的点的距离,更新答案即可。

 

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;
const int N=200001,K=100001,M=N*2,Q=N*3;
int q[Q],d[N],num[N],p[N],Max[K],ans[N];
int v[M],next[M],head[N],k;
int n,m;

struct SegmentTree
{
	int m[Q*3];
	void update(int x)
	{
		int l=x<<1,r=l+1;
		m[x]=m[l];
		if(d[m[x]]>d[m[r]])
			m[x]=m[r];
	}
	void build(int x,int s,int t)
	{
		if(s==t)
		{
			m[x]=q[s];return;
		}
		int mid=s+t>>1;
		build(x<<1,s,mid);build((x<<1)+1,mid+1,t);
		update(x);
	}
	int get(int x,int s,int t,int ll,int rr)
	{
		if(ll<=s&&t<=rr)	return m[x];
		int t1=0,t2=0,mid=s+t>>1;
		if(ll<=mid)	t1=get(x<<1,s,mid,ll,rr);
		if(rr>mid)	t2=get((x<<1)+1,mid+1,t,ll,rr);
		if(d[t1]<d[t2])	return t1;
		else return t2;
	}
}a;
void add(int x,int y)
{
	if((!x)||(!y))	return;
	v[++k]=y;next[k]=head[x];head[x]=k;
}
void dfs(int x,int fa,int deep)
{
	q[++q[0]]=x;num[x]=q[0];d[x]=deep;
	if(d[x]>d[Max[p[x]]])	Max[p[x]]=x;
	for(int i=head[x];i;i=next[i])
		if(v[i]!=fa)
			dfs(v[i],x,deep+1),q[++q[0]]=x;
}
int lca(int x,int y)
{
	if(num[x]>num[y])	swap(x,y);
	return a.get(1,1,q[0],num[x],num[y]);
}
int main()
{
	scanf("%d%d",&n,&m);
	int x,y,z;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",p+i,&x);
		add(x,i);add(i,x);
	}
	dfs(1,0,0);d[0]=INT_MAX;
	a.build(1,1,q[0]);
	for(int i=1;i<=n;i++)
	{
		int tmp=d[i]+d[Max[p[i]]]-d[lca(i,Max[p[i]])]*2;
		ans[p[i]]=max(ans[p[i]],tmp);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
}

Tags: usaco bzoj
评论(0) 阅读(990)

1704: [Usaco2007 Mar]Face The Right Way

2013年3月25日 16:25

http://www.lydsy.com/JudgeOnline/problem.php?id=1704

RunID User Problem Result Memory Time Language Code_Length Submit_Time
375337 Liu_Ts 1704 Accepted 864 kb 428 ms C++ 720 B 2013-03-24 22:31:26

 

题意

给定一个01序列,每次可以将连续的k个数取反。

确定一个k使得,将所有数全变成0的操作次数m最小。

题解

枚举k,O(N)验证,更新答案。

把所有当前为1的反转。

验证时,用一个队列,记录被修改过的点,每次找到对当前枚举点有作用的队列区间,

如果区间长度为奇数,说明该点之前被反转。

 

#include<cstring>
#include<cmath>
#include<cstdio>
#include<climits>
using namespace std;
 
const int N=5001;
 
int b[N],a[N],n,m,k,q[N];
 
 
 
int check(int x)
{
    int l=0,r=1,now=0;
    memcpy(b,a,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        while(l<=r && q[l]<=i-x)  l++;
        if(((r-l+1)&1)) b[i]=1-b[i];
        if(b[i])
            if(i<=n-x+1)
                now++,b[i]=0,q[++r]=i;
            else return INT_MAX;
    }
    return now;
}
 
int main()
{
    scanf("%d",&n);
    int m=INT_MAX;
    for(int i=1;i<=n;i++)
        getchar(),a[i]=getchar()=='B';
    for(int i=1;i<=n;i++)
    {
        int tmp=check(i);
        if(tmp<m)
            m=tmp,k=i;
    }
    printf("%d %d\n",k,m);
}

 

Tags: usaco bzoj
评论(0) 阅读(9231)