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

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

3122: [Sdoi2013]随机数生成器

2013年4月15日 19:51

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391145 Liu_Ts 3122 Accepted 9100 kb 1488 ms C++ 2158 B 2013-04-15 17:39:23

 

题意

已知Xi+1=(aXi + b)mod p;

给定X1,a,b,p(质数),t

求第一个满足Xn=t的n

题解

把原式化开,得

Xn=[a^(n-1)*X1+b*(a^(n-2)+a^(n-3)+..+a^0)]mod p;

分情况讨论

①X1=t时,ans=1;

②a=0时,

    1.b=t时,ans=2;

    2.b!=t时,ans=-1;

③a=1时,

    Xn=[X1+b*(n-1)]mod p=t

    移向之后,相当于求xb+yp=(t-X1)mod p;

    扩展gcd,ans=x+1;

④a>1时,

    Xn=[a^(n-1)*X1+b*(a^(n-1)-1)/(a-1)]mod p

    设c=(a-1)在模p意义下的逆元,即c=(a-1)^(p-2);

    Xn=[a^(n-1)*X1+bc*(a^(n-1)-1)]mod p

    化简得Xn=[(X1+bc)*a^(n-1)-bc]mod p=t

    令q=X1+bc,t`=(t+bc)mod p,

    移向后相当于求[q*a^(n-1)]mod p=t'

    接下来我的做法是,先求xq+yp=t'的解x;

    问题变为求a^x` mod p=x,ans=x`+1。就和山东11年的计算器那题一样了。

 

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<climits>
using namespace std;
typedef long long ll;
const int H=1000001;
int f[H],r[H];
ll p,a,b,x1,x,y,t;
 
ll km(ll a,ll k)
{
    if(!a) return 0;
    ll t=a,q=1;
    while(k)
    {
        if(k&1) q=((q%p)*(t%p))%p;
        t=((t%p)*(t%p))%p;
        k=k>>1;
    }
    return q;
}
void gcd(ll a,ll b,ll c)
{
    if(!b)
        if(!(c%a))
        {
            x=c/a;y=0;
            return;
        }
        else
        {
            x=-1;return;
        }
    gcd(b,a%b,c);
    if(x==-1) return;
    ll t=y;y=x-((a/b)*y);x=t;
}
       
void work1()
{
    t=(t-x1+p)%p;
    x=y=0;
    gcd(b,p,t);
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
        x++;
    }
    printf("%lld\n",x);
}
void work2()
{
    ll c=km(a-1,p-2);
    t=(t+((b*c)%p))%p;
    ll q=(x1+((b*c)%p))%p;
    x=y=0;
    gcd(q,p,t);
    if(x==-1)
    {
        puts("-1");return;
    }
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
    }
    int m=int(floor(sqrt(p)+1)),b=km(a,p-1-m);;
    memset(f,255,sizeof(f));
    memset(r,255,sizeof(r));
    ll now=1;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1) h=(h+1)%H;
        f[h]=now;r[h]=i;now=now*a%p;
    }
    now=x%p;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1)
        {
            if(f[h]==now)
            {
                printf("%d\n",i*m+r[h]+1);
                return;
            }
            h=(h+1)%H;
        }
        now=now*b%p;
    }
    puts("-1");
}
 
void work()
{
    if(x1==t){puts("1");return;}
    if(a==0)
    {
        if(b==t) puts("2");
        else puts("-1");
        return;
    } 
    if(a==1)
    {
        work1();
        return;
    }
    work2();
}
     
int main()
{
    int T;scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
        work();
    }
}

Tags: SDOI bzoj
评论(1) 阅读(1680)

3124: [Sdoi2013]直径

2013年4月15日 16:39

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391083 Liu_Ts 3124 Accepted 14000 kb 1572 ms C++ 1383 B 2013-04-15 16:26:40

 

题意

一棵树,求直径和有多少条边一定在直径上。

题解

我就不说我省选有多傻叉了。

首先DFS求出直径,

显然一定在直径上的边一定是任意一条直径上连续的一段。

所以我们遍历求出的直径(红色+蓝色)上的每个点x,

如果以这个点为起点,在不访问直径上的点的情况下,

求出一条最长链,图中的黑色

如果等于蓝色的长度或红色的长度,那么这段蓝色或红色就不是一定在直径上。

这样不断缩小左右端点,剩下的链上的边就是答案

 

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200011,M=N*2;
int v[M],w[M],next[M],head[N],k=1;
long long d[N],dep[N],ans1,tmp;
int n,pre[N],A,B,leaf;bool vis[N];

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

void dfs(int x,int fa)
{
	pre[x]=fa;
	if(dep[x]>tmp)
		tmp=dep[x],leaf=x;
	for(int i=head[x];i;i=next[i])
		if(v[i]!=fa)
			dep[v[i]]=dep[x]+w[i],dfs(v[i],x);
}

void  find(int x,int fa)
{
	tmp=max(tmp,d[x]);
	for(int i=head[x];i;i=next[i])
		if((v[i]!=fa) && (!vis[v[i]]))
			d[v[i]]=d[x]+w[i],find(v[i],x);
}

int main()
{
	scanf("%d",&n);int x,y,z;
	for(int i=1;i<n;i++)
		scanf("%d%d%d",&x,&y,&z),add(x,y,z);
	tmp=dep[1]=0;dfs(1,0);A=leaf;
	tmp=dep[A]=0;dfs(A,0);B=leaf;
	ans1=tmp;
	printf("%lld\n",ans1);
	memset(vis,0,sizeof(vis));
	for(int i=B;i;i=pre[i]) vis[i]=1;
	bool flag=1;int left=A,right=B;
	for(int i=B;i;i=pre[i])
	{
		long long ldist=dep[i],rdist=ans1-dep[i];
		tmp=d[i]=0;find(i,0);
		if((tmp==ldist) && flag) 
			left=i,flag=0;
		if(tmp==rdist) right=i;
	}
	int ans2=0;
	for(int i=right;i!=left;i=pre[i]) ans2++;
	printf("%d\n",ans2);
}

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

1878: [SDOI2009]HH的项链

2013年3月28日 08:54

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
378013 Liu_Ts 1878 Accepted 32056 kb 1260 ms C++ 1081 B 2013-03-28 08:46:15

 

题意

给定一个序列,询问每个区间上有多少不同的数字。

题解

因为没有修改,所以离线做就可以了。

把询问按右端点排序,

从前到后,对于每个颜色,

在它上一次出现的地方的后一点+1,

在当前位置的后一点-1;

当前询问答案为ΣXi(1..L)

 

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N=1000002;
int n,m;
struct rec{int n,x,y;}a[N];
int color[N],last[N],pre[N],ans[N];
int c[N];
inline bool cmp(rec a,rec b)
{
  return a.y<b.y;
}
inline void inc(int x,int w)
{
  for(;x<=n;x+=lowbit(x))c[x]+=w;
}
inline int sum(int x)
{
  int s=0;
  for(;x;x-=lowbit(x))s+=c[x];
  return s;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
	{
        scanf("%d",color+i);
        pre[i]=last[color[i]];
        last[color[i]]=i;
    }
    scanf("%d",&m);
    for(int i=0;i<m;++i)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].n=i;
    }
    sort(a,a+m,cmp);
    int now=0;
    for(int i=0;i<m;++i)
    {
        while(now<a[i].y)
            inc(pre[++now]+1,1),inc(now+1,-1);
        ans[a[i].n]=sum(a[i].x);
    }
 	for(int i=0;i<m;++i)printf("%d\n",ans[i]);
}

Tags: SDOI bzoj
评论(1) 阅读(1833)