高橋・直樹's Blog

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]），

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

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

bzoj3203
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53	`#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=id;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]+id;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) 阅读(1958)

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就要使最大流量最小。

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

bzoj3130
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90	`#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) 阅读(1890)

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年的计算器那题一样了。

bzoj3122
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124	`#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+((bc)%p))%p;` `ll q=(x1+((bc)%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=nowa%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",im+r[h]+1);` `return;` `}` `h=(h+1)%H;` `}` `now=nowb%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) 阅读(1821)

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，

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

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

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

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

bzoj3124
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58	`#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) 阅读(1757)

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)

bzoj1878
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51	`#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) 阅读(1885)

3203: [Sdoi2013]保护出题人

2013年6月03日 16:21

题意

题解

3130: [Sdoi2013]费用流

2013年4月16日 14:16

题意

题解

3122: [Sdoi2013]随机数生成器

2013年4月15日 19:51

题意

题解

3124: [Sdoi2013]直径

2013年4月15日 16:39

题意

题解

1878: [SDOI2009]HH的项链

2013年3月28日 08:54

题意

题解

RP犇＇樹樹君

分类

热门文章

最新评论

最新留言

友情链接

访客数量