4
28
2016
0

[BZOJ4008] [HNOI2015]亚瑟王

这题真心神题……

首先我们直接考虑第i轮选择谁,那么明显是做不了的,就变成了暴力

我们需要一些独特的DP技巧

首先,我们无视掉m轮的限制,把m次选择全部放在同一轮里面

设$DP[i][j]$为$[i,n]$中的人被选择$j$次的概率

那么显然$DP[0][m]=1$,因为根本没有0号,所以0一定不会被选择

那么转移就变成了

$DP[i][j]=DP[i-1][j]*(1-P[i-1])^j+DP[i-1][j+1]*(1-(1-P[i-1])^{j+1})$

解释:

首先$DP[i-1][j]*(1-P[i-1])^j$表示的是向前面递推到i-1人(因为这一次这一轮没有结束,当前卡牌没有被选择),同样还是j次机会,上一张卡发动技能的概率是$P[i-1]$(因为上一张卡如果发动了技能就跳到下一轮了),那么不发动技能的概率就是$1-P[i-1]$,j轮不发动技能的概率就是$(1-P[i-1])^j$,前面的$DP[i-1][j]$意思是上一张卡没有发动技能结束回合,这次机会留到这张卡

$DP[i-1][j+1]*(1-(1-P[i-1])^{j+1})$意思是上一张卡在第j轮不幸被选中发动技能了,那么下一次想要选到当前卡牌必须跳到下一轮(所以是$j+1$),后面的概率意思是上一张卡在前$j+1$轮发动技能的概率(因为直接选中这张卡后会判断当前这张卡有没有发动技能,前面是发动了技能的概率),那么这次将会跳过这张卡来到当前卡

所以来到当前卡的期望就是上面两者的和

然而答案怎么统计呢?答案因为要统计伤害的期望,那么根据期望的线性性,我们知道第$i$张卡能来到j轮的期望为$DP[i][j]$(来到的意思就是没有在前面发动过技能)

所以$ans=DP[i][j]*(1-(1-P[i])^j)*D[i]$,其中$D[i]$表示的是伤害

怎么找一篇详细的题解那么难。。大部分题解也就两句话,迫使我这样的蒟蒻花很长时间去思考,那些神犇的思维能力太强一句话题解就会做了orzorz

UPD:hzwer的题解比我的好多了。。十分清晰易懂

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=255;

long double dp[N][N],P[N],D[N],ans;
int n,m,T;

long double Qpow(long double x,int y){
long double ans=1.0;
while(y){
	if(y&1)ans=ans*x;
	x*=x;
	y>>=1;
}
return ans;
}

int main(){
freopen("4008.in","r",stdin);
freopen("4008.out","w",stdout);
scanf("%d",&T);
while(T--){
    scanf("%d %d",&n,&m);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
		double x,y;
		scanf("%lf %lf",&x,&y);
		P[i]=x;D[i]=y;
    }
    dp[0][m]=1.0;
    ans=0.0;
    for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=dp[i-1][j]*Qpow(1-P[i-1],j)+dp[i-1][j+1]*(1-Qpow(1-P[i-1],j+1));
			ans+=dp[i][j]*(1-Qpow(1-P[i],j))*D[i];
		}
    }
    printf("%.10lf\n",(double)ans);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
27
2016
0

[BZOJ3450] Tyvj1952 Easy

简单的期望DP

分三种情况考虑就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=300005;

int n;
double F[N],D[N];
char s[N];

