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

0.说明

本文译自Tarjan的论文:

选取了其中的一部分,有删改,以原文为准。

1.简介

在学习全局流分析和程序优化时,如下图论问题自然地浮现出来。设G(V,E,r)是一张流程图(本文中可以简单地代之以‘有向图’——译者注),以r为起点。我们称G中的节点v支配了另一个节点w,如果每一条从r到w的路径都包含了v。如果v支配w,并且w的其他支配点均支配v,我们就称v是w的最近[……]

继续阅读

[CodeChef FEB15]Payton numbers(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 – 5(a1b2 + b1a2) – (c1b2 + b1c2[……]

继续阅读

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

题目


分析

这道题是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++画图

代码下载地址:

2015.8.11更新:

最近突然有一个想法:写一个程序,用来模拟太阳系的行星运动,甚至是任意星球的运动。感觉这个想法非常excited,所以就准备开始写。程序的名字就叫“星系模拟器”吧,或者也可以称作“拉普拉斯的长者?”,英文名Solar Simulator

为了避免写完后过一个月看不懂代码的悲剧重演,我准备把整个开发过程都记在这里。

工具:
①一只NOIP选手
②一台电脑
③稍有的物理学常识

2015.8.13更新:

首先说一下思路。
①每个物体都是一个质点,只考虑万有引力
②先假设所有物体都在二[……]

继续阅读

Farewell, OI!

听说写退役感言是传统,那我也写一个吧……

 

似乎很多OIer会对信息学竞赛怀有一种特殊的感情,我可能没那么强烈。NOI之后,我最主要的感受就一条:结束了,终于结束了。

 

初一最早听说有信息学竞赛的时候,我其实是拒绝的,因为当时我是一个搞数学竞赛的骚年……但还是抱着试一试的心态去了,结果就一发不可收拾,初中是OI数竞一块搞,高中就翘掉数竞全力搞OI,直到现在。

 

我对于OI的记忆大致分两半:一半是浮躁,一半是干活。

 

浮躁的自然很爽。

初中被xwy、cjj、xys、sqh等一堆人带着打CS,NOIP前联机大家被专家BOT血虐,怒而上半自动狙+屏幕[……]

继续阅读

[USACO Open10]数三角形Triangle Counting解题报告

题目


分析

这道题的要点在于:含原点的三角形不好数,我们数不含原点的三角形,最后用C(N,3)扣掉它就是答案了。

怎么数“不含原点的三角形”呢?

画出我们所在的坐标系。我们拿一条过原点的直线l,按极角序去扫描:



直线l分成两条射线,一个是a,另一个是b。它绕着原点(Bessie所在点)旋转,请自行想象在孙悟空手中旋转的金箍棒。
(猴哥,猴哥,你真了不得……)

然后关键在于:每当射线a扫到一个点P时,我们统计P和直线l“左侧”所有点形成的三角形(严格地讲,是和a叉积为正[……]

继续阅读

[USACO Mar10]星牛争霸StarCowraft解题报告

题目


分析

首先可以发现,我们能够把三种单位的战斗力同时乘以一个数而不改变结果。因此,不妨设第三种单位的战斗力S3=1.出于方便,不妨记x=S1,y=S2

对于一场比赛,我们能够写出一个类似这样的式子:

j1x+j2y+j3=)

整理后得到一个类似这样的式子:

ax+by[……]

继续阅读