4
30
2016
0

后缀数组练习

CTSC&APIO感觉自己水平太低,完全没法做……

所以打算利用在北京的这段时间提高一下自己的OI水平

后缀数组虽然会写,但是仅限于会敲模版。。

所以我打算把罗穗骞论文里面的所有题写一遍

----------------------------------------

POJ 2774

两个串连一起搞完后缀数组然后求height最大值判断一下前后是否分别属于两个不同的串就好了

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

const int N=200005;

int n1,n2,n,rank[N],sa[N],rank2[N],wa[N],ws[N],height[N];
char s1[N],s2[N],s[2*N];

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

void GetSA(char *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<<=1,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(char *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 Diff(int x){return (sa[x]<n1 && sa[x-1]>=n1)||(sa[x]>=n1 && sa[x-1]<n1);}

int Solve(){
int MxHeight=0;
for(int i=2;i<=n;i++){
	if(height[i]>MxHeight && Diff(i))MxHeight=height[i];
}
return MxHeight;
}

int main(){
freopen("2774.in","r",stdin);
freopen("2774.out","w",stdout);
scanf("%s %s",s1,s2);
n1=strlen(s1);
n2=strlen(s2);
n=n1+n2;
for(int i=0;i<n1;i++)s[i]=s1[i];
for(int i=n1;i<n;i++)s[i]=s2[i-n1];
s[n]=0;
GetSA(s,sa,n+1,128);
CalHeight(s,sa,n);
printf("%d\n",Solve());
return 0;
}

----------------------------------------

POJ 1743

先差分,然后二分答案k,然后对于height分组(height[i]记录的是sa[i]和sa[i-1]的LCP),那么因为字典序相邻的后缀在sa里的顺序是连续的,那么我们对于判定答案k是否合法的方法就是找到连续的height,它们的值都不小于k(保证重复的串长大于等于k),然后如果组内最靠前和最靠后的位置差也大于等于k,那么这个方案就是合法的。

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

const int N=200005,INF=2100000000;

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

int Abs(int x){return x>0?x:-x;}
int 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<<=1,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++);
}
}

int Solve(int k){
int i=2,Mx,Mn;
while(1){
    while(i<=n && height[i]<k)i++;
    if(i>n)break;
    Mx=sa[i-1];Mn=sa[i-1];
    while(i<=n && height[i]>=k){Mn=min(Mn,sa[i]);Mx=max(Mx,sa[i]);i++;}
    if(Mx-Mn>=k)return 1;
}
return 0;
}

int Div(){
int l=4,r=n*2,ans=0;
while(l<=r){
    int mid=l+r>>1;
    if(Solve(mid)){l=mid+1;ans=mid;}
    else r=mid-1;
}
ans++;
return ans<5?0:ans;
}

int main(){
freopen("1743.in","r",stdin);
freopen("1743.out","w",stdout);
while(scanf("%d",&n),n){
    for(int i=0;i<n;i++)scanf("%d",&s[i]);
    if(n<10){puts("0");continue;}
    n--;
    for(int i=0;i<n;i++)s[i]=s[i+1]-s[i]+89;
    s[n]=0;
    for(int i=0;i<N;i++)wa[i]=ws[i]=0;
    GetSA(s,sa,n+1,200);
    Calheight(s,sa,n);
    printf("%d\n",Div());
}
return 0;
}

----------------------------------------

Category: OI | Tags: OI
4
30
2016
0

[BZOJ4519] [Cqoi2016]不同的最小割

map直接上

其他同ZJOI2011 最小割

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<cstdlib>
using namespace std;
 
const int N=8505,P=855;
const long long INF=210000000000000ll;
 
int n,m,en,h[P],mark[P],cur[P],level[P],S,T,a[P],tmp[P],Ans;
long long ans[P][P];
queue<int> Q;
map<long long,int> Mp;
 
struct Edge{
int b,next,back;
long long f;
}e[N*4];
 
void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}
 
int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}
 
