Archive for category ACM/ICPC

比赛的意义

Posted by twcai in ACM/ICPC, My Life on May 30, 2011

今天是2011 World Finals ACM/ICPC的比赛日，晚上10点开始看比赛的直播，看着每个学校的队伍的排名交错的攀升，看到HDU-Knuth的两题AC，两题WA，突然脑海闪回过自己的大二暑假，背上出了点汗，手臂上起了鸡皮疙瘩。

杭电进World Finals已经不是第一次，但是今年退役后看比赛跟去年在役看比赛是两种心情。在役时似乎更多的是不甘心和一些小嫉妒，因为我显然WF无望。之前自然也知道想进World Finals很难很难，但还是难免偶尔会狂妄的暗暗把这当作自己的目标。现在的我，对自己宽容了，内心平静了，但有时候也怀疑自己是不是失去了激情和进取心。

记得以前北大的CICI姐姐写过一篇日志，大致是说她在World Finals看到一个非洲的大学的队伍，只AC两题，却在赛后激动的跟领队拥抱欢呼。虽然她一个人也可以做出两题，但是她却没有那些人的快乐。

想到这里，我释然了，ACM/ICPC竞赛可以给我的，我都已经得到了。

, , ,

1 Comment

图论图论!

Posted by twcai in ACM/ICPC on August 2, 2009

没错，就是图论！要好好练！

图论旅程第一题 : POJ 2337 Catenyms
5551478 clumsydragon 2337 Accepted 200K 16MS C++ 1775B
以单词的开头字母和结尾字母为点，单词为边，找一条欧拉路。先计算每个点的度数，判断能否构成一条欧拉路，然后再用深搜寻找答案。

Ural 1129 Door painting
这题应该MS是利用图论的性质来求解。题目要求无向图的每条边两端各涂绿或黄色(两端不同)，且一个点内两种颜色数量相差不能超过1。如果这张图能构成一个欧拉回路，假设每条边的头为黄尾为绿，按照欧拉回路来遍历，那么每个点的黄绿两色数量都恰好相等；如果这张图无法构成欧拉回路，那么可以在图中加边来使他满足，因为每个点最多被加一条边，那么拿去这条多余的边，点内黄绿两色的数量变为相差1。我的做法就是先加边，然后dfs把每条路上色。

最小树形图：
对图中的每个点取权值最小的入边，若这个边集组成的图中若没有圈，这得到该图的最小树形图；否则对每个圈进行缩点。缩点中，涉及到对重点在圈内的弧的权值的处理。圈内的边权全部加到最小树形图的代价上，指向圈的入弧比如Arc[i][j] 则减去 Arc[pre[j]][j], 这里pre[j]是圈中的j点的前驱。然后对缩点后的图继续上述的步骤，一直到边集中再也没有圈为止。这些所选的边的边权之和，加上之前已经得到的边权就可以得到最小树形图的总代价了。
突然有个想法，zl算法在缩点前和缩点后的状态之间权值变化的计算，是不是有DP的思想呢？
最小树形图具体的题目有 ：
TJU 2248 Channel Design
PKU 3164 Command Network
UVa 11183 Teen Girl Squad
上面三题都是固定节点的最小树形图，没有固定节点的最小树形图也可以转化成固定节点的方法来做。

HDU 3072 Intelligence System
这也是一题比较有意思的最小树形图。先用Kosaraju算法找出所有强连通分量并缩点，然后再做最小树形图。

