momodi's blog http://gaoyunxiang.com My technology blog Wed, 12 May 2010 01:24:56 +0000 en hourly 1 http://wordpress.org/?v=3.0 浙江理工大学邀请赛流水帐 by momodi@OpenLegend http://gaoyunxiang.com/?p=113 http://gaoyunxiang.com/?p=113#comments Wed, 12 May 2010 01:24:26 +0000 momodi http://gaoyunxiang.com/?p=113 Open是武大长期流传下来的人文精神，也是我们集训队一直的宝贵财富。因此我们在Legend的基础上取名OpenLegend，作为本次比赛的队名。

比赛前一天：

本来是想周六中午BG大家的，结果发现了浙江理工在下沙之后就知道中午来不及BG了，所以改到晚上。晚上的湘菜馆还是挺不错的，虽然我感觉不够辣。。吃饭的时候看大家的状态都不错，都挺Happy的。

周六下午热身赛的时候，Dumbear问了我一句：“我们的比赛策略是什么？”

听到这个问题之后，我顿时感觉大脑空白了几秒。

思索了良久这个问题的答案，回想起了以前在ChaeYeon队伍的时候制定的种种策略，比如赛前要制定表格，说好每个人的读题顺序，想好卡题了怎么办，碰到什么类型的题目让谁做，谁负责主要读题，谁负责帮队友debug等等等等。

在回想完这种种之后，不知道为什么感觉这些策略都不值得提出来，于是跟Dumbear说:“到时候看情况，该怎么样就怎么样吧。”

不过虽然没有继续讨论“策略”这个问题，我仍然在那里静静的思考了良久，或许真正的策略便跟武侠里面一样“重剑无锋，无招胜有招”。

周日上午九点，比赛正式开始了：

简单题H和A：

Dumbear和ISea开始读题。这时候我把每一个题目都扫描了一下。为什么要这么做呢？

这还需要从出题说起，自从去年开始大量出题之后，自我感觉上我对比赛的一些细节问题有了一些很新的认识。比如：一般来说这种强度的邀请赛都会有一个sb题来保证每一个队伍都至少AC一道题。而这种SB题是字符串处理的概率很大，因为字符串处理题好出-.-

在寻找了一圈样例里面有字符串的题目之后，我选中了H，运气挺好的，H确实是一个足够简单的题目。

我在上机的时候Dumbear还问了我H是什么类型的，本想解释一番的我想到Dumbear可能是怕这个题目不够简单，怕我太急了。所以我随口回复了“H是A+B类型的题目。”

AC了H之后Dumbear上来AC了A题。这时候差不多是9点30分，也就是说比赛经过了半个小时了。我猜想接下来的题目应该就没有A和H那么简单了，没想到的是剩下的题目难度也都不大。唯一的压轴难题确是我们几乎没有可能做出来的题。

计算几何D题：

我在写H题的时候就听Dumbear和ISea在讨论有一个简单的计算几何，DumbearAC了A之后我便上机开始敲这道几何题（D题）。计算几何写完之后有个小插曲，就是不知道为什么有一个泛型的函数编译通过不了。在询问了ISea和Dumbear之后，他俩也表示不知道。于是我果断停止在这里纠结，换了一种写法。编译通过并且过了样例之后，我又盯着代码看了一会，继续回想了一下是不是有特殊情况。这时候ISea问怎么样了，我答：“可以交了”。Dumbear附和了一句“交吧，感觉momo这题写的挺仔细，应该没问题。”听到这句话我小小的惊讶了一下，为什么Dumbear会知道我写的很仔细呢？

D题1Y。

状态压缩DP题 B和数据结构题F：

ISea很早就说了B是一个简单题，不过因为题目里面要牵扯到棒球的规则，所以ISea在跟我讲这个题目意思和做法的时候，我只是听了一个大概。不过我还是挺相信ISea的，所以我也就没有追求这个题目的细节，跟ISea表示了一下问题不大后，ISea也是直接去写了。

