POI2010题解

我也不知道我为什么就开始刷POI了

有些题目咕掉了所以不完整（我都不知道POI到底有多少题）

[BZOJ2079][Poi2010]Guilds

（貌似bz跟洛谷上的不是一个题？）

并查集判孤立点就行了。

#include<cstdio>

#include<algorithm>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 2e5+5;

int n,m,fa[N],sz[N];

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

int main(){

	n=gi();m=gi();

	for (int i=1;i<=n;++i) fa[i]=i,sz[i]=1;

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

		int u=gi(),v=gi();

		u=find(u);v=find(v);if (sz[u]<sz[v]) swap(u,v);

		if (u^v) sz[u]+=sz[v],fa[v]=u;

	}

	for (int i=1;i<=n;++i) if (sz[find(i)]==1) return puts("NIE"),0;

	return puts("TAK"),0;

}

[BZOJ2080][Poi2010]Railway

这个题是这的神仙。膜了Claris老师的题解才做出来的。

考虑什么时候两个点不能进同一个栈：当且仅当\(i<j,a_i<a_j\)，且存在一个\(k>j\)使得\(a_k<a_i\)时，\(i,j\)不能在同一个栈里。这样的\(i,j\)点对连边然后跑二分图染色就好了。但是显然暴力建图是承受不了的。

记\(b_i\)表示序列的后缀最小值，即\(b_i=\min_{j=i}^na_j\)，那么上述条件就变成了\(b_j<a_i<a_j\)。

再记一个\(c_i\)表示\(\max\{j|b_j<i\}\)。

开两棵线段树，一棵以原下标为下标维护\(a\)的最大值，一棵以\(a\)值为下标维护原下标的最小值。

可以发现，一个点\(i\)与之相连的是下标在\([i+1,c_{a_i}]\)中\(a\)值大于\(a_i\)的数，以及\(a\)值在\([b_i+1,a_i-1]\)中的所有下标小于\(i\)的数，线段树区间查询，查完就把那个点删掉，就可以走遍整棵\(dfs\)树的树边，构造出一组颜色序列。

然后已知了颜色就再判一下非树边会不会无解就行了。也就是对于每个\(j\)来说，看看有没有与其同色的满足\(b_j<a_i<a_j\)的\(i\)即可。

#include<cstdio>

#include<algorithm>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 1e5+5;

int n,a[N],f[N],b[N],c[N],col[N],bit[3][N];

struct segment_tree{

	int t[N<<2],ty;

	int cal(int i,int j){

		if (!i||!j) return i|j;

		return ty?(i<j?i:j):(a[i]>a[j]?i:j);

	}

	void build(int x,int l,int r){

		if (l==r) {t[x]=ty?f[l]:l;return;}

		int mid=l+r>>1;

		build(x<<1,l,mid);build(x<<1|1,mid+1,r);

		t[x]=cal(t[x<<1],t[x<<1|1]);

	}

	void modify(int x,int l,int r,int p){

		if (l==r) {t[x]=0;return;}

		int mid=l+r>>1;

		if (p<=mid) modify(x<<1,l,mid,p);

		else modify(x<<1|1,mid+1,r,p);

		t[x]=cal(t[x<<1],t[x<<1|1]);

	}

	int query(int x,int l,int r,int ql,int qr){

		if (ql>qr) return 0;if (l>=ql&&r<=qr) return t[x];

		int mid=l+r>>1;

		if (qr<=mid) return query(x<<1,l,mid,ql,qr);

		if (ql>mid) return query(x<<1|1,mid+1,r,ql,qr);

		return cal(query(x<<1,l,mid,ql,qr),query(x<<1|1,mid+1,r,ql,qr));

	}

}T1,T2;

void dfs(int x,int z){

	T1.modify(1,1,n,x);T2.modify(1,1,n,a[x]);col[x]=z;

	while (233){

		int y=T1.query(1,1,n,x+1,c[a[x]]);

		if (!y||a[y]<a[x]) break;dfs(y,z^3);

	}

	while (666){

		int y=T2.query(1,1,n,b[x]+1,a[x]-1);

		if (!y||y>x) break;dfs(y,z^3);

	}

}

