Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Ural Problem Set Volume 1: 1000-1099
发信站: 哈工大紫丁香 (2002年08月13日18:51:01 星期二), 站内信件

Ural Problem Set Volume 1: 1000-1099
题号 标题 难度系数 算法
1000 A+B Problem 10% 直接加
1002 Phone Numbers 50% 动态规划或最短路
1003 Parity 70% 区间减法
1004 Sightseeing trip 60% 最短路
1005 Stone Pile 30% 动态规划或搜索
1006 Square Frames 35% 模拟
1007 Code Words 30% 模拟
1008 Image encoding 30% 广度优先搜索
1009 K-Based Numbers 20% 递推或枚举（数据规模小）
1010 Discrete Function 40% 贪心
1011 Conductors 25% 搜索
1012 K-Based Numbers 30% 递推
1013 K-Based Numbers 33% 递推
1014 The Product of Digits 30% 贪心
1015 Test the differences 35% 模拟
1016 A cube on the walk 50% 搜索或者最短路
1017 The Staircases 30% 递推（母函数）
1018 The Binary Apple Tree 50% 动态规划
1019 A Line painting 40% 离散化处理
1020 Rope 45% 一般的计算几何问题
1021 Sacrament of the sum 40% 动态规划
1022 Genealogical Tree 30% 拓补排序
1023 Buttons 50% 动态规划
1024 Permutations 25% 置换（和题目名字一样）
1025 Democracy in Danger 20% 贪心
1026 Questions and Answers 40% 快速排序
1027 D++ again 40% 字符串处理
1028 Stars 75% 线段树
1029 Ministry 55% 动态规划（注意优化）
1030 Titanic 60% 计算几何（注意精度！）
1031 Railway Tickets 45% 动态规划
1032 Find a mutilple 55% 同余问题
1033 Labyrinth 30% 搜索、遍历
1034 Queens in peaceful positions 35% 搜索
1035 Cross-sitich 60% 欧拉路径问题
1036 Lucky tickets 50% 递推
1037 Memory Management 55% 模拟（注意优化）
1038 Spell Checker 45% 字符串的操作及统计
1039 Anniversary party 40% 树的动态规划
1040 Airline company 55% 搜索
1041 Nikifor 85% 线性代数问题
（过了，但怀疑算法不对）
1042 Central Heating 50% 解线性同余方程组
1043 Cover an Arc. 58% 计算几何
1044 Lucky tickets 40% 递推
1045 A funny game 55% 搜索
1046 Geometrical dreams 88% 很复杂的计算几何
1047 Simple calculations 30% 数学题，解方程吧！
1048 Superlong Sums 48% 高精度加法
1049 Brave ballonists 30% 模拟
1050 Preparing an article 63% 比较麻烦的字符串处理
1051 A simple game on a grid 60% 数学杂题
1052 Rabbit Hunt 28% 简单的计算几何
1053 Pinocchio 32% 求最大公约数（题目意思不明）
1054 Hanoi Tower 50% 数学问题
1055 Combinations 40% 数学问题
1056 Computer net 55% 动态规划
1057 Amount of dergess 53% 数学问题
1058 Chocolate 85% 复杂的计算几何问题
1059 Expression 20% 简单的打印问题
1060 Flip game 35% 我搜索，过了
1061 Buffer Manager 45% 模拟
1062 Triathlon 83% 复杂的不等式问题
1064 Binary Search 48% 搜索
1065 Frontier 75% 动态规划
1066 Garland 40% 数学问题
1067 Disk Tree 45% 模拟或排序
1068 Sum 20% 简单的加法题
1069 The prufer code 50% 构造
1070 A local time 60% 考虑要周全
1071 Nikifor - 2 45% 搜索
1072 Routing 40% 最短路问题
1073 A square problem 50% 动态规划
1074 A very short problem 58% 模拟、判断
1075 A thread in the space 65% 麻烦的计算几何
1076 Trash 50% 二分图的最大权匹配
1077 Travelling Tours 60% 图的遍历
1078 Segments 40% 动态规划
1079 Maxium 50% 数学问题
1080 Map coloring 35% 深度优先搜索
1081 Binary Lexicographic Sequence 40% 数学问题
1082 Gaby Ivanushka 15% 没有算法，直接输出答案
1083 Factorials!!! 25% 简单的数学计算
1084 A goat in a kitchen garden 35% 简单的计算几何
1085 Meeting 55% 最短路
1086 Cryptography 45% 数学问题
1087 The time to take stones 48% 递推
1088 Ilya Murumetz 33% 二叉树的性质
1089  verification with a vocabulary 50% 字符串处理
1090 In the army now 60% 平衡二叉树
1091 Tmutarakan exams 57% 运用容斥原理
1092 Transversal 75% 贪心
1093 Darts 65% 立体解析几何
1094 E-screen 40% 字符串处理
1095 Nikifor - 3 45% 同余问题
1096 Get the right route plate! 40% 广度优先搜索
1097 Square country - 2 63% 离散化处理
1098 Questions 48% 字符串处理
1099 Work scheduling 60% 图的最大基数匹配
　
对于上面算法的一些说明
1002：由于动态规划算法要对字符串做多次匹配检查，所以应该先用一个图存储字符串
的匹配情况，然后处理。
1003：这个问题用的是区间减法。所谓区间减法，也就是当我们知道了[a,b]的情况，[
c,b]的情况，那么我们就可以推算出[a,c]的情况。
1004：这个题目我是用m次dijkstra做的，就是枚举所有的边。每当找到一条边，就把它
去掉，然后搜索一次这条边的两个顶点之间的最短路（用dijkstra）。不过这种办法的
效率很低 :(
1006：这个模拟其实很简单：就是找到一个框框之后，把它拿掉，被它覆盖的地方标上
?。?可以代表任何东西。当我们只剩下?和.的时候，工作完成！
1014：注意一个恶心数据：输入0的时候，你可得输出10啊！
1016：我强行构图，最短路做的 :)
1018：标准程序有问题！他认为一个不含苹果的枝不存在！因此“丢掉了”一大堆东西
……看看Discuss吧。
1024：就是求最小公倍数啦！
1029：典型的动态规划问题。按“层”划分阶段。但是值得注意的是，同一层之间也是
可以规划的，因此这个题目可以说是一个“双重规划”。
1032：这是我认为不错的一道题。最开始我用时间复杂度O(N^2)的动态规划，勉强过了
。后来发现这个题目有如下性质：一定存在一个满足条件的连续数列！理由如下：我们
用Sum[k]记录数列的前k个元素之和mod n的值。如果Sum[k]=0，搞定。如果不为0，由抽
屉原则，必存在Sum[a]=Sum[b],a<>b。不妨假设a<b，那么我们选择序列a+1到b，一定满
足要求。
1035：这个题目是欧拉路径问题。方法嘛……先求图的所有连通分枝，对于每个连通分
枝，求出每个定点“正面度”和“反面度”差的绝对值，把这些绝对值相加，设和为n。
如果n=0，那么这个连通分枝可以1笔画。如果n>0，那么需要的笔画数为n div 2。
1040：这个题目的搜索本来有很多可以优化的地方，但是……由于数据很简单（连一个
NO都没有，我faint），随便搜索一下，竟然过了！$#$#@$%@%@$%#@%$#%#@%$@……
1042：这也是一个不错的题目（可是数据太简单）。首先，我们可以证明不可能选出两
组人，使得这两组人完成的工作相同。然后我们就会发现，工程师有2^N种选法，开关有
2^N种状态。而选法和状态必然一一对应。因此——解方程！
1050：放心大胆的开数组存吧！注意一点：在endofinput的时候别忘了匹配最后一个自
然段的引号啊！
1055：这个题目我用的是筛法。通过一次筛法，即可确定C(m,n)的所有质因子，个数自
然就求出来了。
1058：原先我误以为通过多边形重心的直线一定平分多边形面积。后来经过简单的计算
，否定了这种方法。但是，我们可以证明最佳的分割线一定和某两条夹角相等。因此我
们可以枚举两条边，求出和这两条边夹角相同的直线（注意，有两条），然后平移这条
直线，直到平分多边形面积为止。平移的方法有多种，我采取的是比较精确的二分法（
据说步长0.1移动也可以，我faint）。
1062：这是一个相当麻烦的题目。首先，若要第i个选手“击败”第j个选手，可以列出
不等式：L1/(v1i)+L2/(v2i)+L3/(v3i)<L1/(v1j)+L2/(v2j)+L3/(v3j)。显然我们可以通
过换元的方法把L3消去。这样，我们就可以得到形如a*L1+b*L2+c<0（>0）的不等式。而
我们要判断i是否可以取胜，必须解出所有n-1个上面说到的不等式，求出其交集。注意
到这个不等式的几何意义是一个半平面，仅此求交集实际上就是用这些不等式代表的直
线去“切割”一个平面（第一象限平面），如果平面被“切没了”，那么说明不等式组
的解集为空，第i个选手不可能获胜。否则第i个选手就可以获胜。
1066：我的算法其实很笨：可以证明必有一个灯的“海拔高度”为0。因此我们可以枚举
这个高度为0的灯，选取最优值，问题解决。
1076：求二分图的最大权匹配有两种常用的方法，一种是用最小费用流算法，还有一种
是KM算法。一般而言，后者的效率更高。
1077：这个题目采用的是所谓“找桥”算法。也就是构造这个图的生成树，然后枚举不
在生成树中的边。每一条边对应一个环。
1082：可以证明数列1,2,3,4,...,n就符合要求。直接输出。
1090：这个题目应该使用排序二叉树。因为用表的数据结构，难免较大范围的数据移动
，因此速度比较慢。而使用排序二叉树则可以很好的解决这个问题。所谓的平衡二叉树
，就是深度尽可能小的排序二叉树（也就是尽可能的接近完全二叉树）。这样，我们可
以把时间复杂度从O(N^2)降低到大约O(N*log2(N))。 构造平衡二叉树的方法是引入平衡
指数。具体方法参见清华大学《数据结构（第二版）》。
1093：这个题目的关键是写出靶子所在平面的“点法式”。假设平面过点(x1,y1,z1)，
法向量是(Nx,Ny,Nz)，那么平面的方程为：Nx(x-x1)+Ny(y-y1)+Nz(z-z1)=0。得到这个
式子之后，把运动方程中的x,y,z带入平面方程，就得到一个关于t的二次函数。接下来
的问题就比较简单了……
1099：这个题目的标准方法是“带花树”，当然，用bfs也可以。具体的匈牙利算法比较
复杂，大家有兴趣可以参阅图论有关书籍。
下一卷

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]