Page 1 of 212
五 02

清北学堂比赛 Q1 解题报告

競賽題解 3 Comments »554 views

昨天晚上做了清北学堂的比赛“首届信息学在线测评大赛Q1”，名字很响亮。今天写了一份题解，发出来。

第一题:低价购买

要求求出方案数的最长单调序列(LIS)问题。我把序列先倒转了过来，然后求最长上升序列。由于需要去除重复序列，可以增加一个域Next[i]，定义Next[i]=min{ k | k>i 且 A[k]=A[i] }，表示大于i且离i最近的Next[i]，使得第Next[i]个数与第i个数相同。如果不存在这样的数则Next[i]=无穷大。这样的话如果出现Next[i]不为0且Next[j]<i可直接跳过。

状态设定
F[i]为以第i个元素为结尾的最长上升序列的长度
G[i]为以第i个元素为结尾的最长上升序列的方案数

状态转移方程

F[i] = Max{ F[j] + 1 | A[j] < A[i] 且 Next[j] > i }
G[i] = Sum{ G[j] | F[j] + 1 = F[i] }

边界条件

G[0]=1

为了方便，增加一个极大的元素到序列结尾。这样目标状态为
最长长度 F[N+1]-1
方案数 G[N+1]

第二题:连续串之和

相邻元素绝对值之差必须为1，所以显然构造出的和最大的序列一定为0,1,2,3,…,N-1，和为(N-1)*N/2，最小和同理为-(N-1)*N/2。于是如果给定的S不在最大值与最小值的区间内，一定无解。

我们先生成一个和最大的序列，0,1,2,3,…,N-1，然后再考虑调整使得满足条件。假设当前的和与S的差为D，可以发现，无论怎样变换序列，D的奇偶性的不改变的。因为无论改变那个元素，都只能从比前一个元素多1变成少1，或者从比前一个元素少1变成多1，调整多个也是一样的，变化量为偶数。所以说，如果初始的D为奇数，则一定不可能有解。

余下来的情况一定为有解的情况了。把序列顺序做差，初始化每项差值都为1，则对应了0,1,2,3,…,N-1。可以发现，修改一个差值从1到-1会引起后面所有项的值减少2，总的减少量就是后面项的个数*2。这时就可以设计出算法了，从第一个差值开始尝试从1变成-1，更新当前和，直到等于S为止。最后再根据差值序列还原出原序列。时间复杂度为O(N)。

第三题:决斗

观察发现，如果第i个人想与第j个人决斗(i<j)，i,j必须相邻，也就是i,j之间的人必须全部被打败。换句话说，如果i,j相邻，一定存在一个k(i<k<j)，使得i,k相邻，k与j相邻，而且i可以打败k或者j可以打败k。这样就把问题缩小了，可以以此进行动态规划。考虑到是一个环，我们可以把N个人复制一遍，接在后面。

设定状态
F[i,j] 表示第i个人是否可以与第j个人相邻 (1<=i<j<=N*2)，第i个人在环上另一面的映射为i+N

状态转移方程
F[i,j]= Or { F[i,k]=F[k,j]=true | i可以打败k或j可以打败k }

边界条件
由于i和i+1两个一定是相邻的，所以有
F[i,i+1]=true

判断第i个人可以胜出的条件就是F[i,i+N]=true，此时i两边的人全部败了，i获胜。

时间复杂度O(N^3)。

第四题:最小费用多米诺

把棋盘上每个非障碍格子看作一个顶点，相邻两个非障碍格子对应的顶点连接一条边，权值为在这两个格子上放上多米诺方块的费用。判断是否能放满只需求出该图的最大匹配，并判断是否每个顶点都有匹配。如何求最大匹配？带花树？不，这是一个二分图！

为什么是二分图？因为棋盘是可以2染色的，之间有边的顶点都是相邻的，而相邻的格子必然是颜色不同的，所以这是一个二分图。

接下来就容易了，首先求出最大匹配，如果存在完美匹配（每个顶点都有匹配），再求最佳匹配(最小权值完备匹配)即可。

Read the rest of this entry »

标签：, , , ,
三 24

二分图带权匹配 KM算法与费用流模型建立

計算機科學 9 Comments »2,537 views