void mdf(int j,int k){while(k<=n)++bit[j][k],k+=k&-k;}

int qry(int j,int k){int s=0;while(k)s+=bit[j][k],k^=k&-k;return s;}

int main(){

	n=gi();

	for (int i=1;i<=n;++i) a[i]=gi(),f[a[i]]=i;

	b[n+1]=1e9;

	for (int i=n;i;--i) b[i]=min(b[i+1],a[i]);

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

		while (j<=n&&b[j+1]<i) ++j;

		c[i]=j;

	}

	T2.ty=1;T1.build(1,1,n);T2.build(1,1,n);

	for (int i=1;i<=n;++i) if (!col[i]) dfs(i,1);

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

		if (qry(col[i],a[i]-1)-qry(col[i],b[i])>0) return puts("NIE"),0;

		mdf(col[i],a[i]);

	}

	puts("TAK");

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

	puts("");return 0;

}

[BZOJ2081][Poi2010]Beads

\(Hash\)+去重即可。复杂度\(O(n\log^2n)\) 。

#include<cstdio>

#include<algorithm>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

#define ull unsigned long long

const int N = 2e5+5;

const ull base = 20020415;

int n,a[N],ans,len,q[N];ull pw[N],h1[N],h2[N],tmp[N];

ull cal(int l,int r){

	ull s1=h1[r]-h1[l-1]*pw[r-l+1];

	ull s2=h2[l]-h2[r+1]*pw[r-l+1];

	return min(s1,s2);

}

int main(){

	n=gi();

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

	for (int i=1;i<=n;++i) h1[i]=h1[i-1]*base+a[i];

	for (int i=n;i>=1;--i) h2[i]=h2[i+1]*base+a[i];

	for (int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*base;

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

		int res=0;

		for (int j=1;j+i-1<=n;j+=i) tmp[++res]=cal(j,j+i-1);

		sort(tmp+1,tmp+res+1);

		res=unique(tmp+1,tmp+res+1)-tmp-1;

		if (res>ans) ans=res,q[len=1]=i;

		else if (res==ans) q[++len]=i;

	}

	printf("%d %d\n",ans,len);

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

	return puts(""),0;

}

[BZOJ2082][Poi2010]Divine divisor

\(\mbox{Pollard_Rho}\)质因数分解，取次数最高的那个质因子。第二问答案一定是\(2^k-1\)的形式，随便写个高精，只要支持乘\(2\)就行了。

发现了一种比之前写的快三十倍的新写法，可以通过洛谷模板。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define ll long long

