CheckAC 在Chrome WebStore 上架

2013年暑假集训,我们(@yangz @alwa)发现了一个小众的需求,即在OJ上做题的时候不能确定一道题自己有没有过掉,尤其是在查看别人的提交记录的时候。

下载地址:CheckAC

Github(欢迎提交意见,代码更好):CheckAC

还有,不知道为什么,我们的集训队一直比较关心一个人的过题数量,于是乎我们都在乎了。

(说来惭愧,暑假之后几乎没怎么搞算法,全都是搞应用了,最近虽然考试多,还是要多刷刷题了,太少了看不过去)

于是,我们就决定开发一款Chrome 的扩展程序(插件),能辅助我们在OJ上做题,想法很好,说干就干。

开发速度简直快的惊人(凭记忆):

2013-7-19 14:00 ~ 2013-7-21  2:40 :

36小时速成0.1版,可惜当时还不会用Github ,没有记录下开发过程

  • 当天自学了如何制作插件
  • 当天晚上搞出了可以在POJ网站上抓取过题数量和通过题目列表的正则表达式
  • 学习了一个东西叫XMLHttpRequest ,知道了这东西能在插件里异步访问Web,后来知道了一个东西叫Ajax
  • 学习了一个叫localStorge的本地存储方法作为插件的存储
  • Chrome 插件有个东西叫ContentScript,能在目标网页中运行,能完成打钩的功能
  • Chrome 插件有个BackGroundPage 通过它我才能读取插件能访问的localStorge 并和ContentScript通信,来告诉ContentScript 那些题目我已经AC
  • 用Photoshop 画了个LOGO
  • 21日凌晨抄袭了”印象笔记剪藏”的CSS样式,然后完成了0.1版

不过这个东西的功能仅限于抓AC列表,点插件输入个POJ题号能用绿色和红色表示你题目有没有AC,发下21日凌晨怀着激动的心情在集训队内部论坛发布时的截图:

CheckAC Alpha 屏幕截图

之后的几天:

  • 听说有个东西叫BootStrap 是个前端框架,用上之后果然非常好使,用它写了Setting 和 popup页面
  • 听说有个东西叫Jquery,是个JS库,用上之后果然非常好使
  • 搞定了ZOJ 的题目抓取功能
  • 学了一个东西叫JSON,能序列化对象,终于不用我人工定义localStorge中字符串的格式了
  • ACM-ICPC信息站找了个近期比赛的JSON源,在此表示感谢

现在,CheckAC 已经有了关注他人,ToDoList 等功能。欢迎大家使用。

为什么现在才上架呢?因为Google WebStore开发者账户要用$5验证,要有信用卡,而且不能是中国大陆的。于是鼓动我父亲给我办了张卡,拿到卡之后非常顺利,2小时就完成了从开发者账户验证到上架的过程,在此也给想在ChromeWebStore上架的朋友说一下我的操作。

  1. 招商银行美国运通(AmericaExpress)双币信用卡
  2. Goagent+Chrome隐身模式登陆Google账号
  3. 填写的是香港地址
  4. 中国正常手机号码

迁移至新域名(comzyh.com)啦

今天下午tk域名解析莫名其妙不正常,感觉tk这个小岛国还是有点不靠谱,于是乎迁移至com域名.

目前301重定向什么的都弄好了,就等Google收录了.用以前的tk域名还能够继续访问,会自动跳转过去的.

正好也试试Word2013直接用Xmlrpc发布文章的功能.

感谢大家支持J

等比数列求和的二分法

常见问题:给定整数M,等比数列\{{a_n}\},求其前n项和对M的模

朴素的想法,我们可以用等比数列求和公式S_n=\frac {a_1(1-q^n)}{1-q}求得和再模除M,但是计算过程中取模导致分母下面的1-q不能直接除,要求1-q的乘法逆元;

这里介绍另一种思路,就是使用二分的思想,很像矩阵快速幂
首先,我们先讨论一个简单的问题:
a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8的和
提取公因式,我们能把原式变为
(a^1+a^2+a^3+a^4)(1+a^4)
进一步变换为(a^1+a^2)(1+a^2)(1+a^4)
=a(a+a^1)(1+a^2)(1+a^4)
我们把这种等比数列前2^k项和记为S(k)有递推式S(k)=S(k-1)(1+a^{2^{k-1}})
这是二分法的关键,也就是说我们能在log(n)的时间内求出等比数列前2^k项的和

当我们要求的不是前2的整数次幂的时候,我们将n分解为2的整次幂的和:
比如求前等比数列11项的和,我们将11(二进制表示:1011)分解为1+2+8(二进制表示1+10+1000)
前11项的和可以表示为:
(a^1)+(a^2+a^3)+(a^4+a^5+a^6+a^7+a^8+a^9+a^{10}+a^{11})
可进一步表示为
a^0(a^1)+a^1(a^1+a^2)+a^3(a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8)
即:a^0S(0)+a^1S(1)+a^3S(3)
Well done!我们又把原式分解成了多个a^xS(y)的和
Continue reading

