The Sun Also Rises

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

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  73 随笔 :: 6 文章 :: 169 评论 :: 0 Trackbacks
[Overview] Arab and North Africa 2007, ANARC2007

Judging Olympia
弱智题
Hide That Number
利用mod11的性质直接算出前面应该补充什么。
Rotating Rings
每层判断是否可行。
A Tale from the Dark Side of the Moon
据说是无聊题
Fermat's Chirstmas Theorem
预处理素数列表 + 直接回答,注意2也是第二类素数
Incidental Points
经典题,枚举一个点,算出其他点相对于它的向量,问题就变成count同样的向量有多少个,sort / hash都可以。。。
Let's Go to the Movies
简单的DP题
The Writer's Club
writer之间求一下传递闭包,然后把所有是某个writer的reader合并起来,可以用32位压int来优化.
Moving Sticks
据说直接搜就可以了。To be written
Johnny Hates Math
经典的DP,用BFS来实现。内存稍微有点紧。


posted on 2008-02-16 18:24 FreePeter 阅读(1217) 评论(3)  编辑 收藏 引用 所属分类: ACM/ICPC

评论

# re: [Overview] Arab and North Africa 2007, ANARC2007 2008-02-18 20:52 yyr
Let's Go to the Movies
简单的DP题

可以说得详细一点吗?转移方程是什么样子?谢谢!  回复  更多评论
  

# re: [Overview] Arab and North Africa 2007, ANARC2007 2008-02-18 21:42 xcw
写的很不错
顶一下..  回复  更多评论
  

# re: [Overview] Arab and North Africa 2007, ANARC2007 2008-02-18 22:25 FreePeter
@yyr
经典的树形DP~
f1[i] = 解决所有以i为根的子树的最小费用,i节点的票还没被买好
f2[i] = 解决所有以i为根的子树的最小费用,i节点的票已经买好了

f1[i] = MIN(SingleTicket(i) + Sigma(f2[j]), FamilyTicket(i) + Sigma(f2[j]))
f2[i] = MIN(f1[i], Sigma(f1[j]))
其中j是i的孩子

大体就这样~  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   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.