加载中…
个人资料
杭之翼
杭之翼
  • 博客等级:
  • 博客积分:0
  • 博客访问:18,952
  • 关注人气:7
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
公告
Dream X Dream
评论
加载中…
留言
加载中…
分类
图片播放器
友情链接
访客
加载中…
好友
加载中…
博文
标签:

杂谈

如题,欢迎大家光临~

www.hhanger.com/blog/

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2009-06-20 13:47)
标签:

杂谈

分类: Mood

下雨了。

 

昨天考完要命的体系,灿哥带了我和光哥等三个人去外面吃饭,路上灿哥讲每天忙得要死,羡慕我们能去电影院看电影。

看起来我们以后的生活大概也会这个样子吧,不可避免……

最戏剧性的是本来灿哥要送我们回来再开个会的,结果回来的路上接到电话说儿子生病了,于是只好马上赶过去。。。

 

快乐在哪里,幸福又在哪里,到底应该过怎样的生活,这些到底是否轮得到我们来选择?

不知道,我只好督促自己再加油一点,暑假要抓紧时间做好事情……

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

acm

杂谈

分类: TopCoder
http://info.zjfc.edu.cn/acm/contest/contest_ranklist.aspx?cid=38

 

虽然做的人不多,描述也出了点问题,不过还是很开心,纪念一下。

 

下面是解题报告:

 

1001 Roba's Joke
这次是作为秒杀题的,同时表达下对Roba大牛的仰慕之情。
题目数据已经非常小了,所以怎么暴力都可以,比较方便的就是用gets读,然后用stringstream分词。
其他方法可能稍微麻烦一点,不过注意haha只能是完整单词即可。
一共只有4组数据,其中两组是sample,但是剩下两组强大的case还是卡住了不少人的。
其中有一组只有1个笑话,而且得分为0,有些人这个没处理好。

1002 Growing Numbers
这题一开始描述有误,哎,对不起大家了,检查了好多遍,最后最有把握的题还是出错了,抱歉一下。
例举一下这题比较坑的地方:
1.数据比较大,long long范围的,所以读取和输出的时候要注意一下格式,我干脆都用cin cout了,避免麻烦。
2.虽然输入数据和输出答案都在long long范围,但是中间过程处理不好就超出long long范围了。
3.为了避免上面的问题,可能会使用大数,不过估计会TLE ^^
4.不用大数,好好处理,但是不小心先入为主,使用矩阵来模拟growing,计算一轮的复杂度变成了N^2,则又超时了。
基于怎么处理溢出的问题,只要在计算的时候用除法判断是否会超过10^18即可,一旦超出,则直接赋值为10^18+1,我这样处理的。
上面的都处理好,这题应该就能AC了,不过这次比赛过的不多,成了第一大坑。

1003 Game
博弈题,可以证明:只用看数量最多的堆的个数即可。如果最多的堆的数量为奇数,则Win,否则Lose
证明如下:
1.当前数量为偶数,则不管怎么样去,数量最多堆的个数少了一个,变成了奇数个。
2.当前数量为奇数,则有两种情况,1或者大于等于3。对于后者,则随便取,最多堆的个数变成偶数;对于前者,考虑第二多堆的个数,如果为奇数,则把当前最多的堆取成和其一样,否则取成比其少,于是取好后,最多堆的数量是偶数。
大概就是这样,大家再理解一下。

1004 Good Night, Beautiful Stars
虽然N一共有40,但是保证每种颜色的不超过16,所以这题其实比较基础,就是集合dp。
开dp[1 << n]大小的空间,来记录某种还剩下某些点没有使用的情况下,还可以得到的最大的体积和。
求某个状态的值的时候,枚举当前状态没有使用的点中的所有三个点的组合的情况,当前状态的值为下一状态值加上三点构成长方体的体积和的最大值。
for_each(point i, j, k that are not used in state)
   do
      dp[state] = max(dp[state], dp[nextstate] + volume(i, j, k));
可以预先将所有三个点构成的长方体的体积计算好,以后每次求volume就不用算了,所有的volume都只要算一次。

1005 YiDing's Path
这题过的人数第二多。
把房子看成一个有向图,每个点和上下左右各连一条边。于是题目求的就是这个图的欧拉回路,因为每个点入度等于出度,所以欧拉回路一定存在。所以只要求出图中边的条数即可。
不过注意只要求和D联通的那部分图即可。

