我真搓

Posted by twcai in My Life on September 30, 2008

这两场比赛都很郁闷，感觉像梦游，而且都是刚好在这两场加权的网络赛上。- -!
其他队员经过一个暑假集训都成长了好多，但我却好像根本没什么进步，现在也许我是整个集训队最弱的队员吧。记得暑假刚开始，lcy老师曾经在论坛里发贴跟我说：高手都是要以题量为保证的，指出我做题的数量太少。那时候我也听进去了，但心里总还有一点觉得我被刘老师给bs了。今天想想，觉得其实完全不是那样的，正是因为对我抱有期望所以才来指出我的短处啊。唉～～暑假都结束一个月了，可以看看我的这三个月来，只做了那么点题目，专题的跟进更是不行，跟托蒂简直不能比，太可怜啦。。
自从被szm指责后，我已经改掉了老喜欢发表决心的毛病了。但我觉得这次真的有必要下一次决心，要把以前落下的都一样一样补上！

No Comments

08-9-27

Posted by twcai in My Life on September 27, 2008

非常舒服的天气，也许是lcd盯太久了，偶尔抬头看天，就会有一种刺眼+震撼的感觉。那种湛蓝的颜色以及从视线边际射过来的光线让我不得不眯着眼睛，但是又充斥着就这么一直看下去的欲望。
是不是说明我真的变成一个宅男啦。
不知道为什么，如果被室外的风吹到有点凉意的时候，就会不由自主回忆起很多小时候的事情。且第一个闪过的画面总是自己趴在窗户边羡慕那些在楼下嬉戏的小孩，因为那时的我就很懒，总是不爱做作业所以老被老妈关在家里；那时候从窗外冲进来的风印象中就是这么带着点低温的伤感的。而后就是想起小学时老爸老妈常常带着我出去郊游的情景，低年级的我还是很乖的，每次都很快的把作文以外作业完成，然后星期天就可以出去郊游啦，我总是手里拿着一份树枝在行人踏出的小路上跑来跑去，并且去抽那些路边的野草。因为郊游大部分都在春天和秋天出去，地点也都在山上或者水边，那时候的风也是凉飕飕的。那时候应该还留下了蛮多照片的，不过我从高中后好像就没有去看过了，也许老爸老妈还偶尔会翻一下吧。
长大到底是好还是坏，很难说啊……

No Comments

8-20流水帐

Posted by twcai in My Life on September 21, 2008

看来铃声很有必要换一下，明明是7:30的闹钟，我就偏偏到了8:23才醒来。看到时间差点吓死啦，洗脸刷牙穿衣服，然后把本本和饼干塞进包里，等我冲出寝室时时8:28，有史以来起床最迅速的一次(-_-!)。
到了实验室，还好Teddy已经把机器都开好了(身为队长就是不一样啊)，王云斌也在临比赛前赶到，9:00哈尔滨赛区的网络赛就开始啦。比赛过程中我有很多失误，三个人配合的不是很好，蛮郁闷的，就不多说了。
2:00比赛结束后，教练把我们都拉出去吃饭，看了下他脸色MS不太好，有种会被拉到墙角枪毙的感觉。。。不过后来也没发生什么哈。我们学校的食堂这时候都关门了，小饭馆ms也容纳不下我们全部人，最后都去了传媒的食堂吃盖浇饭，中间大家都一直在调侃托蒂，弄得托蒂脸红耳骚，哈哈。餐后买单的时候教练和几位老队员ms激动了一把，不停得喊100、100，那时候没搞清楚状况，后来才知道，现在为了鼓励消费者要发票，上面都有刮奖，一碗盖浇饭开一张发票，怪不得，哈哈。
Read the rest of this entry »

No Comments

HDOJ 1043

Posted by twcai in ACM/ICPC on September 18, 2008