[二分图带权匹配与最佳匹配]

什么是二分图的带权匹配？二分图的带权匹配就是求出一个匹配集合，使得集合中边的权值之和最大或最小。而二分图的最佳匹配则一定为完备匹配，在此基础上，才要求匹配的边权值之和最大或最小。二分图的带权匹配与最佳匹配不等价，也不互相包含。

我们可以使用KM算法实现求二分图的最佳匹配。方法我不再赘述，可以参考tianyi的讲解。KM算法可以实现为O(N^3)。

[KM算法的几种转化]

KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。

KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。

KM算法求得的最大权匹配是边权值和最大，如果我想要边权之积最大，又怎样转化？还是不难办到，每条边权取自然对数，然后求最大和权匹配，求得的结果a再算出e^a就是最大积匹配。至于精度问题则没有更好的办法了。

[求最小(大)权匹配的费用流建模方法]

求最小(大)权匹配，可以用最小(大)费用最大流的方法。和二分图最大匹配的构图方法类似，添加附加源S和附加汇T，从S向二分图X集合中每个顶点连接一条权值为0，容量为1的有向边，从Y集合中每个顶点向T也连接一条权值为0，容量为1的有向边。然后把原有的边变成容量为1，权值不变的有向边。求从S到T的最小(大)费用最大流，就能求得最小(大)权匹配。

上述建模求最大权匹配的方法求得的一定是最佳匹配(如果存在完备匹配)，因为S到X集合每条边全部满流。如下图所示，最小费用最大流为2。

km1

要求最大权匹配(不一定完备匹配)。如下图，只需再引入一个顶点A，从X集合的每个顶点向A连接一条容量为1，权值为0的边，然后再由A向T连接一条权值为0，容量不小于|X|的边，求最大费用最大流，这时是100。

km2

最小权匹配也类似，不过新加的边权要为一个极大值，大于所有已有边权值。

[KM算法与费用流的比较]

从理论上分析，KM算法的时间复杂度比费用流要好，但是实际上和较好的费用流算法比起来运行效率是差不多的，KM算法优势仅仅在于编程容易。KM算法也有其不可避免的局限性，就是必须用邻接矩阵来表示。这样会浪费很多的空间，尤其是图相当稀疏的时候。而对于十分稀疏的图，许多优秀的费用流算法效率是很高的。这并不说明KM算法不如费用流，毕竟在信息学竞赛中，编程的复杂度也是一个相当重要的需要考虑的因素。

BYVoid 原创讲解，转载请注明。

标签：, , , , , ,
二 03

POI 2001 Peaceful Commission 和平委员会

POI 4 Comments »256 views

把每个政党的两个议员看作两个顶点，不能相处的议员之间连接一条边。类似于二分图的染色，但又不是严格的二分图。我们规定第2*i-1和2*i个顶 点为姊妹顶点。对于图中的每个连通分量，尝试从首个顶点开始访问染色，规定其加入理事会，然后访问该顶点的邻接顶点的姊妹顶点。遍历中如果发现了一对姊妹 顶点都被加入了理事会，则是不合法的，染色失败。如果染色成功，继续查找下一个连通分量，否则重新尝试从首个顶点的姊妹顶点开始访问染色，如果染色成功， 继续查找下一个连通分量，否则染色失败，不可能组建理事会。

该算法巧妙的类比了二分图染色，并根据该题的特点，设计出合适的方案，时间复杂度为O(M)。
Read the rest of this entry »

标签：, , , , ,
十二 09

NOIP2008 双栈排序 twostack 题解

競賽題解 5 Comments »1,300 views

这道题的错误做法很多,但是实际在考场上，大多数人拿到了30分。错误做法却能得满分的也很多,正确的算法是基于二分图的算法。注意，不是二分图匹配！

分析条件，我们把问题抽象为数学模型。设输入序列为S，考虑S[i],S[j]两个元素不能进入同一个栈的条件.注意,这里所说的"S[i],S[j]两个元素不能进入同一个栈",不是说仅仅不能同时在一个栈中,而是自始至终不能进入一个栈,即如果有解,那么S[i],S[j]一定进入过的栈不同.

结论P: S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j].
证明略过,请参考sqybi.尝试后可以发现结论P是正确的.

