加载中…
我去过的地方
国内 (5篇)
国外 (1篇)
个人资料
下雪的天空
下雪的天空
  • 博客等级:
  • 博客积分:0
  • 博客访问:45,166
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
welcome!
Locations of visitors to this page
搜博主文章
评论
加载中…
访客
加载中…
留言
加载中…
好友
加载中…
关于爱
爱情是滋生于悬崖的两株交缠着的藤
一起面对呼啸的山风一起承受风雨雷电
一起吸收清晨的甘露一起看落日的余晖
一起抹去肩上的黄叶 然后一起慢慢地老去
亲爱的  我能告诉你 爱永恒不变
MyHomePage
博文
标签:

博客七周年

我的博客今天578天了,我领取了徽章.  

  • 2007.06.21,我在新浪博客安家。
  • 2007.07.04,我写下了第一篇博文:《上海人的生活态度》。
  • 至今,我的博客共获得32,872次访问。
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-06-09 11:13)
标签:

计算几何

it

分类: 计算几何

做一些基础的题熟悉下计算几何,为看书巩固下。

http://poj.org/problem?id=2318 二分所在盒子的位置,通过叉积判断是否在四边形内。

http://poj.org/problem?id=3304 判断所有线段是否能投射到一条直线上,实际上就是能否找到一条直线可以通过所有的线段,需要想到的是,这样的一条直线通过移动必定会被某两个线段的端点卡住,所以枚举两线段端点作为直线,判断此直线是否可以与所有线段相交。

http://poj.org/problem?id=1269 求两直线交点,先判直线重合,假设两直线(u1,u2)(v1,v2),则重合为Det(u1,v1,v2)==0&&Det(u2,v1,v2)==0,如果是平行,则Det(Point(0,0),u2-u1,v2-v1)==0即可。去掉这两种,就必定相交了,可以用求定比分点方法,或者解方程(也是运用了叉积)来求。

http://poj.org/problem?id=1556 黑书上有讲过,思想为走的路线必定为某两个顶点间的连线,比如能否直达,所以如果能直达,必然两点之间去最

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

acm

dp

codeforces

it

分类: 编程

这个不算是题解,题解在官方网站有详细解答,只是想记录一下自己的想法。

首先是最近的感想,现在有了微薄都懒得再更新博客,但是当看到自己以前写的一些东西,还是可以感受到当时思维的脉搏。我应该多想多写。还有写程序一定要想清楚再下手。好了,言归正传。

这场比赛的D题要说难也不是特别难,但是要是给我,估计一天都想不出来。关键是这题的一个转换,实现则不难。题目的意思是给出长度为n(n <= 10000)的串,现在要使k(<=10)个位置置为1,修改得方式是选取l(l<=100)个区间中一个,使整个区间都反置。看到k为10,第一反应是状态压缩DP,但是却怎么也找不到转移关系。因为区间修改后序列变得非常复杂,状态很难记录。官方题解提出,如果令序列c[], c[i] = c[i] ^ c[i + 1],则题目可以变为使含有2k个1的序列通过最少的操作变为全0。而这里的操作将一个区间[a,b]反转变成c[a-1]和c[b+1]反转。证明很简单,对于[a,b]内部的点,因为同时反转,所以c[i] ^ c[i+1]依然不变,而边界的值会发生反转。而上述从2k个1变为全0也使题目一下全部明朗了,虽然0到2k个1和2k个1到0是等价的,但是反过来想更容易想到状态的转移。接下来就是个2^(2k)的状态

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

codeforces

题解

it

AIrrational problem
题目意思很明确,就是要枚举24种状态,使用C++的next_permutation很方便。

二分枚举结果,因为对于损失来说只要算出所有总体的转移,然后乘以损失系数。

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

it

分类: 心情
在几个月前的《一些总结》里,说有一个愿望,希望可以梦想成真,当时我很害怕会想大话西游里说的,我猜的到故事的开头,却猜不到故事的结局。而事实是我没猜中故事的开头,而猜中了故事的结尾。
大三的时候,我们Caster和Pollux各自为着自己的梦想去奋斗,而最终都是两块银牌告终。也许也是这两个名字所隐藏着的含义(双子座的两兄弟),我们两个队必须要组合成一个队了(神话里一样),于是带着实验室的梦想,我们组成了Puzzle。当时Mcfn就说,去年都是铜牌,今年我们全是银牌,希望明年都是金牌。而今年的各种邀请赛,我们也顺利的实现这这个梦想。直到杭州赛区的杯具,成都赛区的遗憾,我们在故事的开端就失误了。成都回来其实信心受到了很大的挫折,因为在成都我们可以说已经算是尽力了,但是却也只有银牌。而陈党和我们谈心让我们找到了问题所在:我们的策略有问题。为了追求正确率,我们都是两个人做一个题,在成都的时候,到最后手上还有2个题却已经没有时间了。要想在福州出线,必须要“赌”一下,必
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: 心情
这是我的最后一场区域赛,之所以不会再比,是因为我看到了天才,我突然觉得单单为了一个名誉而投入一年一年的时间实在不值得。但是这三年的坚持却让我获得了太多的东西。比如朋友,做题的乐趣,一个进入中科院计算所继续学习的机会。这或许就是无心插柳,我带着一个极功利的心,却得到了如此多的好处。真是奇怪