1006 It is Simple
这题如果用最naive的方法做,则复杂度是O(n^2)的,必定超时,所以要求一个优化的方法。
可以先求出B初始情况下的S值,以后没一次移动B,新的S值可以由上一次的得到。
具体的我不详细说明,大家可以在纸上推一个例子。只需要把S的新表达式和上一次的表达式各位差位详见,就可以发现每次的差值可以O(1)的时间求得。

 

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2009-04-12 01:31)
标签:

三联

杂谈

分类: Mood

晚上,不小心翻到了很多三联的东西,重温了一大堆的文字,虽然仅仅是一些文字,但是那是我整个高中生涯,整整4年的回忆吧。还看到了刚知道高考分数的时候,子玉在论坛发的恭喜贴,几年后回去看,又是一阵额外的感动,原来这些简单的文字,才是最能经得起时间考验的。

然而,回忆,不知道算不算是美好的,却只是我一个人的。自己已经完全不是当年的那个男孩了。在不一样的地方,接触不一样的人,听不一样的歌,玩不同的游戏,交不同的朋友,过着不同的生活。

前段日子很惊奇地在一个ACM群里发现了孟起马,居然现在还是一个高中生,一下子明白了很多,而现在看到,2002年的自己,也和他是一样的。

现在的三联早已物是人非,而我,一个过客,也会继续开拓我的新生活。好好努力,好好爱,让回忆放出激励的火花吧:)

 

下面是一些值得纪念的朋友。发在这里,他们看到的概率几乎为零,不过我希望他们一切都好,永远的朋友:

笨笨

乖乖

周羽

猫猫

12

黑色

霍光

文远

棍子

子玉

天杰星

猎雕

 

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

acm

zju

杂谈

分类: TopCoder

A Square Root Day      现场赛36.13% (155/429)/同步赛42.27% (290/686)
秒杀题,但是在题意方面出了一些问题,一种理解是日和月必须相同,于是一年最多只有一个Square Root Day,一年有一个Square Root Day当且仅当该年的最后2或3位是1-12的平方,这12个完全平方数中的一个。还有一种理解是日和月可以不相同,可以一个是后三位的平方根,另一个是后两位的平方根,于是会多几个日子,比如1225年5月15日。因为题意不清,所以最后两种理解都算过。


B Number of Containers      现场赛4.46% (32/717)/同步赛20.73% (102/492)
中等难度题,n可以很大,所以O(n)的算法显然是会TLE的。首先可以发现,f(n, x) = (n - x) / x,也就是n / x - 1,所以求解F(n)就是i从1到n,对n / i进行求和,最后再减去n就是答案。考察n / i随着i增大时候的情况,可以发现i越增大,n / i这个值变化得越小。于是可以把整个求和过程分成两块,对以1 <= i <= sqrt(n),直接求每个f(n, i)进行累加;而对于sqrt(n) < i <= n,他们的n / i的取值范围为1 - sqrt(n),也就是说,这个范围数虽然多,但是至多只有sqrt(n)种取值,于是我们改成枚举每种取值,求对应该取值的i的个数。这样两块的复杂度都是sqrt(n),可以满足时限要求。还有一点是最后的结果会超出int范围,需要使用long long类型。
题目因为被修改了一下,所以也有个地方没说清楚,不过应该不会误导人,只是理解起来有点费力。比赛的时候被放到了B题的位置,结果N多的队伍直接就来个直接暴力的,下次这种题目应该靠后一点放……


C Rounding or Truncation      现场赛2.12% (7/330)/同步赛7.55% (34/450)
中等难度题,有不少的trick。主要要解决的问题就是通过一组m和p的值,来推测在两种策略下,文件总数可能的取值范围。可以解决这个的话,只要对每组m和p对应的区间求交然后判断交是非为空即可。对于Rounding模式,p可以上下分别浮动0.5个百分点,其中往上的浮动是刚好取不到的(否则就向上进位了)。对于Truncation模式,p可以向上浮动小于1个百分点。这里还有一个问题是p等于0和等于100的时候要特别处理下,p等于0的时候,文件总数的上限是无数;p等于100的时候,因为没有向上浮动的空间了,所以对于Rounding模式,只能向下浮动,对于Truncation模式则完全不能浮动,只能是确定的100。有了p的取值范围就可以去根据m来计算文件总数的范围了,可以用double直接计算,但是处理不好很可能会有误差,推荐直接用整数处理,对p乘以10后,浮动的百分点数也就是整数了。能处理好上面的各项后,应该就能AC了。


