C++博客-hello-worldhttp://www.cppblog.com/hello-world/zh-cnMon, 20 Apr 2026 08:25:06 GMTMon, 20 Apr 2026 08:25:06 GMT60Waterloo local 2002.09.21http://www.cppblog.com/hello-world/archive/2009/03/03/75466.htmlhello_worldhello_worldTue, 03 Mar 2009 15:22:00 GMThttp://www.cppblog.com/hello-world/archive/2009/03/03/75466.htmlhttp://www.cppblog.com/hello-world/comments/75466.htmlhttp://www.cppblog.com/hello-world/archive/2009/03/03/75466.html#Feedback0http://www.cppblog.com/hello-world/comments/commentRss/75466.htmlhttp://www.cppblog.com/hello-world/services/trackbacks/75466.htmlWaterloo local 2002.09.21


Trains
DP，图论
   
 Square  搜索
Blocks  暴力
Faucet Flow


Trains：(==)

Square：
这道搜索题与pku1011有相似的解法，剪枝都一样的，关于1011已经很经典了http://www.acrush.cn/?cat=9这里有很详细的剪枝！基本上改改就能过了~！

blocks：暴力加个界能跑0ms
这道题类似Grocery store




Faucet Flow
这是一道很优美的题，推荐
首先我们来判断一下水到底会从左边漏还是从右边漏，假设左边最高的高度是p， 右边最高的高度是q
若p > q 流往右边
若p < q 流往左边
若p==q 那就要看那边能装下更多的水
前两种那块最高的挡板不可逾越，想想就会明白，后一种水流会分成两股，左右等量，那就要看那边坚持的久了
大概意思就是这样，考点就是可能会有相等高度的挡板，这无疑加大难度，此题的具体实现也需要费些功夫。
再推荐一道类似的题，说类似只是背景类似，解法各异，后一种的代码实现方法也是很不错的             Artificial Lake




hello_world 2009-03-03 23:22 发表评论
]]>Waterloo local contest 1998http://www.cppblog.com/hello-world/archive/2009/03/01/75268.htmlhello_worldhello_worldSun, 01 Mar 2009 15:17:00 GMThttp://www.cppblog.com/hello-world/archive/2009/03/01/75268.htmlhttp://www.cppblog.com/hello-world/comments/75268.htmlhttp://www.cppblog.com/hello-world/archive/2009/03/01/75268.html#Feedback0http://www.cppblog.com/hello-world/comments/commentRss/75268.htmlhttp://www.cppblog.com/hello-world/services/trackbacks/75268.htmlWaterloo local 1998.10.17
Prime Distance
简单刷表
 Yahtzee  DP
 Request for Proposal  简单题
 Australian Voting  模拟
Chocolate Chip Cookies geometry


 Prime Distance

 题目大意就是给你一个区间[l，r]，找出这里相邻素数的最大距离和最小距离
 刷表是经典而实用的方法


Yahtzee
给十三种5个骰子的状态，十三种规则，每种规则下每个状态有一个得分，问怎样分配规则与状态之间的对应关系，让得分最大，同时要注意的是如果前六种规则下的得分如果>=63，那么总得分要加上35！
首先预处理出每种规则下每个状态的得分情况！
如果没有最后一个限制，那么我们可以有两种做法：1，二分图的最大权匹配；2，DP！但是有了最后一个限制，用匹配的话不知怎么下手，我只能想到dp！dp[i][j][k]表示前i种骰子状态已经分配好，分配的情况压缩成一个整数j，并且前六种规则的得分是k的状态，那么状态转移就是 dp[i][j][k] = {max(dp[ i - 1 ][ j - (1<<h) ][ k - score[h][i] ] ) (0<=h<=6)，max(max(dp[ i - 1 ][ j - (1<<h) ][ k ])( 7<=h<13) } (j的第h位为1) ! 复杂度大概是13*2^13*64 ; 中间记录前一个状态， 最后递归输出就好了~
 
Request for Proposal：

Australian Voting：
按照题意模拟就好了~

 Chocolate Chip Cookies

 题目大意就是有一些点（200个）， 用一个给定半径（r==5cm）的圆，最多能罩住多少个点
 200个点的话 o ( n^3 )能过，这样我们有了算法，要罩住最多的点，那个圆必须至少要卡住两个点
 枚举每两个点确定圆心，在检查所有的点是否在圆内。想法很自然
 细节问题上就是如何找到圆心（确定半径和两个圆上的点）这是基本功
 
 如果说直接解方程有些繁琐这里有好方法：

 
 这样只要解二元一次方程，可参考以下代码：
 1 struct point {double x, y;};
 2 
 3 bool centre(point p, point q, double r,point &o1, point &o2)
 4 //两点一半径会确定两个圆心 o1 o2
 5 {
 6    double rise,run,theta;
 7    double chordlen, perplen;
 8    double tantheta,tantheta1;
 9  
10    chordlen = sqrt( (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y) );
11    if (chordlen > 2*r) { return false; }
12    tantheta = sqrt(r*r*4 - chordlen*chordlen)/(chordlen);
13    //圆心角<poq的半角的正切值 
14 
15    run = (p.x-q.x)/2;
16    rise = (p.y-q.y)/2;
17    o1.x= (p.x+q.x)/2 + rise * tantheta;
18    o1.y= (p.y+q.y)/2 + -run * tantheta;
19    o2.x= (p.x+q.x)/2 + -rise * tantheta;
20    o2.y = (p.y+q.y)/2 + run * tantheta;
21   //结合点积就能得出上式
22    return true;
23 }
24 



hello_world 2009-03-01 23:17 发表评论
]]>Waterloo Local 2001.09.29 && 2002.01.26 && 2002.07.01http://www.cppblog.com/hello-world/archive/2009/02/13/73738.htmlhello_worldhello_worldFri, 13 Feb 2009 11:36:00 GMThttp://www.cppblog.com/hello-world/archive/2009/02/13/73738.htmlhttp://www.cppblog.com/hello-world/comments/73738.htmlhttp://www.cppblog.com/hello-world/archive/2009/02/13/73738.html#Feedback0http://www.cppblog.com/hello-world/comments/commentRss/73738.htmlhttp://www.cppblog.com/hello-world/services/trackbacks/73738.htmlWaterloo local 2001.09.29
  题目分类
 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;
         }