int main(){
freopen("3450.in","r",stdin);
freopen("3450.out","w",stdout);
scanf("%d %s",&n,s+1);
for(int i=1;i<=n;i++){
    if(s[i]=='o'){F[i]=F[i-1]+D[i-1]*2+1;D[i]=D[i-1]+1;}
    if(s[i]=='x'){F[i]=F[i-1];D[i]=0;}
    if(s[i]=='?'){F[i]=F[i-1]+(D[i-1]*2+1)/2;D[i]=(D[i-1]+1)/2;}
}
printf("%.4lf\n",F[n]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
27
2016
0

[BZOJ3771] Triple

这题是FFT的应用

考虑构建指数型母函数,系数是物品的个数,指数是物品的价值

然后分成三种情况容斥一下

然后就不会了。。这怎么FFT啊

然后orz了Miskcoo大神的博客,不仅学会了怎么做,还优化了一下速度……

复数什么的直接无视,和正常的情况一样搞就行了

以后还是要多做题啊……

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;

const int N=262145;
const double Pi=acos(-1);

int An,n,Step,mx_val,Rev[N];

struct Complex{
double a,b;
Complex(){a=0.0,b=0.0;}
Complex(double sa,double sb){a=sa;b=sb;}
friend Complex operator+(Complex A,Complex B){return Complex(A.a+B.a,A.b+B.b);}
friend Complex operator-(Complex A,Complex B){return Complex(A.a-B.a,A.b-B.b);}
friend Complex operator*(Complex A,Complex B){return Complex(A.a*B.a-A.b*B.b,A.a*B.b+A.b*B.a);}
}A[N],B[N],C[N],div2=Complex(1.0/2.0,0.0),div3=Complex(1.0/3.0,0.0),div6=Complex(1.0/6.0,0.0);

void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
	Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
	for(int i=0;i<n;i+=k<<1){
		Complex wkj=Complex(1.0,0.0);
        for(int j=0;j<k;j++){
			Complex a=x[i+j],b=x[i+j+k]*wkj;
			x[i+j]=a+b;
			x[i+j+k]=a-b;
			wkj=wkj*wk;
        }
	}
}
if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;
}

int main(){
freopen("3771.in","r",stdin);
freopen("3771.out","w",stdout);
scanf("%d",&An);
for(int i=0;i<An;i++){
	int x;
	scanf("%d",&x);
	A[x].a+=1.0;
	B[x*2].a+=1.0;
	C[x*3].a+=1.0;
	if(3*x>mx_val)mx_val=3*x;
}
for(n=1,Step=0;n<mx_val;n<<=1,Step++);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);
FFT(B,1);
for(int i=0;i<n;i++)A[i]=A[i]*A[i]*A[i]*div6+(A[i]*(A[i]-B[i])-B[i])*div2+A[i];
FFT(A,-1);
for(int i=1;i<mx_val;i++)A[i]=A[i]+C[i]*div3;
for(int i=0;i<mx_val;i++){
	int x=(int)(A[i].a+0.5);
	if(x)printf("%d %d\n",i,x);
}
return 0;
}

 

Category: BZOJ | Tags: OI bzoj
4
26
2016
0

[BZOJ4246] 两个人的星座

考虑暴力求解

先枚举第一个点,把剩下的点全部扔到一个数组里面

然后极角排序,每次选择一个点和之前枚举的点作为这两个三角形中的两个点,然后乘法计数原理就可以了

注意需要对上面和下面各做一遍(因为两个点上下都有可能)

注意这样做会出现重复,具体就是枚举两个点重复一次和中间计算时上下各计算一次一共四次重复,所以总答案除以4就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
 
const int N=3005;
const double Pi=acos(-1);
 
int n,Top,cnt[2][3],test[N];
long long ans;
 
struct Point{
int x,y;
Point(){}
Point(int sa,int sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
}O;
 
double Atan(Point A){double x=atan2(A.y,A.x);return x>0?x:x+Pi;}
 
pair<Point,int> poi[N],St[N],St2[N];
pair<double,int> Stab[N];
 
void Cal(int col){
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=Top;i++)Stab[i]=make_pair(Atan(St[i].first-O),i);
sort(Stab+1,Stab+Top+1);
for(int i=1;i<=Top;i++)St2[i]=St[Stab[i].second];
for(int i=1;i<=Top;i++)St[i]=St2[i];
for(int i=1;i<=Top;i++){
    if(St[i].first.y<O.y || St[i].first.y==O.y && St[i].first.x>O.x)cnt[test[i]=0][St[i].second]++;
    else cnt[test[i]=1][St[i].second]++;
}
for(int i=1;i<=Top;i++){
    cnt[test[i]][St[i].second]--;
    int CanDoneFirst=1,CanDoneSecond=1;
    if(col!=0)CanDoneFirst*=cnt[0][0];
    if(col!=1)CanDoneFirst*=cnt[0][1];
    if(col!=2)CanDoneFirst*=cnt[0][2];
    if(St[i].second!=0)CanDoneSecond*=cnt[1][0];
    if(St[i].second!=1)CanDoneSecond*=cnt[1][1];
    if(St[i].second!=2)CanDoneSecond*=cnt[1][2];
    ans+=(long long)CanDoneFirst*CanDoneSecond;
    CanDoneFirst=1,CanDoneSecond=1;
    if(col!=0)CanDoneFirst*=cnt[1][0];
    if(col!=1)CanDoneFirst*=cnt[1][1];
    if(col!=2)CanDoneFirst*=cnt[1][2];
    if(St[i].second!=0)CanDoneSecond*=cnt[0][0];
    if(St[i].second!=1)CanDoneSecond*=cnt[0][1];
    if(St[i].second!=2)CanDoneSecond*=cnt[0][2];
    ans+=(long long)CanDoneFirst*CanDoneSecond;
    cnt[test[i]^=1][St[i].second]++;
}
}
 
