Posted on 2007-02-20 13:46
oyjpart 阅读(1435)
评论(9) 编辑 收藏 引用 所属分类:
ACM/ICPC或其他比赛
踌躇满志,遥望山顶--开始上路
The Counting Problem Accepted 2-20 2Y的 WA一次因为没考虑1位数的特殊情况 这是一道简单题 但是需要细心 Y掉他！
Always On the Run Accepted 2-20 阶段明显的DP 每一阶段直接更新地图即可
Video Surveillance Accepted 2-20 原这个题目要想写的复杂可以很复杂(比如我的) 要想写的简单 可以很简单(看了10小川的代码 orz) 其实只用在转角处直接限定可放置Video范围就可以了 而限定也可以简化 比如向上的墙只需要限定可选范围的左端
Jugs Accepted 居然死广搜就可以过...比赛的时候我还按数学方法递推来着...真郁闷
City Game Accepted 上->下DP过的
Calendar Game Accepted 2-20 简单的博弈树(有无数学方法?) 只需判断先手是否能获胜 根据题意构建博弈树 一次DP或记忆化搜索即可
John's trip Accepted 2-21 MS听说要转化的？我用DFS的Euler求法过的
从零开始 踏上山脚--真正的旅程
Dividing Accepted 搜过去的 正解是DP
Closest Common Ancestors Accepted 用的是LCA的tanjar算法 注意输入x，x的情况只加入一次询问（这种算法是从下到上合并 简单的逻辑推理+并查集）
Frame Stacking
Piggy-Bank Accepted 很明显的背包
Code the Tree Accepted 看明白题意 直接模拟就可以了 输入有点烦
Square Ice 模拟题 不想做...
千辛万苦 收获颇丰--渐入佳境
1011 Accepted 绝对经典的搜索强剪枝
1018 Accepted 简单题
2662 Accepted 2-27 1.Dijkstra或者Bellman-Ford确定每个定点的距离标号 2.对所有点进行排序 按照距离标号从大到小进行DP
1568 Accepted 3-2 极大极小搜索+Alpha-Beta剪枝
1036
1038
1042 Accepted 2-17简单题 直接枚举结束湖泊+贪心选择就可以了因为集训的时候这个题目莫名WA 故再A一遍 以解心头之恨！
1050 Accepted 简单题
1088 Accepted 排序+记录（可以看成DP么？哈哈）
1093
1096
1112
1117
回望四周 云雾缭绕--勇敢前行
1155 Accepted 2-16 如果能做Apple Tree 相信就能做这题 父结点状态由子结点从左到右DP后的结果决定 逐子树合并
1156
1157 Accepted 简单DP IOI很少有这么简单的题目了 呵呵
1159 Accepted 简单题
1160 Accepted 典型的DP 阶段很明显
1163 Accepted 简单DP
1170
1185
1190
1191
1195
1200
1221
1338 Accepted 简单队列维护
1416
脱离险境 笑看风云--无愧于心
1458 Accepted2-16 这个题目有问题么？用cin就错！用scanf就对。。害我WA。。
1523 Accepted2-15求割点 DFS求subnet 注意 数据有点faint 点不是相连的
1579
1631 Accepted DP+Greedy
1632
1639
1651
1659
1680
1683
1691
1703 Accepted 并查集（可以建立一个敌人的对应关系 这样队后续的判定很方便）
艺术使者 灵魂主人--心灵之旅
1709
1714
1753
1769
1771
1826
1855
1856 Accepted2-15搜索（搜索方式：可以向右向下搜得到覆盖区域，检查内部是否全部为#，再检查环绕一圈是否全部为.即可）注意相遇corner仍然算Bad 比如
.#
#.
1890
见证生命 每一分钟--For the loved ones
1924
1935
1944
1945
1946
1947
1948 Accepted2-15由于数据量不大 利用可行性的状态 进行DP Heron公式
搜索也能过 呵呵 需要预先找到一个较好解 大->小搜 加一定的剪枝
1949
这才是我真正的舞台！-- Go For it！
1950
1951
1952
1979
1980
2170
2288
2331
2339 Accepted 3-4 简单题
解开面纱 最后决战--看看山顶上的风景
2340
2486 Accepted 3x to magicpig 在treeDP中 如果结点的多个子结点既相互分离 又存在状态表示中的局部联系 采用从左到右和并的方式是很好的
2492
2524 Accepted 直接用并查集就OK
2540
2761
2777 Accepted 线段树 比较好的做法是用2进制压缩存储 也可以不用 直接记录颜色是否采用
1012 Accepted 打表
1013 Accepted 2-16 24情况枚举 简单题
1019 Accepted 分段统计 先位数在尾数再位置 我最恶心这类题了
1647
1654
1655 Accepted 最简单的treedp --alpc01
1804 Accepted 逆序对 我见过比较好的算法是 1.归并排序中记录逆序对 2.线段树
2084
回望历史 欣然笑过--路在心中
2187
2195
2242
2295
2353
2354
2362 Accepted 暴搜的简单题
2411 Accepted 状态DP的经典教材
3131
风景这边独好--永远学习！
Feedback
# re: 我的金山 我来书写 回复 更多评论
2007-02-22 01:27 by
为什么你可以做题目，而我现在要一天到晚写那个BT网站哦……
55555555555555555555555555555……………………
# re: 我的金山 我来书写 回复 更多评论
2007-02-22 02:40 by
为什么你可以写网站，而我现在要一天到晚写这个BT题目啊……
55555555555555555555555555555……………………
# re: 我的金山 我来书写 回复 更多评论
2007-10-26 14:52 by
pku1018怎么写呀？
# re: 我的金山 我来书写 回复 更多评论
2007-10-26 14:59 by
这位不知名的大牛，你好
我是一名普通的高二学生，现在正在准备信息学竟赛。
pku1018已经缠了我好久，请你帮帮忙，只要告诉我思路就好。
你可以以回复的形式告诉我，我会常来这里看你是否解答。
你也可以给我发邮件 我的邮箱是 hnaygy1990@163.com
先谢谢你啦。
# re: 我的金山 我来书写[未登录] 回复 更多评论
2007-10-27 19:44 by
你可以枚举那个Mininum 带宽 然后把其他的排序 选择比较小的 呵呵
如果需要代码我可以发邮件给你
# re: 我的金山 我来书写 回复 更多评论
2007-10-27 21:19 by
看到你的回复我感到十分激动，再次对你的帮助表示感谢。
疑问：假设当前我枚举的最小宽带为b0。我对于每一个装置都选其宽带大于b0且价格最小的方案。这样可以得到系统宽带不小于b0时的最小价格。但这样的话不能保证系统宽带就是b0。这时候需要在找到确切的最小宽带。那么上述对于枚举为b0是的时间复杂度是a=n*m*n。枚举量要b<m*n。那么总的时间复杂度要a*b*t，可能超时。（描述中m是m[i]（1<=i<=n）的平均值）
如果你能把标程给我的话，那我就很猥琐的受下啦。
希望你能解释这个疑问，
然后...(说不出口啊...唉，减rp喽)请你把标程发给我吧。
# re: 我的金山 我来书写 回复 更多评论
2007-10-27 21:26 by
哦，对啦，还有一个疑问，为什么很多人都说这是一道dp题呀？
（我最近正在自己找dp题以强化训练，开始还顺利，却被这题卡住啦）
# re: 我的金山 我来书写[未登录] 回复 更多评论
2007-10-27 22:44 by
枚举的带宽实际上是有限制的，也就是说只需要枚举数据中给出的带宽（100＊100）个就可以了。然后每个机器都选择在这个带宽之上的最小费用。也就是枚举之后每个机器需要遍历厂商一次，所以总复杂度是100＊100＊100＊100，的却会超时。但是可以对上述算法做一些简单的优化。就是说，枚举带宽的时候，其实要保证带宽对于每个机器都是又相应的厂商的，也就是说如果枚举之前可以先去掉相当多不需要枚举的带宽。也就是说每句的带宽的下界变成了每个机器在不同厂商下的最小带宽的最大带宽，上界也有类似的变化。这个时间复杂度下的却可能超时，不过你可以试验下这个优化的效果。
# re: 我的金山 我来书写 回复 更多评论
2007-10-28 20:13 by
我刚刚在oibh得到了标程，
http://www.oibh.org/bbs/viewthread.php?tid=17328&pid=194920&page=1&extra=page%3D1#pid194920
(忘啦告诉你，我现在使用pascal语言)
在我对这题的苦苦求解中遇到一个人的bolg与你分享：
http://mrroach.blog.hexun.com/9013336_d.html
他应该是noip或noi的选手吧。
和你交流真的很愉快，不过我想我要暂时说再见啦。
如果这次noip我能拿到一等讲的话，我会转c++。那时我们会再“见面”的。
（只是如果）
就这样吧，谢谢你的帮助啦。