The Sun Also Rises

Algorithm, Mathematica, 计算机科学, C++, photography, GNU/Linux的讨论空间

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  73 随笔 :: 6 文章 :: 169 评论 :: 0 Trackbacks

[Solution] Dhaka 2007

Bachelor Arithmetic
秒杀题

Nested Squares
模拟题

The Dumb Grocer
首先要有1是吧。。。然后我们按照1的个数来分类,我们来计算恰有k1的方案数。
我们在k1的基础上加入新的数,显然第一个数只能是k+1
然后加入的数只能是k + 1 or 2 * (k + 1)
如法炮制。。。发现非1的数都具有(k + 1) * t的形式。。。设其依次为(k + 1) * ti
{ti}这些数也满足题目的性质。。。共有f((n - k) / (k + 1))种方案。

f(n)是要求的函数,则f(n) = sigma(f((n - k) / (k + 1)), (k + 1) | (n + 1) , k>=1
f(0) = 1
这样直接做会T...
我们令g(n) = f(n - 1)
g(n) = f(n - 1) = sigma(f((n - k - 1) / (k + 1))) = sigma(f(n / (k + 1) - 1)) = sigma(g(n / (k + 1)), (k + 1) | n, k >= 1
n = p1^a1 * p2^a2 * ... * pr*ar
h(p1, p2,.., pr, a1, a2...ar) = g(n)
= h(p1,p2, ...pr, b1, b2, ...br),
0<=bi <= ai, bi
不全=ai
注意对于一个确定的nh()中的p1, p2...pr在计算过程中始终不变。。。所以。。。计算结果与pi无关,只与ai有关
这样状态数就大大减少了。。。直接因式分解后dp就行了。。。

ACM Puzzles
状态压缩dp


Inspector's Dilemma
The Bells are Ringing Photographic Tour
这三题好像当时没写summary。。。所以我们假设比较简单~~~


You are around me ...
首先旋转坐标,变成平行与xy轴的椭圆,然后坐标伸缩。。。变成圆。。。最近点对。。。贴模板。。。
ZJU2107 Quoit Design
一道测最近点对的题。


Infinite Matrix
显然,对于固定的j, Ri, j是一个关于i的多项式。
注意到数列Ri, j的差分序列R(i + 1, j) - R(i, j)是可以求出来的(利用Mj, k <= 10的条件,可以在O(10*n^2)的时间内算出)
然后有了差分序列求通项就是O(n^2)的事情。
然后记S(p, j)(n) = Sigma(i^p * R(i, j)) i <= n
继续利用差分序列之类的方法求这个,最后再求一个Sum_S(p, j)
预处理复杂度大致是O(10*n^3)的。
后面的就好办了,对每个询问,把(i + 1)^p二项式展开,最多10项,然后利用公式直接计算。
处理询问复杂度O(p*q*n)
POJ3529 Matrix Analysis
,类似的思想,更简单~

Magnetic Train Tracks
给定n个点,求可以构成多少个锐角三角形。
n <= 1200
话说求锐角三角形不太好算是吧。。。补集转换,我们来求钝角/直角三角形 <=> 求钝角/直角个数。。。
后面的事情就简单了,是对每个点,将其他点按照极角排序 + 扫描。
Dhaka 2005 Counting Triangles
也是一道补集转换的题~(转化成求三点共线的个数)
Shanghai 2004 Amphiphilic Carbon Molecules
也是一道极角排序+扫描的题。

posted on 2008-05-01 20:22 FreePeter 阅读(775) 评论(1)  编辑 收藏 引用 所属分类: AlgorithmACM/ICPC

评论

# re: [Solution] Dhaka 2007 2010-09-10 00:06 Quynh
Dear FreePeter,
I dont really understand your solution to Infinite Matrix problem.
Can you classify it to me ? in more details...?
Furthermore, if you can explain in English, because I have some problems in translating Chinese into English.
If okay, show me the solution to "Matrix Analysis" problem.

Thank you in advance !
Quynh, Nguyen  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Creative Commons License
This site is licensed under a Creative Commons Attribution-Share Alike 2.5 China Mainland License. 本站采用创作共用版权协议, 要求署名、相同方式共享. 转载本站内容必须也遵循“署名-相同方式共享”的创作共用协议. This site is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.