OceanEye | OceanEye's Blog

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

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

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

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

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

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

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

BZOJ1497

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

最小割

从源点向每个人连收益大小的边

人向站连大小为INF的边

站向汇连大小为成本的边

这个时候的割有三种情况：

1.把收益割掉了，此时支出>收入

2.把支出割掉了，此时支出<收入

3.支出和收入同时割掉了，支出=收入

总的答案就是sum-割

#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 400000
#define N 70050

struct Tedge
{
	int from,to,cap,flow;
}edge[E];

#define FROM edge[i].from
#define TO edge[i].to
#define FLO (edge[i].cap-edge[i].flow)

int e_tot,fst[N],NXT[E];
int n,m,tot;

void add_e(int _,int __,int ___)
{
	edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].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=___; edge[e_tot].flow=___;
	NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}

#define calc(x) (x+m)
#define S 0
#define T N-1

void pre()
{
	memset(fst,-1,sizeof(fst));
	read(n); read(m);
	int _,__,___;
	for(int i=1;i<=n;i++)
	{
		read(_);
		add_e(calc(i),T,_);
	}
	for(int i=1;i<=m;i++)
	{
		read(_); read(__); read(___);
		add_e(S,i,___);
		tot+=___;
		add_e(i,calc(__),INF);
		add_e(i,calc(_),INF);
	}
}


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

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

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

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