D Elune's Arrow      现场赛8.95% (12/134)/同步赛8.02% (11/137)
中等偏难的几何题,不是很好想到解法。题目的模型就是用一个固定速度的圆去撞击一个朝固定方向进行匀速直线运动的圆,要选择角度从而尽可能早撞到移动的圆,输出最早撞到的时间。所谓圆撞到圆,就是圆心距离等于半径和,这里可以作一个模型转换,把逃跑的圆看成一个点,把它的半径加到追击的圆上。于是现在就是一个圆去追击一个匀速直线运动的点,依然不是很好处理。因为圆可以向所有角度发射,所以假设圆初始半径为r,速度为v,则在某个t时刻,圆可能触碰到的位置为一个半径为r+vt的圆。于是模型又可以这样转化:一个有初始半径的圆以速度v扩大半径,求何时能碰到一个直线运动的点。因为刚撞到的时候恰好是点在圆上的时候,因此可以立一个关于t的一元二次方程,最后求解方程,如果两个解都小于0则无解,否则输出最小的正解。
PS,这题也可以用其他ws的方法来解决,比如我用枚举角度+三分过了。


E Beverages for Sale      现场赛0.00% (0/2)/同步赛0.00% (0/1)
压轴题。题目给出的是这样一个模型:有一个可分割货物的集合A和购买者的集合B,每个购买者有各自拥有的钱的数量,而每种货物也有各自的数量。其中每个购买者只会购买A的某一个子集。购买者对货物的种类不关心,只想获得最多数量的货物。购买者只会购买他感兴趣的货物中价格最便宜的那些。题目要分析出这样一个模型的稳定状态,也就是说确定各种货物的价格,使得所有货物都卖完,所有购买者的钱也都用完。
我们可以构这样的一个图,所有货物和所有对它们感兴趣的购买者之间连边,流量为无穷(如果某一个货物或者某一个购买者没有任何边,则直接输出Impossible)。对于每个购买者,向一个汇点sink连一条边,流量为他们各自的钱数。然后从一个源点source向每一种货物连一条边,边的流量为货物的价格x。我们首先假设所有货物的价格都是一样的,我们需要二分这个价格x,使得所有的货物刚好可以全部被卖出去,也就是说确定最大的x,使得(source, A B sink)是图的一个最小割。然后考察假设这个时候的残余网络,假设在残余网络中可以到达sink的节点集合为W,设S=A-W,则集合S的所有潜在购买者(对S中任意一个货物感兴趣的购买者)都已经用完了他们的钱,如果再增加x,则会导致S的货物剩余。于是我们可以把所有集合S中的货物价格设置为x。接着,我们把集合S和S的所有潜在购买者集合从网络中去除,提高剩余货物的价格继续前面的步骤,如此循环往复,就可以把所有货物的价格确定下来的。


F Calculate With Abacus      现场赛39.59% (118/298)/同步赛60.00% (240/400)
描述有点长的简单题。已经保证了输入的算盘都是合法的,于是只要计算出算盘所代表的数字即可。其中一种方法就是看每一列的上下部分的|位置,就可以推算出该列代表的数字。这次也没有trick,一般只要读懂题就可以写对了。


G Number Game      现场赛5.36% (11/205)/同步赛13.52% (43/318)
中等难度题。有三个数字,每次可以去掉一个,然后加上剩下两个的和减一。问是否可以从给定的三个数得到给定的另外三个数字。可以发现,如果正着推的话,每次有三种选择,无法有效判断最终的三个数字是否可达。于是考虑逆着推,已知当前的三个数,其中最大的那个一定是新加的,而次大的那个一定是再前一次新加的,于是可以推算出被擦掉的那个数为次大数加一减最小数。这样一来,可以有唯一确定的方法递推回去。不过需要注意的是,正推的第一步,因为当前的三个数不一定满足a+b=c-1这样的等式,所以逆推的时候是无法确定被擦掉的数是多少的。所以,可以对初始的三个数枚举第一次擦掉的数为哪个,得到三种满足等式的情况。于是逆推的时候,一旦能匹配其中的一个就可以了。还有一点就是,只有当三个数满足等式才可以逆推。
赛前JJ曾说这题可能比F还简单,结果不知道什么原因大家都不敢碰。。


