2298: [HAOI2011]problem a

2013年4月01日 15:51

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
381428 Liu_Ts 2298 Accepted 2740 kb 444 ms C++ 797 B 2013-04-01 15:23:28

 

题意

n个人,每个人说Xi个人比我低,Yi个人比我高

问最少有多少个人说假话

题解

其实想的和题解一样,但是忽略题解中所说的情况,一直wa,

掉(xi + yi ≥ n)的,

每句话都可以表示成一个[yi + 1, n - xi]的区间。

一开始所有的区间权值为1;

然后把同样的区间合并,权值设为合并在一起的区间数量

选出最多的互补相交的区间,记为k

那么答案就是n-k。

需要注意的是如果某个同样区间的数量>区间长度,要改成区间长度

 

#include<cstdio>
#include<algorithm>
#include<vector>
#define MP make_pair
#define PB push_back
#define s first
#define t second
using namespace std;
typedef pair<int,int> pr;
int n,f[100001],tot;
vector<pr> p;

bool cmp(pr a,pr b)
{
	if(a.t!=b.t) return a.t<b.t;
	else return a.s<b.s;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		if(x+y>=n)	continue;
		p.PB(MP(y+1,n-x));tot++;
	}
	sort(p.begin(),p.end(),cmp);
	int j=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=f[i-1];
		while(j<tot && p[j].t==i)
		{
			int k;for(k=j;k<tot && p[k]==p[j];k++);
			f[i]=max(f[i],f[p[j].s]+min(k-j,p[j].t-p[j].s));
			j=k;
		}
	}
	printf("%d\n",n-f[n]);
}

 

Tags: HAOI bzoj
评论(0) 阅读(1306)

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) 阅读(798)

1822: [JSOI2010]Frozen Nova 冷冻波

2013年4月01日 11:30

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
381251 Liu_Ts 1822 Accepted 2432 kb 136 ms C++ 3298 B 2013-04-01 11:22:43

 

题意

N个lich,M个spirit,每个lich有一个cd[i]和一个施法半径r[i];

K棵树,每棵树半径为R[i];

如果spirit在lich的施法半径内,且中间不经过任意一棵树,则可以打到。

每次施法只能打掉一个。

求最少多少时间可以打掉所有spirit。

题解

二分答案x,

网络流验证,

S向每个lich连边,容量为x/cd[i]+1

每个lich向它能打的到的spirit连边;

暴力预处理。

 

#include<cstring>
#include<climits>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int K=202,N=500,M=100000;