ll gi(){

	ll x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

ll mul(ll x,ll y,ll mod){

	return (x*y-(ll)((long double)x/mod*y+0.5)*mod+mod)%mod;

}

ll fastpow(ll x,ll y,ll mod){

	ll res=1;

	while (y) {if (y&1) res=mul(res,x,mod);x=mul(x,x,mod);y>>=1;}

	return res;

}

ll f[]={2,3,5,7,11,13,17,19,23,29};

bool MR(ll p){

	for (int i=0;i<10;++i){

		if (p<=f[i]) break;

		if (fastpow(f[i],p-1,p)!=1) return false;

		ll pp=p-1;

		while (~pp&1){

			pp>>=1;ll y=fastpow(f[i],pp,p);

			if (mul(y,y,p)==1&&y!=1&&y!=p-1) return false;

		}

	}

	return true;

}

ll PR(ll n){

	ll x=0,y=0,t=1,q=1,a=1+rand()%(n-1);

	for (int k=2;true;k<<=1,y=x,q=1){

		for (int i=1;i<k;++i){

			x=(mul(x,x,n)+a)%n;

			q=mul(q,abs(x-y),n);

			if (!(i&127)){

				t=__gcd(q,n);

				if (t>1) break;

			}

		}

		if (t>1||(t=__gcd(q,n))>1) break;

	}

	if (t==n) t=1;return t;

}

ll a[50000],b[50000];int len,c[50000],cnt,ans;

void fact(ll n){

	if (n==1) return;

	if (MR(n)) {a[++len]=n;return;}

	ll p=n;while (p==n) p=PR(p);

	fact(p);fact(n/p);

}

const int N = 1000000000;

struct bigint{

	int a[5000],w;

	bigint(){a[w=0]=1;}

	void mul(){

		for (int i=0;i<=w;++i) a[i]<<=1;

		for (int i=0;i<=w;++i) a[i+1]+=a[i]/N,a[i]%=N;

		while (a[w+1]) ++w,a[w+1]+=a[w]/N,a[w]%=N;

	}

	void print(){

		printf("%d",a[w]);

		for (int i=w-1;~i;--i) printf("%09d",a[i]);

		puts("");

	}

}Ans;

int main(){

	srand(20020415);

	int m=gi();

	while (m--) fact(gi());

	sort(a+1,a+len+1);

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

		if (i==1||a[i]>a[i-1]) b[++cnt]=a[i];

		++c[cnt];

	}

	for (int i=1;i<=cnt;++i) ans=max(ans,c[i]);

	for (int i=1;i<=cnt;++i) if (c[i]==ans) Ans.mul();

	printf("%d\n",ans);--Ans.a[0];Ans.print();

	return 0;

}

[BZOJ2083][Poi2010]Intelligence test

\(vector\)上二分。

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

vector<int>v[1000005];

vector<int>::iterator it;

int main(){

	int m=gi();

	for (int i=1;i<=m;++i) v[gi()].push_back(i);

	int n=gi();while (n--){

		int l=gi(),lst=0,ans=1;

		for (int i=1;i<=l;++i){

			int x=gi();

			it=upper_bound(v[x].begin(),v[x].end(),lst);

			if (it==v[x].end()) ans=0;

			else lst=*it;

		}

		puts(ans?"TAK":"NIE");

	}

	return 0;

}

[BZOJ2084][Poi2010]Antisymmetry

一个合法串一定满足：后半段\(01\)翻转以后是回文。

把原串复制一份\(01\)翻转，然后隔一个位置插一个插进原串。这样合法串就变成了一个偶长度的回文串。

把\(Manacher\)魔改一下就可以做只有偶长度的回文串啦。

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 1e6+5;

int n,s[N],p[N],mx,id;char str[N];long long ans;

int main(){

	scanf("%d%s",&n,str);

	for (int i=0;i<n;++i) s[i<<1]=str[i]-'0',s[i<<1|1]=s[i<<1]^1;

	n<<=1;

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

		p[i]=mx>i?min(p[2*id-i],mx-i):0;

		while (i+p[i]<n&&i-p[i]-1>=0&&s[i+p[i]]==s[i-p[i]-1]) ++p[i];

		ans+=p[i]>>1;if (i+p[i]>mx) mx=i+p[i],id=i;

	}

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

	return 0;

}

[BZOJ2086][Poi2010]Blocks

就是要找一个区间使得平均数\(\ge k\)。

把每个数减\(k\)再记前缀和，相当于求两个位置，满足前面小于等于后面，要求下标差最大。找出所有的前缀最小值，从后往前扫一遍即可。

#include<cstdio>

#include<algorithm>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

#define ll long long

const int N = 1e6+5;

int n,m,a[N],q[N],top,ans;long long sum[N],k;

int main(){

	n=gi();m=gi();

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

	while (m--){

		k=gi();top=ans=0;

		for (int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i]-k;

		for (int i=1;i<=n;++i) if (sum[i]<sum[q[top]]) q[++top]=i;

		for (int i=n;i;--i){

			while (top&&sum[i]>=sum[q[top-1]]) --top;

			ans=max(ans,i-q[top]);

		}

		printf("%d ",ans);

	}

	puts("");return 0;

}