贴下HDU 3072的代码：

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <bitset>
  6. #include <string>
  7. #include <vector>
  8. #include <cctype>
  9. #include <cstdio>
  10. #include <ctime>
  11. #include <queue>
  12. #include <stack>
  13. #include <cmath>
  14. #include <list>
  15. #include <map>
  16. #include <set>
  17.  
  18. using namespace std;
  19.  
  20. #define inf 0x7fffffff
  21. #define sz 110
  22.  
  23. vector <int> VS[50010];
  24.  
  25. #define NMAX 51000
  26. vector<int> path[NMAX];
  27. vector<int> npath[NMAX];
  28. int n,m, scc;
  29. int order[NMAX], order_pos, id[NMAX];
  30. bool vis[NMAX];
  31.  
  32.  
  33. int pre[sz];
  34. int del[sz];
  35. bool visited[sz];
  36.  
  37. void dfs(int pos)
  38. {
  39.     int i,j,l;
  40.     vis[pos] = true;
  41.     l = path[pos].size();
  42.     for (i=0;i<l;i++) {
  43.         j = path[pos][i];
  44.         if (!vis[j]) {
  45.             dfs(j);
  46.         }
  47.     }
  48.     order[ order_pos ++ ] = pos;//make order
  49. }
  50.  
  51. void ndfs(int pos)
  52. {
  53.     int i,j,l;
  54.     vis[pos] = true;
  55.     id[pos] = scc;
  56.     VS[scc].push_back(pos);
  57.     l = npath[pos].size();
  58.     for (i=0;i<l;i++) {
  59.         j = npath[pos][i];
  60.         if (!vis[j]) {
  61.             ndfs(j);
  62.         }
  63.     }
  64. }
  65.  
  66. void Kosaraju()
  67. {
  68.     int i,j;
  69.     //dfs in original graph
  70.     memset(vis, 0, sizeof(vis));
  71.     order_pos = 0;
  72.     for (i=0; i<n ;i++) {
  73.         if (!vis[i]) {
  74.             dfs(i);
  75.         }
  76.     }
  77.     //dfs in inverse graph
  78.     memset(vis, 0, sizeof(vis));
  79.     memset(id, 0, sizeof(id));
  80.     scc = 0;
  81.     for (i=order_pos-1; i>=0 ;i--) {
  82.         if (!vis[ order[i] ]) {
  83.             ndfs(order[i]);
  84.             scc ++;
  85.         }
  86.     }
  87.     scc --;
  88. }
  89.  
  90.  
  91. int hash[50010];
  92. struct node{
  93.     int ni, nj, val;
  94. };
  95. node ainfo[100010];
  96. int val[110][110];
  97.  
  98. struct edge{
  99.     int no;
  100.     int vt[400];
  101.  
  102.     edge() { no = 0; }
  103.  
  104.     inline void clear() { no = 0; }
  105.  
  106.     inline int operator [] (const int &x) {
  107.         return vt[x];
  108.     }
  109.  
  110.     inline void push(const int &x) {
  111.         vt[no ++] = x;
  112.     }
  113. };
  114.  
  115. edge arc[sz], rarc[sz];
  116.  
  117.  
  118. inline void modify(int &x, const int &y) {
  119.     x = x < y ? x : y;
  120. }
  121.  
  122. inline int minTree(int root, int n) {
  123.     memset(del, 0, sizeof(del));
  124.     memset(pre, -1, sizeof(pre));
  125.  
  126.     int i, j, k, np, op, mi, ret = 0, last = 0;
  127.     bool fg;
  128.     while(1) {
  129.         for(i = 0; i < n; i++) {
  130.             if(i == root || del[i]) continue;
  131.             fg = 0;
  132.             for(j = 0; j < rarc[i].no; j++) {
  133.                 if(del[rarc[i][j]]) continue;
  134.                 op = rarc[i][j];
  135.                 if(!fg || mi > val[op][i]) {
  136.                     mi = val[op][i];
  137.                     np = op;
  138.                     if(!fg) fg = 1;
  139.                 }
  140.             }
  141.             if(fg) pre[i] = np;
  142.         }
  143.         for(i = last; i < n; i++) {
  144.             if(i == root || del[i]) continue;
  145.             last = i;
  146.             memset(visited, 0, sizeof(visited));
  147.             for(j = pre[i]; j != root && !visited[j]; j = pre[j]) {
  148.                 visited[j] = 1;
  149.             }
  150.             if(j == root) continue;
  151.             i = j;
  152.             do {
  153.                 ret += val[pre[j]][j];
  154.                 del[j] = 1;
  155.                 j = pre[j];
  156.             } while(j != i);
  157.             j = i;
  158.             do {
  159.                 for(k = 0; k < rarc[j].no; k++) {
  160.                     if(del[rarc[j][k]]) continue;
  161.                     op = rarc[j][k];
  162.                     if(val[op][i] == inf) {
  163.                         rarc[i].push(op);
  164.                         arc[op].push(i);
  165.                         val[op][i] = val[op][j] - val[pre[j]][j];
  166.                     }
  167.                     else
  168.                         modify(val[op][i], val[op][j] - val[pre[j]][j]);
  169.                 }
  170.                 for(k = 0; k < arc[j].no; k ++) {
  171.                     if(del[arc[j][k]]) continue;
  172.                     op = arc[j][k];
  173.                     if(val[i][op] == inf) {
  174.                         arc[i].push(op);
  175.                         rarc[op].push(i);
  176.                         val[i][op] = val[j][op];
  177.                     }
  178.                     else
  179.                         modify(val[i][op], val[j][op]);
  180.                 }
  181.                 j = pre[j];
  182.             } while(j != i);
  183.             del[i] = 0;
  184.  
  185.             break;
  186.         }
  187.         if(i >= n) {
  188.             for(i = 0; i < n; i++) {
  189.                 if(i == root || del[i]) continue;
  190.                 ret += val[pre[i]][i];
  191.             }
  192.             return ret;
  193.         }
  194.     }
  195.  
  196.     return ret;
  197. }
  198.  
  199. int main()
  200. {
  201.  
  202.     while (scanf("%d %d" , &n , &m) == 2)
  203.     {
  204.         int i, j;
  205.         for (i=0 ; i < n ; i ++){
  206.             VS[i].clear();
  207.             path[i].clear();
  208.             npath[i].clear();
  209.  
  210.         }
  211.         scc = 0;
  212.  
  213.         int ta , tb;
  214.         for (i=0 ; i < m ; i++){
  215.             scanf("%d %d %d" , &ta , &tb, &ainfo[i].val);
  216.             ainfo[i].ni = ta;
  217.             ainfo[i].nj = tb;
  218.             path[ta].push_back(tb);
  219.             npath[tb].push_back(ta);
  220.         }
  221.  
  222.         Kosaraju();
  223.  
  224.  
  225.         scc ++;
  226.         for(i = 0; i < scc; i++) {
  227.             for(j = 0; j < VS[i].size(); j++) {
  228.                 hash[VS[i][j]] = i;
  229.                 //printf("%d ", VS[i][j]);
  230.             }
  231.             //printf("\n");
  232.         }
  233.         for(i = 0; i < scc; i++) {
  234.             for(j = 0; j < scc; j++) {
  235.                 val[i][j] = inf;
  236.             }
  237.             arc[i].clear();
  238.             rarc[i].clear();
  239.         }
  240.  
  241.         for(i = 0; i < m; i++) {
  242.             ta = hash[ainfo[i].ni];
  243.             tb = hash[ainfo[i].nj];
  244.             if(val[ta][tb] == inf) {
  245.                 arc[ta].push(tb);
  246.                 rarc[tb].push(ta);
  247.                 modify(val[ta][tb], ainfo[i].val);
  248.             }
  249.             else
  250.                 modify(val[ta][tb], ainfo[i].val);
  251.         }
  252.  
  253.         for(i = 0; i < scc; i++) {
  254.             val[i][i] = inf;
  255.         }
  256.  
  257.         int root = hash[0];
  258.         int ret = minTree(root, scc);
  259.  
  260.         printf("%d\n", ret);
  261.     }
  262.  
  263.     return 0;
  264. }