H Cover the String      现场赛0.00% (0/13)/同步赛2.43% (1/41)
中等偏难的动态规划题,需要好好优化才能把复杂度降下来。我的做法是:首先用所有的tiles构造一个trie。用s[i, j]表示原串从i到j的子串。然后考虑从后往前用tile来覆盖串,根据规则,每次放的串起始位置要在上一个之前,结束位置也要在上一个之前。dp[i][j]表示覆盖原串从第i位开始到最后的子串,且最后一个使用的tile覆盖了s[i, j]的方法数。还有一个sum数组,sum[i]表示当前所有的覆盖中,最后一个tile开始于原串第i位或者之前,结束于第i位之后数量。
for i from n - 1 to 0
  for j from i to n - 1  // 考虑覆盖s[i, j]
    dp[i][j] = (number of tiles cover s[i, j]) * sum[j];
  for j from n - 1 to i + 1 // 更新sum数组
    sum[j - 1] += Sum(dp[i][j] .. dp[i][n - 1]);
最后Sum(dp[0][0] .. dp[0][n - 1])就是解。其中number of tiles cover s[i, j]可以用trie在O(1)时间内得到,Sum(dp[i][j] .. dp[i][n - 1])这块可以用一个临时变量累加来优化成O(1),因此整个dp过程复杂度为O(1000^2)。考虑到子串的长度最多为200,因此可以把j这层循环变成tile的长度,这样复杂度变成O(1000*200),不包括前面建trie的时间。
如果不想使用trie,可以用kmp算法来预处理,同样可以在O(1)时间得到number of tiles cover s[i, j]。


I Nine Interlinks      现场赛28.29% (116/410)/同步赛37.54% (202/538)
简单的动态规划题,应该不难找到递归方程,就算不会动规,应该也能找到规律来求解。要把前n个变成on,首先把前n-1个变成on,然后把前n-2个变成off,然后把第n个变成on,然后把前n-2个变成on。所以dp[1] = 1, dp[2] = 2, dp[i] = dp[i - 1] + dp[i - 2] * 2 + 1。

 

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2009-03-09 01:36)
标签:

acm

杂谈

分类: TopCoder

Division summary - 2009 TCO Algorithm - Elimination Round 1, division 1

 

Pos Handle R Score Easy Medium Hard CP PerfAs RCh NR
28 Charizard 46 1277.36 + 234.27 + 463.80 + 529.29 +50.00 3014 +112 2471
78 rejudge 60 1108.37 + 75.00 + 359.17 + 599.20 +75.00 2735 +64 2435
103 gy 60 1032.82 + 247.31 + 264.16 + 521.35 0.00 2634 +61 2333
154 OuyangJialin 54 637.13 + 241.03 + 396.10 + Challenged 0.00 2400 +106 1973
176 caopeng 46 616.67 + 238.88 + 377.79 + Challenged 0.00 2357 +109 1873
247 hhanger 33 552.88 + 196.74 + 381.14 + Challenged -25.00 2340 -28 2491
295 hmilynavi 54 515.14 + 232.62 + 232.52 Opened +50.00 2128 +76 1818
363 smell 15 476.93 + 203.38 + 273.55 + Compiled 0.00 2013 +88 1624
366 chaosgy 6 475.49 + 211.77 + 263.72 Opened 0.00 2095 +45 1910
472 winsty 20 426.32 + 235.18 + 191.14 Closed 0.00 1889 +39 1723
479 Cristiano 7 421.45 + 242.66 + 203.79 Opened -25.00 1935 +27 1816
602 dd_engi 22 242.86 + 242.86 Opened Closed 0.00 1848 -51 2048
611 daiwb 8 242.16 + 242.16 + Compiled Closed 0.00 1737 +42 1549
649 classT 19 237.53 + 237.53 + Compiled Opened 0.00 1698 +44 1515
793 PE 10 222.43 + 222.43 Opened Closed 0.00 1545 +20 1465
1108 liux0229 40 168.30 + 193.30 Opened + Compiled -25.00 1281 -109 1765
1327 owen_water 34 0.00 + Challenged Opened Closed 0.00 731 -133 1275
1478 Fanazhe 25 -25.00 Closed Closed + Challenged -25.00 232 -186 1018
1510 hdu8600 38 -100.00 + Failed Opened Opened -100.00 -316 -191 1310

 这要命的比赛,害我昨晚都没怎么睡着……攒rp。。。

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2009-02-05 12:58)
标签:

杂谈

分类: Mood

好久没有写过一篇正常的日志了。

现在我的耳边环绕着N首曲子,有千千里的Zard,博客里的周惠,还有开老电脑的开机音乐。我觉得,我喜欢一切的音乐。

好像很多事情都是这样,我都喜欢,不知道这是好还是不好。也许是好吧,可能也不太好。

想写Marathon,想了一下,甚至把准备工作也都做好了,我还是放弃了。也许是这真的超出了我的能力范围,也许我本就不适合这个,也许是有了rating我不敢再乱玩了,又也许是我可以但却懒得懂脑子,总之,现在决定不去碰它。

