DO NOT OVERLOAD!

UPD 20160326:
完善最少时间功能;
修复安卓上不能响应的bug。
BEAT 2016: http://www.ultechnet.com/dno/

UPD 20160320:
修正了完不成的bug。
补充了一个计时功能。真的变成竞技了。。。
BEAT 2016: http://www.ultechnet.com/dno/

UPD 20160319:
一个Javascript脚本小练习。开赛车似的。不要越界了哦。其实还是很有难度的样子。
不排除有bug。反正脚本公开,欢迎指正。
BEAT 2016: http://www.ultechnet.com/dno/

对拍模拟器想法和初步实现

Updated Feb. 18, 2016

更新一个注解:此模拟器用于普通OI(ACM等)测试。运行在Windows环境下。使用时,请确认已将g++目录添加到系统环境变量下。(自行Google)

Updated Feb. 17, 2016

用C#写了一个对拍模拟器。主要就是说要求用户输入数据生成器,标程(暴力)和待测,然后程序会开始运行输出结果。Bug众多,未实现功能众多,堪称不忍直视。
我想重点是以下几个功能还没有落实:
1. 无法判断是TLE还是WA。卡时间有的时候会卡不掉。
2. 用户体验非常差,经常会莫名其妙地卡死。
3. 出结果很慢。
4. 如果随机生成器用了srand((unsigned)time(NULL))之类的SB算法,那么你加500个测试点结果还得是一样的。:(
5. Among other things…
v0.8 C# Source Code: Checker

OI复习:动态规划 (u0721)

动态规划适用条件

最优化原理(最优子结构性质)

一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

无后效性

将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。

子问题的重叠性

动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。

第一类动规:线性动规

最简单的一类动规。一位数组,简单略过。

经典问题:最长单调子序列。状态转移方程:dp[i] = max { 1, dp[j] + 1 for j < i AND a[j] <= a[i] }

第二类动规:区域动规

以石子合并为例:有N堆石子要将石子有序的合并成一堆,每次只能移动相邻的2堆石子合并,合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小。

特点为要用到二维数组。状态转移方程:dp[i][j] = min { dp[i][k] + dp[k + 1][j] + sum[i][j] },注意处理边界情况,可做前缀和优化。

难度总体并不大。

第三类动规:树形动规

某公司要举办一次晚会,但是为了使得晚会的气氛更加活跃,每个参加晚会的人都不希望在晚会中见到他的直接上司。求最大活跃指数。(见POJ2342)

可以用可以用f[i,1]和f[i,0]表示第i个人来和不来。j为i的下属,当i来的时候,dp[i][1] += dp[j][0];当i不来的时候,dp[i][0] += max(dp[j][1], dp[j][0])。

此类动规,难度相对要大一点。

第四类动规:背包问题

可以参考背包问题九讲。

第一类:01背包,每种物品只有一件,可以选择放或者不放。转移方程:f[i][v] = max(f[i – 1][v], f[i – 1][v – weight[i]] + cost[i])。由于更新V的状态是对V之后的状态是没有影响的,可以优化空间:f[v] = max{f[v], f[v – weight[i]] + cost[i]},不过循环要从后往前做。

第二类:完全背包,每种物品有无限件。可采用上述的转移方程:f[v] = max{f[v], f[v – weight[i]] + cost[i]},把循环从前往后做就可以了。也可以这样:f[i][v] = max{f[i-1][v], f[i][v – w[i]] + c[i]},注意是i,不是i – 1。

常用的一般也就这两种,当然国家级联赛或是什么的另当别论。

POJ习题集

这里主要推荐一些题并谈一些感想,题解请查询网络。

1015:挺烦的,不过可以直接开三位数组,也就十几M内存,问题不大。注意数组偏移和边界、输出处理。

1018:不难,但是搞了好久。关键在于要把问题想清楚再做。

1141:经典题,略过。

1191:一边看题解一边做题,其实也还好。

1390:很难很烦。参考题解慢慢钻研吧。

1463:如果DP内部写得好,即使数据结构不优化也能飘过。网上的题解很烦,其实跟标准的树形DP还是很相近的,只不过这回员工跟上司至少有一人出席。

1636:并查集加背包。貌似不是很难,但是数组开小了,RE到死。

1671:Special Judge貌似有问题。难点不在DP,在于输出处理。网上看看资料就好了。

1682:有难度,不看题解不会做。不过看了题解嘛,也就这样。

1692:难度还好,要稍微思考一下。优化空间比较大。

1717:似乎和1015很像,不过是简化版?滚动数组,细节注意。

1722:背包变形,要有一点正负号Ad hoc技巧,提交g++就AC了,C++就WA。解释一下?

1947:树形DP,参考参考题解。要自己做的话还是有点难的。(虽然AC了总感觉有点问题。)

2342:你见过这么标准的树形DP?飘过。

3342:加强版2342,小心点,1A。

(暂告一段落)

热水瓶的Dilemma

有一个热水瓶,容量为2L,每天将瓶中的水完全倒去后,在灌入新的水。由于热水瓶设计的原因,有5mL的水无法倒去,但这并不影响热水瓶中的水完全混合。

(1) 求某一水分子在热水瓶中停留的时间的期望。
(2) 假设有一天灌入的水因为某种神秘力量在灌入之前已经被污染(并不改变水的相对分子质量),如一切照常,需要多少天才能基本排尽这些被污染的水。(残余水分子数量的期望小于1视为基本排尽)。

提供数据:\rho=1.0\times10^3 kg/m^3N_A=6.02*10^{23} mol^{-1}

题解:

(1) 设停留时间的随机变量为X,则有
P(X>i)=(\displaystyle\frac{5}{2000})^i,因此
E(X)=\displaystyle\sum_{i=0}^{\infty}P(X>i)=1+\frac{5}{2000}+(\frac{5}{2000})^2+\cdots=\frac{399}{400}

(2) 设经过x天后某一水分子停留下来的概率为p,则p=(\displaystyle\frac{5}{2000})^x
则若水分子总数为N,剩余分子数期望为E=(\displaystyle\frac{5}{2000})^x\times{N}
N=2\times10^3\div18\times6.02*10^{23},此时,令E<=1,解得E的最小值为10。

注:题解可能存在漏洞甚至错误,烦请各位指点一二。

简陋的圆锥曲线弦长计算器

先放链接:http://www.ultechnet.com/math/conic_section_length.php

一个php的小玩意儿,主要目标是使你在得到八分之根号两千四百七十这种答案的时候可以有一个参考。结论不确保正确——但还是烦请得到结论错误的同学们勇于指出,方便进一步改进。

到目前为止只支持中心在原点,焦点在坐标轴上的圆锥曲线(不要问为什么,目前貌似只考这个),只支持斜截式直线(也不要问为什么)。

另外,在技术上,比较tricky的地方是让用户输平方,避免根式处理,呵呵。核心算法并不困难,联立椭圆和直线方程,用弦长公式Sqrt(k^2+1)*Sqrt(delta)/Abs(a)。代入过程,不得不说,相当的复杂。(本人曾经推过不带分子分母的弦长公式,推了半天,发现该公式根本记不住,只好作罢。)今天这件事情就交给Mathematica代劳啦~哈哈哈。。。忍不住放出公式,其实是这样子滴:。。

分子$ans1 = 4*$a1*$b1*($k1+$k2)*($a1*$b2*$k1*$m2+$a2*$b1*$k2*$m2-$a2*$b2*$k2*$m1);
分母$ans2 = pow(($a1*$b2*$k1+$a2*$b1*$k2),2)*$m2;
(其中a1,a2分别是a^2的分子和分母,依次类推。)

另外其实最大的难点倒是在RootReduce上面,就是将根号192化成8根号3。目前用的是暴力算法,即一个for循环点滴到天明。问题其实不大,因为数据规模不大。所以解决问题的关键在于:进一步严格压制数据规模!

差不多结束了。谢谢观赏。

神奇的Tetris,1.0beta

是不是有点失望?这么老的游戏。。。。不过这可是妥妥的MouseOff Game哦,所谓MouseOff Games就是说,不用鼠标也能玩。。。(不用鼠标能不能正确打开还有待考证。)

娱乐娱乐,娱乐娱乐。暂时将其归入Team Alpha类(貌似也没有别的地方可以去了),看在Alpha的好几个项目要么搁浅要么烂尾的份上。

2015年2月22日下载地址:http://www.ultechnet.com/mouseoff/tetris/Tetris.1.0.beta.20150222.zip

(此链接将在有新的beta出现后被替换,在有正式版出现后失效,不过看上去正式版还遥遥无期)

运行库还是比较大的。以后有空提出来,这样就不用每次都是十几M的恶心了。。。

代码写了一堆,bug更是一堆。在文件夹包里,有一个Tetris(这是肯定的),俄罗斯方块当前限于技术条件还没有中文支持。不过还有一个提交反馈,用该程序可以快捷地提交问题和建议。有其他问题的也可以通过回复的形式,在下面跟上。

需要源代码的留邮箱,有打满5000分(就3000分吧,我承认3000也很难)的可以炫耀一下。(不过貌似一旦Game Over就没办法截图了)

各位有何高见,请尽管提上。よろしく お愿いします。

— Feb. 22, 2015 —