, , ,

2 Comments

AC自动机

Posted by twcai in ACM/ICPC on July 31, 2009

AC自动机是KMP算法和Trie数据结构的结合，重点主要在KMP算法的理解。我觉得AC自动机是我学过的最精妙和犀利的算法。
AC自动机的题目有蛮多的，我只做了两题最简单的 :

Keywords Search
最单纯的AC自动机

Word Puzzles
也比较简单，不过我的做法是把单词正反两个方向都建立了Trie，这样后面查找的量能减少一半，在POJ上比我只建立一个方向的代码的效率快了1/3。不过要注意的是，本来keywords都是唯一的，但是建两个方向以后就不唯一了。顺便贴下这题的代码。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <queue>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cmath>
  7. using namespace std;
  8.  
  9. #define sz 197260
  10.  
  11. int dir[8][2] = {-1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1, 0, -1, -1, -1};
  12. int rx[1011], ry[1011], rd[1011], len[1011];
  13. char text[1001][1010];
  14. bool vsd[1011];
  15. int afcg[1011];
  16. int next[sz][26], pos;
  17. int fa[sz], fp[sz], isword[sz], val[sz], id[sz];
  18. int r, c, zf, rm;
  19.  
  20. inline bool valid(const int &x, const int &y) {
  21.     return (x >= 0 && x < r && y >= 0 && y < c);
  22. }
  23.  
  24. inline void build(const int &cur, char *st, const int &k) {
  25.     int op = *st - 'A';
  26.     int ps;
  27.      if(!next[cur][op]) {
  28.         ps = pos;
  29.         next[cur][op] = pos ++;
  30.         val[ps] = op;
  31.         fa[ps] = cur;
  32.     }
  33.     else
  34.         ps = next[cur][op];
  35.     if(*(st + zf) == '\0') {
  36.         if(isword[ps]) {
  37.             if(zf > 0) afcg[k] = -id[ps];
  38.         }
  39.         else {
  40.             isword[ps] = 1;
  41.             id[ps] = k * zf;
  42.         }
  43.     }
  44.     else
  45.         build(ps, st + zf, k);
  46. }
  47.  
  48. inline void bfs() {
  49.     int i, j, op, now, nxt, root = 0;
  50.     fp[root] = -1;
  51.     queue <int> qq;
  52.     while(!qq.empty()) qq.pop();
  53.     for(i = 0; i < 26; i++) {
  54.         if(next[root][i])
  55.             qq.push(next[root][i]);
  56.     }
  57.  
  58.     while(!qq.empty()) {
  59.         now = qq.front(), qq.pop();
  60.         nxt = fa[now];
  61.         op = val[now];
  62.         do{
  63.             nxt = fp[nxt];
  64.         }while(nxt != -1 && !next[nxt][op]);
  65.         if(nxt == -1)
  66.             fp[now] = root;
  67.         else
  68.             fp[now] = next[nxt][op];
  69.         for(i = 0; i < 26; i++) {
  70.             if(next[now][i])
  71.                 qq.push(next[now][i]);
  72.         }
  73.     }
  74. }
  75.  
  76. inline void search(const int &x, const int &y, const int &k) {
  77.     int tx = x, ty = y;
  78.     int op, tmp, dd, cur = 0;
  79.     while(valid(tx, ty)) {
  80.         op = text[tx][ty] - 'A';
  81.         while(cur != -1 && next[cur][op] == 0) {
  82.             cur = fp[cur];
  83.         }
  84.         if(cur == -1) cur = 0;
  85.         else {
  86.             cur = next[cur][op];
  87.             tmp = cur;
  88.             while(tmp != -1) {
  89.                 if(isword[tmp]) {
  90.                     dd = abs(id[tmp]);
  91.                     if(vsd[dd]) break;
  92.                     if(id[tmp] < 0) {
  93.                         rx[dd] = tx;
  94.                         ry[dd] = ty;
  95.                         rd[dd] = (k + 4) & 7;
  96.                     }
  97.                     else {
  98.                         rx[dd] = tx - dir[k][0] * (len[dd] - 1);
  99.                         ry[dd] = ty - dir[k][1] * (len[dd] - 1);
  100.                         rd[dd] = k;
  101.                     }
  102.                     vsd[dd] = 1;
  103.                     rm --;
  104.                 }
  105.                 tmp = fp[tmp];
  106.             }
  107.         }
  108.         tx += dir[k][0];
  109.         ty += dir[k][1];
  110.     }
  111. }
  112.  
  113. inline void init(const int &cur) {
  114.     for(int i = 0; i < 26; i++) {
  115.         if(next[cur][i]) {
  116.             init(next[cur][i]);
  117.             next[cur][i] = 0;
  118.         }
  119.     }
  120.     isword[cur] = 0;
  121. }
  122.  
  123. int main()
  124. {
  125.  
  126.     freopen("ACM.in", "r", stdin);
  127.     freopen("ACM.out", "w", stdout);
  128.  
  129.     char ln[1500];
  130.     int n, root = 0;
  131.     int i, j;
  132.     while(scanf("%d %d %d", &r, &c, &n) != EOF) {
  133.         getchar();
  134.         for(i = 0; i < r; i++) {
  135.             gets(text[i]);
  136.         }
  137.         init(root);
  138.         pos = 1;
  139.         for(i = 1; i <= n; i++) {
  140.             gets(ln + 1);
  141.             afcg[i] = i;
  142.             ln[0] = '\0';
  143.             len[i] = strlen(ln + 1);
  144.             zf = 1;
  145.             build(root, ln + 1, i);
  146.             zf = -1;
  147.             build(root, ln + len[i], i);
  148.         }
  149.         rm = n;
  150.         bfs();
  151.  
  152.         memset(vsd, 0, sizeof(vsd));
  153.         int tr = r - 1, tc = c - 1;
  154.         for(i = 1; i < 5; i++) {
  155.             switch(i)
  156.             {
  157.             case 1:
  158.                 for(j = 0; j < c; j++) {
  159.                     search(tr, j, i);
  160.                 }
  161.             case 2:
  162.                 for(j = 0; j < r; j++) {
  163.                     search(j, root, i);
  164.                 }
  165.                 break;
  166.             case 3:
  167.                 for(j = 0;  j < r; j++) {
  168.                     search(j, root, i);
  169.                 }
  170.             case 4:
  171.                 for(j = 0; j < c; j++) {
  172.                     search(root, j, i);
  173.                 }
  174.                 break;
  175.             }
  176.         }
  177.         for(i = 1; i <= n; i++) {
  178.             if(afcg[i] != i) {
  179.                 j = afcg[i];
  180.                 rd[i] = (rd[j] + 4) % 8;
  181.                 rx[i] = rx[j] + (len[j] - 1) * dir[rd[j]][0];
  182.                 ry[i] = ry[j] + (len[j] - 1) * dir[rd[j]][1];
  183.             }
  184.             printf("%d %d %c\n", rx[i], ry[i], rd[i] + 'A');
  185.         }
  186.     }
  187.     return 0;
  188. }

