HDU OJ一些题目

关于做题这回事，引用一下：

1
2
Chao Xu，Haskell用户.
acm算是用来训练秒面试题的一个方式。 像我这种非cs系学生全靠玩acm的训练秒各个公司。

深以为然。算法题带来的代码能力的效用实在是太大了，除了训练思维外对速度、准确性也有极大帮助。真切感受到解决一个大作业花了数小数编写，再花了更长的时间调试，和立刻写完、写完就对的差异。订阅过一些邮件列表，偶尔能看到一些非常苍白的问题的人，也能看到内容可能更空洞的回复。以及市面上很多浮夸的书。如果方法恰当潜心研习一段时间应该不会出现这样的问题呢。所以当我看到《编程之美》这个书名的时候，第一印象也是那类浮华的书，等待之前某次活动拿到一本看才发现不是，”编程“、”美“字样在我心目中的地位都被这些浮夸的事物玷污了。

我现在发现自己看过的东西拓扑顺序不太对了，简单说就是ld -la -lb -la，这可以算作一个tech joke吧。昨天经过fqj1994指导，今天终于把https开起来了，感觉又有所提高，好开心啊。

HDU 4616 Game

http://acm.hdu.edu.cn/showproblem.php?pid=4616

给出一棵节点带权的树，节点上可以有陷阱，找一条最多经过C个陷阱的简单路径，使得经过的节点权值和最大。另外，一旦访问到了第C个陷阱，就得立刻停下，路径不能继续延伸了。

dp[i][j][k]：以i为一个端点，另一端在i的子树内的路径经过节点权值和的最大值，约束条件有两个：

  • 经过了j个陷阱
  • 端点特性为k。k有两种取值：
    • 0：表示子树内的端点必须是陷阱
    • 1：表示子树内的端点可以任取，没有k为0时的限制

之所以引入k是为了解决题目中要求的一点：当经过第C次陷阱时，必须立刻停下，不能继续前进。考察从起点到终点沿路节点是否有陷阱，有以下四种情况：

  • o-...-o：起点、终点皆无陷阱
  • x-...-o：起点无陷阱，终点有陷阱
  • o-...-x：起点无陷阱，终点有陷阱
  • x-...-x：起点、终点皆有陷阱

如果选择的路径上恰好有C的陷阱，那么前两种情况就是不合法的。因为一旦经过第C次陷阱就得立刻停下，之后不可能再经过无陷阱的节点。

如果选择的路径上有不到C个陷阱，那么前两种情况也可以算上。

