[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/49868575 当然本题只需要求半支配点。 首先按照适当顺序DFS,还原题目描述中所称的DFS生成树。然后直接套算法。 代码如下,思路很简单。要点都写在注释中了。 #include #inc... 查看更多

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

0.说明 本文译自Tarjan的论文: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf 选取了其中的一部分,有删改,以原文为准。 1.简介 在学习全局流分析和程序优化时,如下图论问题自然地浮现出来。设G(V,E,r)是一张流程图(本文中可以简单地代之以‘有向图’——译者注),以r为起点。我们称G中的节点v支配了另一个节点w,如果每一条从r到w的路径都包含了v。如果v支配w,并且w的其他支配点均支配v,我们就称v是w的最近... 查看更多

[CodeChef FEB15]Payton numbers(CUSTPRIM)解题报告

题目 https://www.codechef.com/problems/CUSTPRIM (翻译来自洪华敦) 定义三元组的乘法 def multiply((a1,b1,c1), (a2,b2,c2)): s = (a1a2 + b1b2 + c1c2) + (a1b2 + b1a2) + (c1 + c2) t = floor[s/2] + 16(c1 + c2) – c1c2 A = (t – 2(a1b2 + b1a2) – (a1c2 + c1a2) + 33(a1 + a2)+ (b1b2 – a1a2)) B = (t –... 查看更多

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

题目 http://cogs.pro/cogs/problem/problem.php?pid=2114 分析 这道题是CodeChef上难得一见的优美数论题,比那些(净是中国人出的)丧心病狂的数据结构高到不知道哪里去了。 题目基于两个算法:第一个是Tonelli-Shanks算法,第二个是Shanks大步小步算法(这个Shanks是会玩的)。前者参见我的上一篇博文:http://blog.csdn.net/wmdcstdio/article/details/49862189,后者资料众多,不再赘述。 Tonelli-Shanks算法是一个“开根号”的算法。即,给出奇素数p和某个a,... 查看更多

Tonelli–Shanks算法

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

[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)无法转换成整点(x’,y’),那么即使不考虑障碍,合法的方案数也是0。 如果某个障碍点无法转换成整点(p,q),那么该障碍点永不可能到达,可以直接忽略。 现在,我们得到了... 查看更多

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

2015.8.13更新: 上一章中解决了基本的画图技术,现在就该写真正的程序组件了。 我们将程序分成四个组件: 1)物理学组件physical module,包含基础的物理学和数学工具。 2)场景组件scene,包含场景相关的定义和方法。 3)绘图组件plotting,包含绘图方法。 4)头文件constants.h,包含程序中可能用到的诸多常量。 先写物理学组件physical module.h/cpp。 出于显然的原因,所有值均按国际单位制。 物理学组件包含: ①坐标类Vec3,成员是x,y,z三个坐标,均为float。Vec3这个名字沿用自OpenGL... 查看更多

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

代码下载地址: http://pan.baidu.com/s/1eQjiETc 2015.8.11更新: 最近突然有一个想法:写一个程序,用来模拟太阳系的行星运动,甚至是任意星球的运动。感觉这个想法非常excited,所以就准备开始写。程序的名字就叫“星系模拟器”吧,或者也可以称作“拉普拉斯的长者?”,英文名Solar Simulator 为了避免写完后过一个月看不懂代码的悲剧重演,我准备把整个开发过程都记在这里。 工具: ①一只NOIP选手 ②一台电脑 ③稍有的物理学常识 2015.8.13更新: 首先说一下思路。 ①每个物体都是一个质点,只考虑万有引力 ②先假设所有物体都在二... 查看更多

Farewell, OI!

听说写退役感言是传统,那我也写一个吧……   似乎很多OIer会对信息学竞赛怀有一种特殊的感情,我可能没那么强烈。NOI之后,我最主要的感受就一条:结束了,终于结束了。   初一最早听说有信息学竞赛的时候,我其实是拒绝的,因为当时我是一个搞数学竞赛的骚年……但还是抱着试一试的心态去了,结果就一发不可收拾,初中是OI数竞一块搞,高中就翘掉数竞全力搞OI,直到现在。   我对于OI的记忆大致分两半:一半是浮躁,一半是干活。   浮躁的自然很爽。 初中被xwy、cjj、xys、sqh等一堆人带着打CS,NOIP前联机大家被专家BOT血虐,怒而上半自动狙+屏幕... 查看更多