, ,

2 Comments

ZOJ 3209 Treasure Map

Posted by twcai in ACM/ICPC on July 6, 2009

精确覆盖问题，看着DLX算法的伪码打的。
以格子为行，矩形为列，构造一个描述覆盖情况的矩形，用DLX算法求解。

其他可以用dancing links求解的题目还有
nuaa 1267 N皇后问题

hust 1017 Exact Cover
23849 clumsydragon 1017 Accepted 1872 kb 256 ms C++ 2253 B 2009-07-10 13:37:56

spoj 1771 Yet Another N-Queen Problem
2559174 2009-07-12 07:19:00 CD Yet Another N-Queen Problem accepted 0.36 2.6M C++

tju 3219 Radar

fzu 1686 神龙的难题

神龙的难题允许overlap的覆盖，写了3遍还是TLE，先放一放

贴下3209的代码

下载: 3209.cpp
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. #define sz 451451
  6.  
  7. int l[sz], r[sz], u[sz], d[sz], y[sz];
  8. int s[961];
  9.  
  10. int n, m, ret;
  11.  
  12. inline void remove(const int &c) {
  13.     int i, j;
  14.     r[l[c]] = r[c];
  15.     l[r[c]] = l[c];
  16.     for(i = d[c]; i != c; i = d[i]) {
  17.         for(j = r[i]; j != i; j = r[j]) {
  18.             d[u[j]] = d[j];
  19.             u[d[j]] = u[j];
  20.             s[y[j]] --;
  21.         }
  22.     }
  23. }
  24.  
  25. inline void resume(const int &c) {
  26.     int i, j;
  27.     for(i = u[c]; i != c; i = u[i]) {
  28.         for(j = l[i]; j != i; j = l[j]) {
  29.             d[u[j]] = j;
  30.             u[d[j]] = j;
  31.             s[y[j]] ++;
  32.         }
  33.     }
  34.     r[l[c]] = c;
  35.     l[r[c]] = c;
  36. }
  37.  
  38. inline int dfs(int k) {
  39.     if(ret <= k)
  40.         return 0;
  41.  
  42.     int i, j, c;
  43.     if(r[0] == 0) {
  44.         if(k < ret)
  45.             ret = k;
  46.         return 1;
  47.     }
  48.     int mi = 0x7FFFFFFF;
  49.     for(i = r[0]; i; i = r[i]) {
  50.         if(s[i] < mi) {
  51.             mi = s[i];
  52.             c = i;
  53.         }
  54.     }
  55.  
  56.     remove(c);
  57.     for(i = d[c]; i != c; i = d[i]) {
  58.         for(j = r[i]; j != i; j = r[j]) {
  59.             remove(y[j]);
  60.         }
  61.  
  62.         dfs(k + 1);
  63.  
  64.         for(j = l[i]; j != i; j = l[j]) {
  65.             resume(y[j]);
  66.         }
  67.     }
  68.     resume(c);
  69.  
  70.     return 0;
  71. }
  72.  
  73. int main()
  74. {
  75.     int t, tn, tm, t1, t2, pos;
  76.     int i, j, k;
  77.     int x1, y1, x2, y2;
  78.     scanf("%d", &t);
  79.  
  80.     while(t --) {
  81.         scanf("%d %d %d", &tn, &tm, &n);
  82.         m = tn * tm;
  83.         for(i = 0; i <= m; i++) {
  84.             if(i + 1 > m)
  85.                 t1 = 0;
  86.             else
  87.                 t1 = i + 1;
  88.             r[i] = t1, l[t1] = i;
  89.             u[i] = i;
  90.             s[i] = 0;
  91.         }
  92.  
  93.         int hd;
  94.         t2 = m + 1;
  95.  
  96.         for(i = 1; i <= n; i++) {
  97.             scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
  98.             hd = t2;
  99.             x2 --, y2 --;
  100.             for(j = y1; j <= y2; j++) {
  101.                 pos = j * tn + x1 + 1;
  102.                 for(k = x1; k <= x2; k++) {
  103.                     t1 = t2;
  104.                     if(j == y2 && k == x2)
  105.                         t2 = hd;
  106.                     else
  107.                         t2 ++;
  108.                     u[t1] = u[pos], d[u[t1]] = t1;
  109.                     u[pos] = t1, s[pos] ++;
  110.                     r[t1] = t2, l[t2] = t1;
  111.                     y[t1] = pos;
  112.                     pos++;
  113.                 }
  114.             }
  115.             t2 = t1 + 1;
  116.         }
  117.  
  118.         bool fg = 1;
  119.  
  120.         for(j = 1; j <= m; j++) {
  121.             if(!s[j]) {
  122.                 fg = 0;
  123.                 break;
  124.             }
  125.             d[u[j]] = j;
  126.         }
  127.  
  128.         if(!fg)
  129.             printf("-1\n");
  130.         else {
  131.             ret = 0x7FFFFFFF;
  132.             dfs(0);
  133.             if(ret == 0x7FFFFFFF)
  134.                 printf("-1\n");
  135.             else
  136.                 printf("%d\n", ret);
  137.         }
  138.     }
  139.     return 0;
  140. }
  141.  
  142. /*
  143. 2
  144.  
  145. 5 10 9
  146. 0 0 5 1
  147. 0 1 5 2
  148. 0 2 5 3
  149. 0 3 5 4
  150. 0 4 5 5
  151. 0 5 5 10
  152. 2 3 5 10
  153. 0 5 2 10
  154. 0 3 2 5
  155.  
  156. 30 30 8
  157. 0 0 11 30
  158. 11 0 30 11
  159. 11 11 20 20
  160. 11 20 20 30
  161. 20 11 30 30
  162. 0 0 11 11
  163. 0 11 11 30
  164. 0 0 30 20
  165. */

