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);
  }
}