WC2017 Day2

基于物理的信息学竞赛知识

0x00 用处？

模拟这个世界
物理引擎
工程学
OI！

0x01 Overview

基础物理模拟
Signed Distance Function（如何处理物理边界）
State of the arts

0x02 高中数学/物理

导数
牛顿三定律
胡克定律（弹簧）
万有引力定律

1.你有一个装置，能在高度h处射出初速度为v的子弹，问子弹在初速度方向运动距离

高中物理题，解显而易见
如果考虑空气阻力？空气阻力正比于速度的平方？三次方？

很难找到解析解，只能一帧一帧模拟，取数值解

//主循环基本结构
t=0,dt=0.001; //dt越小模拟越精确，但是耗时越长
while(t<T){
    velocity+=dtforce/mass; //v+=dtf/m
    position+=dt*velocity;
    t+=dt;
}

2.两个球被理想弹簧连接，给出弹簧的k和l，球的初始位置与初始速度，求一段时间后两个球的位置

同样可以使用模拟的方法解决

//考虑这种主循环
t=0,dt=0.001;
while(t<T){
    velocity2=velocity+dtforce/mass;
    position+=dtvelocity;
    velocity=velocity2;
    t+=dt;
}

同时更新速度和位置，但都用更新前的速度和位置去更新
这种方法被称为前向欧拉法，这种方法在数值上不稳定，不满足能量守恒
考虑一个简单太阳系模型，只有地球和太阳，前向欧拉法会导致地球不断远离太阳
具体原因可以用特征值和特征向量解释，特征值大于1，特征向量在多次模拟后就爆炸了。在此按下不表

后向欧拉法呢？

同时更新速度和位置，但都用更新后的速度和位置去更新
看上去好像也不守恒，会把地球向太阳推一点
特征值都小于1，特征向量多次模拟后会收敛成0，起码收敛了
这和有空气阻力的时候很像啊？
这给我们一些启示，似乎可以尝试在前向欧拉法里加一些空气阻力来使系统稳定

都不精确，怎么办？

根本原因是机械能不守恒
有时Eular-Crom会好使，就是我在第一个主循环里写的那个
RK2算法
想法很显然，我们取dt一半处的速度更新位置
比较精确

3.模拟一堆球被弹簧连接？

和两个球的情况类似
被称为弹簧——质点系统

4.模拟一块布？

把布剖分成三角形网格

5.模拟一个果冻？

四面体剖分，我们期望最后网格中都是三角形

dt与稳定性与精度

显然dt越小，稳定性和精度越好
稳定未必精确：后向欧拉无条件稳定
精确未必稳定：同理，RK2精确但没有后向欧拉稳定
关系很复杂

0x03 Signed Distance Field/Function(SDF 有符号距离场)

三维生物小明站在(x,y,z)，在每个点(ia,jb,k*c)上有一个直径r（r<a,b,c）的气球

小明随便乱扔飞镖，求打中气球的概率，精确到1%

精度要求很低，考虑随机一些方向，如何快速判断能否击中气球？

SDF

给定一个点集S
一个点x到S的距离定义为x到S中所有点距离的最小值
如果这个S将平面划分为两部分，定义S内部的点到S距离为负，外部的点到S距离为正
此即为SDF
单位圆的SDF？$ sqrt{x^2+y2}-1 $
矩形的SDF？请有兴趣的读者自行证明。
如何形成两个图形的并的SDF？两个图形SDF取个min？
好像不太行，虽然图形的并外面是对的，但是里面不对。不过符号都是对的。
如何形成两个图形的交的SDF？两个图形SDF取个max？
好像也不太行，这次图形的交里面都是对的，但是外面不对了。

SDB

定义Signed Distance Bound(SDB)
SDB与SDF同号
要求|SDB|<=|SDF|
其实SDB就是SDF的lower_bound
SDB可以直接用min和max取并和交
这里的min和max都是绝对值以后！

SDB减法

$ A-B=Acup complement{B} $
如何取补集？直接符号取反

用一个正方形的SDF构造很多正方形的SDF？

1.这些正方形中心都在x轴上，边与坐标轴平行且位似
定义 a Cmod b = $ a-b*left lfloor frac{a}{b}+0.5 ight floor $
SDF'(x,y)=SDF(x Cmod a,y)
2.这些正方形绕一个点旋转对称
把极角Cmod一下
这个叫Space Folding
解决方法实质是把所有点映射到一个正方形上

