F
e
l
i
c
i
a
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2007年9月
>
日
一
二
三
四
五
六
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
统计
随笔 - 149
文章 - 0
评论 - 315
引用 - 0
公告
访问量
定制我的博客魔方
Yodao提供
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(21)
给我留言
查看公开留言
查看私人留言
随笔分类
(145)
ACM/ICPC 纪事(13)
(rss)
Felicia 的标程(3)
(rss)
TopCoder SRM(5)
(rss)
动态规划(28)
(rss)
计算几何(52)
(rss)
图论(6)
(rss)
心情日记(33)
(rss)
杂题(5)
(rss)
随笔档案
(149)
2010年10月 (5)
2009年1月 (2)
2008年2月 (2)
2008年1月 (8)
2007年12月 (6)
2007年11月 (5)
2007年10月 (30)
2007年9月 (47)
2007年8月 (44)
相册
百度之星2007
女友Ader
校园风景
ACMers
barnabas
Codger
ecjtubaowp
Felicia's New Blog
Flyfox
Hailer
Liang
LittleKid
Nash635
Owen
Richardxx
[推荐]不可不看的超级牛的网站
updog
wywcgs
海狸鼠DLUT
农夫三拳
潘帕斯雄鹰
踏雪赤兔
巫山霏云
星丞
Pretty Girls
Ader
最新随笔
1. [导入]论函数调用约定(修订版)
2. [导入]CodeColorer的可视化插入代码
3. [导入]Gravatar头像被墙的解决方法
4. [导入]Win7下解决80端口被占用的办法
5. [导入]C# 泛型+扩展方法
6. <天龙八部Online>资源包Axp格式研究
7. 如何加载《天龙八部》Skeleton
8. 我已更换新的blog http://gccfeli.cn 此blog的文章已全部转移
9. 今天自己做果冻吃
10. 非常喜欢珞珈山水离版画面的一首诗
搜索
最新评论
1. re: [动态规划]pku1038
@Run&Run
里面的两处>?=是什么意思
--prister
2. re: USACO历年比赛题目列表,测试数据和解题报告下载[未登录]
已经打不开了
--lee
3. re: WF的T-shirt颜色选什么好呢?
我还是喜欢 gekius的t-shirt多些 gekius.com
--banyumalu
4. re: [动态规划]pku3375
求数据
--77
5. re: [动态规划]pku1141
你的这个代码提交WA了
--wwq
阅读排行榜
1. USACO历年比赛题目列表,测试数据和解题报告下载(27193)
2. [动态规划]pku 部分动态规划题目列表(6567)
3. [计算几何]两圆求交点(5822)
4. [动态规划]动态规划总结 by Amber(3948)
5. [计算几何]pku 部分计算几何题目列表(3183)
评论排行榜
1. 友情链接邀请(42)
2. USACO历年比赛题目列表,测试数据和解题报告下载(38)
3. 2007南京赛区总结 by mmd(19)
4. [动态规划]pku2411(12)
5. [计算几何]pku 部分计算几何题目列表(12)
09 2007 档案
[动态规划]pku1185
摘要: 经典的状态压缩DP,状态是f[i][j],表示第i行,以3进制j为状态。j的位代表一个格子,只能是:0表示第i行和第i - 1行都没有炮兵,1表示第i行没有炮兵而第i-1行有炮兵,2表示第i行有炮兵。然后用DFS进行状态转移。一开始我做了超时,后来预处理了一下合法状态,快了不少,才AC。
阅读全文
posted @
2007-09-30 22:09
Felicia 阅读(1042) |
评论 (0)
编辑
[动态规划]pku1163
摘要: 今天郁闷了,贴个小代码
阅读全文
posted @
2007-09-29 22:43
Felicia 阅读(539) |
评论 (0)
编辑
[动态规划]动态规划总结 by Amber
摘要: 动态规划总结 by Amber
阅读全文
posted @
2007-09-29 20:25
Felicia 阅读(3948) |
评论 (0)
编辑
[计算几何]pku3391
摘要: 问题是求平面欧几里德最小生成树的第n - k小边。
平面欧几里德最小生成树是经典问题,可以做到O(nlogn)。具体做法是先对平面点进行三角剖分,时间复杂度是O(nlogn),三角剖分的边就是可能的在最小生成树的边。因为是平面图,所以有O(n)条边,在其上应用 Kruscal 算法即可。
阅读全文
posted @
2007-09-28 20:17
Felicia 阅读(777) |
评论 (0)
编辑
漫谈扭结
摘要: 漫谈扭结
阅读全文
posted @
2007-09-27 17:26
Felicia 阅读(1800) |
评论 (2)
编辑
[计算几何]pku1673
摘要: 此问题可转化为求三角形垂心。我的做法是设垂心坐标为(x, y),然后利用垂直关系解方程。
阅读全文
posted @
2007-09-27 17:18
Felicia 阅读(652) |
评论 (1)
编辑
Ubuntu 6.10 @ Dell XPS M1210 安装手记
摘要: Ubuntu 6.10 @ Dell XPS M1210 安装手记
阅读全文
posted @
2007-09-27 15:21
Felicia 阅读(666) |
评论 (0)
编辑
[转载]好友的一首小诗
摘要: 一首小诗……
阅读全文
posted @
2007-09-27 15:06
Felicia 阅读(192) |
评论 (0)
编辑
[计算几何]平面点的曼哈顿最小生成树
摘要: 平面点的曼哈顿最小生成树
阅读全文
posted @
2007-09-27 14:48
Felicia 阅读(1261) |
评论 (0)
编辑
[计算几何]pku1624
摘要: 简单计算几何,我的做法是列出所有可能的切法(一共18种),求最优值。
阅读全文
posted @
2007-09-26 20:46
Felicia 阅读(572) |
评论 (1)
编辑
[计算几何]pku1408
摘要: 构造所有的线段,然后枚举每对水平-竖直线段,求交点,然后计算四边形面积,求最大值。
阅读全文
posted @
2007-09-25 21:59
Felicia 阅读(621) |
评论 (0)
编辑
[动态规划]pku3133
摘要: 强烈推荐此题!
状态压缩DP的好题!
分析见内
阅读全文
posted @
2007-09-24 21:12
Felicia 阅读(1141) |
评论 (4)
编辑
[计算几何]pku3384
摘要: 强烈推荐此题。半平面交算法的一个应用。
具体做法是,把多边形的每条边向内平移r单位长度,用这些线段所在直线和原多边形作半平面交,得到的区域就是半径为r的圆放入多边形的可行域。可以证明这个区域一定是凸的,或者退化为一条线段,或一个点。那么,我们就可以在这个区域上求最远点对啦。
我的做法是O(n^2)的。应该存在O(nlogn)的做法,因为都是凸多边形,每次半平面交只有最多两个交点,可二分,而最后的求最远点对可以旋转卡壳。比赛的时候时间少,就写了个暴力O(n^2)的。
阅读全文
posted @
2007-09-23 16:19
Felicia 阅读(786) |
评论 (0)
编辑
[计算几何]pku1410
摘要: 基本几何题,判断线段是否与矩形相交。转化为线段在矩形内或线段与四条边相交。
唯一要注意的是题目中关于左上角和右下角的定义。
阅读全文
posted @
2007-09-22 10:58
Felicia 阅读(527) |
评论 (0)
编辑
[计算几何]pku1319
摘要: 这个题需要分情况讨论。如果是grid,就能直接算,如果是skew,就一层层往上模拟着堆。最后取最大值。
阅读全文
posted @
2007-09-21 21:56
Felicia 阅读(436) |
评论 (2)
编辑
[计算几何]两圆求交点
摘要: mmd 和 cz 的智慧结晶。某次比赛的时候写的。
阅读全文
posted @
2007-09-20 18:34
Felicia 阅读(5822) |
评论 (7)
编辑
太难过了
摘要: 这是胡说八道
阅读全文
posted @
2007-09-19 18:06
Felicia 阅读(222) |
评论 (0)
编辑
[计算几何]pku1586
摘要: 超级恶心的精度题。注意读清题意,然后直接做就行了。
阅读全文
posted @
2007-09-19 17:47
Felicia 阅读(448) |
评论 (0)
编辑
[图论][zz]给出一个没有偶圈的简单无向图,求两个顶点间路径的数目
摘要: 给出一个没有偶圈的简单无向图,求两个顶点间路径的数目
阅读全文
posted @
2007-09-19 10:08
Felicia 阅读(969) |
评论 (2)
编辑
[计算几何]pku2954
摘要: Pick公式的应用。先介绍一下Pick公式:
a = e / 2 + i - 1
a为多边形(顶点都在格点上)面积,e为多边形边上的格点数,i为多边形内部的格点数。
题目给出三点坐标,边上的格点数可用gcd求得,剩下的事就是解方程了。
阅读全文
posted @
2007-09-18 21:59
Felicia 阅读(434) |
评论 (0)
编辑
唔,我喜欢这首诗
摘要: 喜欢搞笑的诗的请进
阅读全文
posted @
2007-09-17 18:39
Felicia 阅读(175) |
评论 (0)
编辑
[计算几何]pku1569
摘要: 枚举三角形,然后判断是否其余的点都不在形内,也不在边上。时间复杂度是O(n^4)。
阅读全文
posted @
2007-09-16 21:19
Felicia 阅读(359) |
评论 (0)
编辑
[计算几何]pku3129
摘要: 很简单的几何题。直接硬搞即可。
阅读全文
posted @
2007-09-15 20:25
Felicia 阅读(383) |
评论 (0)
编辑
[转]WinSock学习笔记[2]
摘要: Winsock入门
阅读全文
posted @
2007-09-14 22:26
Felicia 阅读(201) |
评论 (0)
编辑
[转]WinSock学习笔记[1]
摘要: Winsock入门
阅读全文
posted @
2007-09-14 22:23
Felicia 阅读(176) |
评论 (0)
编辑
[计算几何]pku一些关于多边形的题目
摘要: 见内
阅读全文
posted @
2007-09-14 22:21
Felicia 阅读(534) |
评论 (0)
编辑
[计算几何]pku3130
摘要: 又是一个求多边形的核的题。
阅读全文
posted @
2007-09-14 22:18
Felicia 阅读(483) |
评论 (0)
编辑
I Want A Wife
摘要: :)
阅读全文
posted @
2007-09-13 14:17
Felicia 阅读(241) |
评论 (2)
编辑
[计算几何]pku2079
摘要: 先求凸包,然后再用旋转卡壳方法求解。
具体做法是枚举三角形的第一个点i,设j = i + 1,k = j + 1。然后做以下操作:
1.计算i,j,k构成的三角形面积a1和i,j,k + 1构成的三角形面积a2,如果a2 < a1,则进行下一步,否则k++,重复此步。
2.记录此时的三角形面积b,如果b < preb(就是上一个j对应的三角形面积)j++,转第一步,否则退出。
可以证明这个算法的复杂度为O(n2)。具体实现见代码。
阅读全文
posted @
2007-09-13 13:40
Felicia 阅读(852) |
评论 (0)
编辑
[动态规划]pku1038
摘要: 经典的状态压缩DP,《算法艺术与信息学竞赛》的例题。f[i][j]表示前i行,最后两行状态为二进制数j,嵌入的最多芯片数。第i行到第i+1行用DFS进行状态转移。
由于第i+1行只和第i行有关,故可以用滚动数组优化。
阅读全文
posted @
2007-09-12 20:44
Felicia 阅读(1530) |
评论 (3)
编辑
[动态规划]pku3375
摘要: A O(NM) dynamic programming algorithm is quite apparent after sorting the computers and network interfaces by their coordinates. Furthermore, in any optimized case, for each computer the difference between the the indices of the network interfaces matching to and closest to the computer is never larger than N. So the complexity could be reduced to O(N2)
有很多细节不好考虑,应该是我的水平原因。最后我向updog要了数据才过的。而且代码写的不好。将就看一下吧。
阅读全文
posted @
2007-09-11 22:28
Felicia 阅读(799) |
评论 (1)
编辑
[计算几何]pku1494
摘要: 其实是初等几何题。在纸上画一下就出来了。
阅读全文
posted @
2007-09-10 20:48
Felicia 阅读(419) |
评论 (0)
编辑
[计算几何]pku1473
摘要: 很简单的题。直接按照题意模拟即可。
阅读全文
posted @
2007-09-10 16:58
Felicia 阅读(366) |
评论 (0)
编辑
无敌诡异的姓名测试
摘要: 对搞笑的事情感兴趣的请进
阅读全文
posted @
2007-09-10 13:13
Felicia 阅读(173) |
评论 (0)
编辑
[计算几何]pku1039
摘要: 具体算法在《算法艺术与信息学竞赛》里有讲。
阅读全文
posted @
2007-09-09 22:01
Felicia 阅读(765) |
评论 (0)
编辑
[计算几何]pku1133
摘要: 这个题目我用的是枚举。具体做法是,对于每个星座,把它的第1个点放在星图的第i个点上,第2个点放在星图的第j个点上(i != j),保持形状不变,移动这个星座中的其他点,看看这些点是否都和星图中的点重合。若满足条件,则找到一个匹配。如此得到星座c对星图的匹配数a。再得到星座c对它本身的匹配数b。那么星座c的出现次数就是 a / b。对于只有一个星星的星座,要特殊考虑一下。至于找出最亮星座,方法很简单:每次记录亮度值,发现更亮的就更新解。
p.s. 我一开始是用STL的complex做的,超时。后来改成向量做了。
阅读全文
posted @
2007-09-08 22:42
Felicia 阅读(516) |
评论 (1)
编辑
[计算几何]pku1092
摘要: 题目要求统计一个平面图中所有边数为k的面的个数。应该是个经典问题。说说我的算法吧。
枚举每条边,做以下的基本步骤。
基本步骤:以这条边作起始边,不断地找下一条“最左转”的边,并且标记每个点的访问次数,直到某个点第3次被访问为止。
经过这个步骤之后,得到一个顶点序列。容易知道,当且仅当这个顶点序列是2-重复(就是形如12341234这样),并且是逆时针旋转的,那么就是一个面。
接下去我们就把所有找到的边数为k面进行hash去重,就得到答案啦。
貌似我想的这个算法不够好,如果有更好的算法,欢迎和我讨论。
阅读全文
posted @
2007-09-07 19:37
Felicia 阅读(649) |
评论 (0)
编辑
友情链接邀请
posted @
2007-09-07 16:15
Felicia 阅读(1106) |
评论 (42)
编辑
[计算几何]pku1471
摘要: 这题勉强算几何吧。我写了个超级慢的枚举。
阅读全文
posted @
2007-09-06 20:02
Felicia 阅读(418) |
评论 (0)
编辑
[计算几何]pku1434
摘要: 简单几何题,但是容易WA。做法是二分水面高度,然后看看这个高度对应多少水。
阅读全文
posted @
2007-09-05 21:30
Felicia 阅读(312) |
评论 (0)
编辑
到武汉啦!
摘要: 对我的悲惨人生感兴趣的请进
阅读全文
posted @
2007-09-05 20:25
Felicia 阅读(217) |
评论 (0)
编辑
[动态规划]pku1170
摘要: 呼~今天去学校啦!早上7点起床写题,挑了个简单题写 ^_^
这个是IOI95的DP题。用一个b位的6进制数i表示状态。这个6进制数的每一位分别表示相应物品的数量。f[i]表示状态i下的最小花费。同样也可以用6进制数j表示优惠。那么,f[i]就能转移到f[i - j],如果优惠j可用的话。代价是使用优惠j时减少的花费。最后的答案就是min(f[i]),0 <= i <= start(start是初始状态)。
阅读全文
posted @
2007-09-04 08:37
Felicia 阅读(668) |
评论 (0)
编辑
[动态规划]pku1160
摘要: 先预处理,把第i个村子到第j个村子中,建一个邮局的最小代价算出来,存在min_cost[i][j]里。
接下来就可以DP。设f[i][j]为前i个邮局,建在前j个村子的最小代价。那么f[i][j]可以转移到f[i + 1][j + k],(1 <= k 且 j + k <= n),代价是min_cost[j + 1][j + k]。
阅读全文
posted @
2007-09-03 22:44
Felicia 阅读(1495) |
评论 (3)
编辑
[图论]pku1125
摘要: 简单题。很早以前做的。贴一下凌乱的代码。
阅读全文
posted @
2007-09-02 20:09
Felicia 阅读(491) |
评论 (2)
编辑
[动态规划]pku1088
摘要: 简单的记忆化搜索。很早以前做的,代码风格很乱。将就一下啦。
阅读全文
posted @
2007-09-02 20:02
Felicia 阅读(914) |
评论 (5)
编辑
[动态规划]pku1737
摘要: 楼爷的题。递推。f[n]表示n个结点的连通图个数,则有递推公式:
void calc(int n)
{
f[n] = 0;
for (int i = 1; i < n; i++)
f[n] += f[i] * f[n - i] * (pow(i) - 1) * C(n - 2, i - 1);
//pow(x) == 2^x
}
因为数据较多,所以预先算出f[1] -- f[50],再输出。要用高精度。我用了标程。
阅读全文
posted @
2007-09-02 13:53
Felicia 阅读(759) |
评论 (6)
编辑
[动态规划]pku1946
摘要: 首先明确一点:最优解必为奶牛1..n-1轮流领跑,奶牛n撞线。且跑了x圈后,未领跑过的奶牛都耗费了x的体力。
设f[i][j][k]表示前i-1头奶牛已领跑,现在由第i头奶牛领跑,一共跑了j圈,奶牛i耗费了k的体力。
则f[i][j][k]可以转移到f[i][j + p][k + p^2](耗费1分钟,奶牛i以p圈/分钟的速度继续领跑),也可转移到f[i + 1][j][j](换成奶牛i + 1领跑,不耗费时间)。
时间复杂度为O(nde^2.5)。
阅读全文
posted @
2007-09-01 11:42
Felicia 阅读(479) |
评论 (1)
编辑