5月 | 2017 | OceanEye's Blog

@OceanEye7年前

05/12

17:25

BZOJ3884

降幂大法:-D
安利Tangjz题解
出题人的题解也是很强的qwq

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <map>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;

int k;
map<int,int> f;

int ksm(int x,int a,int mod)
{
	ll ret=1;
	for(;a;a>>=1)
	{
		if(a&1) ret=ret*x%mod;
		x=(ll)x*x%mod;
	}
	return (int)ret;
}

int calc_phi(int x)
{
	int ret=x;
	for(int i=2;i*i<=x;i++) if(x%i==0)
	{
		ret-=ret/i;
		while(x%i==0) x/=i;
	}
	if(x>1) ret-=ret/x;
	return ret;
}

int solve(int p)
{
	if(f.count(p)) return f[p];
	int phi=calc_phi(p);
	return f[p]=ksm(2,solve(phi)+phi,p);
}

int T;

int main()
{
	f[1]=0;
	for(read(T);T;T--) { read(k); printf("%d\n",solve(k)); }
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <map>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

int k;

map<int,int> f;

int ksm(int x,int a,int mod)

{

ll ret=1;

for(;a;a>>=1)

{

if(a&1) ret=ret*x%mod;

x=(ll)x*x%mod;

}

return (int)ret;

}

int calc_phi(int x)

{

int ret=x;

for(int i=2;i*i<=x;i++) if(x%i==0)

{

ret-=ret/i;

while(x%i==0) x/=i;

}

if(x>1) ret-=ret/x;

return ret;

}

int solve(int p)

{

if(f.count(p)) return f[p];

int phi=calc_phi(p);

return f[p]=ksm(2,solve(phi)+phi,p);

}

int T;

int main()

{

f[1]=0;

for(read(T);T;T--) { read(k); printf("%d\n",solve(k)); }

return 0;

}

BZOJ3884

@OceanEye7年前

05/11

16:46

BZOJ1227

OceanEye 撰写 BZOJ 树状数组组合数无回复

这题很裸，离散化一维~~本来想写个动态开点的线段树的~~之后逐行处理答案。

大概就是经过一个点就更改对应节点上的value，这个值要用组合数来算一下。

懒得看怎么处理附属就只去看了HZWER的题解……后来自己写了个很暴力的东西:-D。

具体怎么做下面也有:-D大力安利HZWER

代码

/**************************************************************
    Problem: 1227
    User: OceanEYe
    Language: C++
    Result: Accepted
    Time:2304 ms
    Memory:3636 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define P 2147483648LL
char cc; int C;
template <class T>
void read( T &x ){
    x=0; cc=getchar(); C=1;
    while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
    while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
    x*=C;
}
 
using namespace std;
#define N 100010
#define lb(x) (x&-x)
int Arr[N];
inline void add(int pos,int val){
    while(pos<=N) { Arr[pos]+=val; pos+=lb(pos); }
}
 
inline int query(int pos){
    unsigned int ret=0;
    while(pos) { ret+=Arr[pos]; pos-=lb(pos); }
    return ret;
}
#undef lb
 
struct pt
{
    int x,y;
}pool[N];
bool comp(const pt &x,const pt &y){
    return x.x==y.x?x.y<y.y:x.x<y.x;
}
int bin[N],cnt[N],_[N],n,a,b,k;
int calc(int x,int k){
    if(x<k) return 0;
    ll ret=1;
    for(int i=1;i<=k;i++) ret=(ll)ret*(x-i+1)/i;
    return ret%P;
}
int ans;
void solve(){
    int tmp,node2,__;
    for(int node=1;node<=n;){
        tmp=1; node2=node; __=0;
        while(pool[node2].x==pool[node2+1].x) node2++,tmp++;
        for(;node<node2;node++){
            __++;
            ans+=(ll)(query(pool[node+1].y-1)-query(pool[node].y))*calc(__,k)*calc(tmp-__,k)%P;
            add(pool[node].y,(ll)-calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P);
            _[pool[node].y]++;
            add(pool[node].y,(ll)calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P);
        }
        add(pool[node].y,(ll)-calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P);
        _[pool[node].y]++;
        add(pool[node].y,(ll)calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P);
        node=node2+1;
    }
}
 
void pre(){
    read(a); read(b);
    read(n);
    for(int i=1;i<=n;i++)
    {
        read(pool[i].x);
        read(pool[i].y);
        bin[i]=pool[i].y;
    }
    sort(bin+1,bin+1+n);
    for(int i=1;i<=n;i++)
    {
        pool[i].y=lower_bound(bin+1,bin+1+n,pool[i].y)-bin;
        cnt[pool[i].y]++;
    }
    sort(pool+1,pool+1+n,comp);
    read(k);
}
 
int main(){
    pre();
    solve();
    if(ans<0) ans+=P;
    printf("%d",ans);
    return 0;
}

100

101

102

/**************************************************************

Problem: 1227

User: OceanEYe

Language: C++

Result: Accepted

Time:2304 ms

Memory:3636 kb

****************************************************************/

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

#define P 2147483648LL

char cc; int C;

template <class T>

void read( T &x ){

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

#define lb(x) (x&-x)

int Arr[N];

inline void add(int pos,int val){

while(pos<=N) { Arr[pos]+=val; pos+=lb(pos); }

}

inline int query(int pos){

unsigned int ret=0;

while(pos) { ret+=Arr[pos]; pos-=lb(pos); }

return ret;

}

#undef lb

struct pt

{

int x,y;

}pool[N];

bool comp(const pt &x,const pt &y){

return x.x==y.x?x.y<y.y:x.x<y.x;

}

int bin[N],cnt[N],_[N],n,a,b,k;

int calc(int x,int k){

if(x<k) return 0;

ll ret=1;

for(int i=1;i<=k;i++) ret=(ll)ret*(x-i+1)/i;

return ret%P;

}

int ans;

void solve(){

int tmp,node2,__;

for(int node=1;node<=n;){

tmp=1; node2=node; __=0;

while(pool[node2].x==pool[node2+1].x) node2++,tmp++;

for(;node<node2;node++){

__++;

ans+=(ll)(query(pool[node+1].y-1)-query(pool[node].y))*calc(__,k)*calc(tmp-__,k)%P;

add(pool[node].y,(ll)-calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P);

_[pool[node].y]++;

add(pool[node].y,(ll)calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P);

}

add(pool[node].y,(ll)-calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P);

_[pool[node].y]++;

add(pool[node].y,(ll)calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P);

node=node2+1;

}

void pre(){

read(a); read(b);

read(n);

for(int i=1;i<=n;i++)

{

read(pool[i].x);

read(pool[i].y);

bin[i]=pool[i].y;

}

sort(bin+1,bin+1+n);

for(int i=1;i<=n;i++)

{

pool[i].y=lower_bound(bin+1,bin+1+n,pool[i].y)-bin;

cnt[pool[i].y]++;

}

sort(pool+1,pool+1+n,comp);

read(k);

}

int main(){

pre();

solve();

if(ans<0) ans+=P;

printf("%d",ans);

return 0;

}

BZOJ1227

@OceanEye7年前

05/9

21:15

BZOJ4808

OceanEye 撰写 BZOJ 最小割网络流无回复

题目名字很有趣

但是看完题面会发现这就是个黑白染色最小割

网络流大法好，ISAP直接跑

好像这几道题是一个系列的233

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>
#define ll long long 
#define INF 1000000000
char cc; int C;
#define p(x) ('0'<=x&&x<='9')
template <class T>
void read( T &x )
{
	cc=getchar(); C=1; x=0;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}
using namespace std;

#define N 205
#define E 800000
#define S 0
#define T 40009

struct Tedge
{
	int from,to,cap,flow;
}edge[E];
int e_tot,NXT[E],fst[40010];
#define TO edge[i].to
#define FROM edge[i].from
#define FL (edge[i].cap-edge[i].flow)
void add_e(int _,int __,int cap)
{
	edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].cap=cap; edge[e_tot].flow=0;
	NXT[e_tot]=fst[_]; fst[_]=e_tot++;
	edge[e_tot].from=__; edge[e_tot].to=_; edge[e_tot].cap=cap; edge[e_tot].flow=cap;
	NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}

int d[40010],p[40010],cur[40010],cnt[40010];
int mp[N][N],n,m,tot;

bool bfs()
{
	int x,i;
	d[T]=1;
	queue <int> Q;
	Q.push(T);
	while(!Q.empty())
	{
		x=Q.front(); Q.pop();
		cnt[d[x]]++;
		for(i=fst[x];~i;i=NXT[i])
		{
			if(d[TO]||FL) continue;
			d[TO]=d[x]+1;
			Q.push(TO);
		}
	}
	return d[S]!=0;
}

int Augment()
{
	int node,ret,i;
	node=T; ret=INF;
	while(node!=S)
	{
		i=p[node];
		ret=min(ret,FL);
		node=FROM;
	}
	node=T;
	while(node!=S)
	{
		i=p[node];
		edge[i].flow+=ret;
		edge[i^1].flow-=ret;
		node=FROM;
	}
	return ret;
}

int ISAP()
{
	if(!bfs()) return 0;
	int node=S,ret=0,M,i;
	bool flag;
	for(int i=0;i<40010;i++) cur[i]=fst[i];
	while(d[S]<=tot+2)
	{
		if(node==T)
		{
			ret+=Augment();
			node=S;
		}
		flag=false;
		for(i=cur[node];~i;i=NXT[i])
			if(d[TO]==d[node]-1&&FL)
			{
				flag=true;
				p[TO]=cur[node]=i;
				node=TO;
				break;
			}
		if(flag) continue;
		M=tot+5;
		for(cur[node]=i=fst[node];~i;i=NXT[i])
			if(FL) M=min(M,d[TO]+1);
		if(!--cnt[d[node]]) return ret;
		cnt[d[node]=M]++;
		node!=S?node=edge[p[node]].from:node=S;
	}
	return ret;
}

const int _x[8]={1,1,2,2,-1,-1,-2,-2},_y[8]={2,-2,1,-1,2,-2,1,-1};

#define calc(x,y) ( (x-1)*m+y )

void pre()
{
	memset(fst,-1,sizeof(fst));
	read(n); read(m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) read(mp[i][j]);
	int x,y,pt;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j]) continue;
			tot++;
			pt=calc(i,j);
			if((i^j)&1)
			{
				add_e(S,pt,1);
				for(int k=0;k<8;k++)
				{
					x=_x[k]+i; y=_y[k]+j;
					if(mp[x][y])continue;
					if(x>n||x<=0||y>m||y<=0) continue;
					add_e(pt,calc(x,y),INF);
				}
			}
			else
				add_e(pt,T,1);
		}
}