回家了很奇怪,很多次睡不着,要起来看下推理/杀人故事才能睡着,很bt啊。。

很快就要回校了,还是听混沌的。

最近也发现,我比较喜欢回味过去,过去的痕迹。可惜已经回不去那个当时了,很多的事情我也早已想不起来,很多的痕迹,也早已经在岁月的擦洗中被抹去了。

停止一切声音,下面是我的时刻。

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2008-12-13 11:37)
标签:

srm

acm

topcoder

杂谈

分类: TopCoder

Division summary of ZJUer

 

 

Pos Handle R Score Easy Medium Hard CP PerfAs RCh NR
39 hhanger 19 709.78 + 178.71 + 431.07 + Compiled +100.00 2662 +24 2531
72 gy 19 612.50 + 217.80 + 419.70 + Challenged -25.00 2446 +38 2256
76 Charizard 1 605.79 + 240.00 + 390.79 + Challenged -25.00 2491 +2 2484
154 OuyangJialin 12 495.32 + 210.15 + 285.17 + Challenged 0.00 2046 +36 1925
191 hmilynavi 19 450.25 + 164.62 + 285.63 + Challenged 0.00 1958 +28 1862
234 classT 16 392.63 + 187.73 + 204.90 Closed 0.00 1813 +74 1504
450 hdu8600 33 131.88 + 156.88 + Failed Opened -25.00 1263 -18 1344
453 owen_water 30 129.93 + 129.93 Opened Closed 0.00 1289 -26 1393
517 jay23jack 32 50.00 + Failed + Challenged Closed +50.00 1090 -97 1492
528 caopeng 12 0.00 Opened Closed Closed 0.00 882 -127 1440

 

 

好久没写过这么搓的250了,写的时候觉得脑子爆炸了,其实本来几行就可以搞定的,我用了个很麻烦的方法来算……还好500的时候恢复了点。1000的时候,也静不下心来想了。还好最后cha了100分,不然就跌了,cha王道啊……

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2008-12-04 02:18)
标签:

acm

杂谈

分类: TopCoder

Division summary of ZJUer

 

Pos Handle R Score Easy Medium Hard CP PerfAs RCh NR
1 hhanger 9 1824.24 + 248.64 + 492.43 + 883.17 +200.00 2921 +85 2507
3 Charizard 9 1631.39 + 248.60 + 493.19 + 889.60 0.00 2562 +44 2350
9 hmilynavi 4 1528.87 + 247.32 + 493.53 + 788.02 0.00 2150 +96 1790
16 liux0229 11 1446.24 + 221.14 + 433.55 + 766.55 +25.00 1962 -32 2123
20 owen_water 7 1341.33 + 246.86 + 483.60 + 560.87 +50.00 1736 +91 1382
36 Fanazhe 8 1101.24 + 249.02 + 477.22 + 300.00 +75.00 1398 +96 996
41 jay23jack 1 986.68 + 244.23 + 466.55 + 300.90 -25.00 1455 -42 1640

 

 

一场很水的比赛,神奇地cha了3个人拿了第一 -_-。。。没什么好说的……

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2008-11-27 00:46)
标签:

srm

acm

杂谈

分类: TopCoder

Division summary of ZJUer

 

Pos Handle R Score Easy Medium Hard CP PerfAs RCh NR
60 hhanger 19 574.24 + 232.91 + 341.33 Opened 0.00 2503 +22 2394
120 rejudge 7 508.50 + 197.34 + 311.16 + Compiled 0.00 2223 +30 2088
186 caopeng 11 450.47 + 229.65 + 220.82 Opened 0.00 1982 +46 1777
256 jay23jack 32 389.77 + 160.22 + 229.55 Opened 0.00 1784 +42 1612
300 gy 22 233.57 + 233.57 + Failed + Compiled 0.00 1789 -75 2160
526 hdu8600 34 70.18 + 120.18 Opened Closed -50.00 1144 -55 1367
534 owen_water 22 0.00 + Challenged Opened Closed 0.00 923 -79 1228

 

 

N个星期前的比赛了,因为TC统计的那个网站一直挂着所以到现在才写,是crazyb0y出的一套题。

250是很强大的暴力dfs,还好我很快就想到了,没浪费太多时间。

500又是暴力题,暴力枚举直接搞,写了N长N暴力的程序,还好最后过了。

1000是生成树计数,yy dp方法,最重还是不会……

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
  

新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有