选取第K大数的快速选择算法和注意事项

快速选择算法,是一种能在大致O(N)的时间内选取数组中第k大或者k小的算法.其基本思路与快速排序算法类似,也是分治的思想.

其实这个算法是个基础算法,但是不常用,所以今天编的时候错了POJ2388,才有了这篇文章.

  1. 执行Partition算法(就是那个快排里将区间内所有数划分为小的一部分和大的一部分的过程)
  2. 判断第k大的数是在小的部分还是大的部分
  3. 递归,直到区间足够小,返回结果

Continue reading

域名删除记录

据监测 ,北京时间2011-6-3 日17时左右,我的域名被注销,鬼知道为什么
为防止域名注册机构再来抓住我神马把柄,本文不用中文
2010-6-8 又注销一次,并且禁止注册。经过我邮件咨询,又恢复一次,客服态度还好,没有纠缠

网络流入门—用于最大流的Dinic算法

“网络流博大精深”—sideman语

Drainage Ditches
一个基本的网络流问题

感谢WHD的大力支持

最早知道网络流的内容便是最大流问题,最大流问题很好理解:

解释一定要通俗!

如右图所示,有一个管道系统,节点{1,2,3,4},有向管道{A,B,C,D,E},即有向图一张. [1]是源点,有无限的水量,[4]是汇点,管道容量如图所示.试问[4]点最大可接收的水的流量?

这便是简单的最大流问题,显然[4]点的最大流量为50

死理性派请注意:流量是单位时间内的,总可以了吧!

然而对于复杂图的最大流方法是什么呢,有EK,Dinic,SAP,etc.下面介绍Dinic算法(看代码的直接点这)
Continue reading

明天NOIP了 该睡觉了

明天该NOIP了,在宾馆写Blog别有一番风味,以后或许就不能更新Blog了,这种失落简直是难熬的
RP++\\RP=100^{100^{100}}
如果时间 OI之路就此中止,还是有些遗憾的.据说下个月父母把网断了,希望本文不会是绝唱.这段真的很带劲,很带劲,就目前看来,继续OI的唯一途径很渺茫—省队,再议吧.
希望Comzyh留下的些许文章对你有帮助.

感谢诸位神牛们:applepi(billdu),sideman,whd,gczsjdy1994  etc.

迄今为止,
来访者562
访问数1888 很吉利吧
没办法,小博客

Can I help you ??

POJ 2186 & 1236 强连通分量 Tarjan算法

先给链接POJ 2186 Popular Cows ,POJ 1236 Network of Schools
这两道题都是经典的强连通分量问题,本人都采用了伟大的SCC Tarjan算法.
关于SCC Tarjan算法 可以参见本博的处理SCC(强连通分量问题)的Tarjan算法

先说POJ 2186 Popular Cows

(不看这题,直接跳到1236的题解)
题意:每个Cow都梦想成为牛群里最知名的奶牛,在一个有N(1 <= N <= 10,000) 头牛的牛群里,给出最多M(1 <= M <= 50,000) 个数对(A,B)告诉你A认为B是有名的,并且名气可以传递,若果A认为B有名,B认为C有名,则A也会认为C有名,即使在输入的数对中没有给出这段关系,你的任务是计算出被所有牛认为是有名的牛的个数.

引用另一位仁兄Headacher的题解中的一部分(参见PKU POJ 2186 Popular Cows 强连通分量 ),讲的很好,很精辟

算法证明:

1:假设a和b都是最受欢迎的cow,那么,a欢迎b,而且b欢迎a,于是,a和b是属于同一个连通分量内的点,所有,问题的解集构成一个强连通分量。

2:如果某个强连通分量内的点a到强连通分量外的点b有通路,因为b和a不是同一个强连通分量内的点,所以b到a一定没有通路,那么a不被b欢迎,于是a所在的连通分量一定不是解集的那个连通分量。

3:如果存在两个独立的强连通分量a和b,那么a内的点和b内的点一定不能互相到达,那么,无论是a还是b都不是解集的那个连通分量,问题保证无解。

4:如果图非连通,那么,至少存在两个独立的连通分量,问题一定无解。

这样我们便的得到了初步的解决方案

  1. 用Tarjan算法求出强连通分量,设立Belong数组,用并查集将在同一强连通分量的节点并在一起.
  2. 建树,遍历所有输入中的点对(A,B)如果AB分属两个不同的强连通分量,则belong[B]是belong[A]的父节点
  3. 显然,如果点对(A,B),A所在的强连通分量(用并查集指定,getf(A))指向的元素和”A指向的强连通分量“不属于同一强连通分量,则不构成树结构,无解.
  4. 遍历所有强连通分量,如果存在一个强连通分量指向自己,则它是最著名的强连通分量
  5. 遍历所有节点,如果属于答案强连通分量,计数器累加,最后输出答案

本人的代码很丑,用的前向星,第一次写前向星,被yxc同志指为”光建图排序就要N\log (N)“所以用的计数排序,建图部分是为了前向星而前向星,直接无视即可
Continue reading

第 1 页,共 3 页123