int main()
{
//	freopen("BZOJ4808.in","r",stdin);
	pre();
	printf("%d",tot-ISAP());
	return 0;
}

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

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <queue>

#define ll long long

#define INF 1000000000

char cc; int C;

#define p(x) ('0'<=x&&x<='9')

template <class T>

void read( T &x )

{

cc=getchar(); C=1; x=0;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 205

#define E 800000

#define S 0

#define T 40009

struct Tedge

{

int from,to,cap,flow;

}edge[E];

int e_tot,NXT[E],fst[40010];

#define TO edge[i].to

#define FROM edge[i].from

#define FL (edge[i].cap-edge[i].flow)

void add_e(int _,int __,int cap)

{

edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].cap=cap; edge[e_tot].flow=0;

NXT[e_tot]=fst[_]; fst[_]=e_tot++;

edge[e_tot].from=__; edge[e_tot].to=_; edge[e_tot].cap=cap; edge[e_tot].flow=cap;

NXT[e_tot]=fst[__]; fst[__]=e_tot++;

}

int d[40010],p[40010],cur[40010],cnt[40010];

int mp[N][N],n,m,tot;

bool bfs()

{

int x,i;

d[T]=1;

queue <int> Q;

Q.push(T);

while(!Q.empty())

{

x=Q.front(); Q.pop();

cnt[d[x]]++;

for(i=fst[x];~i;i=NXT[i])

{

if(d[TO]||FL) continue;

d[TO]=d[x]+1;

Q.push(TO);

}

return d[S]!=0;

}

int Augment()

{

int node,ret,i;

node=T; ret=INF;

while(node!=S)

{

i=p[node];

ret=min(ret,FL);

node=FROM;

}

node=T;

while(node!=S)

{

i=p[node];

edge[i].flow+=ret;

edge[i^1].flow-=ret;

node=FROM;

}

return ret;

}

int ISAP()

{

if(!bfs()) return 0;

int node=S,ret=0,M,i;

bool flag;

for(int i=0;i<40010;i++) cur[i]=fst[i];

while(d[S]<=tot+2)

{

if(node==T)

{

ret+=Augment();

node=S;

}

flag=false;

for(i=cur[node];~i;i=NXT[i])

if(d[TO]==d[node]-1&&FL)

{

flag=true;

p[TO]=cur[node]=i;

node=TO;

break;

}

if(flag) continue;

M=tot+5;

for(cur[node]=i=fst[node];~i;i=NXT[i])

if(FL) M=min(M,d[TO]+1);

if(!--cnt[d[node]]) return ret;

cnt[d[node]=M]++;

node!=S?node=edge[p[node]].from:node=S;

}

return ret;

}

const int _x[8]={1,1,2,2,-1,-1,-2,-2},_y[8]={2,-2,1,-1,2,-2,1,-1};

#define calc(x,y) ( (x-1)*m+y )

void pre()

{

memset(fst,-1,sizeof(fst));

read(n); read(m);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++) read(mp[i][j]);

int x,y,pt;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

{

if(mp[i][j]) continue;

tot++;

pt=calc(i,j);

if((i^j)&1)

{

add_e(S,pt,1);

for(int k=0;k<8;k++)

{

x=_x[k]+i; y=_y[k]+j;

if(mp[x][y])continue;

if(x>n||x<=0||y>m||y<=0) continue;

add_e(pt,calc(x,y),INF);

}

else

add_e(pt,T,1);

}

int main()

{

// freopen("BZOJ4808.in","r",stdin);

pre();

printf("%d",tot-ISAP());

return 0;

}

BZOJ4808

@OceanEye7年前

05/7

22:56

BZOJ2434

OceanEye 撰写 AC自动机 BZOJ DFS序树树状数组无回复

AC自动机的好题，充分利用了fail树的性质

性质：S串中每个包含了T的后缀的fail指针一定经过若干层指向T

fail指针不成环

把fail树上的点dfs重标号

处理单个询问时可以把S串中的每个节点的DFS序丢进树状数组里面

查询T对应节点的DFS区间即可

处理许多询问的话离线处理即可

为了保证在树上不跑 \(x^2\) 次

可以模拟之前插入节点的方式来计算……

当然开个vector在节点上记录id也是可行的……

代码应该很好看懂

[但是我写的代码一般都巨长所以没多少人看哈哈哈]

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;

#define N 100010
#define E 200010
#define BASE 'a'
#define root 0

#define lb(x) (x&-x)
int Arr[N];
void add(int pos)
{ while(pos<=N) { Arr[pos]++; pos+=lb(pos); } }
void dec(int pos)
{ while(pos<=N) { Arr[pos]--; pos+=lb(pos); } }
int query(int pos)
{
	int ret=0;
	while(pos) { ret+=Arr[pos]; pos-=lb(pos); }
	return ret;
}

int TO[E],NXT[E],fst[N],e_tot;

void Link(int _,int __)
{
	TO[e_tot]=__;
	NXT[e_tot]=fst[_];
	fst[_]=e_tot++;
}

struct node
{
	int ch[26],fail;
	int fa;
	node() { for(int i=0;i<26;i++) ch[i]=-1; }
	vector <int> rec;
	int operator [] (const int &x) { return ch[x]; }
}pool[N];

int pcnt;
int tot,he[N],l[N],r[N],_____;

void dfs(int x)
{
	l[x]=++_____;
	for(int i=fst[x];~i;i=NXT[i]) dfs(TO[i]);
	r[x]=_____;
}

void build()
{
	int x,node;
	queue <int> Q;
	Q.push(0);
	while(!Q.empty())
	{
		x=Q.front(); Q.pop();
		for(int i=0;i<26;i++)
		{
			if(!~pool[x][i]) continue;
			node=pool[x].fail;
			while(~node&&!~pool[node][i]) node=pool[node].fail;
			if(~pool[node][i]) pool[pool[x][i]].fail=pool[node][i];
			else pool[pool[x][i]].fail=root;
			Q.push(pool[x][i]);
		}
	}
	for(int i=1;i<=pcnt;i++) Link(pool[i].fail,i);
}

char s[N];
int Len;

void pre()
{
	memset(fst,-1,sizeof(fst));
	int now=0;
	pool[0].fail=pool[0].fa=-1;
	scanf("%s",s);
	Len=strlen(s);
	for(int i=0;i<Len;i++)
	{
		if(s[i]=='P')
		{
			pool[now].rec.push_back(++tot);
			he[tot]=now;
			continue;
		}
		if(s[i]=='B')
		{
			now=pool[now].fa;
			continue;
		}
		s[i]-=BASE;
		if(!~pool[now][s[i]])
		{
			pool[now].ch[s[i]]=++pcnt;
			pool[pcnt].fa=now;
		}
		now=pool[now][s[i]];
	}
	build();
	dfs(0);
}
vector <int> q[N];
int m,node,ans[N],B;
int A[N];

void solve()
{
	int now=0,__=0;
	for(int i=0;i<Len;i++)
	{
		if(s[i]=='P')
		{
			__++;
			for(int k=0;k<q[__].size();k++)
				ans[q[__][k]]=query(r[he[A[q[__][k]]]])-query(l[he[A[q[__][k]]]]-1);
			continue;
		}
		if(s[i]=='B')
		{
			dec(l[now]);
			now=pool[now].fa;
			continue;
		}
		now=pool[now][s[i]];
		add(l[now]);
	}
}

int main()
{
//	freopen("BZOJ2434.in","r",stdin);
	pre();
	read(m);
	for(int i=1;i<=m;i++) { read(A[i]); read(B); q[B].push_back(i); }
	solve();
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

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

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <vector>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

#define E 200010

#define BASE 'a'

#define root 0

#define lb(x) (x&-x)

int Arr[N];

void add(int pos)

{ while(pos<=N) { Arr[pos]++; pos+=lb(pos); } }

void dec(int pos)

{ while(pos<=N) { Arr[pos]--; pos+=lb(pos); } }

int query(int pos)

{

int ret=0;

while(pos) { ret+=Arr[pos]; pos-=lb(pos); }

return ret;

}

int TO[E],NXT[E],fst[N],e_tot;

void Link(int _,int __)

{

TO[e_tot]=__;

NXT[e_tot]=fst[_];

fst[_]=e_tot++;

}

struct node

{

int ch[26],fail;

int fa;

node() { for(int i=0;i<26;i++) ch[i]=-1; }

vector <int> rec;

int operator [] (const int &x) { return ch[x]; }

}pool[N];

int pcnt;

int tot,he[N],l[N],r[N],_____;

void dfs(int x)

{

l[x]=++_____;

for(int i=fst[x];~i;i=NXT[i]) dfs(TO[i]);

r[x]=_____;

}

void build()

{

int x,node;

queue <int> Q;

Q.push(0);

while(!Q.empty())

{

x=Q.front(); Q.pop();

for(int i=0;i<26;i++)

{

if(!~pool[x][i]) continue;

node=pool[x].fail;

while(~node&&!~pool[node][i]) node=pool[node].fail;

if(~pool[node][i]) pool[pool[x][i]].fail=pool[node][i];

else pool[pool[x][i]].fail=root;

Q.push(pool[x][i]);

}

for(int i=1;i<=pcnt;i++) Link(pool[i].fail,i);

}

char s[N];

int Len;

void pre()

{

memset(fst,-1,sizeof(fst));

int now=0;

pool[0].fail=pool[0].fa=-1;

scanf("%s",s);

Len=strlen(s);

for(int i=0;i<Len;i++)

{

if(s[i]=='P')

{

pool[now].rec.push_back(++tot);

he[tot]=now;

continue;

}

if(s[i]=='B')

{

now=pool[now].fa;

continue;

}

s[i]-=BASE;

if(!~pool[now][s[i]])

{

pool[now].ch[s[i]]=++pcnt;

pool[pcnt].fa=now;

}

now=pool[now][s[i]];

}

build();

dfs(0);

}

vector <int> q[N];

int m,node,ans[N],B;

int A[N];

void solve()

{

int now=0,__=0;

for(int i=0;i<Len;i++)

{

if(s[i]=='P')

{

__++;

for(int k=0;k<q[__].size();k++)

ans[q[__][k]]=query(r[he[A[q[__][k]]]])-query(l[he[A[q[__][k]]]]-1);

continue;

}

if(s[i]=='B')

{

dec(l[now]);

now=pool[now].fa;

continue;

}

now=pool[now][s[i]];

add(l[now]);

}

int main()

{

// freopen("BZOJ2434.in","r",stdin);

pre();

read(m);

for(int i=1;i<=m;i++) { read(A[i]); read(B); q[B].push_back(i); }

solve();

for(int i=1;i<=m;i++) printf("%d\n",ans[i]);

return 0;

}

BZOJ2434

@OceanEye7年前

05/6

13:45

BZOJ2780

OceanEye 撰写 BZOJ SAM 无回复

广义后缀自动机

良心题，教会了我怎么写广义后缀自动机……

其实就是加完一个串之后把last丢回root接着跑啊qaq

这是非TRIE树版本

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int X;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); X=1;
	while(!p(cc)) { if(cc=='-') X=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=X;
}

using namespace std;

#define SIZ 100010
#define N 10010

namespace SAM
{
#define lb(x) (x&-x)
	int Arr[SIZ<<1];
	void inc(int x,int val) { while(x<=(SIZ<<1)) Arr[x]+=val,x+=lb(x); }
	int query(int pos)
	{
		int ret=0;
		while(pos) { ret+=Arr[pos]; pos-=lb(pos); }
		return ret;
	}
#undef lb
	struct node
	{
		int ch[26],fa;
		int len,cnt,col;
		int operator [] (const int &x) { return ch[x]; }
		node() { for(int i=0;i<26;i++) ch[i]=-1; }
	}pool[SIZ<<1];
	int pcnt,last,n,len;
	int C[SIZ<<1],que[SIZ<<1],ans[N];
#define root 0
#define NIL -1
#define BASE 'a'
	char ss[SIZ<<1];
	string s[N];
	bool inq[SIZ<<1];
	queue <int> Q;
	void build(int id)
	{
		last=0;
		int x,node,q,nq;
		char buf;
		len=strlen(ss);
		for(int i=0;i<len;i++)
		{
			buf=ss[i]; buf-=BASE;
			node=++pcnt; x=last;
			pool[node].len=pool[x].len+1;
			last=node;
			for(;~x&&!~pool[x][buf];x=pool[x].fa) pool[x].ch[buf]=node;
			if(!~x)
			{
				pool[node].fa=root;
				continue;
			}
			q=pool[x][buf];
			if(pool[x].len+1==pool[q].len) pool[node].fa=q;
			else
			{
				nq=++pcnt; pool[nq]=pool[q];
				pool[nq].len=pool[x].len+1;
				pool[q].fa=pool[node].fa=nq;
				for(;pool[x][buf]==q&&~x;x=pool[x].fa) pool[x].ch[buf]=nq;
			}
		}
	}
	void rebuild(int id)
	{
		int node=0,p;
		char buf;
		len=s[id].length();
		for(int i=0;i<len;i++)
		{
			buf=s[id][i];
			node=pool[node][buf-BASE];
			for(p=node;~p&&pool[p].col!=id;p=pool[p].fa)
			{
				pool[p].cnt++;
				pool[p].col=id;
			}
		}
	}
	void init(int _)
	{
		pool[root].fa=-1;
		pool[root].len=0;
		n=_;
		int x;
		for(int i=1;i<=n;i++)
		{
			scanf("%s",ss);
			s[i]=string(ss);
			build(i);
		}
		for(int i=1;i<=n;i++)
			rebuild(i);
	}
	int solve(char a[])
	{
		int len=strlen(a);
		int node=0;
		for(int i=0;i<len;i++)
		{
			a[i]-=BASE;
			if(!~pool[node][a[i]])return 0;
			node=pool[node][a[i]];
		}
		return pool[node].cnt;
	}
}

int n,m;
char T[SIZ<<2];
int main()
{
	freopen("BZOJ2780.in","r",stdin);
	read(n); read(m);
	SAM::init(n);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",T);
		printf("%d\n",SAM::solve(T));
	}
//	SAM::solve(0);
//	SAM::out();
	return 0;
}

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

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <string>

#include <vector>

#include <queue>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int X;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); X=1;

while(!p(cc)) { if(cc=='-') X=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=X;

}

using namespace std;

#define SIZ 100010

#define N 10010

namespace SAM

{

#define lb(x) (x&-x)

int Arr[SIZ<<1];

void inc(int x,int val) { while(x<=(SIZ<<1)) Arr[x]+=val,x+=lb(x); }

int query(int pos)

{

int ret=0;

while(pos) { ret+=Arr[pos]; pos-=lb(pos); }

return ret;

}

#undef lb

struct node

{

int ch[26],fa;

int len,cnt,col;

int operator [] (const int &x) { return ch[x]; }

node() { for(int i=0;i<26;i++) ch[i]=-1; }

}pool[SIZ<<1];

int pcnt,last,n,len;

int C[SIZ<<1],que[SIZ<<1],ans[N];

#define root 0

#define NIL -1

#define BASE 'a'

char ss[SIZ<<1];

string s[N];

bool inq[SIZ<<1];

queue <int> Q;

void build(int id)

{

last=0;

int x,node,q,nq;

char buf;

len=strlen(ss);

for(int i=0;i<len;i++)

{

buf=ss[i]; buf-=BASE;

node=++pcnt; x=last;

pool[node].len=pool[x].len+1;

last=node;

for(;~x&&!~pool[x][buf];x=pool[x].fa) pool[x].ch[buf]=node;

if(!~x)

{

pool[node].fa=root;

continue;

}

q=pool[x][buf];

if(pool[x].len+1==pool[q].len) pool[node].fa=q;

else

{

nq=++pcnt; pool[nq]=pool[q];

pool[nq].len=pool[x].len+1;

pool[q].fa=pool[node].fa=nq;

for(;pool[x][buf]==q&&~x;x=pool[x].fa) pool[x].ch[buf]=nq;

}

void rebuild(int id)

{

int node=0,p;

char buf;

len=s[id].length();

for(int i=0;i<len;i++)

{

buf=s[id][i];

node=pool[node][buf-BASE];

for(p=node;~p&&pool[p].col!=id;p=pool[p].fa)

{

pool[p].cnt++;

pool[p].col=id;

}

void init(int _)

{

pool[root].fa=-1;

pool[root].len=0;

n=_;

int x;

for(int i=1;i<=n;i++)

{

scanf("%s",ss);

s[i]=string(ss);

build(i);

}

for(int i=1;i<=n;i++)

rebuild(i);

}

int solve(char a[])

{

int len=strlen(a);

int node=0;

for(int i=0;i<len;i++)

{

a[i]-=BASE;

if(!~pool[node][a[i]])return 0;

node=pool[node][a[i]];

}

return pool[node].cnt;

}

int n,m;

char T[SIZ<<2];

int main()

{

freopen("BZOJ2780.in","r",stdin);

read(n); read(m);

SAM::init(n);

for(int i=1;i<=m;i++)

{

scanf("%s",T);

printf("%d\n",SAM::solve(T));

}

// SAM::solve(0);

// SAM::out();

return 0;

}

TRIE树什么的等会再写

BZOJ2780

@OceanEye7年前

05/4

19:49

BZOJ4318

OceanEye 撰写 BZOJ DP 期望DP 无回复

期望DP
题目要求维护三次方
所以要把二次和一次的期望也给维护了，接着考虑我们DP的含义是什么。
DP[3][i]=DP[3][i-1] + (增长幅度=x^3-(x-1)^3)*(增长概率=p[i])
上面那个三次方展开一下就可以做了

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;
#define N 100010

double dp[4][N],_;
int main()
{
	int n;
	read(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf",&_);
		dp[1][i]=(dp[1][i-1]+1)*_;
		dp[2][i]=(dp[2][i-1]+2*dp[1][i-1]+1)*_;
		dp[3][i]=dp[3][i-1]+(3*dp[2][i-1]+3*dp[1][i-1]+1)*_;
	}
	printf("%.1lf",dp[3][n]);
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

double dp[4][N],_;

int main()

{

int n;

read(n);

for(int i=1;i<=n;i++)

{

scanf("%lf",&_);

dp[1][i]=(dp[1][i-1]+1)*_;

dp[2][i]=(dp[2][i-1]+2*dp[1][i-1]+1)*_;

dp[3][i]=dp[3][i-1]+(3*dp[2][i-1]+3*dp[1][i-1]+1)*_;

}

printf("%.1lf",dp[3][n]);

return 0;

}

BZOJ4318

@OceanEye7年前

05/3

19:03

BZOJ4012

OceanEye 撰写二分查找动态点分治树无回复

某码农题
动态点分治[或者说点分树?]
转化一下[差分一下]就可以看出
要维护一棵树
可以在log~log方的时间复杂度内跑完整棵树的前缀和[1,l-1],[1,r]
于是用了点分树
树链剖分可不可以还没想过，目测是不行的
用了vector来控制空间
当然有大佬愿意写动态开点线段树或者平衡树也是很强的orz

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;

#define N 150010
#define Q 200010

int TO[N<<1],val[N<<1],NXT[N<<1],fst[N],e_tot;

void add_e(int _,int __,int ___)
{
	TO[e_tot]=__; val[e_tot]=___; NXT[e_tot]=fst[_]; fst[_]=e_tot++;
	TO[e_tot]=_; val[e_tot]=___; NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}

int age[N];
//

struct sav
{
	ll tot; int age;
	sav(int _,int __) : tot(_),age(__){}
	bool operator < (const sav &x) const { return age<x.age; }
};

struct rec
{
	int fa,id;
	int son[3],_tot;
	vector <sav> Arr[3];
	vector <sav> dist;
	int operator [] (const int &x) { return son[x]; }
}pool[N];

int root,siz[N],mxsiz[N],d[N],T,now;
bool use[N];

void dfs_push(int x,int f,ll dist)
{
	pool[now].dist.push_back(sav(dist,x));
	siz[x]=1;
	pool[now].Arr[pool[now]._tot].push_back(sav(dist,age[x]));
	for(int i=fst[x];~i;i=NXT[i])
	{
		if(use[TO[i]]||TO[i]==f) continue;
		dfs_push(TO[i],x,dist+val[i]);
		siz[x]+=siz[TO[i]];
	}
}

void getroot(int x,int f)
{
	siz[x]=1; mxsiz[x]=0;
	for(int i=fst[x];~i;i=NXT[i])
	{
		if(TO[i]==f||use[TO[i]]) continue;
		getroot(TO[i],x);
		siz[x]+=siz[TO[i]];
		mxsiz[x]=max(mxsiz[x],siz[TO[i]]);
	}
	mxsiz[x]=max(mxsiz[x],T-siz[x]);
	if(mxsiz[x]<mxsiz[root]) root=x;
}

void dfs_build(int x,int f)
{
	now=x;
	pool[x].fa=f;
	use[x]=true;
	for(int i=fst[x];~i;i=NXT[i])
	{
		if(use[TO[i]]) continue;
		root=0;
		T=siz[TO[i]];
		dfs_push(TO[i],0,val[i]);
		getroot(TO[i],0);
		pool[now].son[pool[now]._tot]=root;
		siz[root]=siz[TO[i]];
		sort(pool[now].Arr[pool[now]._tot].begin(),pool[now].Arr[pool[now]._tot].end());
		for(int j=1;j<pool[now].Arr[pool[now]._tot].size();j++)
			pool[now].Arr[pool[now]._tot][j].tot+=pool[now].Arr[pool[now]._tot][j-1].tot;
		pool[now]._tot++;
	}
	pool[now].dist.push_back(sav(0,now));
	sort(pool[now].dist.begin(),pool[now].dist.end());
	for(int i=0;i<pool[x]._tot;i++) dfs_build(pool[x][i],x);
}

int n,m,A;

void pre()
{
	int _,__,___;
	read(n); read(m); read(A);
	for(int i=1;i<=n;i++)
	{
		fst[i]=-1;
		read(age[i]);
		age[i]++;
	}
	for(int i=1;i<n;i++)
	{
		read(_); read(__); read(___);
		add_e(_,__,___);
	}
	T=n;
	mxsiz[0]=INF;
	getroot(1,0);
	dfs_build(root,0);
}

ll get_ans(int x,int l,int r)
{
	sav _(0,l-1),__(0,r);
	vector <sav> :: iterator it,it2;
	int L,R,pre=0,tot=0,___,S=x;
	ll dist=0,ret=0;
	while(x)
	{
		tot=0;
		for(int i=0;i<pool[x]._tot;i++)
		{
			if(pool[x][i]==pre)
				continue;
			it = upper_bound(pool[x].Arr[i].begin(),pool[x].Arr[i].end(),_);
			if(it!=pool[x].Arr[i].begin())
			{
				it--;
				ret-=it->tot;
				it++;
			}
			it2 = upper_bound(pool[x].Arr[i].begin(),pool[x].Arr[i].end(),__);
			if(it2!=pool[x].Arr[i].begin())
			{
				it2--;
				ret+=it2->tot;
				it2++;
			}
			tot+=distance(it,it2);
		}
		if(age[x]<=r&&age[x]>=l) tot++;
		it=lower_bound(pool[x].dist.begin(),pool[x].dist.end(),sav(0,S));
		dist=it->tot;
		ret+=dist*tot;
		pre=x;
		x=pool[x].fa;
	}
	return ret;
}

ll lastans;

int main()
{
//	freopen("BZOJ4012.in","r",stdin);
	ll _,__,___,L,R;
	pre();
	while(m--)
	{
		read(_); read(__); read(___);
		__+=lastans; ___+=lastans;
		__%=A; ___%=A;
		__++; ___++;
		L=min(__,___);
		R=max(__,___);
		lastans=get_ans(_,L,R);
		printf("%lld\n",lastans);
	}
	return 0;
}

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

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 150010

#define Q 200010

int TO[N<<1],val[N<<1],NXT[N<<1],fst[N],e_tot;

void add_e(int _,int __,int ___)

{

TO[e_tot]=__; val[e_tot]=___; NXT[e_tot]=fst[_]; fst[_]=e_tot++;

TO[e_tot]=_; val[e_tot]=___; NXT[e_tot]=fst[__]; fst[__]=e_tot++;

}

int age[N];

struct sav

{

ll tot; int age;

sav(int _,int __) : tot(_),age(__){}

bool operator < (const sav &x) const { return age<x.age; }

};

struct rec

{

int fa,id;

int son[3],_tot;

vector <sav> Arr[3];

vector <sav> dist;

int operator [] (const int &x) { return son[x]; }

}pool[N];

int root,siz[N],mxsiz[N],d[N],T,now;

bool use[N];

void dfs_push(int x,int f,ll dist)

{

pool[now].dist.push_back(sav(dist,x));

siz[x]=1;

pool[now].Arr[pool[now]._tot].push_back(sav(dist,age[x]));

for(int i=fst[x];~i;i=NXT[i])

{

if(use[TO[i]]||TO[i]==f) continue;

dfs_push(TO[i],x,dist+val[i]);

siz[x]+=siz[TO[i]];

}

void getroot(int x,int f)

{

siz[x]=1; mxsiz[x]=0;

for(int i=fst[x];~i;i=NXT[i])

{

if(TO[i]==f||use[TO[i]]) continue;

getroot(TO[i],x);

siz[x]+=siz[TO[i]];

mxsiz[x]=max(mxsiz[x],siz[TO[i]]);

}

mxsiz[x]=max(mxsiz[x],T-siz[x]);

if(mxsiz[x]<mxsiz[root]) root=x;

}

void dfs_build(int x,int f)

{

now=x;

pool[x].fa=f;

use[x]=true;

for(int i=fst[x];~i;i=NXT[i])

{

if(use[TO[i]]) continue;

root=0;

T=siz[TO[i]];

dfs_push(TO[i],0,val[i]);

getroot(TO[i],0);

pool[now].son[pool[now]._tot]=root;

siz[root]=siz[TO[i]];

sort(pool[now].Arr[pool[now]._tot].begin(),pool[now].Arr[pool[now]._tot].end());

for(int j=1;j<pool[now].Arr[pool[now]._tot].size();j++)

pool[now].Arr[pool[now]._tot][j].tot+=pool[now].Arr[pool[now]._tot][j-1].tot;

pool[now]._tot++;

}

pool[now].dist.push_back(sav(0,now));

sort(pool[now].dist.begin(),pool[now].dist.end());

for(int i=0;i<pool[x]._tot;i++) dfs_build(pool[x][i],x);

}

int n,m,A;

void pre()

{

int _,__,___;

read(n); read(m); read(A);

for(int i=1;i<=n;i++)

{

fst[i]=-1;

read(age[i]);

age[i]++;

}

for(int i=1;i<n;i++)

{

read(_); read(__); read(___);

add_e(_,__,___);

}

T=n;

mxsiz[0]=INF;

getroot(1,0);

dfs_build(root,0);

}

ll get_ans(int x,int l,int r)

{

sav _(0,l-1),__(0,r);

vector <sav> :: iterator it,it2;

int L,R,pre=0,tot=0,___,S=x;

ll dist=0,ret=0;

while(x)

{

tot=0;

for(int i=0;i<pool[x]._tot;i++)

{

if(pool[x][i]==pre)

continue;

it = upper_bound(pool[x].Arr[i].begin(),pool[x].Arr[i].end(),_);

if(it!=pool[x].Arr[i].begin())

{

it--;

ret-=it->tot;

it++;

}

it2 = upper_bound(pool[x].Arr[i].begin(),pool[x].Arr[i].end(),__);

if(it2!=pool[x].Arr[i].begin())

{

it2--;

ret+=it2->tot;

it2++;

}

tot+=distance(it,it2);

}

if(age[x]<=r&&age[x]>=l) tot++;

it=lower_bound(pool[x].dist.begin(),pool[x].dist.end(),sav(0,S));

dist=it->tot;

ret+=dist*tot;

pre=x;

x=pool[x].fa;

}

return ret;

}

ll lastans;

int main()

{

// freopen("BZOJ4012.in","r",stdin);

ll _,__,___,L,R;

pre();

while(m--)

{

read(_); read(__); read(___);

__+=lastans; ___+=lastans;

__%=A; ___%=A;

__++; ___++;

L=min(__,___);

R=max(__,___);

lastans=get_ans(_,L,R);

printf("%lld\n",lastans);

}

return 0;

}

BZOJ4012

@OceanEye7年前

05/3

18:56

BZOJ1419

OceanEye 撰写 DP 数学期望DP 无回复

期望DP
和班上的一个物理大佬一起搞了二十分钟吧……然后发现这个期望(R,B)只和(R-1,B)以及(R,B-1)相关
然后就一个for循环再用一下滚动数组就可以了
dp[r][b]=(dp[r][b-1]-1)*b/(r+b) + (dp[r-1][b]+1)*r/(r+b)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;

int R,B;
double dp[2][5050];

#define now i&1
#define pre now^1

int main()
{
	read(R); read(B);
	for(int i=0;i<=B;i++)
	{
		for(int j=1;j<=R;j++) dp[now][j]=max(0.0,((dp[pre][j]-1)*((double)i/(i+j)))+((dp[now][j-1]+1)*((double)j/(i+j))));
	}
	printf("%.6f",dp[B&1][R]-5e-7);
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

int R,B;

double dp[2][5050];

#define now i&1

#define pre now^1

int main()

{

read(R); read(B);

for(int i=0;i<=B;i++)

{

for(int j=1;j<=R;j++) dp[now][j]=max(0.0,((dp[pre][j]-1)*((double)i/(i+j)))+((dp[now][j-1]+1)*((double)j/(i+j))));

}

printf("%.6f",dp[B&1][R]-5e-7);

return 0;

}

BZOJ1419

@OceanEye7年前

05/2

20:40

BZOJ3236

OceanEye 撰写树状数组莫队无回复

看着这道题觉得很神啊

于是写了个n根号nlogn的就开始跑了

然后就跑过去了……

95s的AC

不过写这份代码好像只花了我十分钟？说明我码力还算不错么qwq[单身狗的怨念]

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;
#define N 100010
#define lb(x) (x&-x)
int Arr[N];
void add(int x,int v)
{
	while(x<=N) { Arr[x]+=v; x+=lb(x); }
}
int query(int pos)
{
	int ret=0;
	while(pos) { ret+=Arr[pos]; pos-=lb(pos); }
	return ret;
}
int Arr2[N];
void ins(int x,int v)
{ while(x<=N) { Arr2[x]+=v; x+=lb(x); } }
int _query(int pos)
{
	int ret=0;
	while(pos) { ret+=Arr2[pos]; pos-=lb(pos); }
	return ret;
}

struct rec
{
	int l,r,id;
	int a,b;
}Q[N*10];

#define SIZ 400
int a[N],n,m,cnt[N];
int l[SIZ],r[SIZ],belong[N],SQR,CNT;
int ans1[N*10],ans2[N*10];

bool comp(const rec &x,const rec &y)
{
	if(belong[x.l]==belong[y.l]) return x.r<y.r;
	return x.l<y.l;
}

void pre()
{
	read(n); read(m);
	SQR=sqrt(n); CNT=(n-1)/SQR+1;
	for(int i=1;i<=CNT;++i) { l[i]=(i-1)*SQR+1; r[i]=i*SQR; }
	r[CNT]=n;
	for(int i=1;i<=CNT;++i)
		for(int j=l[i];j<=r[i];++j) belong[j]=i;
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=1;i<=m;++i)
	{ read(Q[i].l); read(Q[i].r); read(Q[i].a); read(Q[i].b); Q[i].id=i; }
	sort(Q+1,Q+m+1,comp);
}

int main()
{
	pre();
	int nodeL=1,nodeR=0;
	for(int i=1;i<=m;++i)
	{
		while(nodeL>Q[i].l)
		{
			nodeL--;
			add(a[nodeL],1);
			if(!cnt[a[nodeL]]) ins(a[nodeL],1);
			cnt[a[nodeL]]++;
		}
		while(nodeR<Q[i].r)
		{
			nodeR++;
			add(a[nodeR],1);
			if(!cnt[a[nodeR]]) ins(a[nodeR],1);
			cnt[a[nodeR]]++;
		}
		while(nodeL<Q[i].l)
		{
			add(a[nodeL],-1);
			cnt[a[nodeL]]--;
			if(!cnt[a[nodeL]]) ins(a[nodeL],-1);
			nodeL++;
		}
		while(nodeR>Q[i].r)
		{
			add(a[nodeR],-1);
			cnt[a[nodeR]]--;
			if(!cnt[a[nodeR]]) ins(a[nodeR],-1);
			nodeR--;
		}
		ans1[Q[i].id]=query(Q[i].b)-query(Q[i].a-1);
		ans2[Q[i].id]=_query(Q[i].b)-_query(Q[i].a-1);
	}
	for(int i=1;i<=m;i++) printf("%d %d\n",ans1[i],ans2[i]);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <cmath>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

#define lb(x) (x&-x)

int Arr[N];

void add(int x,int v)

{

while(x<=N) { Arr[x]+=v; x+=lb(x); }

}

int query(int pos)

{

int ret=0;

while(pos) { ret+=Arr[pos]; pos-=lb(pos); }

return ret;

}

int Arr2[N];

void ins(int x,int v)

{ while(x<=N) { Arr2[x]+=v; x+=lb(x); } }

int _query(int pos)

{

int ret=0;

while(pos) { ret+=Arr2[pos]; pos-=lb(pos); }

return ret;

}

struct rec

{

int l,r,id;

int a,b;

}Q[N*10];

#define SIZ 400

int a[N],n,m,cnt[N];

int l[SIZ],r[SIZ],belong[N],SQR,CNT;

int ans1[N*10],ans2[N*10];

bool comp(const rec &x,const rec &y)

{

if(belong[x.l]==belong[y.l]) return x.r<y.r;

return x.l<y.l;

}

void pre()

{

read(n); read(m);

SQR=sqrt(n); CNT=(n-1)/SQR+1;

for(int i=1;i<=CNT;++i) { l[i]=(i-1)*SQR+1; r[i]=i*SQR; }

r[CNT]=n;

for(int i=1;i<=CNT;++i)

for(int j=l[i];j<=r[i];++j) belong[j]=i;

for(int i=1;i<=n;++i) read(a[i]);

for(int i=1;i<=m;++i)

{ read(Q[i].l); read(Q[i].r); read(Q[i].a); read(Q[i].b); Q[i].id=i; }

sort(Q+1,Q+m+1,comp);

}

int main()

{

pre();

int nodeL=1,nodeR=0;

for(int i=1;i<=m;++i)

{

while(nodeL>Q[i].l)

{

nodeL--;

add(a[nodeL],1);

if(!cnt[a[nodeL]]) ins(a[nodeL],1);

cnt[a[nodeL]]++;

}

while(nodeR<Q[i].r)

{

nodeR++;

add(a[nodeR],1);

if(!cnt[a[nodeR]]) ins(a[nodeR],1);

cnt[a[nodeR]]++;

}

while(nodeL<Q[i].l)

{

add(a[nodeL],-1);

cnt[a[nodeL]]--;

if(!cnt[a[nodeL]]) ins(a[nodeL],-1);

nodeL++;

}

while(nodeR>Q[i].r)

{

add(a[nodeR],-1);

cnt[a[nodeR]]--;

if(!cnt[a[nodeR]]) ins(a[nodeR],-1);

nodeR--;

}

ans1[Q[i].id]=query(Q[i].b)-query(Q[i].a-1);

ans2[Q[i].id]=_query(Q[i].b)-_query(Q[i].a-1);

}

for(int i=1;i<=m;i++) printf("%d %d\n",ans1[i],ans2[i]);

return 0;

}

BZOJ3236

@OceanEye7年前

05/2

20:04

BZOJ1324

OceanEye 撰写最小割网络流无回复

有些炸裂的题解

题目是一道最大点独立集，比较裸的那种

最大点独立集=最小点覆盖集的补集

然后套最小点覆盖集用sum-tot_flow即可

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;
#define E 100010
#define N 10050

struct Tedge
{
	int from,to,cap,flow;
}edge[E];
#define TO edge[i].to
#define FROM edge[i].from
#define FLO (edge[i].cap-edge[i].flow)
int e_tot,fst[N],NXT[E];
#define calc(x,y) ((x-1)*m+y)
#define S 0
#define T N-1

void add_e(int _,int __,int ___)
{
	edge[e_tot].to=__; edge[e_tot].from=_; edge[e_tot].cap=___; edge[e_tot].flow=0;
	NXT[e_tot]=fst[_]; fst[_]=e_tot++;
	edge[e_tot].to=_; edge[e_tot].from=__; edge[e_tot].cap=___; edge[e_tot].flow=___;
	NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}

int dist[N],cnt[N],cur[N],p[N];

bool bfs()
{
	int x;
	queue <int> Q;
	dist[T]=1;
	cnt[1]=1;
	Q.push(T);
	while(!Q.empty())
	{
		x=Q.front(); Q.pop();
		for(int i=fst[x];~i;i=NXT[i])
		{
			if(dist[TO]||FLO) continue;
			cnt[dist[TO]=dist[x]+1]++;
			Q.push(TO);
		}
	}
	return dist[S]!=0;
}

int Augment()
{
	static int ret,node,i;
	ret=INF; node=T;
	while(node!=S)
	{
		i=p[node];
		ret=min(ret,FLO);
		node=FROM;
	}
	node=T;
	while(node!=S)
	{
		i=p[node];
		edge[i].flow+=ret; edge[i^1].flow-=ret;
		node=FROM;
	}
	return ret;
}

int ISAP()
{
	if(!bfs()) return 0;
	int node=S,ret=0;
	bool flag;
	for(int i=0;i<N;i++) cur[i]=fst[i];
	while(dist[S]<N)
	{
		if(node==T)
		{
			ret+=Augment();
			node=S;
		}
		flag=false;
		for(int i=cur[node];~i;i=NXT[i])
		{
			if(dist[TO]!=dist[node]-1||!FLO) continue;
			flag=true;
			p[TO]=i;
			cur[node]=i;
			node=TO;
			break;
		}
		if(flag) continue;
		int M=N+5;
		cur[node]=fst[node];
		for(int i=fst[node];~i;i=NXT[i])
		{
			if(!FLO) continue;
			M=min(dist[TO]+1,M);
		}
		if(!--cnt[dist[node]]) return ret;
		dist[node]=M;
		cnt[M]++;
		if(node!=S) node=edge[p[node]].from;
	}
	return ret;
}

int a[105][105],tot,n,m;

const int _x[4]={0,0,1,-1},_y[4]={1,-1,0,0};

void pre()
{
	memset(fst,-1,sizeof(fst));
	read(n); read(m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) read(a[i][j]),tot+=a[i][j];
	int _,__;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			if((i^j)&1)
			{
				add_e(calc(i,j),T,a[i][j]);
				continue;
			}
			add_e(S,calc(i,j),a[i][j]);
			for(int k=0;k<4;k++)
			{
				_=i+_x[k]; __=j+_y[k];
				if(_<=0||_>n||__<=0||__>m) continue;
				add_e(calc(i,j),calc(_,__),INF);
			}
		}
}

int main()
{
	pre();
	printf("%d",tot-ISAP());
	return 0;
}

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

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <queue>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define E 100010

#define N 10050

struct Tedge

{

int from,to,cap,flow;

}edge[E];

#define TO edge[i].to

#define FROM edge[i].from

#define FLO (edge[i].cap-edge[i].flow)

int e_tot,fst[N],NXT[E];

#define calc(x,y) ((x-1)*m+y)

#define S 0

#define T N-1

void add_e(int _,int __,int ___)

{

edge[e_tot].to=__; edge[e_tot].from=_; edge[e_tot].cap=___; edge[e_tot].flow=0;

NXT[e_tot]=fst[_]; fst[_]=e_tot++;

edge[e_tot].to=_; edge[e_tot].from=__; edge[e_tot].cap=___; edge[e_tot].flow=___;

NXT[e_tot]=fst[__]; fst[__]=e_tot++;

}

int dist[N],cnt[N],cur[N],p[N];

bool bfs()

{

int x;

queue <int> Q;

dist[T]=1;

cnt[1]=1;

Q.push(T);

while(!Q.empty())

{

x=Q.front(); Q.pop();

for(int i=fst[x];~i;i=NXT[i])

{

if(dist[TO]||FLO) continue;

cnt[dist[TO]=dist[x]+1]++;

Q.push(TO);

}

return dist[S]!=0;

}

int Augment()

{

static int ret,node,i;

ret=INF; node=T;

while(node!=S)

{

i=p[node];

ret=min(ret,FLO);

node=FROM;

}

node=T;

while(node!=S)

{

i=p[node];

edge[i].flow+=ret; edge[i^1].flow-=ret;

node=FROM;

}

return ret;

}

int ISAP()

{

if(!bfs()) return 0;

int node=S,ret=0;

bool flag;

for(int i=0;i<N;i++) cur[i]=fst[i];

while(dist[S]<N)

{

if(node==T)

{

ret+=Augment();

node=S;

}

flag=false;

for(int i=cur[node];~i;i=NXT[i])

{

if(dist[TO]!=dist[node]-1||!FLO) continue;

flag=true;

p[TO]=i;

cur[node]=i;

node=TO;

break;

}

if(flag) continue;

int M=N+5;

cur[node]=fst[node];

for(int i=fst[node];~i;i=NXT[i])

{

if(!FLO) continue;

M=min(dist[TO]+1,M);

}

if(!--cnt[dist[node]]) return ret;

dist[node]=M;

cnt[M]++;

if(node!=S) node=edge[p[node]].from;

}

return ret;

}

int a[105][105],tot,n,m;

const int _x[4]={0,0,1,-1},_y[4]={1,-1,0,0};

void pre()

{

memset(fst,-1,sizeof(fst));

read(n); read(m);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++) read(a[i][j]),tot+=a[i][j];

int _,__;

for(int i=1;i<=n;++i)

for(int j=1;j<=m;++j)

{

if((i^j)&1)

{

add_e(calc(i,j),T,a[i][j]);

continue;

}

add_e(S,calc(i,j),a[i][j]);

for(int k=0;k<4;k++)

{

_=i+_x[k]; __=j+_y[k];

if(_<=0||_>n||__<=0||__>m) continue;

add_e(calc(i,j),calc(_,__),INF);

}

int main()

{

pre();

printf("%d",tot-ISAP());

return 0;

}

BZOJ1324

上一页 1 2

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ3884

BZOJ3884

@OceanEye7年前

BZOJ1227

BZOJ1227

@OceanEye7年前

BZOJ4808

BZOJ4808

@OceanEye7年前

BZOJ2434

BZOJ2434

@OceanEye7年前

BZOJ2780

BZOJ2780

@OceanEye7年前

BZOJ4318

BZOJ4318

@OceanEye7年前

BZOJ4012

BZOJ4012

@OceanEye7年前

BZOJ1419

BZOJ1419

@OceanEye7年前

BZOJ3236

BZOJ3236

@OceanEye7年前

BZOJ1324

BZOJ1324

友情链接

近期文章

标签