int main(){
freopen("4246.in","r",stdin);
freopen("4246.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&poi[i].first.x,&poi[i].first.y,&poi[i].second);
}
for(int i=1;i<=n;i++){
    Top=0;
    for(int j=1;j<=n;j++)if(i!=j)St[++Top]=poi[j];
    O=poi[i].first;
    Cal(poi[i].second);
}
printf("%lld\n",ans/4);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
26
2016
0

[BZOJ1717] [Usaco2006 Dec]Milk Patterns 产奶的模式

二分+后缀数组

对于height分块然后二分判定就可以了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=20005;

int sa[N],rank[N],rank2[N],n,height[N],wa[N],ws[N],a[N],k;

bool cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}

void GetSA(int *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--){sa[--ws[x[i]]]=i;}
for(j=p=1;p<n;j*=2,m=p){
	for(p=0,i=n-j;i<n;i++)y[p++]=i;
	for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;
	for(i=1;i<m;i++)ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];
	for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void CalHeight(int *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k){
	for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
}

bool Check(int x){
int cnt,i=2;
while(1){
	while(i<=n && height[i]<x)i++;
	if(i>n)break;
	cnt=1;
	while(i<=n && height[i]>=x){cnt++;i++;}
	if(cnt>=k)return 1;
}
return 0;
}

int Div2(){
int l=1,r=n,ans=1;
while(l<=r){
	int mid=l+r>>1;
	if(Check(mid)){ans=mid;l=mid+1;}
	else r=mid-1;
}
return ans;
}

int main(){
freopen("1717.in","r",stdin);
freopen("1717.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
a[n]=0;
GetSA(a,sa,n+1,N-4);
CalHeight(a,sa,n);
printf("%d\n",Div2());
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
26
2016
0

[BZOJ1113] [Poi2008]海报PLA

简单的单调栈

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

int n,Stack[250005],Top,ans;

int main(){
freopen("1113.in","r",stdin);
freopen("1113.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
	int x,y;
	scanf("%d %d",&x,&y);
	while(Top && Stack[Top]>=y){if(Stack[Top]!=y)ans++;Top--;}
	Stack[++Top]=y;
}
printf("%d\n",ans+Top);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
25
2016
0

[BZOJ1086] [SCOI2005]王室联邦

树上分块

对于每个子树维护siz

大于B就把这个子树和当前的省作为一块丢掉(这一块一定小于2*B,否则一定会在这个子树的内部再分块)

最后剩下的点在下面找一个子树丢进去就行了,必定满足条件

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=2005;

int n,B,en,h[N],St[N],belong[N],St_size,siz[N],home[N],hcnt;

struct Edge{
int b,next;
}e[N];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void DFS(int u,int fa){
St[++St_size]=u;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v==fa)continue;
	DFS(v,u);
	if(siz[u]+siz[v]>=B){
		siz[u]=0;
		home[++hcnt]=u;
		while(St[St_size]!=u)belong[St[St_size--]]=hcnt;
	}
	else siz[u]+=siz[v];
}
siz[u]++;
}

void Paint(int u,int fa,int col){
if(!belong[u])belong[u]=col;
else col=belong[u];
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa)Paint(v,u,col);
}
}

int main(){
freopen("1086.in","r",stdin);
freopen("1086.out","w",stdout);
scanf("%d %d",&n,&B);
if(n<B){puts("0");return 0;}
for(int i=1;i<n;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdge(u,v);
	AddEdge(v,u);
}
DFS(1,0);
if(!hcnt)home[++hcnt]=1;
Paint(1,0,hcnt);
printf("%d\n",hcnt);
for(int i=1;i<=n;i++)printf("%d ",belong[i]);
putchar('\n');
for(int i=1;i<=hcnt;i++)printf("%d ",home[i]);
putchar('\n');
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
25
2016
0

[BZOJ2194] 快速傅立叶之二

把FFT模版略微改动一下

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
 
const int N=270000;
const double Pi=acos(-1);
 
int An,Bn,Cn,n,Rev[N],Step;
 
struct Complex{
double a,b;
Complex(){}
Complex(double sa,double sb){a=sa;b=sb;}
friend Complex operator+(Complex A,Complex B){return Complex(A.a+B.a,A.b+B.b);}
friend Complex operator-(Complex A,Complex B){return Complex(A.a-B.a,A.b-B.b);}
friend Complex operator*(Complex A,Complex B){return Complex(A.a*B.a-A.b*B.b,A.a*B.b+A.b*B.a);}
}A[N],B[N],C[N];
 
void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
        Complex wkj=Complex(1.0,0.0);
        for(int j=0;j<k;j++){
            Complex a=x[i+j],b=x[i+j+k]*wkj;
            x[i+j]=a+b;
            x[i+j+k]=a-b;
            wkj=wkj*wk;
        }
    }
}
if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;
}
 