状态中的k就是用来区分不合法状况的，当k为0时只允许后两种情况；为时允许所有四种情况。动态规划过程计算完毕之后，还要注意最优路径可能跨立两棵子树，我们需要枚举两棵子树的路径，把它们接合。如果这两条路径的陷阱总数不到C，那么就对端点特性没有要求(四种情况均可)，对应了代码中的if (j+k < c) ans = max(ans, dp[u][j][1] + dp[v][k][1]);；如果总数等于C`，那么路径的一端必须是陷阱。

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef vector<int> VI;

#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define EACH(i, a) for (VI::iterator i = (a).begin(); i != (a).end(); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ZERO(a) memset(a, 0, sizeof a)

const int N = 50000;
VI e[N];
int c, ans, trap[N], val[N], dp[N][4][2];

/*
 * dp[][][0]: entering subtree
 * no further points beyond the end point
 *
 * dp[][][1]: leaving subtree
 * further points allowed beyond the end point
 */

int RI()
{
  int x;
  scanf("%d", &x);
  return x;
}

void dfs(int u, int p)
{
  dp[u][trap[u]][0] = dp[u][trap[u]][1] = val[u];
  ans = max(ans, val[u]);
  EACH(i, e[u]) {
    int v = *i;
    if (v == p) continue;
    dfs(v, u);
    FOR(j, trap[u], c+1)
      FOR(k, trap[v], c-j+1) {
        if (j < c) ans = max(ans, dp[u][j][1] + dp[v][k][0]);
        if (k < c) ans = max(ans, dp[v][k][1] + dp[u][j][0]);
        if (j+k < c) ans = max(ans, dp[u][j][1] + dp[v][k][1]);
      }
    FOR(j, trap[u], c+1) {
      dp[u][j][1] = max(dp[u][j][1], dp[v][j-trap[u]][1] + val[u]);
      if (j > trap[u]) dp[u][j][0] = max(dp[u][j][0], val[u] + dp[v][j-trap[u]][0]);
    }
  }
}

int main()
{
  int cases = RI();
  while (cases--) {
    int n = RI();
    c = RI();
    REP(i, n) {
      e[i].clear();
      val[i] = RI();
      trap[i] = RI();
    }
    REP(i, n-1) {
      int u = RI(), v = RI();
      e[u].PB(v);
      e[v].PB(u);
    }
    ans = 0;
    ZERO(dp);
    dfs(0, -1);
    printf("%d\n", ans);
  }
}

HDU 4689 Derangement

http://acm.hdu.edu.cn/showproblem.php?pid=4689

给出一个长为n的+-序列如++---，这个序列描述一个错位排列。 +对应的数比其位置序号大，而-对应的数比其位置序号小，问满足所有约束的错位排列有多少个。比如[5, 4, 1, 2, 3]就是满足++---的一个错位排列。

数据规模中说的n不超过20很有误导性。下面的描述中，排列的位置编号和数都从0开始。下标为什么要从0开始呢？引用下名人的话好了：

1
2
3
I thought that by now professional programmers knew how much more preferable it is to let the natural numbers start at 0.

-- Edsger W. Dijkstra

没记错的话，TAOCP里Donald E. Knuth坚持从1开始，还说Dijkstra是inconsistent的因为他的乐谱还是什么的是从1开始的……

递推，令f[i][j]表示错位排列的前i个数中有j个对应+的位置尚未填写。这里的j还有令一层意思，即0~i-1中也恰好有j个数未出现在已知的部分错位排列中。原因是如果某个位置填写了数，那么必须是0~i-1其中之一，而有j个位置尚未填写，故0~i-1中有j个未出现。

假如已经考虑了前i位，考虑a[i]：

  • +：这个位置的数也无法确定，算作“未填写”，而之前j个未填的地方可以挑一个填i，对应：f[i+1][j] += f[i][j] * j； 也可以不填i，对应：dp[i+1][j+1] += dp[i][j]
  • -：这个位置的数必须确定，由于0~i-1中恰有j个数未被填写，所以位置i可以填上这j个数中的任何一个。 另外之前j个未确定的位置可以填i(对应：f[i+1][j-1] += f[i][j] * j * j)； 也可以不填i(对应：f[i+1][j] += dp[i][j] * 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
#define __STDC_FORMAT_MACROS
#include <inttypes.h>
#include <stdint.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef int64_t i64;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP1(i, n) for (int i = 1; i <= (n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b); --i >= (a); )

const int N = 20;
i64 f[2][N+1];

int main()
{
  char a[N+1];
  while (gets(a)) {
    int n = strlen(a);
    f[0][0] = 1;
    REP(i, n) {
      i64 *g = f[i&1], *h = f[i+1&1];
      fill_n(h, i + 2, 0);
      if (a[i] == '+')
        REP(j, i + 1) {
          h[j+1] += g[j];
          h[j] += g[j] * j;
        }
      else
        REP(j, i + 1) {
          h[j] += g[j] * j;
          if (j)
            h[j-1] += g[j] * j * j;
        }
    }
    printf("%" PRId64"\n", f[n&1][0]);
  }
}

HDU 4698 Counting

http://acm.hdu.edu.cn/showproblem.php?pid=4698

棋盘内有N(N <= 1000)个点，求包含至少一个点的矩形的数目。

枚举矩形的左边界的位置，左边界所在的直线有两种可能：

  • 穿过至少一个点
  • 没有穿过任何一个点

补集转化为统计不包含点的矩形数目。

右边界所在直线为扫描线，从左边界开始向右移动。扫描线移动时我们还要统计以这根线为左右边界的不包含点的矩形数目。一开始，夹在左右边界内的矩形数目为ymax * (ymax+1) / 2。左右边界内的点相当于一根根水平的栅栏，把区域分成了若干部分，每个包含y根水平线的区域内的矩形数目为y * (y+1) / 2。以枚举的两根竖直线为边界的合法矩形数目就是所有区域y * (y+1) / 2的和。当右边界扫描线扫过新的点时，这个点所在的水平线就会分割区域。于是现在的问题就是要有效处理区间的分裂。

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
#include <stdint.h>
#include <algorithm>
#include <set>
#include <cstdio>
#include <utility>
using namespace std;
typedef int64_t i64;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP1(i, n) for (int i = 1; i <= (n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define fi first
#define se second
typedef pair<int, int> PII;

int RI()
{
  int x;
  scanf("%d", &x);
  return x;
}

#define C(x) ((x) * i64((x)+1) / 2 % MOD)
#define NORM(x) (((x) % MOD + MOD) % MOD)
#define ADD(x, y) x = ((x) + (y)) % MOD

const int N = 1000, MOD = 1000000007;
PII a[N+1];
set<int> S;

int insert(int x)
{
  set<int>::iterator lit = S.lower_bound(x);
  if (lit != S.end() && *lit == x)
    return 0;
  set<int>::iterator rit = lit--;
  S.insert(x);
  return C(*rit - x - 1) + C(x - *lit - 1) - C(*rit - *lit - 1);
}

int main()
{
  int xmax, ymax, n;
  while (scanf("%d%d%d", &xmax, &ymax, &n) == 3) {
    i64 ans = 0;
    REP(i, n) {
      a[i].fi = RI();
      a[i].se = RI();
    }
    a[n++] = PII(xmax + 1, 0);
    sort(a, a + n);

    int xlast = 0;
    for (int ii, i = 0; i < n; i = ii) {
      for (ii = i; ii < n && a[i].fi == a[ii].fi; ii++);
      int lw = a[i].fi - xlast - 1;
      xlast = a[i].fi;

      for (bool flag = false; ; flag = true) {
        S.clear();
        S.insert(0);
        S.insert(ymax + 1);

        i64 cnt = C(ymax);
        int xprev = xlast;
        for (int jj, j = i; j < n; j = jj) {
          int rw = a[j].fi - xprev;
          xprev = a[j].fi;
          if (! (flag && i == j))
            ADD(ans, (i == j ? C(lw) : i64(lw) * rw % MOD) * cnt);
          for (jj = j; jj < n && a[j].fi == a[jj].fi; jj++)
            ADD(cnt, insert(a[jj].se));
        }

        if (flag) break;
        lw = 1;
      }
    }

    printf("%d\n", int(NORM(C(xmax) * C(ymax) - ans)));
  }
}

HDU 4705 Y

http://acm.hdu.edu.cn/showproblem.php?pid=4705

给出一棵树，统计满足如下条件的节点三元组(x, y, z)数目；不存在一条简单路径覆盖这三个节点。

令f[i].first表示i子树的大小，f[i].second为i的子树内，选取一对没有祖孙关系的节点的方案数。

这题解法很多，还可以在x、y、z的最近公共祖先处统计，但这样就需要两次遍历，以及一个递推：前i棵孩子子树选取了j个点的方案数。

另外还可以计算原问题三元组的补集，即x、y、z在一条简单路径上的方案数。在路径中间的节点处统计会比较简单，只需要子树大小这一种统计信息，同样也是一次遍历的。

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
#pragma comment(linker, "/STACK:16777216")
#define PRId64 "I64d"
#define SCNd64 PRId64
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef int64_t i64;
typedef vector<int> VI;

#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define EACH(i, a) for (VI::iterator i = (a).begin(); i != (a).end(); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)

const int N = 100000;
int size[N];
VI e[N];
i64 ans;

int RI()
{
  int x;
  scanf("%d", &x);
  return x;
}

int RI(int &x)
{
  return scanf("%d", &x);
}

pair<i64, i64> dfs(int u, int p)
{
  pair<i64, i64> s(0, 0);
  EACH(i, e[u]) {
    int v = *i;
    if (v == p) continue;
    pair<i64, i64> c = dfs(v, u);
    ans += s.se * c.fi + (s.fi + 1) * c.se;
    s.se += c.se + s.fi * c.fi;
    s.fi += c.fi;
  }
  s.fi++;
  return s;
}

int main()
{
  int n;
  while (RI(n) == 1) {
    REP(i, n)
      e[i].clear();
    REP(i, n - 1) {
      int u = RI() - 1, v = RI() - 1;
      e[u].PB(v);
      e[v].PB(u);
    }
    ans = 0;
    dfs(0, -1);
    printf("%" PRId64 "\n", ans);
  }
}