而后Dumbear跟我讲了讲F题题意以及RMQ的做法。我知道题意之后发现此题就是求一个数列中每一个数的左右两边边比他大的第一个数。这个问题的解法我很早就知道了，代码也很短，所以先把ISea从机器上拉了下来，换我上去AC了这道题。

而后ISea也1Y了状态压缩的B题。

乱搞题I：

接下来ISea和Dumbear讨论了一下I题后发现了其“简单题”的本质，不过这中间有一点点冲突：ISea有一个优美的方法，而Dumbear想直接去暴力模拟。最后Dumbear去用ISea的优美方法写的，可惜的是WA了两次也还没有AC。这时候Dumbear和ISea又再次重新读题，在确保了题意理解无误的情况下，Dumbear没办法换了他原来准备的暴力模拟的方法AC了I题。回想此题，最好的情况应该是Dumbear一开始就写最保险的暴力模拟方法。不过在出问题之后Dumbear能够顶住压力重写代码，还是很赞的。

图论+树形DP题E：

E题样例里面输出的是小数，也就是说E题是两种题目可能性最大：几何题或者概率题。这两种不同类型的题目对我来说完全就是两个极端，每次碰上样例输出小数的题目我都是爱恨交加。

我在读完题之后，悲剧的发现是概率题。

在I题的解决过程中，我仔细的研究了一下E题，发现与概率关系不大，在跑完最短路之后只要两边BFS就可以了。不过因为场上还没有提交这个题目，所以我们也并没有急于去写这个题目。后来在跟Dumbear讲解这个题目的题意和做法的同时，我更加确信这个题目的做法没错。所以做法也没有讲完，我就直接上机去写这个题目了。

写完之后WA了一遍，不过我马上意识到了错误的地方（图有可能不联通），因为这个地方在我刚开始写的时候考虑到了，中间因为I题被打断了一次，竟然所以把这个Trick给忘记了。改过之后E题2Y。

需要转弯的矩阵乘法题G：

在Dumbear写I题的时候，我和ISea一直在思索G题的做法，可惜一直没有找到正确的方向。后来经Dumbear提醒才恍然大悟，原来可以改成递推式用矩阵乘法解决。ISea去写了G。因为还有很长时间去写这个题目，所以我们有足够的信心G题肯定能AC。J题AC之后就是剩下最后一题J了。

压轴题J：

此题是浙江省赛的一个变形，这个题对我们来说是一个很大的悲剧，因为浙江省赛的时候是我们校赛决赛的练习赛，Dumbear和ISea是在参赛，我是在出题，所以没有一个人在当时对这个题有细细的研究。不过因为知道这个题目是一个难题，所以我们前期并没有浪费时间在这个题目上。最后还有一个多小时没事做的情况下，我们才开始细细的推导这道题。

当时有两个思路：

1. 先用强连通分量来判断是不是无解，求这个图的圈覆盖，而后试图把圈合并。

2. 先用强连通分量来判断是不是无解，然后搜索答案。

第一个思路我感觉是比较接近最终答案的，但是因为就连最初的假设“存在哈密顿路的充分必要条件是整个图在一个强连通分量里面”都不确定是不是正确的，所以这个思路并没有发展成熟。

第二个思路比较简单，所以在没有办法的情况下，我去用这个思路试图“水了水”。得到的结果也是理所当然的TLE。在用了各种搜索技巧提交了几十次之后，比赛结束了。

最后的结果是浙大的队伍做出了J题，AK了所有的题目。

我们因为罚时排在了9题第一总排名第二，虽然有些小小的遗憾，但是终究还是输在了实力上，就算没有J题，也是只能第二名。

结束语：

能够和Dumbear和ISea组队很开心，赛后找了一个网吧10个人打Dota内战，大家在尽兴之后开始了此次比赛的结束之旅。

