题目分类
|
| Adventures in Moving - Part IV |
DP |
| Pairsumonious Numbers |
搜索 |
| Snow Clearing |
简单题 |
|
|
| Stack 'em Up |
模拟 |
Adventures in Moving - Part IV：
这题DP的阶段和决策都非常明显。g[i][j]=min( g[i-1][j+dis[i]-dis[i-1]-buy]+buy*pirce[i] )
g[i][j]表示将要离开第i个加油站时，有j升汽油，所要花费的最少的钱。
Pairsumonious Numbers ：
首先 n==3 时很容易求出答案，a1+a2, a1+a3, a2+a3,两两相加再减去另一个
然后 n > 3 时首先我们排序，有顺序就是成功的一半，
如果那 n 个数的大小是 a1 < a2 < a3 < ... < an
那么最小的是 a1+a2, 次小的是 a1+a3，如果我们知道 a2+a3 在哪 那该多好啊
幸运的是 a2+a3只可能出现在第 3 位到第 n 位之间，n又是小于10的数，那我们只要枚举
每种情况就可以了
这样我们就能求出a1 , a2, a3 那对解题有什么用呢？
这时我们把 a1+a2, a1+a3, a2+a3 删掉，剩下的最小的是不是肯定只有 a1+a4,那是不是
a4也求出来了
接着我们把 a1+a4, a2+a4, a3+a4都删掉，剩下最小的不就是 a1+a5了吗
不断进行上述过程就能求出答案
至于有相同元素的时候，很容易就知道也符合上述做法，正因为有相同元素，中间可用multiset
实现上述功能
Snow Clearing：
只需要把每条街加起来再乘以2就是总的距离，除以速度然后化成时间即可！
Stack 'em Up：
这题只要把题意看懂之后，就没问题了。首先给你n种洗牌策略，然后再给你若干个k，在前一次洗好的牌的基础上，按照第k种洗牌策略洗。每洗一次，输出目前的牌的顺序。
Waterloo Local 2002.01.26
题目分类
|
| |
|
| Discrete Logging
|
求离散对数 |
| Hardwood Species |
简单题 |
Forests
|
水题（stl运用）
|
| A Star not a Tree? |
牛顿迭代法
|
Discrete Logging
：
求以b为基模于n的离散对数我们有O(n^0.5*logn)的算法
有兴趣者可查看Shank's Baby-Step-Gaint-Step Algorithm
A Star not a Tree? ：
给你平面上 n ( n < 100)个点， 要求一个点p，使得 p 到各个点的距离之和最小
用牛顿迭代，能证明x,y偏导为0时，有最小值，但我不会证
（
回去学高数）
既然知道方程x，y偏导为0时有最小值，那就好办了，取平均值为初值，然后不断迭代，
但我精度调到 1e-4 才能过，这样我的迭代跑了300ms，别人都跑0ms，总感觉有问题
贴出迭代代码，希望大家给我指正
while( !( zero(x1 - x0) && zero(y1 - y0) ) )
{
x0=x1, y0=y1;
for( fx=0, i=0; i < n; i++)
fx+= (x0 - p[i][0])/ sqrt( (x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) );
for(fxx=0, i =0; i < n; i++)
fxx+=( 2*(x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) ) / ( (x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) );
x1 = x0 - fx/fxx;
for(fy=0, i=0; i < n; i++)
fy+=(y0 - p[i][1])/ sqrt( (x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) );
for(fyy=0, i=0; i < n; i++)
fyy+=( (x0 - p[i][0])*(x0 - p[i][0]) + 2*(y0 - p[i][1])*(y0 - p[i][1]) ) / ( (x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) );
y1=y0 - fy/fyy;
}