int main()
{
	pre();
	printf("%d\n",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 <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 400000

#define N 70050

struct Tedge

{

int from,to,cap,flow;

}edge[E];

#define FROM edge[i].from

#define TO edge[i].to

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

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

int n,m,tot;

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

{

edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].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=___; edge[e_tot].flow=___;

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

}

#define calc(x) (x+m)

#define S 0

#define T N-1

void pre()

{

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

read(n); read(m);

int _,__,___;

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

{

read(_);

add_e(calc(i),T,_);

}

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

{

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

add_e(S,i,___);

tot+=___;

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

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

}

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

int Augment()

{

int node,cur,i;

cur=INF; node=T;

while(node!=S)

{

i=p[node];

cur=min(cur,FLO);

node=FROM;

}

node=T;

while(node!=S)

{

i=p[node];

edge[i].flow+=cur;

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

node=FROM;

}

return cur;

}

bool bfs()

{

int x;

dist[T]=1;

queue<int> Q; Q.push(T);

while(!Q.empty())

{

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

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

if(!FLO&&!dist[TO])

{

Q.push(TO);

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

}

return dist[S]!=0;

}

int ISAP()

{

int node=S,ret=0;

bool flag;

if(!bfs()) return false;

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

{

cur[i]=fst[i];

if(dist[i]) cnt[dist[i]]++;

}

while(dist[S]<=n*2+2)

{

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)

{

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

node=TO;

flag=true;

break;

}

if(flag) continue;

int M=N-1;

cur[node]=fst[node];

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

{

if(!FLO) continue;

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

}

if(!--cnt[dist[node]]) break;

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

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

}

return ret;

}

int main()

{

pre();

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

return 0;

}

BZOJ1497

BZOJ1486

OceanEye 撰写点分治无回复

久违的1A

题目很裸……当年的男人八题现在看来也不过如此吧。

题目的数据范围给的不是很清楚，所以就没有用树状数组用了快排。

每次分治的时候要取重心来保证复杂度。

恩还是有些地方比较傻逼的

没有卡常数

#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

struct Tedge
{
	int to,val;
}edge[N<<1];
#define TO edge[i].to
#define VAL edge[i].val

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

void add_e(int a,int b,int c)
{
	edge[e_tot].to=b; edge[e_tot].val=c; NXT[e_tot]=fst[a]; fst[a]=e_tot++;
	edge[e_tot].to=a; edge[e_tot].val=c; NXT[e_tot]=fst[b]; fst[b]=e_tot++;
}
ll ans;
int n,k;
bool use[N];
int dist[N];
int siz[N],T,mx[N],root,v;
int d[N],tail,b[N],tot;

void pre()
{
	read(n);
	int _,__,___;
	memset(fst,-1,sizeof(fst));
	for(int i=1;i<n;i++)
	{
		read(_); read(__); read(___);
		add_e(_,__,___);
	}
	read(k);
}

void dfs_calc(int x,int f)
{
	ans+=2;
	d[tail++]=dist[x];
	for(int i=fst[x];~i;i=NXT[i])
	{
		if(use[TO]||TO==f) continue;
		if(dist[TO]<=k) dfs_calc(TO,x);
	}
}

void dfs_add(int x,int f)
{
	if(dist[x]<=k) b[tot++]=dist[x];
	siz[x]=1;
	for(int i=fst[x];~i;i=NXT[i])
	{
		if(use[TO]||TO==f) continue;
		dist[TO]=dist[x]+VAL;
		dfs_add(TO,x);
		siz[x]+=siz[TO];
	}
}

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

void dfs_solve(int x,int f,int coc)
{
	T=coc; root=0; tot=1;
	getroot(x,0);
	dist[root]=0;
	for(int i=fst[root];~i;i=NXT[i])
	{
		if(use[TO]) continue;
		dist[TO]=VAL;
		dfs_add(TO,root);
	}
	sort(b+1,b+tot);
	for(int i=fst[root];~i;i=NXT[i])
	{
		if(use[TO]||dist[TO]>k) continue;
		tail=1;
		dfs_calc(TO,root);
		sort(d+1,d+tail);
		for(int j=1;j<tail;j++)
		{
			ans+=upper_bound(b+1,b+tot,k-d[j])-b-1;
			ans-=upper_bound(d+1,d+tail,k-d[j])-d-1;
		}
	}
	use[root]=true;
	for(int i=fst[root];~i;i=NXT[i])
		if(!use[TO]) dfs_solve(TO,f,siz[TO]);
}

int main()
{
	pre();
	mx[0]=INF;
	dfs_solve(1,0,n);
	printf("%lld",ans/2);
	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

#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

struct Tedge

{

int to,val;

}edge[N<<1];

#define TO edge[i].to

#define VAL edge[i].val

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

void add_e(int a,int b,int c)

{

edge[e_tot].to=b; edge[e_tot].val=c; NXT[e_tot]=fst[a]; fst[a]=e_tot++;

edge[e_tot].to=a; edge[e_tot].val=c; NXT[e_tot]=fst[b]; fst[b]=e_tot++;

}

ll ans;

int n,k;

bool use[N];

int dist[N];

int siz[N],T,mx[N],root,v;

int d[N],tail,b[N],tot;

void pre()

{

read(n);

int _,__,___;

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

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

{

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

add_e(_,__,___);

}

read(k);

}

void dfs_calc(int x,int f)

{

ans+=2;

d[tail++]=dist[x];

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

{

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

if(dist[TO]<=k) dfs_calc(TO,x);

}

void dfs_add(int x,int f)

{

if(dist[x]<=k) b[tot++]=dist[x];

siz[x]=1;

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

{

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

dist[TO]=dist[x]+VAL;

dfs_add(TO,x);

siz[x]+=siz[TO];

}

void getroot(int x,int f)

{

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

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

{

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

getroot(TO,x);

siz[x]+=siz[TO];

mx[x]=max(mx[x],siz[TO]);

}

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

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

}

void dfs_solve(int x,int f,int coc)

{

T=coc; root=0; tot=1;

getroot(x,0);

dist[root]=0;

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

{

if(use[TO]) continue;

dist[TO]=VAL;

dfs_add(TO,root);

}

sort(b+1,b+tot);

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

{

if(use[TO]||dist[TO]>k) continue;

tail=1;

dfs_calc(TO,root);

sort(d+1,d+tail);

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

{

ans+=upper_bound(b+1,b+tot,k-d[j])-b-1;

ans-=upper_bound(d+1,d+tail,k-d[j])-d-1;

}

use[root]=true;

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

if(!use[TO]) dfs_solve(TO,f,siz[TO]);

}

int main()

{

pre();

mx[0]=INF;

dfs_solve(1,0,n);

printf("%lld",ans/2);

return 0;

}

BZOJ1486

GDOI记

OceanEye 撰写 GDOI 比赛无回复

如题……

DAY 0

[8:00 p.m.]

颠了一个下午的车来到了东莞。

天气很好，基本上就是太阳太阳太阳……果然天气预报一直都是不准的呢。然后在酒店里面就呆了一会，就去东华高中吃饭。跟着某mhx一起看~~神奇宝贝~~精灵宝可梦。饭后和mhx一起被一排老师奶炸……还被爆出机房打机的黑历史……心塞

[11:35 p.m.]

临睡前A了两道题，心情愉悦。

GDOI 2017 Bless All.

DAY 1

[11:56 p.m.]
进考场的时候没什么感觉，先拍了一下自己的vim配置……然后发现没有背全？[茫然.jpg]

接下来开考看题。一上来看第一题五分钟，这不是裸一道KMP签到题吗……然后拍了一个半小时= =确认无误之后看了看T2……题面太长跳过了。看着T3想着这题不可做啊，就写了个35分的暴力，自己过了样例和自己的几个数据时候就没有接着看了。
回头看T2，发现自己会一个n根号n的莫队算法，就开始写……写到考试结束还是有一个小bug，但是无奈还是交了

中午吃饭和其他人交流的时候突然脑子好了……想到T3应该使用广义SAM来跑跑跑接着按照dep深度来过一遍就能做的题目。 T2 whj大神给了个nlogn的神做法……~~后来被他自己叉掉了。~~
后来听评讲，第一题不想听，第二题出题人给了O(nlogn)和O(n)的做法[真·神做法]。第三题就是广义SAM。T4是NTT套路题，但是没碰过NTT所以理所应带的没有分了。zawedx还给了个nlogn的做法……很可取的做法

后来出成绩的时候发现只有五十，T1完全没分，全是RE。第一反应是数组开小了，赶紧去复评。
……数组真开小了，直接丢了一百分

气

睡觉了……明早还有一场考试……看看能不能翻盘吧233
[看脸+看实力的考试啊qwq]

DAY2

实力作死吧T3搞炸了

T1签到题分层图SPFA随便过，然而还是有很多人被卡常数[？？？]

T2出题人给了个有理有据的暴力算法大力用n平方+优化艹掉了n=1e6的数据……不得不服

T3就是个n方的特殊一点的DP，之后利用树状数组瞎搞就可以了

就可以了……然后我作死把那个N方的改成了nlogn的，于是关键的生成字符串就求不了了，就炸了。

T4场上一看这不是炒鸡码农动态点分治么，果断不写……【事实证明这个决定有一半是错误的】

讲评的时候果真听见出题人在说这个点分树，但是好像码量也不是太大？

说什么只要用到期望线性可加就可以搞出一个log方……果然是我too young

DAY3

bless all

先一步离开了东莞，不过早上睡到十二点还是很爽的:-D

事后

严重怀疑自己被毒奶致死，，明年再战

GDOI记

上一页 1 2 3 4 5 6 7 8 下一页

OceanEye's Blog

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

@OceanEye7年前

BZOJ2434

BZOJ2434

@OceanEye7年前

BZOJ2780

BZOJ2780

@OceanEye7年前

BZOJ4318

BZOJ4318

@OceanEye7年前

BZOJ4012

BZOJ4012

@OceanEye7年前

BZOJ1419

BZOJ1419

@OceanEye7年前

BZOJ3236

BZOJ3236

@OceanEye7年前

BZOJ1324

BZOJ1324

@OceanEye7年前

BZOJ1497

BZOJ1497

@OceanEye7年前

BZOJ1486

BZOJ1486

@OceanEye7年前

GDOI记

DAY 0

DAY 1

DAY2

DAY3

事后

GDOI记

友情链接

近期文章

标签