3203: [Sdoi2013]保护出题人

2013年6月03日 16:21

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
427418 Liu_Ts 3203 Accepted 5884 kb 264 ms C++ 1119 B 2013-06-03 15:47:57

 

题意

题目很复杂0.0

对于每一关,会加一个血量为a[i]的僵尸在队首,每个僵尸之间间隔d,

队首的坐标为x[i],僵尸移动速度1单位长度/s

每次求一个植物的最小攻击力y[i]点血/s,使得出题人不被吃掉的情况下,打死所有僵尸。

注意:如果某次植物攻击,大于当前僵尸的血量,超出的攻击力会打到下一个僵尸。

题解

设s[i]=sigm(a[i])

则y[i]=max{(s[i]-s[j-1])/(x[i]+(i-j)*d)}  (i≥j);

于是对于每个僵尸j我们设点(j*d,s[j-1]),

那么答案就相当于每次给定一个点(x[i]+i*d,s[i]),

在当前僵尸中求一个点使得这两个点的斜率最大。

这样维护下凸壳,再二分就可以了。

#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=100010;
const double eps=1e-8;
struct point
{
    ld x,y;
}p[N],c;
int n,q[N],top;
ld s[N],x[N],d,ans;
 
ld cross(point c,point a,point b)
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
 
int find()
{
    int tmp=1,l=2,r=top,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(cross(c,p[q[mid]],p[q[mid-1]])<-eps)
            tmp=max(tmp,mid),l=mid+1;
        else r=mid-1;
    }
    return tmp;
}
  
int main()
{
    double o1,o2;
    scanf("%d%lf",&n,&o1);d=o1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&o1,&o2);s[i]=o1,x[i]=o2,s[i]+=s[i-1];
        p[i].x=i*d;p[i].y=s[i-1];
    }
    int j;
    for(int i=1;i<=n;i++)
    {
        while(top>1 && cross(p[q[top-1]],p[q[top]],p[i])<-eps) top--;
        q[++top]=i;c.x=x[i]+i*d;c.y=s[i];j=q[find()];
        ans+=(c.y-p[j].y)/(c.x-p[j].x);//printf("%.5lf\n",(double)ans);
    }
    printf("%.0lf\n",(double)ans);
}

 

 

Tags: SDOI bzoj
评论(0) 阅读(1840)

3144: [Hnoi2013]切糕

2013年5月28日 20:36

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
405097 Liu_Ts 3144 Accepted 96900 kb 1516 ms C++ 1941 B 2013-05-05 09:58:21

 

题意

一个n*m*k的立方体,从侧面切过去,切出一个N*M的切面(不是一个面,是崎岖的0.0),切到的每个点都有一个权值v(x,y,z)。

且切到的每个点与四周被切点的高度差(即z轴坐标的差)不能超过给定的D(切面要平滑0.0)。

最小化∑v(x,y,z){(x,y,z)∈切面}

题解

首先做k+1层n*m的点,对于第i层的每个点向i+1层的该点连容量为v(x,y,i)的边。

s向最下层的每个点连+∞的边,最上层连t,容量为+∞

这样之后就把点权转到了边上,做最小割。

然后处理高度差D的限制,

把第i层(x,y)的每个点向它处在i-D层的周围的点连+∞的边。

转换成割来考虑的话,就是如果把第i层(x,y)到i+1层的(x,y)割掉的话,

那么它周围的点必须割在差在D以内的边,画个图就很明显啦~~

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
const int N=100001,M=6000000;
const int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
int u[M],v[M],w[M],next[M],head[N],k=1;
int d[N],pre[N],low[N],vd[N],cur[N];
int p,q,r,D,s,t;
 
int num(int x,int y,int z)
{   
    if(x<1||y<1||z<1||x>p||y>q||z>(r+1)) return N-1;
    return (z-1)*(p*q)+(x-1)*q+y;
}
 
int solve(int s,int t) 
{ 
    int now=s,i,ans=0; 
    low[s]=INT_MAX;vd[0]=t; 
    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) 
        { 
            low[v[i]]=min(low[now],w[i]);pre[v[i]]=i;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; 
}
void add(int x,int y,int z)
{
    u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}