Waterloo local 2002.07.01


题目分类
 Hay Points  简单题
 Jogging Trails  图论，中国邮路问题
 Beavergnaw  简单题
 Power Strings  水题
Relatives
欧拉函数
Jogging Trails：
题目意思是给定一些点，然后一些边，并且两个点之间可能有多条边，问从一个点出发，遍历完所有的边至少一次且最后在回到出发点需要走的最少距离！
如果这个图是欧拉图，那么距离就是边之和，一个图存在欧拉图的充要条件是每个定点的度为偶数！
但是如果不是欧拉图，那么我们就要把这个图变成欧拉图，只需要添加一些边，顶点的度全部为偶数就好了，因为一个图中奇数度顶点一定有偶数个！所以只要枚举这样的奇数度顶点，添加边使其度为偶数，很明显添加的边不会影响其他偶数度顶点的奇偶性！并且由于要距离最小，所以添加的边一定是这两个顶点的最短距离！这一步可以用记忆化搜索实现！


欧拉函数的一些题目（
转http://hi.baidu.com/wuxyy/blog/item/33957f1ee03a1cf51bd5761d.html
）

欧拉函数入门题目：poj3090 Visible Lattice Points  poj2407 Relatives
poj2478 Farey Sequence
欧拉函数高级应用：poj2480 Longge's problem  poj1091 跳蚤

跳蚤题目很有意思，推荐




hello_world 2009-02-13 19:36 发表评论
]]>Waterloo local 2001.09.22http://www.cppblog.com/hello-world/archive/2009/02/12/73668.htmlhello_worldhello_worldThu, 12 Feb 2009 15:08:00 GMThttp://www.cppblog.com/hello-world/archive/2009/02/12/73668.htmlhttp://www.cppblog.com/hello-world/comments/73668.htmlhttp://www.cppblog.com/hello-world/archive/2009/02/12/73668.html#Feedback0http://www.cppblog.com/hello-world/comments/commentRss/73668.htmlhttp://www.cppblog.com/hello-world/services/trackbacks/73668.htmlWaterloo local 2001.09.22
  题目分类
 Average Speed  简单题
 Subway  图论，最短路
Babelfish  Map
Bounding box  几何
A multiplication game
博弈，局面

Subway：
把n个地铁站抽象为点，起点为家，终点为学校！一共n+2个点，仅当两个地铁站在一条线路上且相邻他们的距离才是实际距离的1/4, 各个点之间的距离就为实际距离，然后求起点到终点的最短距离即可，然后换算成时间，注意的是虽然题目没有说但是每条线路上的站点是各不相同的！不用考虑得太麻烦！

Babelfish：
此题偷懒做可以用C++中的map，不过效率不是很高。如果想加快效率，可以用Trie树来做。

bounding box：
求出圆心然后不断旋转

a multiplication game：
找必胜局与必负局，递规求解

疲劳ing~~







hello_world 2009-02-12 23:08 发表评论
]]>Waterloo local 2001.06.02http://www.cppblog.com/hello-world/archive/2009/02/12/73667.htmlhello_worldhello_worldThu, 12 Feb 2009 14:34:00 GMThttp://www.cppblog.com/hello-world/archive/2009/02/12/73667.htmlhttp://www.cppblog.com/hello-world/comments/73667.htmlhttp://www.cppblog.com/hello-world/archive/2009/02/12/73667.html#Feedback0http://www.cppblog.com/hello-world/comments/commentRss/73667.htmlhttp://www.cppblog.com/hello-world/services/trackbacks/73667.htmlWaterloo local 2001.06.02
  题目分类
 No Tipping  二进制表示状态，DFS
Sumsets  查找，搜索
Zipf's Law 字符串处理
Ones 简单题
No Tipping:
题目要求把一个有两个支点的杠杆上的重物拿掉，使得杠杆始终保持平衡，然后输出某个可行的顺序。显然，状态的表示和物体拿走的顺序有关，此题从正面入手，状态表示比较困难。其实可以换个角度看，就是在一块空的杠杆上，依次放上重物，杠杆要始终保持平衡，这个顺序就是拿走的顺序。用二进制可以方便的表示状态，如果（s|1<<i）这个状态可行，就说明在s的状态下，放上物体i不会使杠杆倾斜。判断是否平衡的条件，要用到物理知识，力矩=力避 x 力， 重心的坐标，也可以通过(力矩/重力)求出。只要重心坐标在两个支点之间就能保持平衡。

Sumsets：
题目要求求出给定集合中最大的一个数，这个数要满足是集合中其他三个数的和，即求 a+b+c=d ！
我的做法：先对集合排序，暴力算出集合中任意两个数的和即a+b，然后对和排序，对集合中的数从大到小枚举d，看是否存在c，使d-c在和的集合中！因为和的集合是有序的，所以可以二分查找，同时注意这四个数不能相同就可以了！

Zipf's Law：
字符串处理，按照题目意思做就好了，使用string会很方便，处理全部的单词，然后排序处理~

Ones：
从1开始不断的模n，然后对结果*10+1，循环直到为0即可~


hello_world 2009-02-12 22:34 发表评论
]]>