long long DFS(int u,long long flow){
if(u==T)return flow;
long long f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    long long fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        f-=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
 
long long Dinic(){
long long ans=0;
while(BFS()){for(int i=1;i<=n;i++)cur[i]=h[i];ans+=DFS(S,INF);}
return ans;
}
 
void Rebuild(){
for(int i=1;i<=en;i+=2){
    e[i].f=e[i].f+e[i+1].f;
    e[i+1].f=0;
}
}
 
void dfs(int u){
mark[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(e[i].f && !mark[v])dfs(v);
}
}
 
void Solve(int l,int r){
if(l==r)return;
Rebuild();S=a[l];T=a[r];
long long flow=Dinic();
int L=l,R=r;
memset(mark,0,sizeof(mark));
dfs(S);
for(int i=1;i<=n;i++){
    if(!mark[i])continue;
    for(int j=1;j<=n;j++){
        if(!mark[j])ans[i][j]=ans[j][i]=min(ans[i][j],flow);
    }
}
for(int i=l;i<=r;i++){if(mark[a[i]])tmp[L++]=a[i];else tmp[R--]=a[i];}
for(int i=l;i<=r;i++)a[i]=tmp[i];
Solve(l,L-1);Solve(R+1,r);
}
 
int main(){
scanf("%d %d",&n,&m);
memset(ans,127,sizeof(ans));
for(int i=1;i<=n;i++)a[i]=i;
for(int i=1;i<=m;i++){
    int sa,sb;
    long long sc;
    scanf("%d %d %lld",&sa,&sb,&sc);
    AddEdge(sa,sb,sc);
    AddEdge(sb,sa,sc);
}
Solve(1,n);
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        if(Mp[ans[i][j]]==0){
            Mp[ans[i][j]]=1;
            Ans++;
        }
    }
}
printf("%d\n",Ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
30
2016
0

[BZOJ2229] [Zjoi2011]最小割

这题我写了很长很长时间。。。

SB错误1:无向图要建双向边,然而我只建了单向边……

SB"错误"2:要加当前弧优化!一开始偷懒没加,然后TLE了N次

分治最小割,直接上Gusfield算法

顺便庆祝lyz lyf wyx cjy大爷签了PKU一本线 太神了orzzzzzzzzzzzzz

我这种蒟蒻ZJOI完全不敢去……

要补一补ZJOI讲课的Gusfield和Stoer-wanger算法了

为什么重建边时直接均分流量是对的啊……我按照正常方法写的然后跑的奇慢无比

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

const int N=3005,P=155;
const long long INF=210000000000000ll;

int n,m,en,h[P],q,level[P],S,T,a[P],mark[P],tmp[P],Data_Num,cur[P];
long long ans[P][P];
queue<int> Q;

struct Edges{
int a,b;
long long v;
}es[N];

struct Edge{
int b,next,back;
long long f;
}e[N*4];

void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
Q.push(S);
level[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
    for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}

long long DFS(int u,long long flow){
if(u==T)return flow;
long long f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    long long fl;
    if(level[u]+1==level[v] && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
		e[i].f-=fl;
		e[e[i].back].f+=fl;
        f-=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}

long long Dinic(){
long long ans=0;
while(BFS()){for(int i=1;i<=n;i++)cur[i]=h[i];ans+=DFS(S,INF);}
return ans;
}

void dfs(int u){
mark[u]=1;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(e[i].f && !mark[v])dfs(v);
}
}

void Build(){
en=0;
memset(h,0,sizeof(h));
for(int i=1;i<=m;i++)AddEdge(es[i].a,es[i].b,es[i].v),AddEdge(es[i].b,es[i].a,es[i].v);;
}

void Rebuild(){
for(int i=1;i<=en;i+=2){e[i].f=e[i+1].f+e[i].f;e[i+1].f=0;}
}

void Solve(int l,int r){
if(l==r)return;
Rebuild();S=a[l];T=a[r];
long long flow=Dinic();
int L=l,R=r;
memset(mark,0,sizeof(mark));
dfs(S);
for(int i=1;i<=n;i++){
	if(!mark[i])continue;
	for(int j=1;j<=n;j++){
		if(!mark[j])ans[i][j]=ans[j][i]=min(ans[i][j],flow);
	}
}
for(int i=l;i<=r;i++){
	if(mark[a[i]])tmp[L++]=a[i];
	else tmp[R--]=a[i];
}
for(int i=l;i<=r;i++)a[i]=tmp[i];
Solve(l,L-1);Solve(R+1,r);
}

int main(){
freopen("2229.in","r",stdin);
freopen("2229.out","w",stdout);
scanf("%d",&Data_Num);
while(Data_Num--){
	memset(ans,127,sizeof(ans));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d %d %lld",&es[i].a,&es[i].b,&es[i].v);
	for(int i=1;i<=n;i++)a[i]=i;
	Build();
	Solve(1,n);
	scanf("%d",&q);
	while(q--){
		int Ans=0;
		long long x;
		scanf("%lld",&x);
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(ans[i][j]<=x)Ans++;
			}
		}
		printf("%d\n",Ans);
	}
	puts("");
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
29
2016
0

CTSC2016&APIO2016 游记

先坑着

这两次考试再也不能炸了。毕竟已经炸了NOIP2015,WC2016,AHOI2016,再炸就真GG了

----------------------------------------

并不想写游记了

两场考试全部纸牌回家

还是写写UOJ群聚吧

嗯……看到了VFK好萌哒

还有好多神犇……

完全忝列其中

VFK还向每个人敬了酒(当然不认识我了)

----------------------------------------

热烈祝贺Newnode成为中国国家队队长!

lzz没考好rank6,面试被刷了

也就这么多了吧

Category: 随笔 | Tags: 随笔
4
28
2016
0

[BZOJ4025] 二分图

这题我写+调了一晚上……代码能力太差

首先忘了LCT怎么维护生成树,看了半天以前的代码

然后写了1.5h。。然后过不了样例

调试

调试

调试

呀!原来这里写错了!改!

样例还是不对……

调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试

Splay写错了!改!

样例过了!

提交,AC了!

真心写不动题解了……Claris题解

现在才真正感受到wzf AHOI2016Day1考场写12k+代码AK的可怕……我写调了将近3h,然而这代码4k不到……

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

const int N=200005,INF=2100000000;

int n,m,T,cnt,in[N],on[N];

struct Line{int v;Line *next;Line(int ux=0){v=ux;next=NULL;}}*Sline[N],*Eline[N];
void AddLineS(int u,int v){Line *x=new Line(v);x->next=Sline[u];Sline[u]=x;}
void AddLineE(int u,int v){Line *x=new Line(v);x->next=Eline[u];Eline[u]=x;}

struct Edge{
int u,v,t;
}e[N];

struct Node{
int v,rev,sum,id;
Node *ch[2],*fa,*mne;
Node(){}
Node(int vx,int vy);
void Pushdown();
void Pushup();
}*tree[2*N],*Null;

Node::Node(int val,int vy){
v=val;
id=vy;
sum=id>n;
rev=0;
ch[0]=ch[1]=fa=Null;
mne=this;
}

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

void Node::Pushup(){
mne=this;
sum=id>n;
if(ch[0]!=Null){if(mne->v>ch[0]->mne->v)mne=ch[0]->mne;sum+=ch[0]->sum;}
if(ch[1]!=Null){if(mne->v>ch[1]->mne->v)mne=ch[1]->mne;sum+=ch[1]->sum;}
}

bool 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();}
Node *GetNull(){Node *p=new Node(INF,0);p->v=INF;p->id=p->sum=p->rev=0;p->ch[0]=p->ch[1]=p->fa=p->mne=p;return p;}

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;
y->Pushup();
x->Pushup();
}

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[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}
void Makeroot(Node *x){Access(x);Splay(x);x->rev^=1;swap(x->ch[0],x->ch[1]);}
void Link(Node *x,Node *y){Makeroot(x);x->fa=y;}
void Cut(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}}
Node *Find(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}
Node *ToLct(int x){return tree[x];}

