2017年4月 – OceanEye's Blog

Date Time

17/04/28 23:34

Author

OceanEye

Tags

最小割, 网络流

Leave a Reply

BZOJ1497

最小割

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

人向站连大小为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;

}

Date Time

17/04/28 20:39

Author

OceanEye

Tags

点分治

Leave a Reply

BZOJ1486

久违的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;

}

Date Time

17/04/28 20:07

Author

OceanEye

Tags

GDOI, 比赛

Leave a Reply

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

事后

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

Date Time

17/04/27 09:59

Author

OceanEye

Tags

bitset, 神技巧, 莫队

Leave a Reply

BZOJ4810 莫队+bitset

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4810

kry大爷的代码好短……可以看看orz

[bzoj 4810] [Ynoi2017]由乃的玉米田

这题目测只要是根号+压位就能过得去的了……所以不要太在意细节
[然后就被细节骗走了五次wa]
如果我们压了位……
减法就可以直接右移解决 b-c=a
加法的话把它反过来右移解决大概是变成 a+b=c -> b-c=-a

乘法很simple，直接暴力就好了，根号可是比n/64要小的
而且时限30s，跑起来好像还挺稳的？
代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#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 SIZ 400
bitset <N> Appear,Rev,____;

int a[N],cnt[N],n,m;
int l[SIZ],r[SIZ],belong[N],SQR,CNT;

struct rec
{
	int l,r,c,type;
	int id;
}pool[N];

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);
	for(int i=1;i<=n;i++) read(a[i]);
	SQR=sqrt(n); CNT=(n-1)/SQR+1;
	for(int i=1;i<=CNT;i++)
	{ l[i]=(CNT-1)*SQR+1; r[i]=CNT*SQR; }
	r[CNT]=n;
	for(int i=1;i<=n;i++) belong[i]=(i-1)/SQR+1;
	for(int i=1;i<=m;i++) { read(pool[i].type); read(pool[i].l); read(pool[i].r); read(pool[i].c); pool[i].id=i; }
	sort(pool+1,pool+1+m,comp);
}

int ans[N];

void solve(int i)
{
	if(pool[i].type==1)
	{
		____=Appear;
		____>>=pool[i].c;
		____&=Appear;
		if(____.any()) ans[pool[i].id]=1;
		else ans[pool[i].id]=0;
		return;
	}
	if(pool[i].type==2)
	{
		____=Rev;
		____>>=(100000-pool[i].c);
		____&=Appear;
		if(____.any()) ans[pool[i].id]=1;
		else ans[pool[i].id]=0;
		return;
	}
	if(pool[i].type==3)
	{
		for(int j=1;j*j<=pool[i].c;j++) if(cnt[j]&&cnt[pool[i].c/j])
		{
			if(pool[i].c%j==0)
			{
				ans[pool[i].id]=1;
				return;
			}
		}
		ans[pool[i].id]=0;
		return;
	}
}

int main()
{
	pre();
	int nodeR,nodeL;
	nodeR=0;nodeL=1;
	for(int i=1;i<=m;i++)
	{
		while(nodeR<pool[i].r)
		{
			nodeR++;
			cnt[a[nodeR]]++;
			if(cnt[a[nodeR]]==1) Appear[a[nodeR]]=1,Rev[100000-a[nodeR]]=1;
		}
		while(nodeL>pool[i].l)
		{
			nodeL--;
			cnt[a[nodeL]]++;
			if(cnt[a[nodeL]]==1) Appear[a[nodeL]]=1,Rev[100000-a[nodeL]]=1;
		}
		while(nodeL<pool[i].l)
		{
			cnt[a[nodeL]]--;
			if(!cnt[a[nodeL]]) Appear[a[nodeL]]=0,Rev[100000-a[nodeL]]=0;
			nodeL++;
		}
		while(nodeR>pool[i].r)
		{
			cnt[a[nodeR]]--;
			if(!cnt[a[nodeR]]) Appear[a[nodeR]]=0,Rev[100000-a[nodeR]]=0;
			nodeR--;
		}
		solve(i);
	}
	for(int i=1;i<=m;i++) ans[i]?puts("yuno"):puts("yumi");
	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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <iostream>

#include <bitset>

#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 SIZ 400

bitset <N> Appear,Rev,____;

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

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

struct rec

{

int l,r,c,type;

int id;

}pool[N];

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);

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

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

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

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

r[CNT]=n;

for(int i=1;i<=n;i++) belong[i]=(i-1)/SQR+1;

for(int i=1;i<=m;i++) { read(pool[i].type); read(pool[i].l); read(pool[i].r); read(pool[i].c); pool[i].id=i; }

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

}

int ans[N];

void solve(int i)

