momodi's blog
msgbartop
My technology blog
msgbarbottom

18 Apr 10 武汉大学第八届程序设计竞赛部分决赛题目分析

在这里简单说一些我出的题目。

F: Pie

此题很明显的是一个最小匹配的模型。而后根据题目数据的特点可以利用DP来解决。

简单说一下性质：

1. 排序之后的匹配是不存在交叉线的。也就是说，如果第i高的男的和第j高的女的匹配，那么比i矮的男的就不能和比j高的女的匹配。同理，比i高的男的也就不能和比j矮的女的匹配。

2. 题目里有说男女的人数相差不到100，所以我们可以知道一个人的的可选匹配数量最多是100个。再加上这个性质，我们就可以用O(n * 100) = O(1000000)的DP来解决这个问题。相关的实现要用到滚存。

附上代码：

Pie.cpp
  1. /*
  2. * Author: momodi
  3. * Created Time:  2010-4-11 15:24:02
  4. * File Name: Pie.cpp
  5. */
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <cstring>
  9. #include <cmath>
  10. #include <cstdlib>
  11. #include <algorithm>
  12. #include <vector>
  13. using namespace std;
  14. #define out(v) cerr << #v << “: “ << (v) << endl
  15. #define SZ(v) ((int)(v).size())
  16. const int maxint = -1u>>1;
  17. template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
  18. template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}
  20. const int maxn = 10000;
  21. double dtn[maxn], dtm[maxn];
  22. int n, m;
  23. double f[2][maxn + 1];
  24. double solve() {
  25. memset(f, 0, sizeof(f));
  26. f[0][0] = f[1][0] = 0;
  27. for (int i = 1; i <= n; ++i) {
  28. double *now = f[1 ^ (i & 1)], *pre = f[i & 1];
  29. now[i - 1] = 1e100;
  30. for (int j = i; j + (n – i) <= m; ++j) {
  31. now[j] = min(now[j - 1], pre[j - 1] + abs(dtn[i - 1] – dtm[j - 1]));
  32. }
  33. }
  34. return f[1 ^ (n & 1)][m];
  35. }
  37. int main() {
  38. //freopen(“Pie.out”, “w”, stdout);
  39. while (scanf(“%d %d”, &n, &m) == 2 && (n || m)) {
  40. for (int i = 0; i < n; ++i) {
  41. scanf(“%lf”, dtn + i);
  42. }
  43. for (int i = 0; i < m; ++i) {
  44. scanf(“%lf”, dtm + i);
  45. }
  46. sort(dtn, dtn + n);
  47. sort(dtm, dtm + m);
  48. if (n > m) {
  49. for (int i = 0; i < n; ++i) {
  50. swap(dtn[i], dtm[i]);
  51. }
  52. swap(n, m);
  53. }
  54. printf(“%.6f\n”, solve());
  55. }
  56. return 0;
  57. }

G: Precious

这个题说白了就是判断一个简单多边形内部的两个点是不是可见的。做法也很简单，可能大家都对几何不感冒，不是很愿意去做。

判断两个点是不是可见的做法：

1. 用两个点来做一个端点都是开的线段，然后和多边形求交点，如果有交点的话，那么就是不可见的。

2. 取这个线段的中点来看看这个点是不是在简单多边形内部，如果不在内部的话，那么也是不可见的。

满足上面两个条件的就都是可见的。

知道了任意两个点是不是可见的之后，建立一个图，然后跑一下最短路就好了。

代码：