在回去的路上得知了另外两只6题的队伍，一个银牌第一，一个银牌第三。不过是因为输在题数上，所以我想也没什么特别的遗憾。

Dumbear和ISea在赛场上显得很老练，对各种问题的处理也很成熟。我想他们两个再加上我们的传奇人物，一定能够在赛场上取得辉煌的成绩。

虽然今年我们集训队相比去年来说有种种不足和问题，但是我相信今年区域赛我们还是会有更大的突破的。

大家加油～激情比赛，为了目标而奋斗到底：）

]]> http://gaoyunxiang.com/?feed=rss2&p=113 6 HDOJ Monthly Contest – 2010.05.01 Line belt http://gaoyunxiang.com/?p=111 http://gaoyunxiang.com/?p=111#comments Sat, 01 May 2010 10:36:41 +0000 momodi http://gaoyunxiang.com/?p=111 这题是我最早想给HDOJ月赛的，现在借lxh达到了这个目的-.-!

http://acm.hdu.edu.cn/vip/contest_showproblem.php?pid=1004&cid=289

没啥特别意思的几何题。。做法就是双重三分，也就是三分里面套一个三分。

放在这里记录一下我的出题成果：）

突然发现，最近这一年我也狠狠的出了不少题了。从区域赛的出题到我们的校赛，再加上PKU和HDU的月赛加起来有几十道了。每一道题我都力求创新，绝不Copy陈题。。

想想出题最累的还是给区域赛出的题。。从最初组建了多人的出题委员会，到最后这个委员会只有我一个人。那个时候我相当囧迫，每天绞尽脑汁的想Idea想了整整一个暑假，好不容易凑出来十个题目。

虽然没啥经验，但是这十个题目还是整合了我参加acm这么多年以来的精华。我感觉挺不错的有两个：1. 原创了圆的面积并的算法。2. 完成了一个很复杂的但是却很有实际背景图论模型的建模（后来的决赛的I题）。

因为题目是我一个人出的，所以必然显得类型很偏门。不过我很奇怪的是为啥复旦的一些人那么愤愤不平，公然在校内上鄙视我们学校-.-（让我想起了多年以前也是复旦一队的成员公然跑到我们学校的OJ上说我们的OJ垃圾，骗代码。。）

预赛搞完了之后，和复旦的这件事好像搞的很多人都知道了，我们集训队也有很多人愤愤不平，跑到人家校内上有了开始对骂的势头-.-
没办法，为了不让事情搞大影响集训队的形象，我专门找到复旦的一个负责人，跟人家说明情况，并且对题目表示Sorry。。还好复旦也比较通情达理，都删掉了校内上的那些对话，一段往事就这样平息了。。

不过还是有点小小的无语。。我们都已经表示了决赛的题目不是我们出，预赛是因为经费问题所以才由我们自己出的。为啥有些人就不能宽容一点？还好当时正在研究佛法，我表示”忍了“，要是按照我以前的火爆性子，早就不知道啥样了。。

再后来看见有人用很不友好的言语在他的blog里面说我们学校公布的标程故意耍帅，故意不让别人看懂。。在表示无语的同时我也理解了一个道理，在做一些自认为是好事的时候，必然有一些人对你进行言语上的攻击，他们也不一定就是恶意，只是表示一下自己不爽了。。

]]> http://gaoyunxiang.com/?feed=rss2&p=111 5 武汉大学第八届程序设计竞赛部分决赛题目分析 http://gaoyunxiang.com/?p=108 http://gaoyunxiang.com/?p=108#comments Sun, 18 Apr 2010 06:56:52 +0000 momodi http://gaoyunxiang.com/?p=108 在这里简单说一些我出的题目。

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的。。结果也不对

