问题求解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

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

法一:缩环暴力

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

法二:DP / 序列自动机

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

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

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]dp[x][0]表示xx的子树中的边被完全覆盖,xx不选时的最小覆盖数;dp[x][1]dp[x][1]表示xx选。
dp[x][0]=y=son[x]dp[y][1]dp[x][0] = \sum\limits_{y=son[x]} dp[y][1],
dp[x][1]=1+y=son[x]min(dp[y][0],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

公式:

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

应用:

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

2-7 Problem B 【POJ 1322】Chocolate

有C种颜色的巧克力,每次从C种颜色中随机拿一个放在桌子上,如果桌子上存在两个颜色相同的就吃掉。问拿N次之后桌子上有M个巧克力的概率。 C100C\leq 100N,M106N, 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,且体重之和的差距最小。
n100n\leq 1001wi4501\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);
}