Precious.cpp
  1. /*
  2. * Author: momodi
  3. * Created Time:  2010-4-14 15:55:08
  4. * File Name: Precious.cpp
  5. */
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <cstring>
  9. #include <cmath>
  10. #include <cstdlib>
  11. #include <algorithm>
  12. #include <vector>
  13. using namespace std;
  14. #define out(v) cerr << #v << “: “ << (v) << endl
  15. #define SZ(v) ((int)(v).size())
  16. const int maxint = -1u>>1;
  17. template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
  18. template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}
  20. const double eps = 1e-9;
  21. int sgn(double a) {
  22. return (a > eps) – (a < -eps);
  23. }
  24. #define SQR(v) ((v) * (v))
  25. struct P {
  26. double x, y;
  27. P(double x, double y):x(x), y(y){}
  28. P():x(0), y(0){}
  29. double cross(P a, P b) const {
  30. return (a.x – x) * (b.y – y) – (a.y – y) * (b.x – x);
  31. }
  32. double dot(P a, P b) const {
  33. return (a.x – x) * (b.x – x) + (a.y – y) * (b.y – y);
  34. }
  35. double dist(P a) const {
  36. return sqrt(SQR(a.x – x) + SQR(a.y – y));
  37. }
  38. };
  41. const int maxn = 110;
  42. int n, m;
  43. P poly[maxn];
  44. int type[maxn];
  46. bool inter(P a, P b, P c, P d) {
  47. double s1 = a.cross(b, c);
  48. double s2 = a.cross(b, d);
  49. if (sgn(s1 – s2) == 0) {
  50. return false;
  51. }
  52. P t = P((c.x * s2 – d.x * s1) / (s2 – s1), (c.y * s2 – d.y * s1) / (s2 – s1));
  53. return sgn(t.dot(a, b)) < 0 && sgn(t.dot(c, d)) <= 0;
  54. }
  55. int inside(const P &p) {
  56. int ans = -1;
  57. for (P *it = poly + n – 1, *jt = poly; jt != poly + n; it = jt++) {
  58. double t = it->y < jt->y ? it->cross(*jt, p) : jt->cross(*it, p);
  59. if (sgn(t) == 0 && sgn(p.dot(*it, *jt)) <= 0) {
  60. return 0;   // point p is on the polygon.
  61. }
  62. if (sgn(t) < 0 && ((sgn(it->y – p.y) < 0) ^ (sgn(jt->y – p.y) < 0))) {
  63. ans *= -1;
  64. }
  65. }
  66. return ans; //if ans == 1 point is in the polygon and if ans == -1 point is out the polygon.
  67. }
  69. bool conn(P S, P T) {
  70. if (inside(P((S.x + T.x) / 2, (S.y + T.y) / 2)) == -1) {
  71. return false;
  72. }
  73. for (int i = n – 1, j = 0; j < n; i = j++) {
  74. if (inter(S, T, poly[i], poly[j])) {
  75. return false;
  76. }
  77. }
  78. return true;
  79. }
  81. double adj[maxn][maxn];
  83. double solve() {
  84. for (int i = 0; i <= n; ++i) {
  85. for (int j = i + 1; j <= n; ++j) {
  86. if (conn(poly[i], poly[j])) {
  87. adj[i][j] = adj[j][i] = poly[i].dist(poly[j]);
  88. } else {
  89. adj[i][j] = adj[j][i] = 1e100;
  90. }
  91. }
  92. }
  93. for (int k = 0; k <= n; ++k) {
  94. for (int i = 0; i <= n; ++i) {
  95. for (int j = 0; j <= n; ++j) {
  96. get_min(adj[i][j], adj[i][k] + adj[k][j]);
  97. }
  98. }
  99. }
  100. double tot = 0, OK = 0;
  101. for (int i = 0; i < n; ++i) {
  102. if (type[i] != 0) {
  103. ++tot;
  104. }
  105. }
  106. for (int i = 0; i < n; ++i) {
  107. for (int j = 0; j < n; ++j) {
  108. if (type[i] == -1 && type[j] == 1 && sgn(adj[n][i] + adj[n][j] – m) <= 0) {
  109. ++OK;
  110. }
  111. }
  112. }
  113. //for (int i = 0; i < n; ++i) {
  114. //printf(“%.2f “, adj[i][n]);
  115. //}
  116. //puts(“”);
  117. //printf(“%.0f %.0f %.0f\n”, I, O, tot);
  118. if (tot == 0) return 0;
  119. return OK / (tot * tot);
  120. }
  122. int main() {
  123. //freopen(“test.in”, “r”, stdin);
  124. freopen(“Precious.out”, “w”, stdout);
  125. while (scanf(“%d %d”, &n, &m) == 2 && (n || m)) {
  126. for (int i = 0; i <= n; ++i) {
  127. scanf(“%lf %lf”, &poly[i].x, &poly[i].y);
  128. if (i < n) {
  129. scanf(“%d”, type + i);
  130. }
  131. }
  132. printf(“%.9f\n”, solve());
  133. }
  134. return 0;
  135. }

H: Railway

题意就是边是属于无向图的0个环，1一个环，还是多个环。

这是一个利用双连通分量来求解的图论题。

把原来的图的双连通分量都求出来之后，判断每一个连通分量里面的点和边的数量的关系。

1. 点>边 那么这些边都是没有用的。

2. 点=边 那么这些边都是有用的。

3. 点<边 那么这些边都是会发生冲突的。

代码：