反正基本没有猜对。。

]]> http://gaoyunxiang.com/?feed=rss2&p=108 3 HDOJ Monthly Contest – 2010.04.04 Problem 1003 Point http://gaoyunxiang.com/?p=102 http://gaoyunxiang.com/?p=102#comments Mon, 05 Apr 2010 03:27:27 +0000 momodi http://gaoyunxiang.com/?p=102 http://acm.hdu.edu.cn/vip/contest_showproblem.php?pid=1003&cid=276

题目大意就是用下面的距离定义来求每一个点的最近点对。

Distance (A, B) = max (|Ax – Bx|, |Ay – By|)

这题是我最初给我们学校去年的区域赛准备的题目。说一下做法：对于每一个点，先二分答案，这样转化为判断是不是一个正方形内有点的问题。对于解决这个问题，用二维的线段树来解决。很多人对于二维线段树的理解就是把一维变成二维，空间复杂度从O(n)变成O(n^2)。其实不是这样的，复杂度为O(n^2)的线段树基本没有什么用处。

可以用变化一下的实现方法使得空间复杂度变成O(nlogn)。具体的实现方法可以参见我们学校的wiki上我贴的代码。

http://acm.whu.edu.cn/wiki/index.php/Point

]]> http://gaoyunxiang.com/?feed=rss2&p=102 7 WHU2010校赛预赛J题：Guard http://gaoyunxiang.com/?p=99 http://gaoyunxiang.com/?p=99#comments Mon, 05 Apr 2010 03:18:26 +0000 momodi http://gaoyunxiang.com/?p=99 http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&cid=288

题意：给定一个简单多边形，问内部哪个点可以看到的面积最大。（可视范围是已知的R，也就是说，如果没有遮挡，那个可视面积就是一个半径为R的圆）

这题是我出的另一个复杂几何，说一下做法：经过爬山处理之后，就变成了一个纯粹的几何题，问题：给定一个简单多边形，和一个点，问这个点能看到的面积是多大。

我的做法就是把圆和所有的线段离散化。除了他们交点之外还要用到视线的射线来离散化。

离散化之后就是判断每一个单元小块是不是可见的。。麻烦是麻烦了点，但是思路还是挺清晰的。不知道有没有人有兴趣去做做这个题目。

]]> http://gaoyunxiang.com/?feed=rss2&p=99 4 WHU2010校赛预赛G题：Pseudoforest http://gaoyunxiang.com/?p=95 http://gaoyunxiang.com/?p=95#comments Mon, 05 Apr 2010 03:10:33 +0000 momodi http://gaoyunxiang.com/?p=95 http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1007&cid=288

题目大意：给一个图，求这个图的最大伪森林生成树。所谓的伪森林就是图中的任意两个圈都没有公共部分。

这题是我出的，这里说一下做法：从大到小排个序之后用类似Kruskal算法的并查集操作求得答案。对于已经有环的部分，需要做一个标记。

有一个很容易想到的但是是错误的做法：先求最大生成树，然后在每一个联通块里面添加最大边。对于这种数据，这种做法是明显错误的。

A—B—-C—D（AB, BC, CD分别连接）

A–E–B   C–F–D （AE, EB, CF, FD连接）

如果先求得最大生成树，那么最终答案一定有B-C这条边。

但是事实上，我们很容易构造边权，使得ABC和CDF分别连通来构成最大伪森林。（这样就不包含B-C这条边了)

]]> http://gaoyunxiang.com/?feed=rss2&p=95 0 WHU2010校赛预赛C题：Ice-sugar Gourd http://gaoyunxiang.com/?p=92 http://gaoyunxiang.com/?p=92#comments Mon, 05 Apr 2010 02:55:12 +0000 momodi http://gaoyunxiang.com/?p=92 http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&cid=288

题目大意：给一个由两种水果组成的冰糖葫芦，现在需要把这两种水果平均送给两个人。问最少需要切割多少次。（切割不能把水果切开）

这题是我出的，在这里说一下做法：如果能够猜到一个结论：最多需要切割两次。

那这个题就很简单了。。

说一下证明：