int main()
{
    scanf("%d%d%d",&p,&q,&r);
    scanf("%d",&D);
    s=p*q*(r+2)+1;t=s+1;
    for(int i=1;i<=p;i++)
        for(int j=1;j<=q;j++)
        {
            add(num(i,j,r+1),t,INT_MAX);add(s,num(i,j,1),INT_MAX);
            for(int o=0;o<4;o++)
                add(num(i,j,r+1),num(i+dx[o],j+dy[o],r+1-D),INT_MAX);
        }
    int x;
    for(int k=1;k<=r;k++)
        for(int i=1;i<=p;i++)
            for(int j=1;j<=q;j++)
            {
                scanf("%d",&x);
                add(num(i,j,k),num(i,j,k+1),x);
                for(int o=0;o<4;o++)
                    add(num(i,j,k),num(i+dx[o],j+dy[o],k-D),INT_MAX);
            }
    printf("%d\n",solve(s,t));
}

 

Tags: HNOI bzoj
评论(0) 阅读(1593)

3119: Book

2013年4月18日 08:24

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
393153 Liu_Ts 3119 Accepted 904 kb 328 ms C++ 504 B 2013-04-18 07:59:10

 

题意

要求构造一个序列,

满足,长度为N,和为M,第一个数是X,

从第二项开始一定比前一项大A或比前一项小B;

保证有解。

题解

如果在第i个位置上+A,他会对所有i以后(N-i+1)个数造成影响,

即对和造成的影响是+(N-i+1)*A

那么设+A操作总共对x个数造成影响,-B操作总共对y个数造成影响。

列得:

     xA-yB=M-N*X;

     x+y=n*(n-1)/2;

可以把x、y解出来。

问题就变成了用1..n-1之间的数去凑x或者y。

就从n-1开始,不断减小x就可以了。

 

#include<cstdio>
#include<cstring>
using namespace std;
long long N,M,n,m,x,y,X,A,B;
bool f[100011];
int main()
{
	scanf("%lld%lld%lld%lld%lld",&N,&X,&A,&B,&M);
	m=M-N*X;n=N*(N-1)/2;
	x=(m+B*n)/(A+B);y=n-x;
	int now=N-1;
	while(x)
	{
		if (x-now>=0)
			f[now]=1,x-=now;
		now--;
	}
	printf("%lld",X);
	for(int i=N-1;i>=1;i--)
	{
		if(f[i]) X+=A;else X-=B;
		printf(" %lld",X);
	}
	puts("");
}

 

Tags: bzoj
评论(61) 阅读(2119)

3106: [cqoi2013]棋盘游戏

2013年4月16日 14:57

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391578 Liu_Ts 3106 Accepted 96528 kb 5728 ms C++ 1294 B 2013-04-16 13:10:46

 

题意

一个n*n(n>=2)棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子,A先走。

        A:移动白棋子。可以往上下左右四个方向之一移动一格。

        B:移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。

当某游戏者把自己的棋子移动到对方棋子所在的格子时就赢了。两个游戏者都很聪明,当可以获胜时会尽快获胜,只能输掉的时候会尽量拖延时间。判断谁会赢,需要多少回合。

题解

不看题解不会- =

然后找到一种很奇怪的做法。。

首先没有平局- =,

如果黑色不在白色的旁边,黑色一定赢(因为白色永远吃不到它0.0)。

接下来的问题是求需要多少步

 

暴力,然后,其实是卡时。。

我们猜测答案不超过3n步。。。。

记忆化搜索,f[a][b][c][d][x][y]表示白(a,b),黑(c,d),x步,y表示当前游戏者是谁。

