Algorithm 版 (精华区)

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

Ural Problem Set Volume 2: 1100-1197
题号 标题 难度系数 算法
1100 Final Standings 50% 反复统计
1101 Robot in the field 30% 表达式求值
1102 Strange Dialog 60% 动态规划或语法图
1103 Pencils and Circles 65% 不错的几何问题
1104 Don'k ask a woman about her age 55% 同余问题
1105 Observer's coloring 75% 构造法
1106 Two Teams 40% 贪心
1107 Warehouse Problem 50% 同余问题
1108 Heritage 60% 贪心
1109 Conference 40% 二分图的最大基数匹配
1110 Power 25% 求幂的余数
1111 Squares 60% 计算几何
1112 Cover 43% 动态规划
1113 Jeep 30% 倒推的方法
1114 Boxes 45% 组合数学问题
1115 Ships 50% 深度优先搜索
1116 Piecewise constant function 40% 模拟
1117 Hierarchy 50% 树的性质
1118 Nontrivial numbers 40% 搜索
1119 Metro 45% 动态规划
1120 Sum of sequential numbers 40% 解方程
1121 Branches 45% 统计问题
1122 Game 40% 我用的搜索
1123 Salary 35% 贪心方法
1124 Mosaic 50% 一笔画问题
1125 Hopscotch 48% 模拟
1126 Magnetic storms 55% 哈希排序
1127 Colored bricks 35% 简单统计
1128 Partition into groups 58% 贪心方法
1129 Door painting 45% 贪心方法
1130 Nikifor's walk 55% 构造法
1131 Copying 30% 数学方法
1132 Square Root 65% 标准算法！
1133 Fibonacci Sequence 50% 数学计算
1134 Cards 45% 模拟
1135 Recruits 40% 直接计算
1136 Parliament 35% 树的遍历
1137 Bus Routes 40% 递归打印
1138 Integer Percentage 50% 动态规划
1139 City Blocks 47% 离散统计
1140 Swamp Incident 45% 贪心
1141 RSA Attack 55% 标准算法！
1142 Relation 45% 组合问题。用递推求
1143 Electric Path 55% 动态规划
1144 The Emperor's Riddle 90% 动态规划（？？）
1145 Labyrinth 60% 递归
1146 Maximum Sum 40% 动态规划
1147 Shaping Regions 55% 离散化处理
1148 Building Tower 85% 组合数学难题
1149 Sinus Dance 30% 简单循环输出
1150 Digits 40% 统计+计算
1151 Radiobeacons 65% 统计
1152 The False Mirrors 40% 深度优先搜索
1153 Supercomputer 50% 高精度计算
1154 The contest of mega 50% 统计+求最值
1155 Troubleduons 55% 贪心
1156 Two days 50% 动态规划
1157 Young Tiler 45% 搜索就行
1158 Censored! 80% 麻烦的递推
1159 Fence 65% 计算几何问题
1161 Stripies 45% 贪心方法
1162 Currency Exchange 55% 最短路算法
1163 Chapayev 80% 麻烦的动态规划
1164 Fillword 30% 直接统计
1165 Subnumber 70% 搜索
1167 Bicoloured Horses 50% 动态规划
1168 Radio Stations 55% 搜索
1169 Pairs 60% 构造问题
1170 Desert 65% 计算几何
1171 Lost in Space 60% 记忆化搜索
1172 Ship Routes 45% 组合计数问题
1173 Lasy snail 50% 构造
1174 Weird Permutations 35% 构造
1175 Strange Sequence 60% hash表/数学方法
1176 Hyperchannels 50% 欧拉回路
1177 Like Comparisons 60% 动态规划
1178 Akbardin’s Roads 45% 计算几何
1179 Numbers in Text 50% 简单统计
1180 A stone game 40% 归纳
1181 Cutting a painted polygon 50% 构造（贪心）
1182 Team them up 55% 动态规划
1183 Brackets sequence 45% 动态规划
1184 Cable master 45% 二分查找
1185 Wall 40% 计算几何
1186 Chemical reactions 50% 字符串处理
1187 Statistical trouble 55% 字符串处理（读懂题目很重要）
1188 Library 65% 搜索
1189 Pairs of integers 50% 数学问题
1190 Chocolate tile 40% 统计与处理
1191 Cops and Robbers 40% 模拟
1192 Ball in dream 45% 数学问题（简单的等比数列求和）
1193 Queue to Exam 50% 统计
1194 Handshakes 30% 简单计算
1195 Ouths and Crosses 45% 博弈问题
1196 History Exam 40% 统计
1197 Lonesome knight 35% 简单统计
　
对于上面算法的一些说明
1100：由于待排序的元素个数相当多（最多150000个），这些元素值的分布却很集中，
只有1到100。因此，常规的不稳定的排序方法在这里是不适用的。我们应该反复对这些
元素进行统计，第一次统计值为100的，第二次统计99的……这样一来，算法的时间复杂
度大约是M*Max(N)，完全可以接受。
1102：对于这类匹配问题，最容易想到的方法便是动态规划。但是由于动态规划在滚动
的时候涉及到一个指针和取模的运算，而且对于给定的字符是一一匹配的，因此效率比
较低。较好的方法是所谓“语法图”的办法。可以先把所有的“单词”分解为“词根”
，然后用一个图表示词根之间的相互关系。因而我们可以把对字母的操作转化为对词根
的操作。这样一来，判断的效率自然提高不少。
1103：这是一个相当不错的几何问题。首先，我们可以过两个点取一条乘托直线（即所
有不在线上的点都在线的同侧），设这两个点为A,B。对于其他所有点Ki(i=1,2,...,n-
2)，我们求出角AKiB的大小。由于任三点不共线，任四点不共圆，因此这些角AKiB的大
小肯定不等。因此我们可以把这些角排序。又由于圆内角>圆周角>圆外角，所以假设大
小恰好位于中间位置的角为AKjB，则A,B,Kj即为所求。
1107：我们不难发现任何两个“相似”的集合除以(n+1)的余数一定不等。而商店又至少
有n个，所以……
1109：也是匈牙利算法，不过不涉及带花树，因此比较简单。
1111：值得注意的是，题目并没有说所有正方形的边都和x,y坐标轴平行。
1115：先把队列按长度排序，然后采用“双重深度优先搜索”即可。当然，这个题目还
可以用随机化算法。
1116：我们可以开一个大数组，模拟两次定义的情况，最后做统计即可。值得注意的是
，我们应该用数组的a到b-1元素表示区间[a,b)。
1124：我们把每个盒子看作一个点，如果盒子i里存在不属于这个盒子，而属于盒子j的
木块，我们就在i,j之间连一条有向边。那么我们只用统计一下这个有向图至少要用多少
笔才能画成（就是欧拉路径问题）。
1126：最好先建一个哈希表，然后记录数值的分布情况。然后每次在哈希表中检索即可
。
1143：这个题乍一看是NP问题。但是稍加思考我们不难发现，最优的路径一定不自交。
因此实际上这个题目是可以动态规划的。
1145：这个题目考察的主要是空间的优化。首先，我们应该用一个Byte存储8位0/1，这
样就可以把整个地图存储下来。然后，就可以用一个递归的过程搜索结果。递归的时候
同样要注意空间的优化。
1153：这个题目相当于求一个数x，满足1+2+3+...+x=m。即x(x+1)/2=m，x(x+1)=2m。又
因为x^2<x(x+1)<(x+1)^2，因此我们大可不必解方程，直接用x=Trunc(Sqrt(2m))就行了
。剩下的问题就是高精度开平方，建议采用二分求精的办法做。
1155：这是一个相当不错的题目，数学意味很浓。而解这个题目的核心是——染色法！
首先，我们可以把这个立方体的8个顶点染成红色和蓝色，要求与红色顶点相邻的必须是
蓝色顶点，反之亦然。然后，我们不难发现每次操作必然是同时改变红色顶点和蓝色顶
点中的粒子数量。所以假如一开始红色顶点中的粒子总数跟蓝色顶点中的不等，问题一
定无解——否则一定有解。有解的时候解的构造就比较简单了，大家自己动动脑筋吧！
 :p