[BZOJ2087][Poi2010]Sheep

先求一下凸包上任意两点之间连边后两侧的羊数是否都是偶数，然后直接\(O(n^3)\)区间\(dp\)。

注意一下一条对角线恰好经过某一只羊的情况（这样的边不能连）。

#include<cstdio>

#include<algorithm>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 605;

struct node{

	int x,y;

	node operator - (const node &b) const

		{return (node){x-b.x,y-b.y};}

	int operator * (const node &b) const

		{return x*b.y-y*b.x;}

}a[N],b[N<<6],now;

bool cmp(node a,node b){

	return (a-now)*(b-now)<0;

}

int n,m,mod,f[N][N],g[N][N];

int main(){

	n=gi();m=gi();mod=gi();

	for (int i=1;i<=n;++i) a[i]=(node){gi(),gi()};

	for (int i=1;i<=m;++i) b[i]=(node){gi(),gi()};

	now=a[1];sort(a+2,a+n+1,cmp);

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

		now=a[i];sort(b+1,b+m+1,cmp);

		for (int j=i+1,k=0;j<=n;++j){

			while (k<m&&(b[k+1]-now)*(a[j]-now)<0) ++k;

			if ((k&1)||(k<m&&(b[k+1]-now)*(a[j]-now)==0)) continue;

			f[i][j]=1;

		}

	}

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

	for (int l=3;l<=n;++l)

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

			for (int k=i+1;k<j;++k)

				if (f[i][k]&&f[k][j])

					(g[i][j]+=g[i][k]*g[k][j])%=mod;

	printf("%d\n",g[1][n]);return 0;

}

[BZOJ2088][Poi2010]Teleportation

可以发现最终的图是一个分层图，共四层，每层内连成一个完全图，相邻两层之间两两连边。其中与\(1\)相连的点在第一层，与\(2\)相连的点在第四层。

很显然没有跟\(1,2\)连边的点不会放在第一层或是最后一层，因为一定不更优，不如放在中间两层。

与与\(1\)相邻的点相邻的点在第二层，与与\(2\)相邻的点相邻的点在第三层。

其余的点是放在第二层还是放第三层呢？只需要比较第一层与第四层的大小即可。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 2e6+5;

int n,m,to[N],nxt[N],head[N],cnt,vis[N],s[6];

long long ans;

int main(){

	n=gi();m=gi();vis[1]=vis[2]=-1;

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

		int u=gi(),v=gi();

		to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;

		to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;

	}

	for (int e=head[1];e;e=nxt[e]) vis[to[e]]=1,++s[1];

	for (int e=head[2];e;e=nxt[e]) vis[to[e]]=4,++s[4];

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

		if (vis[i]==1)

			for (int e=head[i];e;e=nxt[e])

				if (!vis[to[e]]) vis[to[e]]=2,++s[2];

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

		if (vis[i]==4)

			for (int e=head[i];e;e=nxt[e])

				if (!vis[to[e]]) vis[to[e]]=3,++s[3];

	for (int i=3;i<=n;++i) if (!vis[i]) ++s[s[1]>s[4]?2:3];

	s[0]=s[5]=1;

	for (int i=0;i<=4;++i) ans+=1ll*s[i]*s[i+1];

	for (int i=1;i<=4;++i) ans+=1ll*s[i]*(s[i]-1)>>1;

	printf("%lld\n",ans-m);return 0;

}

[BZOJ2090][Poi2010]Monotonicity

（2089是弱化版）

设\(f_i\)表示\(a_i\)作为序列的末尾的最长长度。考虑把\(f_i\)转移出去，这样下一步的符号也就确定了。拿两棵线段树分别维护一下就行了。

（洛谷上需要输出方案）

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 1e6+5;

int n,m,a[N],b[N],las[N],f[N],pre[N],ans,S[N],top;char s[10];

int Max(int i,int j){return f[i]>f[j]?i:j;}