void Add(int id){
int u=e[id].u,v=e[id].v;
if(u==v){cnt++;in[id]=1;return;}
if(Find(ToLct(u))!=Find(ToLct(v))){on[id]=1;Link(ToLct(u),ToLct(id+n));Link(ToLct(v),ToLct(id+n));}
else {
	Makeroot(ToLct(u));
	Access(ToLct(v));
	Splay(ToLct(v));
	int idx=ToLct(v)->mne->id-n;
    if(e[idx].t<e[id].t){
		if(ToLct(v)->sum&1^1){in[idx]=1;cnt++;}
		Cut(ToLct(e[idx].u),ToLct(idx+n));Cut(ToLct(e[idx].v),ToLct(idx+n));
		Link(ToLct(u),ToLct(id+n));Link(ToLct(v),ToLct(id+n));
		on[idx]=0;on[id]=1;
    }
    else if(ToLct(v)->sum&1^1){in[id]=1;cnt++;}
}
}

void Del(int id){
if(in[id]){in[id]=0;cnt--;}else if(on[id]){Cut(ToLct(e[id].u),ToLct(id+n));Cut(ToLct(e[id].v),ToLct(id+n));}
}

int main(){
freopen("4025.in","r",stdin);
freopen("4025.out","w",stdout);
scanf("%d %d %d",&n,&m,&T);
Null=GetNull();
for(int i=1;i<=n;i++)tree[i]=new Node(INF,i);
for(int i=1;i<=m;i++){
	int x;
	scanf("%d %d %d %d",&e[i].u,&e[i].v,&x,&e[i].t);
	AddLineS(x,i);
	AddLineE(e[i].t,i);
	tree[i+n]=new Node(e[i].t,i+n);
}
for(int i=0;i<T;i++){
	for(Line *j=Sline[i];j!=NULL;j=j->next)Add(j->v);
	for(Line *j=Eline[i];j!=NULL;j=j->next)Del(j->v);
	puts(cnt?"No":"Yes");
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
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

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