1182：
    首先，我们分析一下分组的要求：
1、把所有的人分成2组，每组至少有1人；
2、每组之间的人两两认识。
    非常明显，如果存在两个人A和B，A不认识B，或B不认识A，那么A和B一定不能分在
同一组。因此，我们以人为结点重新构造一个图G。假如A和B不能分在同一组，那么就在
G中增加一条无向边(A,B)。这样，我们就得到了一个较为“单纯”的模型。下面我们对
这个模型进行简单分析。
    我们先研究G的一个连通分量K1。对于这个连通分量，可以先求出K1的生成树T1。对
于K1中的任意结点a，假如a在T1中的深度为奇数，我们就把a加入点集S1；否则我们把a
加入点集S2（S1,S2最初为空集）。显然最后S1,S2的交集为空。
    不难证明，如果存在不同结点p和q，p和q同属于S1或S2，而且G中存在边(p,q)，那
么要做到满足题目要求的分组是不可能的，应输出No solution。否则，我们就得到了连
通分量K1的唯一分组方案：分为S1,S2两组。
    对于G中的每个连通分量Ki，我们可以求出相应的S1i,S2i。最后，我们的目的是把
全部人分为2组。也就是说，对于i=1,2,3,...,m，我们必须决定把S1i中的人分到第1组
，S2i中的人分到第2组，还是做刚好相反的处理。由于题目要求最后两组的总人数差最
小，我们可以用动态规划的办法来确定究竟选取上面的哪种决策。
    不妨假设G中共有m个连通分量，记|S1i|=xi,|S2i|=yi(i=1,2,3,...,m)。我们用f[
i,j]表示把前i个连同分量分为2组，且这两组总人数差的绝对值恰好为j是否可能。如果
可能，f[i,j]=true；否则f[i,j]=false。初始条件是f[0,0]=true, f[0,x]=false(x=1
,2,3,...)。然后我们可以按照如下方法确定f[i,j](0<i<=m, j>=0)：
    f[i,j]= f[i-1, j-Abs(xi-yi)] or f[i-1, j+Abs(xi-yi)];
    当然，在求解的同时，我们可以记录路径。最后，res=min{i: f[m, i]=true}即为
最佳分组的人数差，而它对应的路径就是我们要求的分组方案。
上一卷    下一卷

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