Railway.cpp
  1. /*
  2. * Author: momodi
  3. * Created Time:  2010-4-15 14:32:25
  4. * File Name: Railway.cpp
  5. */
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <cstring>
  9. #include <cmath>
  10. #include <cstdlib>
  11. #include <algorithm>
  12. #include <vector>
  13. #include <cassert>
  14. using namespace std;
  15. #define out(v) cerr << #v << “: “ << (v) << endl
  16. #define SZ(v) ((int)(v).size())
  17. const int maxint = -1u>>1;
  18. template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
  19. template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}
  21. const int maxn = 10000;
  22. const int maxm = 100000;
  23. int n, m;
  24. vector<int> adj[maxn];
  25. int pre[maxn], low[maxn];
  26. int ans[3];
  27. int tim;
  28. void dfs(int f, int v, int &anstype, int &anscnt) {
  29. anstype = anscnt = 0;
  30. int newtype = 0, newcnt = 0;
  31. low[v] = pre[v] = tim++;
  32. for (vector<int>::const_iterator it = adj[v].begin(); it != adj[v].end(); ++it) {
  33. if (*it != f) {
  34. if (pre[*it] == -1) {
  35. dfs(v, *it, newtype, newcnt);
  36. ++newcnt;
  37. if (low[*it] >= pre[v]) {
  38. ans[min(2, newtype)] += newcnt;
  39. } else {
  40. get_min(low[v], low[*it]);
  41. anstype += newtype;
  42. anscnt += newcnt;
  43. }
  44. } else {
  45. get_min(low[v], pre[*it]);
  46. if (pre[*it] < pre[v]) {
  47. ++anstype;
  48. ++anscnt;
  49. }
  50. }
  51. }
  52. }
  53. }
  55. int main() {
  56. //freopen(“test.in”, “r”, stdin);
  57. //freopen(“Railway.out”, “w”, stdout);
  58. while (scanf(“%d %d”, &n, &m) == 2 && (n || m)) {
  59. for (int i = 0; i < n; ++i) {
  60. adj[i].clear();
  61. }
  62. for (int i = 0; i < m; ++i) {
  63. int u, v;
  64. scanf(“%d %d”, &u, &v);
  65. adj[u].push_back(v);
  66. adj[v].push_back(u);
  67. }
  68. tim = 0;
  69. fill(pre, pre + n, -1);
  70. fill(ans, ans + 3, 0);
  71. int type, cnt;
  72. for (int i = 0; i < n; ++i) {
  73. if (pre[i] == -1) {
  74. dfs(i, i, type, cnt);
  75. }
  76. }
  77. //fprintf(stderr, “%d %d %d\n”, ans[0], ans[1], ans[2]);
  78. assert(ans[0] + ans[1] + ans[2] == m);
  79. printf(“%d %d\n”, ans[0], ans[2]);
  81. }
  82. return 0;
  83. }

I: Special Fish

这题我觉得没啥意思。。凑数的。把一个点拆成两个点之后，建立一个模型，然后跑km就好了。

