【切题】POI2010

乱搞记

切得差不多了

P1

还是打不过神题啊（可能有些还行？）

Guilds

思路：判一下有没有孤立点即可。

Railway

思路：

  • 如果存在$i,j,k$满足$i<j<k,a_k<a_i<a_j$，那么$i,j$不能在一个栈中；
  • 以此建图；
  • 然后图的二分图染色等价于其生成树的二分图染色；
  • 用线段树维护即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
#define N 300000
#define INF 0x3f3f3f3f
int n,x,now,tp1,tp2,s1[N],s2[N],c[N],d[N],seg0[N],seg1[N],pos[N],col[N];
struct node{int v,i;}a[N];
bool cmpv(node p,node q){return p.v<q.v;}
bool cmpi(node p,node q){return p.i<q.i;}
#define ls (x<<1)
#define rs (x<<1|1)
void build(int x,int l,int r){
	if (l==r){seg0[x]=a[l].v; seg1[x]=pos[l]; return;}
	int mid=(l+r)>>1;
	build(ls,l,mid); build(rs,mid+1,r);
	seg0[x]=max(seg0[ls],seg0[rs]); seg1[x]=min(seg1[ls],seg1[rs]);
}
void del0(int x,int l,int r,int k){
	if (l==r){seg0[x]=0; return;}
	int mid=(l+r)>>1;
	if (k<=mid) del0(ls,l,mid,k); else del0(rs,mid+1,r,k);
	seg0[x]=max(seg0[ls],seg0[rs]);
}
void del1(int x,int l,int r,int k){
	if (l==r){seg1[x]=INF; return;}
	int mid=(l+r)>>1;
	if (k<=mid) del1(ls,l,mid,k); else del1(rs,mid+1,r,k);
	seg1[x]=min(seg1[ls],seg1[rs]);
}
int qry0(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return seg0[x];
	int mid=(l+r)>>1,tmp=0;
	if (L<=mid) tmp=max(tmp,qry0(ls,l,mid,L,R));
	if (R>mid) tmp=max(tmp,qry0(rs,mid+1,r,L,R));
	return tmp;
}
int qry1(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return seg1[x];
	int mid=(l+r)>>1,tmp=INF;
	if (L<=mid) tmp=min(tmp,qry1(ls,l,mid,L,R));
	if (R>mid) tmp=min(tmp,qry1(rs,mid+1,r,L,R));
	return tmp;
}
#undef ls
#undef rs
void dfs(int x,int w){
	del0(1,1,n,x); del1(1,1,n,a[x].v); col[x]=w;
	if (c[a[x].v]>x){
		int tmp;
		while ((tmp=qry0(1,1,n,x+1,c[a[x].v]))>a[x].v){
			dfs(pos[tmp],3-w);
		}
	}
	if (d[x]<a[x].v){
		int tmp;
		while ((tmp=qry1(1,1,n,d[x],a[x].v-1))<x)
			dfs(tmp,3-w);
	}
}
	
int main(){
	scanf("%d",&n); now=1;
	for (int i=1;i<=n;i++){scanf("%d",&a[i].v); a[i].i=i; pos[a[i].v]=i;}
	sort(a+1,a+n+1,cmpv);
	int mx=0; for (int i=1;i<=n;i++){c[i]=max(c[i],mx); mx=max(mx,a[i].i);}
	sort(a+1,a+n+1,cmpi); memset(d,0x3f,sizeof d);
	int mn=INF; for (int i=n;i>=1;i--){d[i]=min(d[i],mn); mn=min(mn,a[i].v);}
	build(1,1,n);
	for (int i=1;i<=n;i++) if (!col[i]) dfs(i,1);
	int now=1;
	for (int i=1;i<=n;i++){
		if (col[i]==1) s1[++tp1]=a[i].v;
		else s2[++tp2]=a[i].v;
		while (s1[tp1]==now||s2[tp2]==now){
			if (s1[tp1]==now) tp1--; else tp2--;
			now++;
		}
	}
	if (now>n){
		puts("TAK");
		for (int i=1;i<=n;i++) printf(i==n?"%d\n":"%d ",col[i]);
	}
	else puts("NIE");
	
	return 0;
}

