问题求解2 编程作业

课程
  1. 2-1 Problem A 【NJU-Training-OJ 1068】房产投资
  2. 2-2 Problem D 【CF 596E】Wilbur and Strings
    1. 法一：缩环暴力
    2. 法二：DP / 序列自动机
  3. 2-3 Problem C 【HDU 1054】Strategic Game
    1. 法一：树形DP
    2. 法二：二分图
      1. 补充二分图的性质
    3. 法三：贪心
  4. 2-4 Problem D 【POJ 2084】Game of Connections
  5. 2-7 Problem B 【POJ 1322】Chocolate
  6. 2-8 Problem C 【UVA 12174】Shuffle
  7. 2-8 Problem D 【POJ 2576】Tug of War

包括：2-1-A、2-2-D、2-3-C、2-4-D、2-7-B、2-8-C、2-8-D
其中生成函数和 bitset 我还不太会

2-1 Problem A 【NJU-Training-OJ 1068】房产投资

限制每座城市最多只能拥有2套房屋，问1000（未知单位的）钱最多能买多少面积的房子。输出方案。
城市数量：5
每座城市可购房产的数量：8—15，取整数
每套房产的面积：20—200，取整数
每套房产的总价：面积的0.3—3倍，取整数

本来想背包发现有限制，那就DP（据说这叫分组背包）。
DP[i][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
#include <cstdio>
int n, pos, tot[10], area[10][20], price[10][20], ans[10][20], dp[10][1005], pre[10][1005], num1[10][1005], num2[10][1005];
 
void Update(int w, int v, int t, int x, int y) {
	for(int i = v; i <= 1000; ++i) {
		if(dp[t - 1][i - v] + w > dp[t][i]) {
			dp[t][i] = dp[t - 1][i - v] + w;
			num1[t][i] = x;
			num2[t][i] = y;
			pre[t][i] = i - v;
		}
	}
}
 
int main() {
	// 输入
	for(int i = 1, x; i <= 5; ++i) {
		while(scanf("%d", &x) && x != -1)
			area[i][++tot[i]] = x;
	}
	for(int i = 1; i <= 5; ++i) {
		for(int j = 1; j <= tot[i]; ++j)
			scanf("%d", &price[i][j]);
		scanf(" -1");
	}
	// DP
	for(int t = 1; t <= 5; ++t) {
		Update(0, 0, t, 0, 0);
		for(int i = 1; i <= tot[t]; ++i) {
			Update(area[t][i], price[t][i], t, i, 0);
			for(int j = i + 1; j <= tot[t]; ++j)
				Update(area[t][i] + area[t][j], price[t][i] + price[t][j], t, i, j);
		}
	}
	// 输出最大面积
	for(int i = 0; i <= 1000; ++i)
		if(!pos || dp[5][i] > dp[5][pos])
			pos = i;
	printf("%d\n", dp[5][pos]);
	// 输出方案
	for(int t = 5; t; --t) {
		ans[t][num1[t][pos]] = ans[t][num2[t][pos]] = 1;
		pos = pre[t][pos];
	}
	for(int t = 1; t <= 5; ++t) {
		for(int i = 1; i <= tot[t]; ++i)
			printf("%d", ans[t][i]);
		printf("\n");
	}
}

2-2 Problem D 【CF 596E】Wilbur and Strings

有一个值为\(0-9\)的矩阵。对于每一个\(0-9\)的值有一个方向向量\(d\)，如果坐标\((x,y)\)处的值为\(z\)，则下一次走到\((x+dx_z, y+dy_z)\)，如果会越界则不动。 现在给一个\(0-9\)的字符串，问是否存在一个移动方式（从任意坐标开始），使得字符串可以按顺序被写出来（每经过一个点可以选择写或不写），即满足给定字符串是移动路径经过点的值的子序列。

法一：缩环暴力

每个点的出度最多为\(1\)，那么图的联通性会出现三种情况：一条链、一条链结尾成环、一个环。于是缩环，每次从入度为\(0\)的点开始一直走，贪心判断。
\(O(q\times n\times m\times len)\) 数据貌似水了

法二：DP / 序列自动机

序列自动机 by jibancanyang
\(dp[i][j][k]\)表示坐标\((i, j)\)下一次移动到值为\(k\)的点的坐标。这个可以记忆化搜索。
或者说，感觉这个做法就是记忆化搜索。

其实看起来两种方法差别不大 

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
	
int n, m, Q, dx[15], dy[15], num[205][205], pos[205][205], exist[40005][15], in_du[205][205];
char s[1000005];
	
bool Check() {
	scanf("%s", s);
	int len = strlen(s);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (!in_du[i][j] || (num[i][j] == s[0] - '0' && pos[i][j])) { // 入度为0或在环中
				int x = i, y = j, now = 0;
				while (now < len && !pos[x][y]) { // 贪心走下去
					int col = num[x][y];
					if (col == s[now] - '0') now++;
					if (x + dx[col] < 1 || x + dx[col] > n || y + dy[col] < 1 || y + dy[col] > m) { // 单点
						while(now < len && col == s[now] - '0') now++;
						break;
					}
					x += dx[col];
					y += dy[col];
				}
				if (pos[x][y]) { // 进入环中
					int cir = pos[x][y];
					while(now < len && exist[cir][s[now] - '0']) now++;
				}
				if (now == len) return 1;
			}
	return 0;
}
	
int dfs_num, top, tot_circle, dfn[205][205], low[205][205];
bool vis[205][205];
std::pair<int, int> st[40005];
	
void Tarjan(int x, int y) { // 其实这题的性质太好了，随便DFS一下就行
	dfn[x][y] = low[x][y] = ++dfs_num;
	vis[x][y] = 1;
	st[++top] = std::make_pair(x, y);
	int x2 = x + dx[num[x][y]], y2 = y + dy[num[x][y]];
	if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m) {
		in_du[x2][y2] ++;
		if (!dfn[x2][y2])
			Tarjan(x2, y2), low[x][y] = std::min(low[x][y], low[x2][y2]);
		else if (vis[x2][y2])
			low[x][y] = std::min(low[x][y], dfn[x2][y2]);
	}
	if (dfn[x][y] == low[x][y]) {
		if (st[top] == std::make_pair(x, y)) { 
			top--;
			vis[x][y] = 0;
		} else { // 缩环
			tot_circle++;
			for (std::pair<int, int> v = std::make_pair(-1, -1); v != std::make_pair(x, y); ) {
				v = st[top--];
				pos[v.first][v.second] = tot_circle;
				exist[tot_circle][num[v.first][v.second]] = 1;
				vis[v.first][v.second] = 0;
			}
		}
	}
}
	