于是就过了,不明真相。

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=21;
int f[N][N][N][N][N*3][2],n,a,b,c,d;
int DFS(int a,int b,int c,int d,int x,int y)
{
    if(x>3*n)  return 1<<30;
    if(a==c&&b==d)  return y==1?1<<30:0;
    if(f[a][b][c][d][x][y])  return f[a][b][c][d][x][y];
    int &ans=f[a][b][c][d][x][y];
    if(y==0)
    {
        if(a>1)  ans=max(ans,DFS(a-1,b,c,d,x+1,1)+1);
        if(b>1)  ans=max(ans,DFS(a,b-1,c,d,x+1,1)+1);
        if(a<n)  ans=max(ans,DFS(a+1,b,c,d,x+1,1)+1);
        if(b<n)  ans=max(ans,DFS(a,b+1,c,d,x+1,1)+1);
    }
    else
    {
        ans=1<<30;
        if(c>1)  ans=min(ans,DFS(a,b,c-1,d,x+1,0)+1);
        if(d>1)  ans=min(ans,DFS(a,b,c,d-1,x+1,0)+1);
        if(c<n)  ans=min(ans,DFS(a,b,c+1,d,x+1,0)+1);
        if(d<n)  ans=min(ans,DFS(a,b,c,d+1,x+1,0)+1);
        if(c>2)  ans=min(ans,DFS(a,b,c-2,d,x+1,0)+1);
        if(d>2)  ans=min(ans,DFS(a,b,c,d-2,x+1,0)+1);
        if(c+2<=n)  ans=min(ans,DFS(a,b,c+2,d,x+1,0)+1);
        if(d+2<=n)  ans=min(ans,DFS(a,b,c,d+2,x+1,0)+1);
    }
    return ans;
}
int main()
{
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
    if(abs(a-c)+abs(b-d)==1) printf("WHITE 1\n"); 
    else DFS(a,b,c,d,0,0),printf("BLACK %d\n",f[a][b][c][d][0][0]);
}

Tags: bzoj CQOI
评论(1) 阅读(1894)

3130: [Sdoi2013]费用流

2013年4月16日 14:16

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391645 Liu_Ts 3130 Accepted 864 kb 76 ms C++ 1934 B 2013-04-16 14:07:23

 

题意

一个图(有重边,无自环),给定一个整数P

第一问:求1到N最大流。

第二问:Alice确定一种最大流的方案,Bob给一些边分配费用,各边的单位费用和为P;求在Bob采取最优策略的情况下,Alice如何确定最大流方案,能使得最后总费用最小。

题解

显然Bob的最优策略就是把当前流量最大的一条边加上费用P;

所以Alice就要使最大流量最小。

二分答案,要注意这题因为有重边所以答案可能为实数!

 

#include<cmath>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
const int N=201,M=2010,T=1001;
const double eps=1e-6;

int u[M],v[M],next[M],head[N];
int cur[N],d[N],vd[N],pre[N];
int n,m,p,x[T],y[T],k;
double l,r,low[N],w[M],z[T];


void add(int x,int y,double z)
{
	u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
	u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}

void rebuild(double v)
{
	memset(head,0,sizeof(head));k=1;
	for(int i=1;i<=m;i++)
		add(x[i],y[i],min(v,z[i]));
}
double solve(int s,int t,double x)
{
	rebuild(x);
	memset(d,0,sizeof(d));
	memset(vd,0,sizeof(vd));
	memset(low,0,sizeof(low));
	memset(cur,0,sizeof(cur));
	int now=s,i;double ans=0;
	low[s]=INT_MAX;vd[0]=t;
	while(d[s]<t)
	{
		for(i=head[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(low[now],w[i]);
			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;
}




int main()
{
	scanf("%d%d%d",&n,&m,&p);
	l=r=1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%lf",&x[i],&y[i],&z[i]);
		r=max(r,z[i]);
	}
	double maxflow=solve(1,n,r);
	printf("%.0lf\n",maxflow);
	int ans=0;
	while(r-l>=eps)
	{
		double mid=(l+r)/2,flow=solve(1,n,mid);
		if(maxflow-flow<=eps) r=mid-eps;
		else l=mid+eps;
	}
	printf("%.4lf\n",l*p);
}

Tags: bzoj SDOI
评论(0) 阅读(1828)