,

1 Comment

省赛总结

Posted by twcai in ACM/ICPC on May 24, 2009

rank name solved A B C D E F G H I J K 罚时
15 HDU-Firebirds 7 13 (1) 144 (3) 138 (1) 7 0 22 (1) 0 0 24 (1) 121 (2) 66 (2) 608

省赛对我来说是入队以来最重要的比赛，因为直到那天我都还没想好省赛后是否退役，说不定这就是我最后一场比赛了(明年省赛不算，如果退役了，相信那时候也只是抱着旅游的态度了)。省赛前夜11点就整理完东西，洗漱上床了，但一直醒到2点多。

第二天6点半起来了，感觉有点睡眠不足，不过还算蛮精神的。上午的东西都直接略过，下午在机房门口等比赛开始的时候，发现去年杭州赛区的主场作战真的是蛮大的优势。

比赛开始我猜C是ms题，然后看了题目，是跟通常情况有点不同的MST，我们队不熟prim，又不会证明kruscal肯定可以得到正解，于是我放下C看I，并发现是简单题上机敲。敲完sample出不来，于是打印。Teddy上机敲A，在无声无息中过掉了。我发现自己I想复杂了，上去改了下，还是有问题。甘露上机敲F，期间我发现I的一个bug，甘露过掉F后，我上去改了I，提交后Yes。