struct point
{
	double x,y;
	point operator +(const point b)
	{
		point ans;ans.x=x+b.x;ans.y=y+b.y;
		return ans;
	}
	point operator -(const point b)
	{
		point ans;ans.x=x-b.x;ans.y=y-b.y;
		return ans;
	}
	double operator *(const point b)
	{
		double k=x*b.y-b.x*y;
		if((-1e-8)<k && k<(1e-8))	return 0;
		return k;
	}
}lich[K],spirit[K],tree[K];
inline double dist(point a,point b)
{
	point p=a-b;
	return sqrt(p.x*p.x+p.y*p.y);
}
inline double square(point a,point b,point c)
{
	double k=(b-a)*(c-a);
	return abs(k);
}
int n,m,k,S,T;
double Rlich[K],Tlich[K],Rtree[K];
bool can[K][K];
bool check(int p,int q)
{
	if(Rlich[p]<dist(lich[p],spirit[q])) return 0;
	for(int i=1;i<=k;i++)
	{
		double l=square(lich[p],spirit[q],tree[i])/dist(lich[p],spirit[q]);
        if (Rtree[i]-l>(1e-8)) return 0;
	}
	return 1;
}
int init()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&lich[i].x,&lich[i].y,&Rlich[i],&Tlich[i]);
    for(int i=1;i<=m;i++) scanf("%lf%lf",&spirit[i].x,&spirit[i].y);
    for(int i=1;i<=k;i++) scanf("%lf%lf%lf",&tree[i].x,&tree[i].y,&Rtree[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(check(i,j))	can[i][j]=true;
	S=n+m+1;T=S+1;
}

int u[M],v[M],w[M],next[M],head[N],o;
int low[N],d[N],vd[N],pre[N],cur[N];

void add(int x,int y,int z)
{
	u[++o]=x;v[o]=y;w[o]=z;next[o]=head[x];head[x]=o;
	u[++o]=y;v[o]=x;w[o]=0;next[o]=head[y];head[y]=o;
}
int solve(int s,int t)
{
    memset(cur,0,sizeof(cur));
    memset(d,0,sizeof(d));
    memset(vd,0,sizeof(vd));
    int now=s,ans=0,i;
    vd[0]=t;low[s]=INT_MAX;
    while(d[s]<t)
    {
        for(i=cur[now];i;i=next[i])
            if(w[i]>0&&d[now]==d[v[i]]+1)
                break;
        cur[now]=i;
        if(i)
        {
            pre[v[i]]=i;low[v[i]]=min(w[i],low[now]);
            now=v[i];
            if(now==t)
            {
                for(;now!=s;now=u[pre[now]])
                    w[pre[now]]-=low[t],w[pre[now]^1]+=low[t];
                low[s]=INT_MAX;ans+=low[t];
            }
        }
        else
        {
            if(!--vd[d[now]])   break;
            d[now]=t;
            for(i=head[now];i;i=next[i])
                if(w[i]>0&&d[now]>d[v[i]]+1)
                    d[now]=d[v[i]]+1,cur[now]=i;
            vd[d[now]]++;
            if(now!=s)  now=u[pre[now]];
        }
    }
    return ans;
}

bool work(int x)
{
	memset(head,0,sizeof(head));o=1;
	for(int i=1;i<=n;i++)
	{
		add(S,i,x/Tlich[i]+1);
		for(int j=1;j<=m;j++)
			if(can[i][j])
				add(i,n+j,1);
	}
	for(int i=1;i<=m;i++)
		add(n+i,T,1);
	return solve(S,T)==m;
}	
	
int main()
{
	init();
	int l=0,r=10000000,ans=-1;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(work(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans);
}

Tags: JSOI bzoj
评论(0) 阅读(1204)

2879: [Noi2012]美食节

2013年3月31日 15:11

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
380608 Liu_Ts 2879 Accepted 5536 kb 4296 ms C++ 1539 B 2013-03-31 14:48:33

 

题意

有n道菜,每道菜需要p[i]份,m个厨师,第j个厨师做第i到菜需要时间t[i][j],求做完所有菜,所有人等待的最小总时间。

题解

和之前有个usaco一样,

令Sp=Σp[i]

把每个厨师拆成Sp个点,

每道菜向一个点连边,费用为这个厨师倒数第p道做这个菜,对所有人产生的影响,即p*t[i][j];(会对当前这个人以及厨师接下来所做菜的几个人产生影响)

但是这道题范围太大,

所以动态加边,

每次增广完后,找到一个当前还没有被增广的厨师,拆n个点,继续增广。

具体看程序理解。

 

#include<cstring>
#include<cstdio>
using namespace std;
const int N=1000,M=100000;
int u[M],v[M],w[M],c[M],next[M],head[N],k=1;
int n,m,q[M],d[N],pre[N],sp,p[41],t[41][101],cnt[101],last[101];
bool vis[N];
void add(int x,int y,int z,int zz)
{
	u[++k]=x;v[k]=y;w[k]=z;c[k]=zz;next[k]=head[x];head[x]=k;
	u[++k]=y;v[k]=x;w[k]=0;c[k]=-zz;next[k]=head[y];head[y]=k;
}
void spfa(int s,int t)
{
	memset(d,127,sizeof(d));
	d[s]=0;vis[s]=true;
	int l=0,r=1;q[r]=s;
	while(l<r)
	{
		l=l%M+1;
		for(int i=head[q[l]];i;i=next[i])
			if(w[i]&&d[v[i]]>d[u[i]]+c[i])
			{
				d[v[i]]=d[u[i]]+c[i];pre[v[i]]=i;
				if(!vis[v[i]])
				{
					vis[v[i]]=true;
					r=r%M+1;q[r]=v[i];
				}
			}
		vis[q[l]]=false;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",p+i);
		sp+=p[i];
	}
	int S=n+m+sp+1,T=S+1;
	for(int i=1;i<=n;i++)
	{
		add(S,i,p[i],0);
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&t[i][j]);
			add(i,n+j,1,t[i][j]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		cnt[i]=1;
		add(n+i,T,1,0);
		last[i]=k;
	}
	int ans=0;
	for(;sp;sp--)
	{
		spfa(S,T);ans+=d[T];
		for(int i=T;i!=S;i=u[pre[i]])
			w[pre[i]]--,w[pre[i]^1]++;
		int j;
		for(j=1;j<=m&&w[last[j]-1];j++);
		cnt[j]++;
		for(int i=1;i<=n;i++)
			add(i,n+m+sp,1,t[i][j]*cnt[j]);
		add(n+m+sp,T,1,0);
		last[j]=k;
	}
	printf("%d\n",ans);
}

Tags: bzoj NOI
评论(1) 阅读(1820)

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) 阅读(1114)