这里的证明要用到计算几何里面很重要的一个问题：给平面上的两种点，一定存在一条直线，把这两种点分别均分。

那么怎么应用到我们这个题目里面呢？就是想象把冰糖葫芦弯曲成一个抛物线。根据上面的结论，我们一定可以把这个抛物线用一条直线切割开来。这条直线与抛物线最多有两个交点-.-所以问题得证。。

]]> http://gaoyunxiang.com/?feed=rss2&p=92 2 WHU2010校赛预赛B题：fix http://gaoyunxiang.com/?p=90 http://gaoyunxiang.com/?p=90#comments Mon, 05 Apr 2010 02:43:24 +0000 momodi http://gaoyunxiang.com/?p=90 题目地址：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=288

题目意思是告诉很多点（最多18个），然后有一些点是固定住了的，有一些点是没有固定的。现在需要用小木棍连接，使得所有的点都固定住。

问小木棍的总长度最短是多少。

这个题目是我出的，在这里说一下这个题目的做法：

可以用状态压缩的DP来解决这个问题。2^n来表示状态，每一次添加一个点来更新状态。

在这个题目的最初版本里面，对于B–R–R–B这种数据也是属于固定住了的。这是一个很深的Trick，但是想到了之后，却不难解决。只要在DP的拓展状态的时候，加上一个判断，判断是不是有点在当前的小木棍上就可以了。

]]> http://gaoyunxiang.com/?feed=rss2&p=90 0 推荐一个vim的配色方案desertEx http://gaoyunxiang.com/?p=83 http://gaoyunxiang.com/?p=83#comments Sun, 14 Feb 2010 13:07:49 +0000 momodi http://gaoyunxiang.com/?p=83 可以在这里下载：http://vimcolorschemetest.googlecode.com/svn/colors/desertEx.vim

使用方法：

将文件下载到vim目录下的colors。然后在vimrc里面加入colo desertEx就好了。

感觉比默认的desert清爽一点。

效果图：

image

]]> http://gaoyunxiang.com/?feed=rss2&p=83 0 SRM 461 http://gaoyunxiang.com/?p=79 http://gaoyunxiang.com/?p=79#comments Sun, 14 Feb 2010 07:06:43 +0000 momodi http://gaoyunxiang.com/?p=79 300P: ColoringRectangle

Greedy algorithm works to this problem:

After we sort the red disks and blue disks by descending order, the final disk placed order would be determined if we choose one of the largest red and blue disks as the left-most disk, where the red disks alternate with the blue disks.

Trick: The disk cannot be used whose diameter is less the height of the rectangle.

500: BuildingCities

Build a graph with at most 50 * 2000 (f[i][j]) vertexes, which means the minimum distance of vertex i which has used j new cities.

Then run shortest path algorithm (SPFA or Dijkstra) on this graph to find the answer.

950: FencingGarden

 

let Y be the an edge of the rectangular garden which is orthogonal to the wall, and let Y be the edge parallel to the wall.

2X + Y = S (the sum of length of the fence segments)

And we want to the answer of max(X * Y).

We know that max(X * Y) = max(2X * Y) / 2 = S/2 * S/2.

We can divide the segments into two groups, and we enumeration 2^(n/2) to each group, and merge it to find the answer.

We can only cut one segment into two parts, so one of the edges of the rectangle must consist of non-cut segments.

Case 1: one of the orthogonal-to-the-wall edges consists of non-cut segments.

For each combination in a group, if we put it on an edge of orthogonal-to-the-wall ones, we can make sure that the choices of the less of this edge must be leaved to  two combinations in another group as the length of this edge need to be close to S/4.

Case 2: the parallel-to-the-wall edge consists of non-cut segments.

This method is just similar to the method of case 1, but we changed the purpose to find a combination whose length is closed to S/2.

We can use sweeping lines algorithm, and it can run in O(2 ^ 20).

]]> http://gaoyunxiang.com/?feed=rss2&p=79 0