过完I，看了下statistics，B和K都很多人过，我推了下B，是一个B - (X + A / X)的函数，忘掉怎么求最小值，直接扔给斌哥了。然后看K，简单构造题，上机打完后，Teddy对我的解法不是很肯定，造了几组数据测了下，然后提交CE……崩溃，赛前测编译器，好像就是平常poj的g++编译器，没想到还是出现这种错误。然后加了头文件，返回Yes。wyb上机打B。

接着看了下J，很熟悉的题目，记得是一个DP。不过Teddy对于这题的解法记忆不是很清晰了，我想了个简单的解法，换下wyb实现了下，过不了造的数据。这时teddy记起来解法了，换下wyb敲J。我帮斌哥一起看B，另外想了个解法，不过到最后还是跟斌哥已经wa的做法一样，感觉有两种可能，一种是情况没考虑全，一种是精度问题，然后一直在讨论。teddy过了J后，对C还是拿不定，我觉得还是应该试下kruscal。甘露很快敲好了C，提交以后居然Yes了……昏倒。接着wyb上去改了一下B，也过掉了。

这时候过了两个钟头多，我们的rank好像是在11，但是罚时没有优势。我们都很清楚要稳拿金牌一定要再过一题，而且剩下时间还蛮充裕的。wyb最先开了D题，我和甘露讨论了G。但是我图论实在烂，在读过几乎全部题目后(除了D)决定用搜索开H。wyb用暴力打好D，提交后tle，然后甘露上机敲G，敲到一半他觉得不肯定，换我上机敲H  =,=||

