C++博客-算法学社

[奋战2013regional] 南京赛区总结

西月弦 — Thu, 07 Nov 2013 05:53:00 GMT

距离去年狂刷题的日子已经过去一年了，一年来发生了很多，改变了很多。
是成熟了，还是老了呢。我不知道，不知不觉已经很少再刷题，不过还会坚持做定期的在线比赛。
可惜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个半小时，你看看我，我看看你，然后就结束了 = =... 最后银奖第四。。。

西月弦 2013-11-07 13:53 发表评论

【奋战2013regional】Guass消元的一些应用（坑）

西月弦 — Fri, 13 Sep 2013 17:13:00 GMT

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。求期望

西月弦 2013-09-14 01:13 发表评论

【奋战2013regional】 2013东北赛总结

西月弦 — Sun, 09 Jun 2013 16:59:00 GMT

摘要: 阅读全文

西月弦 2013-06-10 00:59 发表评论

【奋战2013regional】【和小学弟一起刷题】topcoder 477 div1 待续。。。

西月弦 — Fri, 31 May 2013 17:09:00 GMT

摘要: topcoder 577 阅读全文

西月弦 2013-06-01 01:09 发表评论

【奋战2013regional】【和小学弟一起刷题】codeforces #186 div2

西月弦 — Fri, 31 May 2013 12:48:00 GMT

摘要: 阅读全文

西月弦 2013-05-31 20:48 发表评论

【奋战2013regional】老骥伏枥，志在千里 --- 通化邀请赛总结

西月弦 — Mon, 27 May 2013 16:53:00 GMT

摘要: 。。。阅读全文

西月弦 2013-05-28 00:53 发表评论

【奋战2013regional】迭代法求解方程组

西月弦 — Thu, 23 May 2013 15:03:00 GMT

我们知道，求解方程组的一般方法是高斯消元，时间复杂度为 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）。迭代过程中可以逐渐缩小大型矩阵的规模，使网格由细变粗。

具体细节有待钻研。

西月弦 2013-05-23 23:03 发表评论

【奋战2013regional】【和小学弟一起刷题】codeforces #182 div1 【坑】

西月弦 — Thu, 23 May 2013 11:24:00 GMT

摘要: 这场比赛发挥的不错，rank 33，但是unrated。。。。题目都很有意思，这里回忆一下阅读全文

西月弦 2013-05-23 19:24 发表评论

【奋战2013regional】【和小学弟一起刷题】NEERC 2012 练习赛总结【坑】

西月弦 — Wed, 22 May 2013 17:25:00 GMT

总之，这场练习赛是有史以来做的最不好的。做了四个小时大家就草草收场总结了。

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

比赛开始，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. 组队模式有缺陷，卡题逆风乏力，后期乏力。目前队内还是过于依赖我主敲代码，但是当我接连卡题的时候，节奏就全没有了，也缺乏足够的冷静。后期攻难题也依赖平均水平和队友的综合实力，这个需要慢慢磨合。

西月弦 2013-05-23 01:25 发表评论

致歉

西月弦 — Tue, 21 May 2013 15:28:00 GMT

由于昨天我的不冷静言行，无意伤害了很多人。现在我将一些不妥的言论删除，大家宽宏大量，不要在意！

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

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

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

最后祝愿所有ACMer都能实现自己的梦想！

西月弦 2013-05-21 23:28 发表评论

C++博客-算法学社

[奋战2013regional] 南京赛区总结

【奋战2013regional】Guass消元的一些应用（坑）

【奋战2013regional】 2013东北赛总结

【奋战2013regional】 【和小学弟一起刷题】topcoder 477 div1 待续。。。

【奋战2013regional】 【和小学弟一起刷题】codeforces #186 div2

【奋战2013regional】 老骥伏枥，志在千里 --- 通化邀请赛总结

【奋战2013regional】 迭代法求解方程组

【奋战2013regional】 【和小学弟一起刷题】codeforces #182 div1 【坑】