[CodeChef FEB14]Graph Challenge解题报告(求半支配点)

题意 给一张有向图,使得从1开始按某种顺序DFS,可以让每个点的标号等于其DFS序号。求每个点的半支配点。 http://cogs.pro/cogs/problem/problem.php?pid=2117 题解 使用Lengauer Tarjan算法,对这一算法的描述和证明见我的上一篇博文: http://blog.csdn.net/wmdcstdio/article/details/49868 … 继续阅读“[CodeChef FEB14]Graph Challenge解题报告(求半支配点)”

在流程图中求支配点的一种快速算法

0.说明 本文译自Tarjan的论文: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf 选取了其中的一部分,有删改,以原文为准。 1.简介 在学习全局流分析和程序优化时,如下图论问题自然地浮现出来。设G(V,E,r)是一张流程图(本 … 继续阅读“在流程图中求支配点的一种快速算法”

[CodeChef OCT13]斐波那契数Fibonacci Number解题报告

题目 http://cogs.pro/cogs/problem/problem.php?pid=2114 分析 这道题是CodeChef上难得一见的优美数论题,比那些(净是中国人出的)丧心病狂的数据结构高到不知道哪里去了。 题目基于两个算法:第一个是Tonelli-Shanks算法,第二个是Shanks大步小步算法(这个Shanks是会玩的)。前者参见我的上一篇博文:http://blog.csd … 继续阅读“[CodeChef OCT13]斐波那契数Fibonacci Number解题报告”

Tonelli–Shanks算法

Tonelli-Shanks算法是一个求解二次平方根的算法。即,对于奇素数p,和p的一个二次剩余n,求解x^2≡n (mod p)这样的方程。“n是二次剩余”是什么意思呢?就是这个方程有解,如果没解,就叫“二次非剩余”…… 关于二次剩余,有一个叫“勒让德符号”(Legendre symbol)的玩意,它能判断对于奇素数p,a是否为p的二次剩余。懒得贴图片,把它写成L(a,p),其定义就是: L(a … 继续阅读“Tonelli–Shanks算法”

[CodeChef September Challenge 2012]Knight Moving(KNGHTMOV)题解翻译

首先,让我们忘掉答案可能会非常大,需要模10^9+7这一事实。我们将稍后考虑这一问题,讨论这将对解答造成何种影响。 问题分为两种情况。 情况1:A和B线性无关 由于A和B线性无关,我们可以对空间中的所有点,向由正交向量A和B确定的空间中做一线性映射。 这意味着我们可以将每个点(u,v)用(p,q)代替,使得: p*Ay + q*Bx = u p*Ay + q*By = v 如果终点(X,Y)无法转 … 继续阅读“[CodeChef September Challenge 2012]Knight Moving(KNGHTMOV)题解翻译”

星系模拟器开发日志(二) 各个组件

2015.8.13更新: 上一章中解决了基本的画图技术,现在就该写真正的程序组件了。 我们将程序分成四个组件: 1)物理学组件physical module,包含基础的物理学和数学工具。 2)场景组件scene,包含场景相关的定义和方法。 3)绘图组件plotting,包含绘图方法。 4)头文件constants.h,包含程序中可能用到的诸多常量。 先写物理学组件physical module.h … 继续阅读“星系模拟器开发日志(二) 各个组件”

星系模拟器开发日志(一) 如何科学地用C++画图

代码下载地址: http://pan.baidu.com/s/1eQjiETc 2015.8.11更新: 最近突然有一个想法:写一个程序,用来模拟太阳系的行星运动,甚至是任意星球的运动。感觉这个想法非常excited,所以就准备开始写。程序的名字就叫“星系模拟器”吧,或者也可以称作“拉普拉斯的长者?”,英文名Solar Simulator 为了避免写完后过一个月看不懂代码的悲剧重演,我准备把整个开 … 继续阅读“星系模拟器开发日志(一) 如何科学地用C++画图”

Farewell, OI!

听说写退役感言是传统,那我也写一个吧……   似乎很多OIer会对信息学竞赛怀有一种特殊的感情,我可能没那么强烈。NOI之后,我最主要的感受就一条:结束了,终于结束了。   初一最早听说有信息学竞赛的时候,我其实是拒绝的,因为当时我是一个搞数学竞赛的骚年……但还是抱着试一试的心态去了,结果就一发不可收拾,初中是OI数竞一块搞,高中就翘掉数竞全力搞OI,直到现在。   … 继续阅读“Farewell, OI!”