赛后想起来这段时间真的是在梦游，我敲H的时候心里很虚，但是还是觉得不应该放弃有想法的题目，敲完大部分代码。敲到没想清楚的地方后，换上wyb继续敲D。我记得这时候已经剩下一个钟头不到的时间了，于是和teddy都渐渐放弃了自己的题目，和wyb一起做D。这题他用了上次宁波刚从DD牛那里学到的逆元来处理做除法取模，本来我们都以为这题会很有希望的，没想到就一直这么修修改改到比赛结束。

时间还是无情的指向了5:25。我们已经明白金牌无望，伤心下一直在抱怨题目区分度不好。但是冷静下来想想，这真的只是题目的原因吗？我们队还是在比赛策略上有很大的失误：

一是C题太犹豫。Kruscal只需要5分钟的机时，但是我们一直到2个多钟头才下决心去试，是对比赛形势的错误估计。这种比赛，有6、7个队过掉了就应该果断的尝试。

二是7题以后的各自为战。我们队的优势是互补，平常比赛难题也都是合作解出的。

三是最后合力攻D时，阵脚已经乱了。两个人不去好好读题，却不停修改代码以及问wyb各种问题，影响了他深入思考。到比赛结束teddy还没有理解题意，我还没有读懂wyb的解法，最后一次提交代码的版本都搞乱了。这种时候，应该有一个人出来稳定整个队的情绪。

四是练习赛没有把握好测环境的机会，导致CE的出现。这是经验和总结的欠缺。

银牌实在是令人遗憾，但也是真实水平的反映。每一次比赛都是绝好的积累经验和反省的机会，希望再通过一个暑假的集训，Firebirds能拿到让我们三个人都满意的成绩。

No Comments