算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
我擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦.....


最近真是忙成狗,要是这个节奏真是要跪啊。
真是对不起关注我博客的同学。
最近在忙什么呢?

1. 邢老师的项目
2. 选修课大作业
3. 同学的毕设
4. 找实习

真是牵扯精力。。。
其实说白了,还是时间分配有问题。。。

所以。。。 为了区域赛不坑队友。。。
哥决定!

坚持刷题写博客,以后的博文前面都写上【奋战2013regional】

大家监督!!!
posted @ 2013-05-05 14:14 西月弦 阅读(374) | 评论 (2)编辑 收藏
好像bzoj有些题是看不到 & 做不了的?
包括我以前做过的一些题。
听说得捐款或者出题,有没有知道详情的。。。
posted @ 2013-03-26 15:44 西月弦 阅读(437) | 评论 (1)编辑 收藏
     摘要: 我的名字叫韩飞,是哈工程的一枚弱菜... 10级....   阅读全文
posted @ 2012-04-23 14:44 西月弦 阅读(1236) | 评论 (11)编辑 收藏
距离去年狂刷题的日子已经过去一年了,一年来发生了很多,改变了很多。
是成熟了,还是老了呢。我不知道,不知不觉已经很少再刷题,不过还会坚持做定期的在线比赛。
可惜rating迟迟也上不去,雄心壮志也渐渐褪去。

额,还是来说这个比赛吧。。。去南京的途中没什么好说的,除了再一次做火车累得要死,和想到应该是最后一次做长途火车了,也没什么特别的感觉了。

比赛前一天晚上很紧张,两点多才睡着。。。 偷偷告诉自己,只要保持注意力集中,就能给力!

比赛开始,xy从头往后看题,孟神从后往前看题,我输入密码登录pc^2。这时xy已经告诉我A题是个水题了。。。
xy上去敲A,我再确认了一下A题的条件,然后提醒了xy一些细节。12min 1Y

这时发现J题已经有队伍提交了。孟神给我解释了一下题意,我想了一个贪心的做法。然后上去敲。
这时候直播的镜头ms拍到我了,当时我很紧张,表情比较纠结。。。 生怕交错了增加罚时。。。不过好在A了 = = 27min 1Y
然后,孟神给我讲了I题的做法,我感觉靠谱,然后就自己敲了。。。。 结果调样例各种不过,然后就把代码带出来扔给孟神了。

然后发现C是tiling问题,怒搞之。。。 然后样例也没过,各种调。。。。
后来孟神终于发现了I题的傻逼错误,74min 1Y.
紧接着我也发现了C题的bug,84min 1Y.

然后此时排名是第五,感觉很不错。
发现B有人A,和xy讨论了一个算法,上去敲,怒写二分,期间因为太紧张(智商低)衍生出来各种疑问,被xy拉下来了 = =...

然后xy 1WA = =... 我接着我那个敲,但是我也不能保证Yes。。。 但是ms可以避免一些精度问题,敲完了之后,测了一些数据,发现和xy的一样。。。更没底了

不过还是交了,出乎意料的yes ...152min 2Y

然后就是2个半小时,你看看我,我看看你,然后就结束了 = =... 最后银奖第四。。。
posted @ 2013-11-07 13:53 西月弦 阅读(381) | 评论 (0)编辑 收藏
0。Guass消元的方法
Guass消元可以求矩阵的秩,行列式,逆元,解方程组等等。
矩阵的值可以是整数 or 浮点数。
对于解方程组来说,x1 + x2 + ... mod m = b 用主列消元法,需要求逆元。
如果是浮点数,可以用迭代法(spfa),在姜碧野的论文里有讲。


1。利用Guass消元解决计数问题

这一类我掌握的不好,一般来讲是求方程组的解的个数。
当然应该只对 x1 + x2 + ... + xn mod m = b 这样的整数方程组有效了。
srm 590 div1 500就是典型的例子,在n个数中挑选一些数,让其xor值小于等于limit。
这个问题和等于是等价的。至于等于怎么求,就是方程组的解数了。和自由元的个数相关。

srm 590div1 500pt

2。开关问题

3。求期望

posted @ 2013-09-14 01:13 西月弦 阅读(286) | 评论 (0)编辑 收藏
我们知道,求解方程组的一般方法是高斯消元,时间复杂度为 O(n^3)。

如果求得解是实数的话,我们可以通过牺牲精度的方法来迭代求解。具体见2009年姜碧野的论文。

原理是这样的:
a11 * x1 + a12 * x2 + ... + a1n * xn = b1 可以变化成

x1 = 1/a11 * (b1 - a12 * x2 - a13 * x3 - .. a1n * xn);

如果x1 ... xn已经估计了一个值,那么通过上式进行进一步迭代就会得到更精确的解。
如果有解的话,最后一定是收敛的。
但是如果无解,或者有多个解,结果怎么样我就不知道了。。。。