{

if(pool[i].type==1)

{

____=Appear;

____>>=pool[i].c;

____&=Appear;

if(____.any()) ans[pool[i].id]=1;

else ans[pool[i].id]=0;

return;

}

if(pool[i].type==2)

{

____=Rev;

____>>=(100000-pool[i].c);

____&=Appear;

if(____.any()) ans[pool[i].id]=1;

else ans[pool[i].id]=0;

return;

}

if(pool[i].type==3)

{

for(int j=1;j*j<=pool[i].c;j++) if(cnt[j]&&cnt[pool[i].c/j])

{

if(pool[i].c%j==0)

{

ans[pool[i].id]=1;

return;

}

ans[pool[i].id]=0;

return;

}

int main()

{

pre();

int nodeR,nodeL;

nodeR=0;nodeL=1;

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

{

while(nodeR<pool[i].r)

{

nodeR++;

cnt[a[nodeR]]++;

if(cnt[a[nodeR]]==1) Appear[a[nodeR]]=1,Rev[100000-a[nodeR]]=1;

}

while(nodeL>pool[i].l)

{

nodeL--;

cnt[a[nodeL]]++;

if(cnt[a[nodeL]]==1) Appear[a[nodeL]]=1,Rev[100000-a[nodeL]]=1;

}

while(nodeL<pool[i].l)

{

cnt[a[nodeL]]--;

if(!cnt[a[nodeL]]) Appear[a[nodeL]]=0,Rev[100000-a[nodeL]]=0;

nodeL++;

}

while(nodeR>pool[i].r)

{

cnt[a[nodeR]]--;

if(!cnt[a[nodeR]]) Appear[a[nodeR]]=0,Rev[100000-a[nodeR]]=0;

nodeR--;

}

solve(i);

}

for(int i=1;i<=m;i++) ans[i]?puts("yuno"):puts("yumi");

return 0;

}

Date Time

17/04/25 11:23

Author

OceanEye

Tags

DFS, SPFA, 强连通分量

Leave a Reply

BZOJ1179

(点我)题目链接

老题。
强连通分量把能一起抢的缩成一个点
然后在图上跑SPFA或者DP都可以
写SPFA写惯了……

/**************************************************************
    Problem: 1179
    User: OceanEYe
    Language: C++
    Result: Accepted
    Time:9392 ms
    Memory:42020 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#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 500010
 
int fa[N];
#define S 0
#define T n+5
vector <int> G[N];
 
int n,m,val[N],s,TT[N];
bool p[N];
 
void pre()
{
    int _,__;
    read(n); read(m);
    for(int i=1;i<=m;i++)
    {
        read(_); read(__);
        G[_].push_back(__);
    }
    for(int i=1;i<=n;i++)
        read(val[i]);
    read(s); read(__);
    for(int i=1;i<=__;i++)
    {
        read(_); p[_]=true;
    }
}
 
int STA[N],top,SSTA[N],TOP;
int dfn[N],low[N],cur[N],in[N],tot;
bool inSTA[N],vis[N];
 
void Tarjan(int x)
{
    SSTA[++TOP]=x;
    low[x]=dfn[x]=++top;
    STA[top]=x;
    fa[x]=x;
    vis[x]=true;
    inSTA[x]=true;
    bool flag;
    for(;TOP;)
    {
        flag=true;
        int u=SSTA[TOP];
        for(int i=cur[u];i<G[u].size();i++)
        {
            if(!vis[G[u][i]])
            {
                vis[G[u][i]]=true;
                fa[G[u][i]]=u;
                low[G[u][i]]=dfn[G[u][i]]=++top;
                STA[top]=G[u][i];
                inSTA[G[u][i]]=true;
                SSTA[++TOP]=G[u][i];
                cur[u]=i+1;
                flag=false;
                break;
            }
            else continue;
        }
        if(!flag) continue;
        for(int i=0;i<G[u].size();i++)
            if(fa[G[u][i]]==u) low[u]=min(low[u],low[G[u][i]]);
            else if(inSTA[G[u][i]]) low[u]=min(low[u],dfn[G[u][i]]);
        if(low[u]==dfn[u])
        {
            tot++;
            while(top!=dfn[u])
            {
                in[STA[top]]=tot;
                inSTA[STA[top]]=false;
                TT[tot]+=val[STA[top--]];
            }
            in[STA[top]]=tot;
            inSTA[STA[top]]=false;
            TT[tot]+=val[u]; top--;
        }
        TOP--;
    }
}
 
vector <int> MP[N];
bool inq[N];
int dist[N];
 
int solve()
{
    queue <int> Q;
    Q.push(S); inq[S]=true;
    while(!Q.empty())
    {
        int x=Q.front(); inq[x]=false; Q.pop();
        for(int i=0;i<MP[x].size();i++)
        {
            if(dist[MP[x][i]] < dist[x] + TT[MP[x][i]])
            {
                dist[MP[x][i]]=dist[x] + TT[MP[x][i]];
                if(!inq[MP[x][i]]) Q.push(MP[x][i]),inq[MP[x][i]]=true;
            }
        }
    }
    return dist[T];
}
 
int main()
{
    pre();
    Tarjan(s);
    for(int i=1;i<=n;i++)
    {
        if(!in[i]) continue;
        for(int j=0;j<G[i].size();j++)
        {
            if(in[G[i][j]]==in[i]) continue;
            MP[in[i]].push_back(in[G[i][j]]);
        }
    }
    MP[S].push_back(in[s]);
    for(int i=1;i<=n;i++)
        if(p[i]) MP[in[i]].push_back(T);
    printf("%d",solve());
    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

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

Problem: 1179

User: OceanEYe

Language: C++

Result: Accepted

Time:9392 ms

Memory:42020 kb

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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <queue>

#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 500010

int fa[N];

#define S 0

#define T n+5

vector <int> G[N];

int n,m,val[N],s,TT[N];

bool p[N];

void pre()

{

int _,__;

read(n); read(m);

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

{

read(_); read(__);

G[_].push_back(__);

}

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

read(val[i]);

read(s); read(__);

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

{

read(_); p[_]=true;

}

int STA[N],top,SSTA[N],TOP;

int dfn[N],low[N],cur[N],in[N],tot;

bool inSTA[N],vis[N];

void Tarjan(int x)

{

SSTA[++TOP]=x;

low[x]=dfn[x]=++top;

STA[top]=x;

fa[x]=x;

vis[x]=true;

inSTA[x]=true;

bool flag;

for(;TOP;)

{

flag=true;

int u=SSTA[TOP];

for(int i=cur[u];i<G[u].size();i++)

{

if(!vis[G[u][i]])

{

vis[G[u][i]]=true;

fa[G[u][i]]=u;

low[G[u][i]]=dfn[G[u][i]]=++top;

STA[top]=G[u][i];

inSTA[G[u][i]]=true;

SSTA[++TOP]=G[u][i];

cur[u]=i+1;

flag=false;

break;

}

else continue;

}

if(!flag) continue;

for(int i=0;i<G[u].size();i++)

if(fa[G[u][i]]==u) low[u]=min(low[u],low[G[u][i]]);

else if(inSTA[G[u][i]]) low[u]=min(low[u],dfn[G[u][i]]);

if(low[u]==dfn[u])

{

tot++;

while(top!=dfn[u])

{

in[STA[top]]=tot;

inSTA[STA[top]]=false;

TT[tot]+=val[STA[top--]];

}

in[STA[top]]=tot;

inSTA[STA[top]]=false;

TT[tot]+=val[u]; top--;

}

TOP--;

}

vector <int> MP[N];

bool inq[N];

int dist[N];

int solve()

{

queue <int> Q;

Q.push(S); inq[S]=true;

while(!Q.empty())

{

int x=Q.front(); inq[x]=false; Q.pop();

for(int i=0;i<MP[x].size();i++)

{

if(dist[MP[x][i]] < dist[x] + TT[MP[x][i]])

{

dist[MP[x][i]]=dist[x] + TT[MP[x][i]];

if(!inq[MP[x][i]]) Q.push(MP[x][i]),inq[MP[x][i]]=true;

}

return dist[T];

}

int main()

{

pre();

Tarjan(s);

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

{

if(!in[i]) continue;

for(int j=0;j<G[i].size();j++)

{

if(in[G[i][j]]==in[i]) continue;

MP[in[i]].push_back(in[G[i][j]]);

}

MP[S].push_back(in[s]);

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

if(p[i]) MP[in[i]].push_back(T);

printf("%d",solve());

return 0;

}

Date Time

17/04/23 15:45

Author

OceanEye

Tags

可并堆

Leave a Reply

BZOJ1455

还是可并堆的题目……而且一如既往的很裸
合并，弹出都是log的复杂度
看代码吧……没什么细节但是我还是没有1A

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#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 1000010

struct node
{
	int lc,rc,val;
	int fa;
}pool[N];

int n,m;

#define Lc pool[x].lc
#define Rc pool[x].rc

int merge(int x,int y)
{
	if(!y) return x; if(!x) return y;
	if(pool[y].val<pool[x].val) swap(x,y);
	pool[x].rc=merge(y,pool[x].rc);
	pool[pool[x].rc].fa=x;
	return x;
}

int pop(int x)
{
	pool[x].fa=-1;
	pool[Lc].fa=0; pool[Rc].fa=0;
	merge(Lc,Rc);
	return pool[x].val;
}

void pre()
{
	read(n);
	for(int i=1;i<=n;i++) read(pool[i].val);
}

int main()
{
	freopen("roman.in","r",stdin);
	int _,__;
	pre();
	read(m);
	char cmd[10];
	while(m--)
	{
		scanf("%s",cmd);
		if(cmd[0]=='M')
		{
			read(_);read(__);
			while(pool[_].fa&&~pool[_].fa) _=pool[_].fa;
			while(pool[__].fa&&~pool[__].fa) __=pool[__].fa;
			if(pool[_].fa==-1||pool[__].fa==-1) continue;
			if(_==__) continue;
			merge(_,__);
		}
		if(cmd[0]=='K')
		{
			read(__);
			while(pool[__].fa&&~pool[__].fa)
				__=pool[__].fa;
			if(~pool[__].fa) printf("%d\n",pop(__));
			else puts("0");
		}
	}
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#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 1000010

struct node

{

int lc,rc,val;

int fa;

}pool[N];

int n,m;

#define Lc pool[x].lc

#define Rc pool[x].rc

int merge(int x,int y)

{

if(!y) return x; if(!x) return y;

if(pool[y].val<pool[x].val) swap(x,y);

pool[x].rc=merge(y,pool[x].rc);

pool[pool[x].rc].fa=x;

return x;

}

int pop(int x)

{

pool[x].fa=-1;

pool[Lc].fa=0; pool[Rc].fa=0;

merge(Lc,Rc);

return pool[x].val;

}

void pre()

{

read(n);

for(int i=1;i<=n;i++) read(pool[i].val);

}

int main()

{

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

int _,__;

pre();

read(m);

char cmd[10];

while(m--)

{

scanf("%s",cmd);

if(cmd[0]=='M')

{

read(_);read(__);

while(pool[_].fa&&~pool[_].fa) _=pool[_].fa;

while(pool[__].fa&&~pool[__].fa) __=pool[__].fa;

if(pool[_].fa==-1||pool[__].fa==-1) continue;

if(_==__) continue;

merge(_,__);

}

if(cmd[0]=='K')

{

read(__);

while(pool[__].fa&&~pool[__].fa)

__=pool[__].fa;

if(~pool[__].fa) printf("%d\n",pop(__));

else puts("0");

}

return 0;

}

Date Time

17/04/21 16:09

Author

OceanEye

Tags

CDQ分治, 树状数组, 离线算法

Leave a Reply

BZOJ3262

CDQ分治做三维偏序
很裸很裸
直接看代码吧= =

[CDQ分治的思想就是一段询问有三个维度，离散化两个维度，对第三个维度我们扫一遍来计算贡献]
[通常取mid是比较优秀的]

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define p(x) ('0'<=x&&x<='9')
#define INF 100000000
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 200000
#define lowbit(x) (x&-x)
	int Arr[N+10];
	void inc(int x) { while(x<=N) { Arr[x]++; x+=lowbit(x); } }
	void dec(int x) { while(x<=N) { Arr[x]--; x+=lowbit(x); } }
	int query(int x)
	{
		int ret=0;
		while(x)
		{
			ret+=Arr[x];
			x-=lowbit(x);
		}
		return ret;
	}
#undef lowbit

struct q
{
	int x,y,z;
	int cp;
}Q[N],NQ[N];

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

bool comp(const q &x,const q &y)
{
	if(x.x==y.x&&x.y==y.y) return x.z<y.z;
	if(x.x==y.x) return x.y<y.y;
	return x.x<y.x;
}

void pre()
{
	read(n); read(m);
	for(int i=1;i<=n;i++)
	{
		read(Q[i].x); read(Q[i].y); read(Q[i].z);
		Q[i].cp=i;
	}
	sort(Q+1,Q+1+n,comp);
}

void solve(int l,int r,int L,int R)
{
	if(l>r) return;
	if(L==R)
	{
		int node=l;
		while(node<=r)
		{
			int k=node+1;
			while(Q[node].x==Q[k].x&&k<=r) k++;
			for(int i=node;i<k;i++) inc(Q[i].y);
			for(;node<k;node++) ans[Q[node].cp]+=query(Q[node].y);
		}
		for(int i=l;i<=r;i++) dec(Q[i].y);
		return;
	}
	int mid=(L+R)>>1;
	for(int i=l;i<=r;i++)
	{
		if(Q[i].z<=mid) inc(Q[i].y);
		if(Q[i].z>mid) ans[Q[i].cp]+=query(Q[i].y);
	}
	for(int i=l;i<=r;i++) if(Q[i].z<=mid) dec(Q[i].y);
	int nodeL=l,nodeR=mid+1;
	int nl[2],nr[2];
	nl[0]=nr[0]=INF;
	nl[1]=nr[1]=-INF;
	for(int i=l;i<=r;i++)if(Q[i].z<=mid)
	{
		NQ[nodeL++]=Q[i];
		nl[0]=min(nl[0],Q[i].z);
		nl[1]=max(nl[1],Q[i].z);
	}
	nodeR=nodeL;
	for(int i=l;i<=r;i++) if(Q[i].z>mid)
	{
		NQ[nodeR++]=Q[i];
		nr[0]=min(nr[0],Q[i].z);
		nr[1]=max(nr[1],Q[i].z);
	}
	for(int i=l;i<=r;i++) Q[i]=NQ[i];
	solve(l,nodeL-1,nl[0],nl[1]);
	solve(nodeL,r,nr[0],nr[1]);
}

int main()
{
	pre();
	solve(1,n,1,m);
	//for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	for(int i=1;i<=n;i++) cnt[ans[i]]++;
	for(int i=1;i<=n;i++) printf("%d\n",cnt[i]);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

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

#define INF 100000000

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 200000

#define lowbit(x) (x&-x)

int Arr[N+10];

void inc(int x) { while(x<=N) { Arr[x]++; x+=lowbit(x); } }

void dec(int x) { while(x<=N) { Arr[x]--; x+=lowbit(x); } }

int query(int x)

{

int ret=0;

while(x)

{

ret+=Arr[x];

x-=lowbit(x);

}

return ret;

}

#undef lowbit

struct q

{

int x,y,z;

int cp;

}Q[N],NQ[N];

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

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

{

if(x.x==y.x&&x.y==y.y) return x.z<y.z;

if(x.x==y.x) return x.y<y.y;

return x.x<y.x;

}

void pre()

{

read(n); read(m);

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

{

read(Q[i].x); read(Q[i].y); read(Q[i].z);

Q[i].cp=i;

}

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

}

void solve(int l,int r,int L,int R)

{

if(l>r) return;

if(L==R)

{

int node=l;

while(node<=r)

{

int k=node+1;

while(Q[node].x==Q[k].x&&k<=r) k++;

for(int i=node;i<k;i++) inc(Q[i].y);

for(;node<k;node++) ans[Q[node].cp]+=query(Q[node].y);

}

for(int i=l;i<=r;i++) dec(Q[i].y);

return;

}

int mid=(L+R)>>1;

for(int i=l;i<=r;i++)

{

if(Q[i].z<=mid) inc(Q[i].y);

if(Q[i].z>mid) ans[Q[i].cp]+=query(Q[i].y);

}

for(int i=l;i<=r;i++) if(Q[i].z<=mid) dec(Q[i].y);

int nodeL=l,nodeR=mid+1;

int nl[2],nr[2];

nl[0]=nr[0]=INF;

nl[1]=nr[1]=-INF;

for(int i=l;i<=r;i++)if(Q[i].z<=mid)

{

NQ[nodeL++]=Q[i];

nl[0]=min(nl[0],Q[i].z);

nl[1]=max(nl[1],Q[i].z);

}

nodeR=nodeL;

for(int i=l;i<=r;i++) if(Q[i].z>mid)

{

NQ[nodeR++]=Q[i];

nr[0]=min(nr[0],Q[i].z);

nr[1]=max(nr[1],Q[i].z);

}

for(int i=l;i<=r;i++) Q[i]=NQ[i];

solve(l,nodeL-1,nl[0],nl[1]);

solve(nodeL,r,nr[0],nr[1]);

}

int main()

{

pre();

solve(1,n,1,m);

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

for(int i=1;i<=n;i++) cnt[ans[i]]++;

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

return 0;

}

Date Time

17/04/21 13:30

Author

OceanEye

Tags

概率方程, 高斯消元

Leave a Reply

BZOJ3270

这是一份简单的题解
用一个二元组表示两个人的状态 (A,B)
然后在二元组里面跑概率方程
稍微参照了一下黄学长的方程列法
不过还是觉得在起点(A,B) 那里可以更漂亮的。
都一样啦过了

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define db double
#define eps 1e-6

using namespace std;
#define N 440
#define BASE 20
vector <int> G[BASE+1];
int n,m,___,b,siz,out[BASE+1];
//int G[N][N];
db a[N][N],C[BASE+1];
#define calc(x,y) (x-1)*n+y
void build(int _,int __)
{
	int pt=calc(_,__),cur,_1,_2;
	a[pt][pt]--;
	for(int i=0;i<G[_].size();i++)
		for(int j=0;j<G[__].size();j++)
		{
			_1=G[_][i]; _2=G[__][j];
			cur=calc(_1,_2);
			if(_1==_2) continue;
			if(_1==_&&_2==__) a[pt][cur]+=C[_1]*C[_2];
			else if(_1==_) a[pt][cur]+=C[_1]*(1-C[_2])/out[_2];
			else if(_2==__) a[pt][cur]+=C[_2]*(1-C[_1])/out[_1];
			else a[pt][cur]+=(1-C[_2])*(1-C[_1])/out[_1]/out[_2];
		}
}

void pre()
{
	int _,__; db t;
	scanf("%d %d %d %d",&n,&m,&___,&b);
	siz=n*n;
	a[calc(___,b)][siz+1]=-1;
	for(int i=1;i<=n;i++) G[i].push_back(i);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&_,&__);
		out[_]++; out[__]++;
		G[_].push_back(__);
		G[__].push_back(_);
	}
	for(int i=1;i<=n;i++) scanf("%lf",&C[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) build(i,j);
}

void gauss()
{
	db t;
	int now=1,to;
	for(int i=1;i<=siz;i++)
	{
		for(to=now;to<=siz;to++) if(abs(a[to][i])>eps) break;
		if(to>siz) continue;
		if(to!=now) swap(a[to],a[now]);
		for(int j=1;j<=siz;j++)
		{
			if(j==now) continue;
			t=a[j][i]/a[now][i];
			for(int k=1;k<=siz+1;k++) a[j][k]-=t*a[now][k];
		}
		now++;
	}
}

int main()
{
	pre();
	gauss();
	for(int i=1;i<=n;i++)
	{
		printf("%.6lf ",a[calc(i,i)][siz+1]/a[calc(i,i)][calc(i,i)]);
	}
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <vector>

#define db double

#define eps 1e-6

using namespace std;

#define N 440

#define BASE 20

vector <int> G[BASE+1];

int n,m,___,b,siz,out[BASE+1];

//int G[N][N];

db a[N][N],C[BASE+1];

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

void build(int _,int __)

{

int pt=calc(_,__),cur,_1,_2;

a[pt][pt]--;

for(int i=0;i<G[_].size();i++)

for(int j=0;j<G[__].size();j++)

{

_1=G[_][i]; _2=G[__][j];

cur=calc(_1,_2);

if(_1==_2) continue;

if(_1==_&&_2==__) a[pt][cur]+=C[_1]*C[_2];

else if(_1==_) a[pt][cur]+=C[_1]*(1-C[_2])/out[_2];

else if(_2==__) a[pt][cur]+=C[_2]*(1-C[_1])/out[_1];

else a[pt][cur]+=(1-C[_2])*(1-C[_1])/out[_1]/out[_2];

}

void pre()

{

int _,__; db t;

scanf("%d %d %d %d",&n,&m,&___,&b);

siz=n*n;

a[calc(___,b)][siz+1]=-1;

for(int i=1;i<=n;i++) G[i].push_back(i);

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

{

scanf("%d %d",&_,&__);

out[_]++; out[__]++;

G[_].push_back(__);

G[__].push_back(_);

}

for(int i=1;i<=n;i++) scanf("%lf",&C[i]);

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

for(int j=1;j<=n;j++) build(i,j);

}

void gauss()

{

db t;

int now=1,to;

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

{

for(to=now;to<=siz;to++) if(abs(a[to][i])>eps) break;

if(to>siz) continue;

if(to!=now) swap(a[to],a[now]);

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

{

if(j==now) continue;

t=a[j][i]/a[now][i];

for(int k=1;k<=siz+1;k++) a[j][k]-=t*a[now][k];

}

now++;

}

int main()

{

pre();

gauss();

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

{

printf("%.6lf ",a[calc(i,i)][siz+1]/a[calc(i,i)][calc(i,i)]);

}

return 0;

}

Date Time

17/04/17 08:26

Author

OceanEye

Tags

BZOJ, 可并堆, 模版题

Leave a Reply

BZOJ2809可并堆裸题

题面大概是这样子的：

很裸，就学了一下可并堆的姿势然后就写了
1A啊:-D
写的是左偏树，安利百度文库的文章
但是不知道为什么跑了3k+ms
不理了可能是vector的原因吧

#include <cstdio>
#include <algorithm>
#include <vector>
#define p(x) ('0'<=x&&x<='9')
#define ll long long
char cc;
template <class T>
void read( T &x )
{
	x=0; cc=getchar();
	while(!p(cc)) cc=getchar();
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
}
template <class T,class TT>
void read(TT &_,T &__,T &___) { read(_); read(__); read(___); }
template <class T>
void comp( T &x, T y )
{
	x>y?x=x:x=y;
}
using namespace std;
#define N 100010
// zuo pian shu
struct node
{
	int l,r,k,d;
}pool[N];

int combine(int _,int __)
{
	if(!~_) return __; if(!~__) return _;
	if(pool[_].k<pool[__].k) swap(_,__);
	pool[_].r=combine(pool[_].r,__);
	if(~pool[_].r) pool[_].d=pool[pool[_].r].d+1;
	else pool[_].d=0;
	return _;
}
void pop(int &_)
{
	int l=pool[_].l,r=pool[_].r;
	_=combine(l,r);
}
//
vector <int> G[N];
ll C[N],L[N],ANS,SUM[N];
int n,m,SIZ[N],rt[N];
void init()
{
	read(n); read(m);
	for(int i=1,_;i<=n;i++)
	{
		G[i].reserve(10);
		read(_,C[i],L[i]);
		G[_].push_back(i);
	}
}
void dfs(int x)
{
	pool[x].l=pool[x].r=-1;
	SUM[x]=pool[x].k=C[x];
	SIZ[x]=1; rt[x]=x;
	for(int i=0,to;i<G[x].size();i++)
	{
		to=G[x][i];
		dfs(G[x][i]);
		rt[x]=combine(rt[x],rt[to]);
		SUM[x]+=SUM[to];
		SIZ[x]+=SIZ[to];
	}
	for(;SUM[x]>m;) { SUM[x]-=pool[rt[x]].k; pop(rt[x]); SIZ[x]--; }
	comp(ANS,L[x]*SIZ[x]);
}

int main()
{
	init();
	dfs(1);
	printf("%lld",ANS);
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <vector>

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

#define ll long long

char cc;

template <class T>

void read( T &x )

{

x=0; cc=getchar();

while(!p(cc)) cc=getchar();

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

}

template <class T,class TT>

void read(TT &_,T &__,T &___) { read(_); read(__); read(___); }

template <class T>

void comp( T &x, T y )

{

x>y?x=x:x=y;

}

using namespace std;

#define N 100010

// zuo pian shu

struct node

{

int l,r,k,d;

}pool[N];

int combine(int _,int __)

{

if(!~_) return __; if(!~__) return _;

if(pool[_].k<pool[__].k) swap(_,__);

pool[_].r=combine(pool[_].r,__);

if(~pool[_].r) pool[_].d=pool[pool[_].r].d+1;

else pool[_].d=0;

return _;

}

void pop(int &_)

{

int l=pool[_].l,r=pool[_].r;

_=combine(l,r);

}

vector <int> G[N];

ll C[N],L[N],ANS,SUM[N];

int n,m,SIZ[N],rt[N];

void init()

{

read(n); read(m);

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

{

G[i].reserve(10);

read(_,C[i],L[i]);

G[_].push_back(i);

}

void dfs(int x)

{

pool[x].l=pool[x].r=-1;

SUM[x]=pool[x].k=C[x];

SIZ[x]=1; rt[x]=x;

for(int i=0,to;i<G[x].size();i++)

{

to=G[x][i];

dfs(G[x][i]);

rt[x]=combine(rt[x],rt[to]);

SUM[x]+=SUM[to];

SIZ[x]+=SIZ[to];

}

for(;SUM[x]>m;) { SUM[x]-=pool[rt[x]].k; pop(rt[x]); SIZ[x]--; }

comp(ANS,L[x]*SIZ[x]);

}

int main()

{

init();

dfs(1);

printf("%lld",ANS);

return 0;

}

Date Time

17/04/14 17:38

Author

OceanEye

Tags

BZOJ, 分块

Leave a Reply

BZOJ1858: [Scoi2010]序列操作

题目链接

好久没写过这么长的代码了= =

像狗一样看了一个上午终于在下午的时候狠下心来写对拍

对拍大法好qwq

一份暴力一份正解

~~以后有空再写线段树~~

暴力

#include <cstdio>
#include <algorithm>
#define p(x) ('0'<=x&&x<='9')
char cc; 
template <class T>
void read(T &x)
{
	cc=getchar(); x=0;
	while(!p(cc)) cc=getchar();
	while(p(cc)) x=x*10+cc-48,cc=getchar();
}

using namespace std;
#define N 500
int a[N];

int count(int l,int r)
{
	int cnt=0;
	for(int i=l;i<=r;i++) if(a[i]) cnt++;
	return cnt;
}

int solve(int l,int r)
{
	int node=0,cur[2],col=-1;
	cur[0]=cur[1]=0;
	for(int i=l;i<=r;i++)
	{
		if(col!=a[i])
		{
			if(~col)
				cur[col]=max(cur[col],node);
			col=a[i];
			node=0;
		}
		node++;
	}
	cur[col]=max(cur[col],node);
	return cur[1];
}

void fill(int l,int r,int col)
{
	for(int i=l;i<=r;i++) a[i]=col;
}

void rev(int l,int r)
{
	for(int i=l;i<=r;i++) a[i]^=1;
}
int n,m;
int main()
{
	freopen("BZOJ1858.in","r",stdin);
	freopen("BZOJ1858BF.out","w",stdout);
	read(n); read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=m;i++)
	{
		int _,b,c;
		read(_); read(b); read(c);
		if(_==0) fill(b+1,c+1,0);
		if(_==1) fill(b+1,c+1,1);
		if(_==2) rev(b+1,c+1);
		if(_==3) printf("%d",count(b+1,c+1));
		if(_==4) printf("%d",solve(b+1,c+1));
		if(m>1&&_>=3) puts("");
		printf("%d : ",i);
		for(int i=1;i<=n;i++) printf("%d ",a[i]);
		puts("");
	}
	return 0;
}

#include <cstdio>

#include <algorithm>

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

char cc;

template <class T>

void read(T &x)

{

cc=getchar(); x=0;

while(!p(cc)) cc=getchar();

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

}

using namespace std;

#define N 500

int a[N];

int count(int l,int r)

{

int cnt=0;

for(int i=l;i<=r;i++) if(a[i]) cnt++;

return cnt;

}

int solve(int l,int r)

{

int node=0,cur[2],col=-1;

cur[0]=cur[1]=0;

for(int i=l;i<=r;i++)

{

if(col!=a[i])

{

if(~col)

cur[col]=max(cur[col],node);

col=a[i];

node=0;

}

node++;

}

cur[col]=max(cur[col],node);

return cur[1];

}

void fill(int l,int r,int col)

{

for(int i=l;i<=r;i++) a[i]=col;

}

void rev(int l,int r)

{

for(int i=l;i<=r;i++) a[i]^=1;

}

int n,m;

int main()

{

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

freopen("BZOJ1858BF.out","w",stdout);

read(n); read(m);

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

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

{

int _,b,c;

read(_); read(b); read(c);

if(_==0) fill(b+1,c+1,0);

if(_==1) fill(b+1,c+1,1);

if(_==2) rev(b+1,c+1);

if(_==3) printf("%d",count(b+1,c+1));

if(_==4) printf("%d",solve(b+1,c+1));

if(m>1&&_>=3) puts("");

printf("%d : ",i);

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

puts("");

}

return 0;

}

正解

#include <cstdio>
#include <iostream>
#include <cmath>
#include <bitset>
#define p(x) ('0'<=x&&x<='9')
char cc; 
template <class T>
void read(T &x)
{
	cc=getchar(); x=0;
	while(!p(cc)) cc=getchar();
	while(p(cc)) x=x*10+cc-48,cc=getchar();
}
template <class T>
void comp(T &x,T y) { y>x?x=y:x=x; }
using namespace std;

#define N 100010
#define SQR 400
int n,m,SIZ,CNT;
bitset <SQR> B[SQR],U;
int L[SQR],R[SQR],Len_L[2][SQR],Len_R[2][SQR],MXL[2][SQR];
int belong[N],a;

int BFcount(int x,int l,int r)
{
	int ret=0;
	for(int i=l;i<=r;i++) if(B[x][i]==1) ret++;
	return ret;
}

int count(int l,int r)
{
	if(belong[l]==belong[r]) return BFcount(belong[l],(l-1)%SIZ+1,(r-1)%SIZ+1);
	int ret=BFcount(belong[l],(l-1)%SIZ+1,SIZ)+BFcount(belong[r],1,(r-1)%SIZ+1);
	for(int i=belong[l]+1;i<belong[r];i++) ret+=B[i].count();
	return ret;
}

int cur[2];
void calc(int x,int l,int r) //Checked
{
	int col=-1,node=0;
	cur[0]=cur[1]=0;
	for(int i=l;i<=r;i++)
	{
		if(col!=B[x][i])
		{
			if(~col) comp(cur[col],node);
			node=0;
			col=B[x][i];
		}
		node++;
	}
	comp(cur[B[x][r]],node);
}

int solve(int l,int r)
{
	int ret=0,ext=0;
	if(belong[l]==belong[r])  //Checked
	{
		calc(belong[l],(l-1)%SIZ+1,(r-1)%SIZ+1);
		return cur[1];
	}
	//Checked
	calc(belong[l],(l-1)%SIZ+1,SIZ);
	ret=cur[1];
	ext=min(Len_R[1][belong[l]],R[belong[l]]-l+1);
	//Checked
	for(int i=belong[l]+1;i<belong[r];i++)
	{
		if(MXL[1][i]==SIZ)
		{
			ext+=MXL[1][i];
			continue;
		}
		ext+=Len_L[1][i];
		comp(ret,ext);
		comp(ret,MXL[1][i]);
		ext=Len_R[1][i];
	}
	//Checked
	calc(belong[r],1,(r-1)%SIZ+1);
	ext+=min(Len_L[1][belong[r]],r-L[belong[r]]+1);
	comp(ret,ext);
	comp(ret,cur[1]);
	return ret;
}

void build(int x) //Checked
{
	int len=R[x]-L[x]+1;
	Len_L[1][x]=Len_L[0][x]=Len_R[0][x]=Len_R[1][x]=MXL[0][x]=MXL[1][x]=0;
	int node;
	for(node=2;B[x][node]==B[x][node-1]&&node<=len;node++);
	Len_L[B[x][1]][x]=node-1;
	for(node=len-1;B[x][node]==B[x][node+1]&&node;node--);
	Len_R[B[x][len]][x]=(len-node);
	int col=-1; node=0;
	for(int i=1;i<=len;i++)
	{
		if(col!=B[x][i])
		{
			if(~col) comp(MXL[col][x],node);
			node=0;
			col=B[x][i];
		}
		node++;
	}
	comp(MXL[col][x],node);
}

void fill(int l,int r,int col) // Checked
{
	if(belong[l]==belong[r])
	{
		for(int i=(l-1)%SIZ+1;i<=(r-1)%SIZ+1;i++)
			B[belong[l]][i]=col;
		build(belong[l]);
		return;
	}
	for(int i=(l-1)%SIZ+1;i<=SIZ;i++) B[belong[l]][i]=col;
	build(belong[l]);
	for(int i=1;i<=(r-1)%SIZ+1;i++) B[belong[r]][i]=col;
	build(belong[r]);
	for(int i=belong[l]+1;i<belong[r];i++)
	{
		if(col==1)
		{
			B[i]=U;
			MXL[0][i]=Len_L[0][i]=Len_R[0][i]=0;
			MXL[1][i]=Len_L[1][i]=Len_R[1][i]=SIZ;
		}
		else
		{
			B[i].reset();
			MXL[1][i]=Len_L[1][i]=Len_R[1][i]=0;
			MXL[0][i]=Len_L[0][i]=Len_R[0][i]=SIZ;
		}
	}
}

void rev(int l,int r) //Checked
{
	if(belong[l]==belong[r])
	{
		for(int i=(l-1)%SIZ+1;i<=(r-1)%SIZ+1;i++)
			B[belong[l]].flip(i);
		build(belong[l]);
		return;
	}
	for(int i=(l-1)%SIZ+1;i<=SIZ;i++)
		B[belong[l]].flip(i);
	build(belong[l]);
	for(int i=1;i<=(r-1)%SIZ+1;i++)
		B[belong[r]].flip(i);
	build(belong[r]);
	for(int i=belong[l]+1;i<belong[r];i++)
	{
		B[i]^=U;
		swap(Len_L[0][i],Len_L[1][i]);
		swap(Len_R[0][i],Len_R[1][i]);
		swap(MXL[0][i],MXL[1][i]);
	}
}

void init()
{
	read(n); read(m);
	SIZ=floor(sqrt(n));
	for(int i=1;i<=SIZ;i++) U[i]=1;
	CNT=(n-1)/SIZ +1;
	for(int i=1;i<=n;i++) belong[i]=(i-1)/SIZ +1;
	for(int i=1;i<=n;i++)
	{
		read(a);
		if(a)B[belong[i]][(i-1)%SIZ +1]=1;
	}
	for(int i=1;i<=CNT;i++)
	{
		L[i]=(i-1)*SIZ+1; R[i]=i*SIZ;
	}
	R[CNT]=n;
	for(int i=1;i<=CNT;i++) build(i);
}

int main()
{
//	freopen("BZOJ1858.in","r",stdin);
//	freopen("BZOJ1858.out","w",stdout);
	int a,b,c;
	init();
	for(int i=1;i<=m;i++)
	{
		read(a); read(b); read(c);
		if(a==0) fill(b+1,c+1,0);
		if(a==1) fill(b+1,c+1,1);
		if(a==2) rev(b+1,c+1);
		if(a==3) printf("%d\n",count(b+1,c+1));
		if(a==4) printf("%d\n",solve(b+1,c+1));
//		printf("%d : ",i);
//		for(int i=1;i<=n;i++) cout << B[belong[i]][(i-1)%SIZ+1] << " ";
//		puts("");
	}
	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

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

#include <cstdio>

#include <iostream>

#include <cmath>

#include <bitset>

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

char cc;

template <class T>

void read(T &x)

{

cc=getchar(); x=0;

while(!p(cc)) cc=getchar();

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

}

template <class T>

void comp(T &x,T y) { y>x?x=y:x=x; }

using namespace std;

#define N 100010

#define SQR 400

int n,m,SIZ,CNT;

bitset <SQR> B[SQR],U;

int L[SQR],R[SQR],Len_L[2][SQR],Len_R[2][SQR],MXL[2][SQR];

int belong[N],a;

int BFcount(int x,int l,int r)

{

int ret=0;

for(int i=l;i<=r;i++) if(B[x][i]==1) ret++;

return ret;

}

int count(int l,int r)

{

if(belong[l]==belong[r]) return BFcount(belong[l],(l-1)%SIZ+1,(r-1)%SIZ+1);

int ret=BFcount(belong[l],(l-1)%SIZ+1,SIZ)+BFcount(belong[r],1,(r-1)%SIZ+1);

for(int i=belong[l]+1;i<belong[r];i++) ret+=B[i].count();

return ret;

}

int cur[2];

void calc(int x,int l,int r) //Checked

{

int col=-1,node=0;

cur[0]=cur[1]=0;

for(int i=l;i<=r;i++)

{

if(col!=B[x][i])

{

if(~col) comp(cur[col],node);

node=0;

col=B[x][i];

}

node++;

}

comp(cur[B[x][r]],node);

}

int solve(int l,int r)

{

int ret=0,ext=0;

if(belong[l]==belong[r]) //Checked

{

calc(belong[l],(l-1)%SIZ+1,(r-1)%SIZ+1);

return cur[1];

}

//Checked

calc(belong[l],(l-1)%SIZ+1,SIZ);

ret=cur[1];

ext=min(Len_R[1][belong[l]],R[belong[l]]-l+1);

//Checked

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

{

if(MXL[1][i]==SIZ)

{

ext+=MXL[1][i];

continue;

}

ext+=Len_L[1][i];

comp(ret,ext);

comp(ret,MXL[1][i]);

ext=Len_R[1][i];

}

//Checked

calc(belong[r],1,(r-1)%SIZ+1);

ext+=min(Len_L[1][belong[r]],r-L[belong[r]]+1);

comp(ret,ext);

comp(ret,cur[1]);

return ret;

}

void build(int x) //Checked

{

int len=R[x]-L[x]+1;

Len_L[1][x]=Len_L[0][x]=Len_R[0][x]=Len_R[1][x]=MXL[0][x]=MXL[1][x]=0;

int node;

for(node=2;B[x][node]==B[x][node-1]&&node<=len;node++);

Len_L[B[x][1]][x]=node-1;

for(node=len-1;B[x][node]==B[x][node+1]&&node;node--);

Len_R[B[x][len]][x]=(len-node);

int col=-1; node=0;

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

{

if(col!=B[x][i])

{

if(~col) comp(MXL[col][x],node);

node=0;

col=B[x][i];

}

node++;

}

comp(MXL[col][x],node);

}

void fill(int l,int r,int col) // Checked

{

if(belong[l]==belong[r])

{

for(int i=(l-1)%SIZ+1;i<=(r-1)%SIZ+1;i++)

B[belong[l]][i]=col;

build(belong[l]);

return;

}

for(int i=(l-1)%SIZ+1;i<=SIZ;i++) B[belong[l]][i]=col;

build(belong[l]);

for(int i=1;i<=(r-1)%SIZ+1;i++) B[belong[r]][i]=col;

build(belong[r]);

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

{

if(col==1)

{

B[i]=U;

MXL[0][i]=Len_L[0][i]=Len_R[0][i]=0;

MXL[1][i]=Len_L[1][i]=Len_R[1][i]=SIZ;

}

else

{

B[i].reset();

MXL[1][i]=Len_L[1][i]=Len_R[1][i]=0;

MXL[0][i]=Len_L[0][i]=Len_R[0][i]=SIZ;

}

void rev(int l,int r) //Checked

{

if(belong[l]==belong[r])

{

for(int i=(l-1)%SIZ+1;i<=(r-1)%SIZ+1;i++)

B[belong[l]].flip(i);

build(belong[l]);

return;

}

for(int i=(l-1)%SIZ+1;i<=SIZ;i++)

B[belong[l]].flip(i);

build(belong[l]);

for(int i=1;i<=(r-1)%SIZ+1;i++)

B[belong[r]].flip(i);

build(belong[r]);

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

{

B[i]^=U;

swap(Len_L[0][i],Len_L[1][i]);

swap(Len_R[0][i],Len_R[1][i]);

swap(MXL[0][i],MXL[1][i]);

}

void init()

{

read(n); read(m);

SIZ=floor(sqrt(n));

for(int i=1;i<=SIZ;i++) U[i]=1;

CNT=(n-1)/SIZ +1;

for(int i=1;i<=n;i++) belong[i]=(i-1)/SIZ +1;

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

{

read(a);

if(a)B[belong[i]][(i-1)%SIZ +1]=1;

}

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

{

L[i]=(i-1)*SIZ+1; R[i]=i*SIZ;

}

R[CNT]=n;

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

}

int main()

{

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

// freopen("BZOJ1858.out","w",stdout);

int a,b,c;

init();

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

{

read(a); read(b); read(c);

if(a==0) fill(b+1,c+1,0);

if(a==1) fill(b+1,c+1,1);

if(a==2) rev(b+1,c+1);

if(a==3) printf("%d\n",count(b+1,c+1));

if(a==4) printf("%d\n",solve(b+1,c+1));

// printf("%d : ",i);

// for(int i=1;i<=n;i++) cout << B[belong[i]][(i-1)%SIZ+1] << " ";

// puts("");

}

return 0;

}