Code Snippet
  1. /*
  2. * Author: momodi
  3. * Created Time:  2010-4-11 15:08:20
  4. * File Name: SpecialFish.cpp
  5. */
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <cstring>
  9. #include <cmath>
  10. #include <cstdlib>
  11. #include <algorithm>
  12. #include <vector>
  13. using namespace std;
  14. #define out(v) cerr << #v << “: “ << (v) << endl
  15. #define SZ(v) ((int)(v).size())
  16. const int maxint = -1u>>1;
  17. template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
  18. template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}
  20. struct Graph {
  21. static const int maxn = 100;
  22. int w[maxn][maxn], lx[maxn], ly[maxn], matx[maxn], maty[maxn], n;
  23. bool fx[maxn], fy[maxn];
  24. void clear() {
  25. memset(w, 0, sizeof(w));
  26. n = 0;
  27. }
  28. void insert(int u, int v, int c) {
  29. get_max(n, max(u + 1, v + 1));
  30. w[u][v] = c;
  31. }
  32. int match() {
  33. memset(ly, 0, sizeof(ly));
  34. for (int i = 0; i < n; ++i) {
  35. lx[i] = -maxint;
  36. for (int j = 0; j < n; ++j) {
  37. get_max(lx[i], w[i][j]);
  38. }
  39. }
  40. memset(matx, -1, sizeof(matx));
  41. memset(maty, -1, sizeof(maty));
  42. for (int i = 0; i < n; ++i) {
  43. memset(fx, false, sizeof(fx));
  44. memset(fy, false, sizeof(fy));
  45. if (!dfs(i)) {
  46. –i;
  47. int p = maxint;
  48. for (int k = 0; k < n; ++k) {
  49. if (fx[k] == true) {
  50. for (int j = 0; j < n; ++j) {
  51. if ((fy[j] == false)) {
  52. get_min(p, lx[k] + ly[j] – w[k][j]);
  53. }
  54. }
  55. }
  56. }
  57. for (int j = 0; j < n; ++j) {
  58. ly[j] += fy[j] * p;
  59. }
  60. for (int k = 0; k < n; ++k) {
  61. lx[k] -= fx[k] * p;
  62. }
  63. }
  64. }
  65. int ans = 0;
  66. for (int i = 0; i < n; ++i) {
  67. ans += w[maty[i]][i];
  68. }
  69. return ans;
  70. }
  71. bool dfs(int u) {
  72. fx[u] = 1;
  73. for (int v = 0; v < n; ++v) {
  74. if (lx[u] + ly[v] == w[u][v] && fy[v] == false) {
  75. fy[v] = true;
  76. if (maty[v] == -1 || dfs(maty[v])) {
  77. matx[u] = v;
  78. maty[v] = u;
  79. return true;
  80. }
  81. }
  82. }
  83. return false;
  84. }
  85. };
  87. Graph g;
  88. int main() {
  89. //freopen(“SpecialFish.out”, “w”, stdout);
  90. int n;
  91. while (scanf(“%d”, &n) == 1 && n) {
  92. vector<int> V(n);
  93. for (int i = 0; i < n; ++i) {
  94. scanf(“%d”, &V[i]);
  95. }
  96. vector<vector<bool> > adj(n, vector<bool>(n, 0));
  97. for (int i = 0; i < n; ++i) {
  98. char buf[n + 1];
  99. scanf(“%s”, buf);
  100. for (int j = 0; j < n; ++j) {
  101. if (buf[j] == ’1′) {
  102. adj[i][j] = true;
  103. }
  104. }
  105. }
  106. g.clear();
  107. for (int i = 0; i < n; ++i) {
  108. for (int j = 0; j < n; ++j) {
  109. if (adj[i][j]) {
  110. g.insert(i, j, V[i] ^ V[j]);
  111. }
  112. }
  113. }
  114. printf(“%d\n”, g.match());
  115. }
  116. return 0;
  117. }

SPX`3W4KSFGGEBS(VFXN3WF

我在公司比较忙，这次出题，其他题目我基本都没有看题意。整体上是xay把握的，所以其他题目的分析我就不说啦。标程和数据过会应该xay他们会发到官方网站上。

从Rank上来看，题目出的有点难了。。虽然我感觉题目和预赛的差不多。。G和H都ac的这么少，实在是出乎意料。

B题xay在赛前跟我说是难题，结果ac的这么多。。

A题xay说是sb题，结果没啥人ac。。

G题我以为会有5-6个队伍ac的。。结果也不对

反正基本没有猜对。。

Tags: , , , ,

Filed in Iproblem
«
»

Reader's Comments

  1. starvae | 22 Apr 2010 4:12 pm

    您好，请教一下H题，我给你一个图
    5个点，6条边
    1 2
    1 3
    2 3
    3 4
    4 5
    3 5

    这个图是应该算有用的呢？还是应该算冲突的呀？
    其实关于这一点，题目描述中并没有说的很明白。
    谢谢~

    [Reply]

    momodi Reply:
    April 22nd, 2010 at 8:32 pm

    这些点都属于一个环，都是好的。是怎么说清楚，图中环的定义不能有两个同样的点。

    [Reply]

    starvae Reply:
    April 23rd, 2010 at 8:10 am

    恩，我现在知道了，你所说的双联通分量是指点的双联通分量，不是边的双连通分量。

    [Reply]

Leave a Comment

sidebartop

My Calendar

September 2010
M T W T F S S
« May    
 12345
6789101112
13141516171819
20212223242526
27282930  
sidebarbottom
sidebartop

Categories

sidebarbottom
sidebartop

Recent Posts

sidebarbottom
sidebartop

Recent Comments

sidebarbottom
sidebartop

Tag cloud

visual tool c语言 dancing links vimrc GCC 病毒 总结 配色方案 vim HDOJ Monthly WHU2010校赛预赛 WHU2010校赛决赛 三分 贪心 图论 Computational Geometry 匹配 计算几何 圆的面积并 哈尔滨 线段树 网络流 浙江理工大学邀请赛 成都 合肥 Windows 7 Poj Monthly 南京 chaeyeon SRM 动态规划 二维线段树
sidebarbottom
sidebartop

Blogroll

sidebarbottom
sidebartop

Meta

sidebarbottom
sidebartop

1,106
Unique
Visitors
Powered By Google Analytics
sidebarbottom
© momodi's blog / Design: Smashing Wordpress Themes