int main() {
	scanf("%d%d%d", &n, &m, &Q);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%1d", &num[i][j]);
	for (int i = 0; i <= 9; ++i)
		scanf("%d%d", &dx[i], &dy[i]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if(!dfn[i][j]) Tarjan(i, j);
	for (; Q; --Q)
		printf(Check() ? "YES\n" : "NO\n");
}

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
#include <cstring>
#include <cstdio>
#include <queue>
const int N = 205;
int n, m, q, top, g[N][N], dx[10], dy[10];
bool vis[N][N][10], in_du[N][N];
std::pair<int, int> f[N][N][10], dfs_stack[N];
char s[1000005];
void Dfs(int x, int y, int k) {
	if (vis[x][y][k]) return ;
	vis[x][y][k] = 1;
	int num_now = g[x][y];
	int x_next = x + dx[num_now], y_next = y + dy[num_now];
	if (x_next < 1 || x_next > n || y_next < 1 || y_next > m) {
		if(num_now == k)
			f[x][y][k] = std::make_pair(x, y);
	} else {
		in_du[x_next][y_next] = 1;
		if(g[x_next][y_next] == k) 
			f[x][y][k] = std::make_pair(x_next, y_next);
		else 
			Dfs(x_next, y_next, k), f[x][y][k] = f[x_next][y_next][k];
	}
}
bool Query() {
	scanf("%s", s);
	int len = strlen(s);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (!in_du[i][j] || (g[i][j] == s[0] - '0' && f[i][j][g[i][j]] == std::make_pair(i, j))) {
				int now_l = (g[i][j] == s[0] - '0'), now_x = i, now_y = j;
				while (now_l < len && f[now_x][now_y][s[now_l] - '0'].first) {
					std::pair<int, int> next = f[now_x][now_y][s[now_l] - '0'];
					now_x = next.first;
					now_y = next.second;
					now_l++;
				}
				if (now_l == len) return 1;
			}
	return 0;
}
int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%1d", &g[i][j]);
	for (int i = 0; i <= 9; ++i)
		scanf("%d%d", &dx[i], &dy[i]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			for (int k = 0; k <= 9; ++k)
				if (!vis[i][j][k])
					Dfs(i, j, k);
	for (; q; --q)
		printf(Query() ? "YES\n" : "NO\n");
}

2-3 Problem C 【HDU 1054】Strategic Game

树上的最小点覆盖数（点覆盖：点集S满足每一条边都至少有一个端点在S中；即选择一个点可以覆盖相邻的边，最后使得边全部被覆盖）

本来是个非常简单的题，然后。。
第一次写完发现DP有问题，改了改发现理解错题了应该是覆盖边不是覆盖点，重写发现DP又双叒叕出了点小问题，改完发现调试的输出忘了删。。
于是WA了无数发，身败名裂。。

法一：树形DP

\(dp[x][0]\)表示\(x\)的子树中的边被完全覆盖，\(x\)不选时的最小覆盖数；\(dp[x][1]\)表示\(x\)选。
则\(dp[x][0] = \sum\limits_{y=son[x]} dp[y][1]\),
\(dp[x][1] = 1 + \sum\limits_{y=son[x]} min(dp[y][0], dp[y][1])\).

法二：二分图

图的最小点覆盖是NPC问题，但如果为二分图，则有
König定理：二分图的最小点覆盖数 = 最大匹配数（证明）

因为无向图G为二分图的充分必要条件是，G至少有两个顶点，且其所有回路的长度均为偶数。
树没有回路，满足上述条件。可以将树中的节点分为奇数层和偶数层，则满足二分图的条件（同一个集内的顶点不相邻）。

而二分图最大匹配可以用匈牙利算法或者网络流。

补充二分图的性质

性质1：最小点覆盖数 = 最大匹配数
性质2：最小边覆盖数 = 最大独立集
性质3：最小点覆盖数 + 最大独立集 = 顶点数
性质4：最大团 = 补图的最大独立集

其中：
点覆盖：点集，满足每条边都被接触
边覆盖：边集，满足每个顶点都被接触
匹配：边集，满足任意两条边都没有公共顶点
独立集：点集，满足两两不相连
团：点集，满足两两相连（完全图）

参考：二分图的最大匹配、完美匹配和匈牙利算法 by Renfei Song、二分图的最小顶点覆盖 最大独立集 最大团 by jianglangcaijin

法三：贪心

DFS的递归过程（从下到上）中，如果一个节点和它的父亲节点都没有被覆盖，那么选择父节点，并标记当前节点和父节点被覆盖。
或者理解为，对于一个节点，如果它存在一个孩子节点没有被选，那么选择该节点。

参考：题解 & 标程 by C20180630_zjf、良心题解 by jhljx

下为法一的程序，其他见上面参考中的两份题解 

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define to first
#define next second
const int N = 1505;
int n, ecnt, head[N], dp[N][2];
std::pair<int, int> E[N << 1];
void Addedge(int x, int y) {
	E[++ecnt] = std::make_pair(y, head[x]);
	head[x] = ecnt;
}
void Dfs(int x, int fa) {
	dp[x][0] = 0;
	dp[x][1] = 1;
	for (int e = head[x]; e; e = E[e].next) {
		int y = E[e].to;
		if (y == fa) continue;
		Dfs(y, x);
		dp[x][0] += dp[y][1];
		dp[x][1] += std::min(dp[y][0], dp[y][1]);
	}
}
int main() {
	while (scanf("%d", &n) != EOF) {
		ecnt = 0;
		memset(head, 0, sizeof(head));
		for (int i = 1, x, y, num; i <= n; ++i) {
			for (scanf("%d:(%d)", &x, &num); num; --num) {
				scanf("%d", &y);
				Addedge(x + 1, y + 1);
				Addedge(y + 1, x + 1);
			}
		}
		Dfs(1, 0);
		printf("%d\n", std::min(dp[1][0], dp[1][1]));
	}
}

2-4 Problem D 【POJ 2084】Game of Connections

我当然不是为了写这个题，而是总结一波 Catalan 数（OEIS A000108）

公式：

  • \(C_n = \binom{2n}{n}-\binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)
  • \(C_n = \frac{1}{n+1} \sum\limits_{i=0}^n \binom{n}{i}^2\)
  • \(C_n = \frac{2(2n-1)}{n+1}C_n\) (其中\(C_0 = 1\))
  • \(C_n = \sum\limits_{i=0}^{n-1} C_i C_{n-i-1}\) (其中\(C_0 = 1\))
  • 渐进增长 \(C_n\sim \frac{4^n}{n^{3/2}\sqrt{\pi}}\)

应用：

  1. n 对括号组成的合法序列的个数（任位置之前的左括号数量 >= 右括号）。
  2. n 个数的出栈序列的个数。
  • n+1 个数连乘，不同的乘法顺序方案数。
  • n×n 格点中不越过对角线的单调路径的个数。图为 n=4 时。
  • n 个节点组成的不同构的二叉树的方案数。下图中，n=3，圆形表示节点，月牙形表示什么都没有。
  • 2n+1 个节点（n 个内部节点、n+1 个叶子）组成的不同构的满二叉树的方案数。下图中，n=3，圆形表示内部节点，月牙形表示外部节点。
  • 将凸 n+2 边形分成 n 个三角形的方案数。图为 n=4 时。
  • 圆周上 2n 个点连成互不相交的 n 条边的方案数。
  • 用 n 个长方形填充一个高度为 n 的阶梯状图形的方案数。图为 n=4 时。
  • 1, 2, ..., 2n 被放置在一个 2×n 的矩形中并保证每行每列的数字升序排列的方案数。(杨氏矩阵的特殊情况)

2-7 Problem B 【POJ 1322】Chocolate

有C种颜色的巧克力，每次从C种颜色中随机拿一个放在桌子上，如果桌子上存在两个颜色相同的就吃掉。问拿N次之后桌子上有M个巧克力的概率。 \(C\leq 100\)，\(N, M\leq 10^6\)。

生成函数，我还不会
集训队论文《母函数的性质及应用》

2-8 Problem C 【UVA 12174】Shuffle

给n首格，和长度为s的音乐随机播放序列，问有多少种合理的开始方式，即除开头和结尾可以≤n外，中间每n个为一轮，其中不重复。

Code by ZYB：
b[i]表示判断i后面的n个是否合法。 

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
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int i,j,k,l,s,n,m,test,a[N],b[N],ans,last[N],L;
int main() {
	scanf("%d",&test);
	while (test--) {
		scanf("%d%d",&n,&m);
		for (i=1;i<=m;i++) scanf("%d",&a[i]);
		for (i=1;i<=n;i++) last[i]=m+1;
		L=m+1;
		for (i=m;i;i--) {
			L=min(L,last[a[i]]);
			last[a[i]]=i;
			if (min(i+n-1,m)<L) {
				if (i+n>m||b[i+n]) b[i]=1;
				else b[i]=0;
			}
			else b[i]=0;
		}
		for (i=-n+2;i<=1;i++) if (min(i+n-1,m)<L&&(i+n>m||b[i+n])) ans++;
		printf("%d\n",ans);
		for (i=1;i<=m;i++) b[i]=0;
		ans=0;
	}
}

2-8 Problem D 【POJ 2576】Tug of War

将n个人分为两队进行拔河比赛，使得两队人数之差≤1，且体重之和的差距最小。
\(n\leq 100\)，\(1\leq wi\leq 450\)。

Code by ZYB 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<algorithm>
#include<cstdio>
#include<bitset>
#define N 65*3
using namespace std;
bitset<450*51>f[65];
int i,j,k,l,s,n,m,ans[N],a[N];
int main() {
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]),s+=a[i];
	f[0][0]=1;
	for (i=1;i<=n;i++) 
	for (j=min((n+1)/2-1,i-1);j>=0;j--) f[j+1]|=(f[j]<<a[i]);
	int ans=s/2;
	while (!f[(n+1)/2][ans]&&!f[(n+1)/2-1][ans]) ans--;
	printf("%d %d\n",ans,s-ans);
}

背包 DP 二分图 最小点覆盖 Catalan数 生成函数 bitset