把每个元素按照输入序列中的顺序编号,看作一个图中的每个顶点.这时,我们对所有的(i,j)满足i<j,判断是否满足结论P,即S[i],S[j]两个元素能否进入同一个栈.如果满足P,则在i,j之间连接一条边.

我们对图染色,由于只有两个栈,我们得到的图必须是二分图才能满足条件.由于要求字典序最小,即尽量要进入栈1,我们按编号递增的顺序从每个未染色的顶点开始染色,相邻的顶点染上不同的色,如果发生冲突,则是无解的.否则我们可以得到每个顶点颜色,即应该进入的栈.

接下来就是输出序列了,知道了每个元素的决策,直接模拟了.

在判断数对(i,j)是否满足P时,枚举检查是否存在k的时间复杂度是O(n),则总的时间复杂度是O(n^3),对于n=1000是太大了.这原因在于过多得枚举了k,我们可以用动态规划把枚举k变为O(1)的算法.

设F[i]为Min{S[i],S[i+1],S[i+2]..S[n-1],S[n]},状态转移方程为F[i]=Min{ S[i] , F[i+1] }.边界为F[N+1]=极大的值.

判断数对(i,j)是否满足P,只需判断(S[i]<S[j] 并且 F[j+1]<S[i])即可.时间复杂度为O(n^2).

参考资料:sqybi的题解

?View Code CPP
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
98
99
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: NOIP2008 twostack
 * Author: Guo Jiabao
 * Time: 2008.12.9 21:22:52
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
 
using namespace std;
 
const int MAXN=1002;
const int INF=0x7FFFFFFF;
 
class tStack
{
	private:
		int top;
		int S[MAXN];
	public:
		tStack() : top(0) {}
		void ins(int k)
		{
			S[++top]=k;
		}
		int tp()
		{
			return S[top];
		}
		void pop()
		{
			top--;
		}
};
 
int S[MAXN],F[MAXN],bel[MAXN];
bool adjm[MAXN][MAXN];
int N,top1,top2;
tStack T[3];
 
void init()
{
	int i;
	freopen("twostack.in","r",stdin);
	freopen("twostack.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&S[i]);
	}
}
 
void noanswer()
{
	printf("0");
	exit(0);
}
 
void color(int i,int c)
{
	bel[i]=c;
	int j;
	for (j=1;j<=N;j++)
	{
		if (adjm[i][j])
		{
			if (bel[j]==c) //conflict : not a bipartite graph
			{
				noanswer();
			}
			if (!bel[j])
			{
				color(j,3-c); // color the opposite color 1<->2
			}
		}
	}
}
 
void dye()
{
	int i,j;
	F[N+1]=INF;
	for (i=N;i>=1;i--)
	{
		F[i]=S[i];
		if (F[i+1]<F[i])
			F[i]=F[i+1];
	}
	for (i=1;i<=N-1;i++)
	{
		for (j=i+1;j<=N;j++)
		{
			if (S[i]<S[j] && F[j+1]<S[i])
			{
				adjm[i][j]=adjm[j][i]=true;
			}
		}
	}
	for (i=1;i<=N;i++)
	{
		if (!bel[i])
		{
			color(i,1);
		}
	}
}
 
void solve()
{
	int i,should=1,s;
	for (i=1;i<=N;i++)
	{
		s=bel[i];
		if (s==1)
		{
			T[1].ins(S[i]);
			printf("a ");
		}
		else
		{
			T[2].ins(S[i]);
			printf("c ");
		}
		while (T[1].tp()==should || T[2].tp()==should)
		{
			if (T[1].tp()==should)
			{
				T[1].pop();
				printf("b");
				if (should!=N)
					printf(" ");
				should++;
			}
			else
			{
				T[2].pop();
				printf("d");
				if (should!=N)
					printf(" ");
				should++;
			}
		}
	}
}
 
int main()
{
	init();
	dye();
	solve();
	return 0;
}
标签：, , , ,
六 17

USACO 4.2.2 The Perfect Stall 完美的牛栏 stall4

USACO 1 Comment »333 views

Read the rest of this entry »

标签：, , , ,
26 queries. 0.547 seconds. Designed by NattyWP .
Images by desEXign.