struct segment_tree{

	int t[N<<2];

	void modify(int x,int l,int r,int p,int v){

		t[x]=Max(t[x],v);if (l==r) return;int mid=l+r>>1;

		if (p<=mid) modify(x<<1,l,mid,p,v);

		else modify(x<<1|1,mid+1,r,p,v);

	}

	int query(int x,int l,int r,int ql,int qr){

		if (ql>qr) return 0;if (l>=ql&&r<=qr) return t[x];

		int mid=l+r>>1,s=0;

		if (ql<=mid) s=Max(s,query(x<<1,l,mid,ql,qr));

		if (qr>mid) s=Max(s,query(x<<1|1,mid+1,r,ql,qr));

		return s;

	}

}T1,T2;

int main(){

	n=gi();m=gi();

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

	for (int i=1;i<=m;++i) scanf("%s",s),b[i]=s[0]=='='?2:s[0]=='>';

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

		pre[i]=Max(las[a[i]],Max(T1.query(1,1,N,1,a[i]-1),T2.query(1,1,N,a[i]+1,N)));

		f[i]=f[pre[i]]+1;ans=Max(ans,i);int op=b[(f[i]-1)%m+1];

		if (!op) T1.modify(1,1,N,a[i],i);

		else if (op&1) T2.modify(1,1,N,a[i],i);

		else las[a[i]]=i;

	}

	printf("%d\n",f[ans]);

	for (int i=ans;i;i=pre[i]) S[++top]=i;

	for (int i=top;i;--i) printf("%d ",a[S[i]]);puts("");

	return 0;

}

[BZOJ2091][Poi2010]The Minima Game

很显然每次选的都会是最大的若干个数不然不可能更优。

所以就可以\(dp\)了。设\(f_i\)表示前\(i\)小被选完，先手比后手多赢多少。转移\(f_i=\max_{j<i}a_{j+1}-f_j\)。

#include<cstdio>

#include<algorithm>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

#define ll long long

const int N = 1e6+5;

int n,a[N];ll f[N],s;

int main(){

	n=gi();

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

	sort(a+1,a+n+1);s=a[1];

	for (int i=1;i<=n;++i) f[i]=s,s=max(s,a[i+1]-f[i]);

	printf("%lld\n",f[n]);return 0;

}

[BZOJ2093][Poi2010]Frog

先线性处理出每个位置跳一次跳到的位置，然后相当于要求这个置换的\(m\)次方。倍增数组开不下，可以采用快速幂的写法，空间复杂度\(O(n)\)。

#include<cstdio>

#include<algorithm>

using namespace std;

#define ll long long