Beads

思路：蛤希一下即可。

Intelligence test

思路：枚举原序列，贪心取即可。

Antisymmetry

思路：枚举中点，二分+蛤希即可。

Hamsters

思路：用$f_{i,j}$表示从 串$i$到串$j$还需要接的字母个数；类似floyd，用矩乘优化。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define uLL unsigned LL
#define N 205
#define M 120000
#define B 233
#define INF 0x3f3f3f3f3f3f3f3fLL
LL n,m,ans,len[N];
uLL pw[M],f[N][M];
char s[N][M];
struct matrix{
	LL f[N][N];
	matrix(){memset(f,0x3f,sizeof f);}
	void clear(){memset(f,0,sizeof f);}
	matrix operator * (const matrix P) const{
		matrix ret;
		for (LL k=1;k<=n;k++)
			for (LL i=1;i<=n;i++)
				for (LL j=1;j<=n;j++) ret.f[i][j]=min(ret.f[i][j],f[i][k]+P.f[k][j]);
		return ret;
	}
}G;
int main(){
	scanf("%lld%lld",&n,&m);
	for (LL i=1;i<=n;i++){
		scanf("%s",s[i]+1); len[i]=strlen(s[i]+1);
		for (LL j=1;j<=len[i];j++) f[i][j]=f[i][j-1]*B+s[i][j];
	}
	pw[0]=1; for (int i=1;i<=110000;i++) pw[i]=pw[i-1]*B;
	for (LL i=1;i<=n;i++)
		for (LL j=1;j<=n;j++)
			for (LL k=0;k<len[i]&&k<len[j];k++)
				if (f[i][len[i]]-f[i][len[i]-k]*pw[k]==f[j][k])
					G.f[i][j]=len[j]-k;
	matrix A; A.clear();
	bool fl=1; for (m--;m;m>>=1,G=G*G) if (m&1){if (fl) A=G,fl=0; else A=A*G;}
	ans=INF;
	for (LL i=1;i<=n;i++)
		for (LL j=1;j<=n;j++) ans=min(ans,A.f[i][j]+len[i]);
	printf("%lld\n",ans);
	
	return 0;
}

Blocks

思路：即求区间平均值大于等于$k$的最长区间，单调栈维护。

Teleportation

思路：分层贪心即可。

Monotonicity 2

思路：

  • 如果$i$出现了，位置一定是$f_i$；
  • 线段树优化dp即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
#define N 1200000
int n,m,ans,a[N],f[N],s0[N],s1[N*4],s2[N*4];
char s[N];
#define ls (x<<1)
#define rs (x<<1|1)
void mdf1(int x,int l,int r,int t,int k){
	if (l==r){s1[x]=max(s1[x],k); return;}
	int mid=(l+r)>>1;
	if (t<=mid) mdf1(ls,l,mid,t,k); else mdf1(rs,mid+1,r,t,k);
	s1[x]=max(s1[ls],s1[rs]);
}
void mdf2(int x,int l,int r,int t,int k){
	if (l==r){s2[x]=max(s2[x],k); return;}
	int mid=(l+r)>>1;
	if (t<=mid) mdf2(ls,l,mid,t,k); else mdf2(rs,mid+1,r,t,k);
	s2[x]=max(s2[ls],s2[rs]);
}
int qry1(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return s1[x];
	int mid=(l+r)>>1,tmp=0;
	if (L<=mid) tmp=max(tmp,qry1(ls,l,mid,L,R));
	if (R>mid) tmp=max(tmp,qry1(rs,mid+1,r,L,R));
	return tmp;
}
int qry2(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return s2[x];
	int mid=(l+r)>>1,tmp=0;
	if (L<=mid) tmp=max(tmp,qry2(ls,l,mid,L,R));
	if (R>mid) tmp=max(tmp,qry2(rs,mid+1,r,L,R));
	return tmp;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=m;i++)
		for (s[i]=getchar();s[i]!='<'&&s[i]!='>'&&s[i]!='=';s[i]=getchar());
	for (int i=1;i<=n;i++){
		f[i]=1;
		f[i]=max(f[i],s0[a[i]]+1);
		if (a[i]-1>0) f[i]=max(f[i],qry1(1,1,1000000,1,a[i]-1)+1);
		if (a[i]+1<1000000) f[i]=max(f[i],qry2(1,1,1000000,a[i]+1,1000000)+1);
		if (s[(f[i]-1)%m+1]=='=') s0[a[i]]=max(s0[a[i]],f[i]);
		if (s[(f[i]-1)%m+1]=='<') mdf1(1,1,1000000,a[i],f[i]);
		if (s[(f[i]-1)%m+1]=='>') mdf2(1,1,1000000,a[i],f[i]);
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	
	return 0;
}