int main(){
freopen("2194.in","r",stdin);
freopen("2194.out","w",stdout);
scanf("%d",&An);
Bn=An;Cn=An+Bn-1;
for(int i=0;i<An;i++)scanf("%lf %lf",&A[i].a,&B[An-i].a);
for(n=1,Step=0;n<Cn;n<<=1,Step++);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=Cn/2+1;i<=Cn;i++)printf("%d\n",(int)(C[i].a+0.5));
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
23
2016
0

[BZOJ2049] [Sdoi2008]Cave 洞穴勘测

LCT

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m;

struct Node{
int rev;
Node *ch[2],*fa;
Node(Node *fat);
void Pushdown();
}*root[10005],*Null;

Node::Node(Node *fat){
fa=fat;
ch[0]=ch[1]=Null;
rev=0;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
}

int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}

void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else {Rotate(x,0);Rotate(x,1);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}

void Link(Node *u,Node *v){
Makeroot(u);
u->fa=v;
}

void Cut(Node *u,Node *v){
Makeroot(u);
Access(v);
Splay(v);
if(v->ch[0]==u){v->ch[0]=Null;u->fa=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

Node *GetNull(){
Node *p=new Node(Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->rev=0;
return p;
}

Node *ToLct(int x){
return root[x];
}

int main(){
freopen("2049.in","r",stdin);
freopen("2049.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=n;i++)root[i]=new Node(Null);
for(int i=1;i<=m;i++){
	int u,v;
	char s[10];
    scanf("%s %d %d",s,&u,&v);
    if(s[0]=='C')Link(ToLct(u),ToLct(v));
    if(s[0]=='D')Cut(ToLct(u),ToLct(v));
    if(s[0]=='Q'){
		if(Find(ToLct(u))==Find(ToLct(v)))puts("Yes");
		else puts("No");
	}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
23
2016
0

[BZOJ2662] [BeiJing wc2012]冻结

水题可以愉悦身心

分层图SPFA

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

int n,m,k,en,h[55],D[55][55],flag[55][55],ans;

struct Que{
int a,b;
Que(int sa,int sb){a=sa;b=sb;}
};

queue<Que> Q;

struct Edge{
int b,v,next;
}e[2005];

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void SPFA(){
memset(D,127,sizeof(D));
flag[0][1]=1;
D[0][1]=0;
Q.push(Que(0,1));
while(!Q.empty()){
	Que u=Q.front();
	Q.pop();
	flag[u.a][u.b]=0;
    for(int i=h[u.b];i;i=e[i].next){
		int v=e[i].b;
		if(D[u.a][v]>D[u.a][u.b]+e[i].v){
			D[u.a][v]=D[u.a][u.b]+e[i].v;
            if(!flag[u.a][v]){
				flag[u.a][v]=1;
                Q.push(Que(u.a,v));
            }
		}
    }
    if(u.a<k){
		for(int i=h[u.b];i;i=e[i].next){
			int v=e[i].b;
			if(D[u.a+1][v]>D[u.a][u.b]+e[i].v/2){
				D[u.a+1][v]=D[u.a][u.b]+e[i].v/2;
				if(!flag[u.a+1][v]){
					flag[u.a+1][v]=1;
					Q.push(Que(u.a+1,v));
				}
			}
		}
    }
}
ans=D[0][n];
for(int i=1;i<=k;i++)ans=min(ans,D[i][n]);
}

int main(){
freopen("2662.in","r",stdin);
freopen("2662.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=m;i++){
	int u,v,w;
	scanf("%d %d %d",&u,&v,&w);
	AddEdge(u,v,w);
	AddEdge(v,u,w);
}
SPFA();
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com