这种方法叫做 jacobi 迭代法,复杂度O(k * n^2)。

缺点是后期收敛速度很慢。

有一种改进方法,叫做代数多重网格法(Algebraic Multi-Grid)。迭代过程中可以逐渐缩小大型矩阵的规模,使网格由细变粗。

具体细节有待钻研。
posted @ 2013-05-23 23:03 西月弦 阅读(343) | 评论 (0)编辑 收藏
     摘要: 这场比赛发挥的不错,rank 33,但是unrated。。。。 题目都很有意思,这里回忆一下  阅读全文
posted @ 2013-05-23 19:24 西月弦 阅读(595) | 评论 (0)编辑 收藏
总之,这场练习赛是有史以来做的最不好的。做了四个小时大家就草草收场总结了。

说实话确实是受心情影响了,而且还是学弟喷我。。。。 不过算了,清者自清,想踩我先努力到位再说!

比赛开始,xy看A题,孟神看最后一题,我看题目描述短的一题。
其实这样做不是很妥,因为A题和J题未必就很水,所以以后应该一个人负责一个区间,然后挑短的看!

A题是构造题,不难写10多分钟就1A了。

接下来G题也有若干人过,题意是求[0,n]中K进制和-K进制表示一样的数的个数。
孟神确认这样的数用K进制表示后,奇数位一定是0,数位DP可搞。

但是隐隐觉得数位DP有点大材小用,而且一开始这么多队过应该不难。
不过没细想,就敲了,交上去后WA。孟神上去对拍,xy给我讲H题。

H题是给你一个字符串,求所有可以经过重排列构成回文串的子串的个数,N是3e5。
隐隐觉得是不是CF某场出过。。。。 当时很冲动的想了一个DP,后来发现是错的,当时应该和xy确认一下就好了。。。。

G题对拍了写了很长时间,当时隐隐觉得节奏不对,可是也没别的题可敲(暴露出队内DPS不足的致命缺点,而且对拍应该是最后手段)。发现数位dp想错了一个很重要的地方,改了依然wa。这是隐隐觉得是long long的问题,但是暂时没有想到是哪里long long 用的不对,其实之间已经想出了sqrt(n)的构造算法,不过总觉得源程序改改就能过。。。。

期间H题我想到可以将52个字母的前缀和的奇偶hash成二进制,然后存到map中。多亏了省赛的H。。。。 不久敲完,wa了一发,发现了long long的问题,然后再交,TLE。
10^7次map操作已经超过了两秒,我之前一直没有意识到。。。。 这样一直卡着两题,xy确认了E的题意,觉的是贪心,和我确认了一发,我觉得靠谱,于是让他搞,我调两道题的错。

终于发现G题输入没用long long的sb错误,于是上去改之,AC。。。当时我还大吼了一下。。。。
H题改用hash代替map,wa了两发不明原因,后来发现是hash的插入过程写错了一点点。。。。

这暴露了另一个问题,队内的其他人看不懂我代码。。。 队内没有统一模板的习惯。。。。
E题xy说有反例,我说改成背包不是问题。但是要输出DP路径,状态是三维的,十分恶心。。。最后没有心情敲了。。。。

还是做题量偏少。。。。C题一开始觉得是二分答案,但是分数精度很难控制,后来发现可以贪心,随手交一发,wa,于是我敲E了。

让xy和孟神查错,不久他们举出了一个反例,于是我马上确认了这是斜率DP。。。。然后我当时很累了。。。于是就开会总结了。。。

目前主要有这么几个问题:
1. 卡题的时候查错效率太低。。。。队友不熟悉我代码,队内没有统一模板,盲目对拍。。。
2. 开题草率,依然是这个问题。 G题一开始用了麻烦做法,H没有正确估计时间,C题E题用了错误的贪心,没有去证明正确性。
3. 组队模式有缺陷,卡题逆风乏力,后期乏力。目前队内还是过于依赖我主敲代码,但是当我接连卡题的时候,节奏就全没有了,也缺乏足够的冷静。后期攻难题也依赖平均水平和队友的综合实力,这个需要慢慢磨合。
posted @ 2013-05-23 01:25 西月弦 阅读(782) | 评论 (3)编辑 收藏
由于昨天我的不冷静言行,无意伤害了很多人。现在我将一些不妥的言论删除,大家宽宏大量,不要在意!

我诚恳的向黑龙江所有ACMer致歉,无心之言,多加包涵!

也十分感谢"无"和“退役很久了”两位朋友对我的规劝,也感谢为我说话,替我着想的一些朋友,这些情谊鄙人有生难忘!

至于匿名恶意攻击我的人,咱们两不相欠!

最后祝愿所有ACMer都能实现自己的梦想!
posted @ 2013-05-21 23:28 西月弦 阅读(780) | 评论 (24)编辑 收藏
仅列出标题  下一页