Frog

思路：倍增即可。

Bridges

思路：

  • 混合图欧拉回路；
  • 给无向边随机分配方向，判断奇偶性是否合法；
  • 然后网络流调整无向边方向。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
#define N 8000
#define INF 0x3f3f3f3f
#define fill(x,y) memset(x,y,sizeof x)
int n,m,tot,ans,S,T,mn,a[N],b[N],x[N],y[N],lvl[N],head[N],iter[N],q[N],d1[N],d2[N];
struct edge{int v,cap,rev,nxt;}e[N];
void add(int x,int y,int z){
	e[++tot].v=y; e[tot].cap=z; e[tot].rev=tot+1; e[tot].nxt=head[x]; head[x]=tot;
	e[++tot].v=x; e[tot].cap=0; e[tot].rev=tot-1; e[tot].nxt=head[y]; head[y]=tot;
}
void bfs(int S){
	memset(lvl,-1,sizeof lvl);
	int tt=0,ww=1; q[1]=S; lvl[S]=0;
	while (tt<ww){
		int u=q[++tt];
		for (int i=head[u],v;i;i=e[i].nxt)
			if (e[i].cap>0&&lvl[v=e[i].v]==-1){
				lvl[v]=lvl[u]+1;
				q[++ww]=v;
			}
	}
}
int dfs(int u,int T,int f){
	if (u==T) return f;
	for (int &i=iter[u],v;i;i=e[i].nxt)
		if (e[i].cap>0&&lvl[v=e[i].v]>lvl[u]){
			int tmp=dfs(v,T,min(e[i].cap,f));
			if (tmp>0){e[i].cap-=tmp; e[e[i].rev].cap+=tmp; return tmp;}
		}
	return 0;
}
int dinic(int S,int T){
	int flow=0;
	while (1){
		bfs(S); if (lvl[T]<0) break;
		memcpy(iter,head,sizeof iter);
		for (int f=dfs(S,T,INF);f>0;f=dfs(S,T,INF)) flow+=f;
	}
	return flow;
}
bool check(int k){
	fill(d1,0); fill(d2,0); fill(e,0); fill(head,0); tot=0;
	for (int i=1;i<=m;i++){
		if (x[i]>k&&y[i]>k) return 0;
		if (x[i]<=k){
			d1[a[i]]++,d2[b[i]]++;
			if (y[i]<=k) add(a[i],b[i],1);
		}
		else d1[b[i]]++,d2[a[i]]++;
	}
	int mxf=0;
	for (int i=1;i<=n;i++){
		if ((d1[i]-d2[i])&1) return 0;
		if (d1[i]>d2[i]) add(S,i,(d1[i]-d2[i])/2),mxf+=(d1[i]-d2[i])/2;
		if (d2[i]>d1[i]) add(i,T,(d2[i]-d1[i])/2);
	}
	return dinic(S,T)==mxf;
}
int main(){
	scanf("%d%d",&n,&m); S=0,T=n+1;
	for (int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a[i],&b[i],&x[i],&y[i]);
		mn=min(mn,x[i]); mn=min(mn,y[i]);
	}
	int l=mn,r=1000; ans=-1;
	while (l<=r){
		int mid=(l+r)>>1;
		if (check(mid)) ans=mid,r=mid-1; else l=mid+1;
	}
	if (ans==-1) puts("NIE");
	else printf("%d\n",ans);
	
	return 0;
}

Pilots

思路：单调队列即可。

emmmmm......