八数码问题，pku上的数据太弱了，zju还在升级中(非常期待啊)，我的代码在hdoj上跑了14XXms，用的是优先队列+bfs。
明天整个白天都有课，等有空了再优化吧，花了一天多的时间A了这题，贴下代码先。

  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. #define END 123456789
  5. int hash[362880];
  6. short path[362880];
  7. int fa[362880];
  8. char eight[25];
  9. int fi[9]={0,1,2,6,24,120,720,5040,40320};
  10. int ten[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
  11.  
  12. inline int lt(const int &x)
  13. {
  14.     return x-1;
  15. }
  16.  
  17. inline int rt (const int &x)
  18. {
  19.     return x+1;
  20. }
  21.  
  22. inline int up(const int &x)
  23. {
  24.     int t0=10-x%10;
  25.     int t1=x/ten[t0];
  26.     int t2=t1%1000;
  27.     t1=t1-t2+(t2%100)*10+t2/100;
  28.     t1*=ten[t0];
  29.     return (t1+x%ten[t0]-3);
  30. }
  31.  
  32. inline int dn(const int &x)
  33. {
  34.     int t0=7-x%10;
  35.     int t1=x/ten[t0];
  36.     int t2=t1%1000;
  37.     t1=t1-t2+(t2/10)+(t2%10)*100;
  38.     t1*=ten[t0];
  39.     return (t1+x%ten[t0]+3);
  40. }
  41.  
  42. inline int hashfun(const int &x)
  43. {
  44.     int di=0;
  45.     int cou=8;
  46.     int tem=x;
  47.     int dig[9]={0};
  48.     while(tem>0)
  49.     {
  50.         dig[cou--]=tem%10;
  51.         tem/=10;
  52.     }
  53.     for(int i=1;i<8;i++)
  54.     {
  55.         tem=0;
  56.         for(int j=0;j<i;j++)
  57.             if(dig[j]>dig[i]) tem++;
  58.         di+=tem*fi[i];
  59.     }
  60.     di+=(9-dig[8])*fi[8];
  61.     return di;
  62. }
  63.  
  64. inline int gu(const int &x)
  65. {
  66.     int di=0;
  67.     int bk;
  68.     int tem=x;
  69.     bk=x%10;tem/=10;bk--;
  70.     for(int i=8;i>=0;i--)
  71.     {
  72.         if(i==bk) continue;
  73.         if(tem%10!=i+1) di++;
  74.         tem/=10;
  75.     }
  76.     return di;
  77. }
  78.  
  79. struct node{
  80.     int sta;
  81.     int no;
  82.     int va;
  83.     int ga;
  84. };
  85. bool operator <(const node &x,const node &y)
  86. {
  87.     return x.va>y.va;
  88. }
  89.  
  90. node now,next;
  91. priority_queue <node> et;
  92. int be,bef;
  93.  
  94. inline int bfs()
  95. {
  96.     int bk;
  97.     memset(hash,0,sizeof(hash));
  98.     while(!et.empty()) et.pop();
  99.     now.sta=be;now.ga=0;
  100.     now.va=gu(now.sta);
  101.     now.no=hashfun(now.sta);bef=now.no;
  102.     fa[now.no]=0;path[now.no]=0;
  103.     et.push(now);hash[now.no]=1;
  104.     while(!et.empty()){
  105.         now=et.top();et.pop();
  106.         if(now.sta==END) return now.no;
  107.         bk=now.sta%10;
  108.         for(int i=0;i<4;i++)
  109.         {
  110.             switch(i)
  111.             {
  112.             case 0:if(bk==1 || bk==4 || bk==7) continue;
  113.                 next.sta=lt(now.sta);
  114.                 next.no=hashfun(next.sta);
  115.                 next.va=gu(next.sta);
  116.                 next.ga=now.ga+1;
  117.                 if((next.ga+next.va)<(now.ga+now.va)) continue;
  118.                 if(hash[next.no]==1) continue;
  119.                 path[next.no]=i;fa[next.no]=now.no;
  120.                 et.push(next);hash[next.no]=1;
  121.                 break;        //left
  122.             case 1:if(bk==3 || bk==6 || bk==9) continue;
  123.                 next.sta=rt(now.sta);
  124.                 next.no=hashfun(next.sta);
  125.                 next.va=gu(next.sta);
  126.                 next.ga=now.ga+1;
  127.                 if((next.ga+next.va)<(now.ga+now.va)) continue;
  128.                 if(hash[next.no]==1) continue;
  129.                 path[next.no]=i;fa[next.no]=now.no;
  130.                 et.push(next);hash[next.no]=1;
  131.                 break;        //right
  132.             case 2:if(bk<4) continue;
  133.                 next.sta=up(now.sta);
  134.                 next.no=hashfun(next.sta);
  135.                 next.va=gu(next.sta);
  136.                 next.ga=now.ga+1;
  137.                 if((next.ga+next.va)<(now.ga+now.va)) continue;
  138.                 if(hash[next.no]==1) continue;
  139.                 path[next.no]=i;fa[next.no]=now.no;
  140.                 et.push(next);hash[next.no]=1;
  141.                 break;        //up
  142.             case 3:if(bk>6) continue;
  143.                 next.sta=dn(now.sta);
  144.                 next.no=hashfun(next.sta);
  145.                 next.va=gu(next.sta);
  146.                 next.ga=now.ga+1;
  147.                 if((next.ga+next.va)<(now.ga+now.va)) continue;
  148.                 if(hash[next.no]==1) continue;
  149.                 path[next.no]=i;fa[next.no]=now.no;
  150.                 et.push(next);hash[next.no]=1;
  151.                 break;        //down
  152.             }
  153.         }
  154.     }
  155.     return 0;
  156. }
  157.  
  158. inline void dfs(const int &n)
  159. {
  160.     if(n==bef) return ;
  161.     dfs(fa[n]);
  162.     switch(path[n])
  163.     {
  164.     case 0:printf("l");
  165.         break;
  166.     case 1:printf("r");
  167.         break;
  168.     case 2:printf("u");
  169.         break;
  170.     case 3:printf("d");
  171.         break;
  172.     }
  173. }
  174.  
  175. int main()
  176. {
  177.     int x,en,xpl;
  178.     int tem,di,cou,dig[9]={0};
  179.     while(gets(eight))
  180.     {
  181.         be=0;xpl=0;
  182.         for(int i=0;eight[i]!='\0';i++)
  183.         {
  184.             if(eight[i]>='0' && eight[i]<='9')
  185.             {be*=10;be+=eight[i]-'0';xpl++;}
  186.             else if(eight[i]=='x')
  187.                 x=xpl+1;
  188.         }
  189.         be*=10;be+=x;
  190.         di=0;cou=8;tem=be;
  191.         while(tem>0)
  192.         {
  193.             dig[cou--]=tem%10;
  194.             tem/=10;
  195.         }
  196.         for(int i=1;i<8;i++)
  197.         {
  198.             tem=0;
  199.             for(int j=0;j<i;j++)
  200.                 if(dig[j]>dig[i]) tem++;
  201.             di+=tem;
  202.         }
  203.         if((di&1)!=0) printf("unsolvablen");
  204.         else {
  205.             en=bfs();
  206.             dfs(en);
  207.             printf("n");
  208.         }
  209.     }
  210.     return 0;
  211. }

1 Comment

SRM417

Posted by twcai in TopCoder on September 12, 2008

郁闷啊，哭死啦，55555.
250没什么好说的，500分的写到一半觉得怎么查找前缀和后缀字符串的思路很模糊，看看时间还是45分钟左右，去开了1000分。1000分刚开始以为是概率就是长度比，其实没这么简单，估计是一个两头窄中间宽的分布，写着写着时间就怎么没了，结果到最后只有230多分。
然后弄了一组比较长的数据，去cha别人的500，盲cha，失败两次，哭死。
唉，解题报告先欠着，明天软件2+2要开学报名了，下午还有比赛，慢慢来吧。
另外GX黄队终于变蓝啦。

No Comments