SDF有什么用？

Collision Detection（防穿发补丁？）
把这个碰撞粒子推出碰撞物体，关键在于方向和距离。
方向？SDF的法向量，中心差分，前向欧拉搞一搞
距离？-SDF

射出一个子弹，问什么时候会撞到SDF表示的边界？

这类问题被称作Ray Marching
每次至少可以前进SDF(当前位置)距离
设置一个eps
复杂度是O(可过)，可以卡但一般没人卡
括弧，SDB也可以Ray Marching，一般是用SDB做，因为SDF不好求

回到气球的问题

对气球搞SDF，配合Space Folding
然后Ray Marching

三维生物小红站在(x,y,z)手持一个皮球

提供一个函数d(x,y,z)，返回点(x,y,z)距离边界的距离

有Q个询问，给出初速度和方向

保证边界曲率不会很大，每时每刻运行方向与边界夹角不小于10°，忽略引力，球与边界完美弹性碰撞，输出3次碰撞后的运行方向

分析问题

Collision Detection？把SDF缩小球的半径，这样球就等价于点了。
如何求碰撞平面的法向量？中心差分。
如何求反弹后的速度？原速度向量对法向量反射
为什么最多反弹三次？为什么曲率不大？为什么夹角不能太小？为了减小误差。

终极问题

给出一些星体，模拟它们的运动

全裸：$ O(Tn^2) $
Barnes-Hut Tree Code
把较远的一些点合并成一个质点

0x04 前沿应用

如何模拟水

表现成一堆粒子/场
有很多方法Eulerian V.S. Lagrangian
两个特点：质量守恒（粒子化）和不可压缩性（压强场）

如何模拟刚体

碰撞处理

可并行算法与分布式编程

杜教啊orz

杜教好像没怎么准备好

0x00 OI中的常见并行算法

Bitset（详见2014年沈洋论文）
排序网络（详见2016年金策论文）
通过所有的01序列测试可以判断一个网络是否是排序网络
在许多排序相关问题中只要考虑01序列就可解决

0x01 分布式编程

什么是分布式编程？

你有n台计算机（n一般为100）
你要使用这n台计算机共同完成一些任务
计算机节点之间可以互相通信，但是通信的代价比较高昂，需要将许多信息放在一起传输
可以使用库在本机搭起一个分布式环境

分解一个$ 10^18 $那么大的数的质因数？

分段检验

素数筛？

思想类似

卷积？

FFT每一步本来就是并行的

排序？

随机选一小部分，排序
剩下的大部分按照小部分排序结果分到各个节点上，分别排序并合并

$ 10^9 $个数，有一个数出现的次数了超过一半，找出那个数？

每个节点处理$ 10^7 $个数，维护一个出现次数最多的计数器

$ 3.5*10^8 $ 个数，求最小的只出现过一次的数？

（留给有兴趣的读者自行思考

哈希以后再发
排序
都行

RMQ?

ST表每一层可以并行
建线段树也可以并行
询问怎么办？
实质上每个询问需要查询$ log_2{n} $个值
线段树上的值哈希打乱丢到M个节点里

逆序对？

划分成$ sqrt{M} $段，两两求逆序对
能不能把$ nlog_2{n} $的做法除个M？
2k次二分出归并过程中长为k的两段中的第l大数
注意所有2k次二分可以并行进行

字符串匹配？

哈希可搞
KMP不太可搞

后缀数组？

也能并行，但需要传输的信息太多，要$ nlog_2{n} $

求回文子串个数？

Manacher不太可搞
分k块Manacher+inom{k}{2}个节点枚举端点位置+拓展KMP求LCP
这里几乎掉线
其实可以做到$ frac{N}{M} $，没听懂不表

动态规划？

只考虑N*N的二维动规
状态值只和左上有关
按对角线计算可以并行
具体实现时可以按列进行，每算完$ frac{N}{M} $个传给右边一列
石子归并？
每个步长并行计算

图论算法？

一般只适用稠密图且点数较少

极大独立集？

Luby算法

图的染色？

Luby算法

0x02 后记

妈呀后面根本听不懂
掉线不能重连
也许我可以给我的学弟们讲这个。。。他们可能会用到。。
据说WC会有一道分布式算法题，害怕，然而我串行算法都不会写，不要说并行了

许愿弥生改二