ll gi(){

	ll x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 1e6+5;

int n,k,S[N],T[N],tmp[N];ll m,a[N];

void mul(int *f,int *g){

	for (int i=1;i<=n;++i) tmp[i]=g[f[i]];

	for (int i=1;i<=n;++i) f[i]=tmp[i];

}

int main(){

	n=gi();k=gi();m=gi();

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

	for (int i=1,l=1,r=min(k+1,n);i<=n;++i){

		while (r<n&&a[r+1]-a[i]<a[i]-a[l]) ++l,++r;

		S[i]=i;T[i]=a[r]-a[i]>a[i]-a[l]?r:l;

	}

	while (m) {if (m&1) mul(S,T);mul(T,T);m>>=1;}

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

	puts("");return 0;

}

[BZOJ2095][Poi2010]Bridges

先判无解，有奇度点当然就无解。

对于每条边先随便定向，假设是\(u \to v\)，然后再考虑反悔。反悔会使\(u\)的度数\(+2\)而\(v\)的度数\(-2\)。而每个点都要满足度数为\(0\)，所以从源汇连一些边不足一下，判补的这些边能不能流满。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 2005;

struct edge{int to,nxt,w;}a[N<<3];

int n,m,L,R,u[N],v[N],x[N],y[N],du[N],tot,head[N],cnt,S,T,dep[N],cur[N];

queue<int>Q;

void link(int u,int v,int w){

	a[++cnt]=(edge){v,head[u],w};head[u]=cnt;

	a[++cnt]=(edge){u,head[v],0};head[v]=cnt;

}

bool bfs(){

	memset(dep,0,sizeof(dep));

	dep[S]=1;Q.push(S);

	while (!Q.empty()){

		int u=Q.front();Q.pop();

		for (int e=head[u];e;e=a[e].nxt)

			if (a[e].w&&!dep[a[e].to])

				dep[a[e].to]=dep[u]+1,Q.push(a[e].to);

	}

	return dep[T];

}

int dfs(int u,int f){

	if (u==T) return f;int res=0;

	for (int &e=cur[u];e;e=a[e].nxt)

		if (a[e].w&&dep[a[e].to]==dep[u]+1){

			int d=dfs(a[e].to,min(a[e].w,f));

			a[e].w-=d;a[e^1].w+=d;f-=d;res+=d;

			if (!f) break;

		}

	if (!res) dep[u]=0;return res;

}

int dinic(){

	int res=0;

	while (bfs()){

		for (int i=1;i<=T;++i) cur[i]=head[i];

		res+=dfs(S,1000000000);

	}

	return res;

}

bool check(int mid){

	memset(head,0,sizeof(head));cnt=1;

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

		if (y[i]<=mid) link(u[i],v[i],1);

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

		if (du[i]>0) link(S,i,du[i]>>1);

		if (du[i]<0) link(i,T,-du[i]>>1);

	}

	return dinic()==tot;

}

int main(){

	n=gi();m=gi();S=n+1;T=S+1;

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

		u[i]=gi();v[i]=gi();x[i]=gi();y[i]=gi();

		if (x[i]>y[i]) swap(u[i],v[i]),swap(x[i],y[i]);

		L=max(L,x[i]);R=max(R,y[i]);

		++du[u[i]];--du[v[i]];

	}

	int fg=1;

	for (int i=1;i<=n;++i) if (du[i]&1) fg=0;

	if (!fg) return puts("NIE"),0;

	for (int i=1;i<=n;++i) if (du[i]>0) tot+=du[i]>>1;

	while (L<R){

		int mid=L+R>>1;

		if (check(mid)) R=mid;

		else L=mid+1;

	}

	printf("%d\n",R);return 0;

}

[BZOJ2096][Poi2010]Pilots

维护两个单调队列，就行了。

#include<cstdio>

#include<algorithm>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 3e6+5;

int n,k,a[N],q1[N],h1=1,t1,q2[N],h2=1,t2,ans;

int main(){

	k=gi();n=gi();

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

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

		while (h1<=t1&&a[i]>a[q1[t1]]) --t1;

		while (h2<=t2&&a[i]<a[q2[t2]]) --t2;

		q1[++t1]=q2[++t2]=i;

		while (a[q1[h1]]-a[q2[h2]]>k)

			if (q1[h1]<q2[h2]) j=q1[h1]+1,++h1;

			else j=q2[h2]+1,++h2;

		ans=max(ans,i-j+1);

	}

	printf("%d\n",ans);return 0;

}

巴特西

POI2010题解

POI2010题解

[BZOJ2079][Poi2010]Guilds

[BZOJ2080][Poi2010]Railway

[BZOJ2081][Poi2010]Beads

[BZOJ2082][Poi2010]Divine divisor

[BZOJ2083][Poi2010]Intelligence test

[BZOJ2084][Poi2010]Antisymmetry

[BZOJ2086][Poi2010]Blocks

[BZOJ2087][Poi2010]Sheep

[BZOJ2088][Poi2010]Teleportation

[BZOJ2090][Poi2010]Monotonicity

[BZOJ2091][Poi2010]The Minima Game

[BZOJ2093][Poi2010]Frog

[BZOJ2095][Poi2010]Bridges

[BZOJ2096][Poi2010]Pilots

最新文章

热门文章