不过追名逐利这本身就是错的,不管它现在是否给我带来好处,如果仍然这样,终有一天会眩晕,会迷失,会后悔。

我希望我的告别赛用绚烂的方式结束。是的,我们办到了。

练习赛手感很好,四题全部一Y。比赛前一天晚上九点就早早睡去。结果半夜三点就醒了。就兴奋的再也没睡着。然后在床上翻来覆去。一遍一遍的回忆比赛策略。直到现场赛开始。
比赛一开始我从后往前看,罗牛从前往后看。我一看J是一道暴力题。立刻上去写,不久就写好了,调了一会过了样例。马上交,结果返回WA.心中顿时一丝阴影,幸好陈乾马上发现关于除法的trick,改掉2Y.这时场上H过的人很多。BE也有人过。罗牛马上上去敲H,我
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

spoj

it

分类: 编程
SPOJ(YY牛),红色的表示还没有代码实现。
55 多边形求面积,用有向面积来求,最终的答案是多边形面积+点数/2+1。
56 栈模拟。
57 给定一个n排列,求存在于任意一个最长上升子序列的所有元素。思想是判断当前一个元素是存在于一个最长的上升子序列,判断方法是记录当前这个元素左边满足递减可以达到的最长,右边满足递增可以达到的最长,用树状数组优化,nlogn.
58 将时间结点离散化,然后枚举时间,枚举过程就就是一边进入一边出去,要注意的地方是人到底怎么进出的。
59 怎么处简便理树路径上的更新呢?
60 有很巧妙的解法,转化到分数,非常的神奇。此题解法用到了某些结论,用一个栈模拟,最后需要把S全去除,因为当竖直时,怎么交换都不会影响,还有如果有偶数个R可以消除。
61 如果把'('当做1,')'当做-1的话,那么只要所有从最左
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2010-09-08 16:02)

很有没有更新博客,也发生了许许多多的事情。做完纠结到晚上3点题,心情大好,于是更新一下博客。
据上次更新已经long long ago,条件反射般的,想typedef long long LL;
本来暑假要一心一意的训练,不巧申请香港浸会大学一波三折,一直到了快开学才基本尘埃落定,基本上还剩下程序上的部分要过一下,HKBU还希望我早些去香港,可是我的ACM梦还没有实现,做完最后一年ACM,也就不会有遗憾。现在看到队友开始忙碌申请保研的事情,我真诚的祝福他们,都可以到自己想要的学校去,

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

acm

题解

月赛

it

分类: 编程

比赛的名次是第六,第一名7道题,我们5道题.

就题目本身来说,做一个简要的思路回顾:

A是一个贪心,但是题目的精度给的太高,高到我认为标程都跑不出来的程度,最后我用低精度抱着试试的心态水过,这道题是出题人的失误.

B据说是一个数字图像上的比较经典的问题,一行一行搞的想法是比较容易想到的.但是明显当时比赛的时候用树状数组是繁琐了,像素点的取值在[0,255]之间,直接线性扫描一遍即可

C找到第一个比y大的数x,并且x的数位和等于y的数位和.直接从低位往高位枚举即可.F是一道类似的但是更为繁琐的一道数位统计题

 

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

acm

题解

月赛

it

分类: 编程
http://www.cppblog.com/puzzle/articles/110328.html

A.Amicable Pair
亲和数,先暴力算出数据,然后打表之。

B.A New Sequence Problem
先 YM一下AC。根据题目里的公式,先生成A数组。算A[0]需要通过fibonacci找循环节,找循环节的方法就直接暴力即可,当f[i]=f[1]& amp;&f[i-1]=f[0],i-1必是一个循环的长度。算出A数组以后,其实就是对于字符串的操作了。比赛的时候用后缀数组算出来了,但 是没想到O(n)的操作。赛后看到AC说是o(n)的DP,坚定复杂度后想到,在算出height数组后,用当前位置表示为最低位置,然后向左向右扩展到 第一个比当前位置低的地方,并bl[],br[]数组记录这个最左和最右,几乎就是o(n)的。


C.Coin Puzzle
给出一个多边形和两个圆,问两个圆能不能放在多边形里,并且两圆不相交。
求出两个

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
  

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

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

新浪公司 版权所有