准备noi2009时的oj笔记
这是我在准备noi2009时在online judge上的做的部分题目. 从wordpress的修订版本记录来看, 主要记的应该是2008年9月至2009年5月做的题目, 每题都附有简短的算法描述. 另外, usaco曾写过第三章之后几乎全部题解, 但因为Rob认为题解对使用usaco的练习者有害, 所以后来全部删除. 这里曾作为blog的一个页面存在, 现在在online judge上做题没有以前那样的耐心写感受, 即使某天忽然想写专门的题解了, 那也一定是值得我写一篇单独blogpost的收获, 所以这个页面只是留下来做纪念, 不再更新, 发布时间仍保留在2008年.
btw, 我知道自己好没有恒心与毅力, 大家就不用留言鄙视我的题量了.
103 Traffic Lights
边有规律时通时闭的图的最短路,仍用dijkstra.
时间复杂度 O(n^2)
106 Traffic Lights
数学方法. 有两大难点, 一个是多种零的情况的讨论, 另一个是精度问题.. 教训, 整数除法对负数的取整结果和使用的C编译器有关, 所以不要忽视强制类型转换!!
109 Magic of David Copperfield II
一个魔术..找规律,构造
111 Very simple problem
求高精度数X的开方的整数部分.手动开方
时间复杂度 O(T^2),其中T为X的位数
114 Telecasting station
求加权平均数
时间复杂度 O(nlogn)
121 Bridges painting
WindyWinter已经写的很详细了. 不同的连通块分开处理. 对于一个特定的连通块, 分根有一个孩子还是一个以上的孩子两种情况来讨论即可. 我两次都是想着想着就绕进去了.. 做题时脑子要清楚.
时间复杂度 O(n+m)
122 The book
好麻烦的一道构造题. 构造一个哈密顿回路, 由于每个点至少与剩下的点中的一半相邻接, 因此可以利用一个图论中的定理在多项式时间复杂度内构造出一个回路. 构造方法可以简述为 构造链 – 构造圈 – 拆成链.
1. 尽可能在当前构造出的链的两端加点.
2. 不能加点时, 由每个点的邻接点个数可知, 链长至少为(N+3)/2. 链中有两端点的所有邻接点. 因此, 由抽屉原理可知, 必定存在点i, 满足i与链尾有边, i+1与链首有边. 于是拆开 i 和 i+1 之间的边, 连接 i 与链尾, 连接 i+1 与链首, 构造出一个环.
3. 如果此时所有点都已经在一个环内, 则程序结束. 否则, 找环中某个点k, 使其与某不在环中的点有边相连, 同时在这个位置打破环.
4. 回到第一步.
写的时候还是有些晕, 所以花了很长时间写代码, 倒是没怎么调试.
时间复杂度 O( n^2 )
124 Broken line
计算几何,向右水平无限延伸,计交点个数
时间复杂度 O(n)
125 Shtirlits
搜索题, 数据范围很小, 随便加个剪枝就ac了. 开始以为3*3的格子中最坏只需要1~5五个数字就够了, 明明需要九个…
131 Hardwood floor
简单状态压缩
133 Border
排序
时间复杂度 O(nlogn)
136 Erasing Edges
大胆去做就可以过. 这道题的评测只是让你找到两组各n个数, 使这n个数之间两两的平均数等于给定值. 以x坐标为例.
a1+a2=2*x1, a2+a3=2*x2, … , a(n-1) + an = 2 * xn
确定一个数其他的数字跟着就出来了.
当n是奇数时, 2*xn-2*x(n-1)+2*x(n-2)-…+2*x1 = 2 * a1, 所以一定有解.
当n是偶数时, 2*xn-2*x(n-1)+2*x(n-2)-…-2*x1 = a1 – a1, 所以当方程左边为零时有无数多组解, 可以给a1任意值计算, 否则无解.
时间复杂度 O(n)
138 Games of Chess
我想到图论方面去了, 从amber牛的题解中知道还是构造.. 总的比赛场数显然是所有人的比赛次数之和的一半, 记为m. 因为一定有解, 所以任何一个人的比赛数不会超过m/2 ( 根据抽屉原理和一个人不能自己跟自己比赛 ). 我们可以把所有人按比赛场数的多少从大到小排序( 防止只有一场比赛的人中断比赛列表 ), 然后把他们依次填入比赛列表, 优先选择他们会赢, 当只剩一次比赛时选择他们会输, 再用剩余没有填入的人将比赛列表填满即可.
时间复杂度 O(n)
139 Help Needed!
见http://dqfind.com/blog/archives/491.
141 Jumping Joe
将题目中的式子变一下形就得到A*x1 + B*x2 = P. 因此, 只要找到满足方程的A, B, 且 | A | + | B | 与 K同奇偶且不大于K即可. 再通过一定的调整就可以得到题目的解了.
时间复杂度 O(nlogn)
142 Keyword
给定一个由’a'和’b'组成的字符串T, 求一个最短字符串s使s不是T的子串.
T的长度不超过50000, 因此我们可以知道s的长度不超过19 ( 长度为19的子串有2^19 > 50000 ). 这样问题就简单了, 只要枚举s的长度, 找一个不在T里出现的字符串s即可.
时间复杂度 O(n)
143 Long Live the Queen
简单的树型dp. f[i]表示以i为根的子树中加上i所能得到的最大利润, f[i]=profit_of_i + sum ( f[ j ], j是i的孩子且f[j]>0 ). 注意答案可能是负数.
146 The Runner
就是很简单的累加然后”取余”(被除数是浮点数),运算过程中可乘以10^4以消除小数点.但是发现读入带四位小数的浮点数就会出现误差. 所以只好按字符串读入数据,然后将整数部分和小数部分分别处理. 循环部分读入用c风格,iostream会导致超时. (居然要用”%I64d”而不是”%lld”, sgu的评测环境是windows?)
148 B-Station
可以说是模拟, 但需要一些技巧. 先统计出从i..j共有多少水, 然后设cut数组, 二分找到如果想使第i层自然跨掉, 至少需要从哪一层炸起, 并在这一层的cut值中加上第i层的建造费用.
我们只需要从第n层到第一层枚举, 每到一层就加上该层的p[i]并减去cut[i](即前面的部分楼层不需要再人工炸掉), 并记录最小值即可.
时间复杂度 O(nlogn)
151 Construct a triangle
用中线定理算出第三边的长. 将A固定在原点, B放在x轴, A和B的位置就很容易确定了. C是以A和B为圆心, 两个半径已知的圆的交点, 联立两圆求出两圆交点连线( 易知它与x轴垂直 ), 得到C的横坐标, 再用勾股定理算出它的纵坐标即可. 注意这个三角形的面积可以为零, 因此在无解的判断中要去掉等号.
152 Making round
我开始没明白题意. 题意是说让你把每个数占总数的百分比算出来, 百分比可以通过上入或下舍成为整数( 不一定是四舍五入 ), 要求百分比总和等于100. 所以..模拟就行了.
153 Playing with matches
动态规划的方程很容易想到, 但是n的值太大了. 我们发现每一个状态的胜负最多只和之前九个状态的值有关, 于是我们可以把这九位压成一个数, 不断递推, 直到出现重复, 这时便出现了一个循环, 可以很快求出n个火柴时的状态. 这样不同的状态数最多只有2^9-1=511种.
时间复杂度 O( B*m*k ), 其中B是不同状态的个数.
154 Factorial
数学问题.找n!中因子5的个数即是末尾0的个数.注意除5^k时k应大些(如14)
时间复杂度 O(logANS)
160 Magic Multiplying Machine
m的值很小, 于是我们可以维护一个f[i]表示i能不能拼出来, 每加进一个新数, 用现有的f[i]去和新数相乘得到更多可以拼出的数, 然后找一个最大的输出. 看成相加了, 交了n次都是wa on test 1, 囧..
163 Wise King
简单数学题
时间复杂度 O(n)
165 Basketball
逐步转化问题, 详见朱晨光2004年国家集训队作业.
时间复杂度 O(nlogn)
168 Matrix
发现取值范围是一个梯形,预处理一下就可以了
时间复杂度 O(nm)
169 Numbers
好玩的数学分析,发现满足条件的数都是11111…11*形的
时间复杂度 O(1)
171 Sarov zones
拿到题目就想到二分图匹配, 发现时空复杂都太高后发现只要贪心就可以了. 将所有人按重量由大到小排序, 再按这个顺序找到q
时间复杂度 O( mlogm + nm ), n是学生的总数, m是组的个数.
174 Walls
一个平面上,在线地建立一些墙, 当某一个墙与前面某些墙一起构成了一个封闭的平面, 输出这个墙的编号. 可以用哈希表加并查集解决, HASH函数随便设计, 主要用于查出某一个点在并查集中的序号, 然后对于每一个墙, 判断其两个端点在不在一个集合内, 若在, 说明构成了一个封闭平面, 若不在, 则把这个端点合并. SGU很不稳定, 这道题我交好多遍, 用同一个程序, 一会儿对, 一会儿错, 搞不懂.
时间复杂度 O(M), 有一个不算很大的系数
176 Flow construction
求有上下界的网络最小流, 建议先做194. 加一个t->s无穷大的边, 检查可行性, 记此时从s流出的流大小为g, 然后求 t->s 最大流 f 以求出正向最小流, 注意反向最大流不可超过g, 则答案为 g-f.
177 Square
一个正方形,不断的染色. 统计白色块面积.先建了n棵线段树,严重超时.后用二维线段树.
时间复杂度 O(mlongn)
178 Chain
每拆一个长度为L的chain, chain就变成1, x, L – x – 1这样三段, 如果拆k次, 则拆得k个长度为1的和k+1个长度不定的链. 为了不浪费链, 长度不定的链中最短的长为k+1, 次短的长2*(k+1), 然后是2*2*(k+1), 以此类推. 则拆k次最多可以拼出长为k+(k+1)*( 2^(k+1) – 1 )长度的chain. 所以我们只要枚举k直到所能拼出的最长chain大于n为止. 这个..对我来说有些难想到.
时间复杂度 O( logN )
183 Painting the balls
动态规划. 用 f[i][j] 表示最后一个选的是第i个, 倒数第二个是第i-j个, 则 f[ i ][ j ] = min ( f[ i - j ][ k ], k到i的距离不超过m ). 这样做时空均超. 改用f[i][j]表示最后一个选i, 并在i-j…i-1中选一个做倒数第二个, 则f[ i ][ j ] = min ( f[ i ][ j - 1 ], f[ i - j ][ m - j ] + p[ i ] ). 用滚动数组可以将空间复杂度优化到 O ( M^2 )
时间复杂度 O( n * m )
186 The chain
题意好难懂: 大概是说有n条链子, 每个链子上有若干个扣, 一个人每分钟可以解开一个链上的扣并用此扣链上任意两个链, 问最少要几分钟可以把所有链合并成一个链. 我用贪心, 每次解开最短的链上的一个扣并链上两个最长的链, 注意n=0的情况.
188 Factory guard
模拟题. 头晕, 在跨过0的地方相遇的条件总是表述不清楚, 其实就是只要两个人相向距离小于等于两人速度的绝对值的和就能相遇.
时间复杂度 O( N^2 * T )
190 Dominoes
将棋盘黑白染色, 根据颜色不同构成二分图再求最大匹配, 若能覆盖全部未删除的点, 则有解. ( 敲完就交, 一次ac, 最近几周来最有手感的一道题 ;) )
时间复杂度 O( N^4 )
193 Chinese Girls’ Amusement
如果跳跃x次后再次回到1, 则xk mod N = 0, 且x是满足此式的最小的自然数. 因此可以想到要让每个人都被点到, 则必须让x=n, 即N和k互质. 问题转化成求不超过N / 2的最大数k, 使N和k互质. 分情况讨论:
当N是奇数时, 由(N-1)与N互质可知(N-1)/2与N互质, (N-1)/2即为答案;
否则, 当N/2是奇数时, ( N, N / 2 – 2 ) = ( N / 2 – 2, 4 ) = 1, ( N / 2 – 2 )即为答案;
否则, 即N/2是偶数时, ( N, N / 2 – 1 ) = ( N / 2 – 1, 2 ) = 1, ( N / 2 – 1 )即为答案.
194 Reactor Cooling
求有上下界的网络可行流. 对图不做任何修改, 直接套用判断有上下界网络流可行性的标程就可以了.
195 New Year Bonus Grant
给一棵树, 求最大匹配的个数. 树型DP很容易想到. 但居然贪心就可以了. 从叶子开始选发奖金的, 能选就选即可. 一个结点如果没被选, 那么它的孩子和父亲必定都已经被匹配了. 这时候如果拆掉父亲的自然是少一个多一个结果不变, 拆掉孩子的话, 那么孩子的孩子又没被匹配, 而匹配是从下往上进行的, 所以孩子的孩子肯定无法再进行匹配, 所以仍是少一个多一个结果不变.
时间复杂度 O(n)
196 Matrix Multiplication
给定一个矩阵A, 求A的转置矩阵B( 即b[ i, j ] = a[ j, i ] )与A的矩阵积的各元素之和. 根据矩阵乘法的运算法则, 发现答案其实就是B的每一列和的平方的和, 即A的每一行和的平方的和. 也就是将输入矩阵每一行i中”1″的个数统计出来记为c[ i ], 答案就是 c[ 1 ] * c[ 1 ] + c[ 2 ] * c[ 2 ] + … + c[ n ] * c[ n ].
时间复杂度 O( M + N )
197 Nice Patterns Strike Back
很容易看出是矩阵优化的状态压缩DP. 头一次用矩阵优化dp.
时间复杂度 O( m^3logn )
199 Beautiful People
先按第一个数据为第一关键字升序, 第二个数据为第二关键字降序排序, 把第一数据一样的看作一类, 则题目要我们求由不同类组成的按第二个数据得到的最长上升子序列. 套用经典的最长不下降子序列O(nlogn)算法就可以了.
时间复杂度 O( NlogN )
203 Hyperhuffman
求一篇文章用哈夫曼树编码后的长度. 数据排好了序, 因此可以再用一个队列, 每次取两个队列中较小的, 和加进answer, 并加到新队列的队尾. 原队列空了之后, 每次从新队列队首取两个, 再合并, 直到新队列中只剩一个元素即可.
时间复杂度 O( n )
207 Robbers
我想了个dp+贪心. f[ i ][ j ]表示到 i 个人用掉 j 个金块, 则f[ i ][ j ] = f[ i - 1 ][ j - k ] + 第 i 个人拿k个金块后的unfairness. 时间复杂度太高, 但想到这个k不用枚举太多, 大概在x[ i ] / y * m周围枚举三四个数就可以了. 再加个滚动数组降低空间复杂度就可以了. 看了一下Amber牛的, 先给每个人下取整的x[ i ] / y * m个金块, 然后按与期望获得的误差大小排序, 按误差由大到小多给一块金块就可以了. 我真脑残啊..
时间复杂度 O( nlogn )
210 Beloved Sons
按国王对儿子的喜爱顺序对王子们排序, 易知应该优先满足更受喜爱的王子. 匹配用类似KM算法的过程就可以了.
220 Little Bishops
n象问题. 动态规划. 把棋盘黑白相邻的染色, 相邻的两个格子染不同的颜色. 然后发现染白色的格子与染黑色的格子没有关系, 所以可以把两种格子分开处理. 以黑色为例. 把棋盘旋转45度, 则从第1行开始, 黑色方格的列数为1, 3, 5, 7, … , 7, 5, 3, 1. 可以把这些行等价的换成1, 1, 3, 3, 5, 5, 7, 7, … 然后每行只能放一个棋子, 每放一个棋子, 下面的行就少一个放棋子的选择. f[ i ][ j ]表示前i行放j个象. 方程为 f[ i ][ j ] = f[ i - 1 ][ j ] + f[ i - 1 ][ j - 1 ] * ( r[ i ] – j + 1 ), 即第i行不放棋子和放棋子两种选择, 其中r[ i ]为第 i 行的格子数目. 注意答案是int64型.
时间复杂度 O( nk )
221 Big Bishops
同220. 注意答案是高精度数字.
222 Little Rooks
记忆化搜索.
时间复杂度 O(n^2 * 2^n)
224 Little Queens
N皇后问题. 朴素搜索.
226 Colored graph
BFS. 注意两点之间可能有多条不同颜色的边.
时间复杂度 O(n^2)
230 Weighings
用比较信息构图, 拓扑排序即可. 注意可能有重边.
231 Prime Sum
注意到如果两个素数相加得素数, 则其中之一必为2 ( 否则相加为偶数 ), 问题就简单了.
236 Greedy Path
求最优比率环. 可以参考最优比率生成树的解法, 使用二分枚举答案 k, 然后构造 (k * time – cost) 为边的图, 用 bellman-ford 找负环, 如果存在负环则方案可行, 增大比率即可.
249 Matrix
先考虑一维情形.
n = 1时, 答案 000 001
n = 2时, 答案 000 001 011 010
n = 3时, 答案 000 001 011 010 110 111 101 100
可以发现, n每增加1, 新增加的就按把前面的逆序, 然后在新增加的位上置1.
类似的处理二维情形, ans[ i ][ j ] = f[ i ] << m + f[ j ], 其中f[ i ]是一维情形是第i个数.
摘自amber牛题解.
259 Printed PR
贪心. 优先做需要较长时间来送货的.
269 Rooks
先将各行的列数按从小到大的顺序排序. f[ i ][ j ]表示前i行放j个棋子, 则f[ i ][ j ] = f[ i - 1 ][ j ] + f[ i - 1 ][ j - 1 ] * ( s[ i ] – j + 1 ), 其中s[ i ]是第i行的列数. 比较像220的解法. 答案要用高精度 ( 高乘低的高精度没注意低精度数字是0的情况, wa了n次 ).
271 Book Pile
给一堆书维护翻转和插入两种操作.用循环队列解决. 将顶上K本书放入队列中. ADD操作对应入队, ROTATE把front和rear换位即可.
时间复杂度 O(N+M)
274 Spam-filter
字符串处理. 有很多细节, 比如开头和结尾都不能有’.'( 即不能有空的word ), 这将导致wa on test 2; 不能有连续两个‘.’ ( 同样将产生空的word ); 不能用scanf读入字符串, 否则会忽略不该忽略的空白字符, 这将导致wa on test 3.. 考验耐心与认真.
275 To xor or not to xor
Amber牛的题解没看懂, 后来找到一个高斯消元的解决方法. 我们自然希望答案的64个二进制位上都是1, 但是情况不一定能得到满足, 于是我们要优先满足高位. 用f[ i ][ j ]表示 Ai 的第 j 位. 则第k个方程为
( f[ 1 ][ k ] * x1 ) xor ( f[ 2 ][ k ] * x2 ) xor ( f[ 3 ][ k ] * x3 ) xor … xor ( f[ n ][ k ] * xk ) = 1
共计m个方程.
我们可以用xor操作消元. 从高位开始消. 最后把消元后仍能满足左右相等的方程所表示的位标记为1即可.
276 Andrew’s Troubles
模拟. 没说的.
282 Isomorphism
群论. 见http://dqfind.com/blog/archives/491.
296 Sasha vs. Kate
贪心. 从最高位开始确定要留下的数字(即可选数字中最大的), 并删去要留下之前的. 比如12934删去三个数字, 就先删12使9占最高位, 接着删去3使4占次高位.
时间复杂度 O(k^2)
297 Fair-play
求sum(si)%n.
时间复杂度 O(m)
299 Triangle
排序, 再逐一枚举相邻三个边即可.
326 Perspective
显然球队1最多赢得 r[1]+w[1] 场比赛, 记为X. 将比赛作为点集A, 球队作为点集B, 添加源点s, 汇点t. 与球队1有关的比赛不列在图中 (显然这些比赛的赢家是球队1). 如果i, j之间有 rem[i][j] 场比赛, 则从 s 向表示 i, j 之间比赛的结点 k 连一条边, 容量为 rem[i][j], 从 k 向表示球队 i 和球队 j 的结点各连一条边, 容量为无穷大. 从代表每个球队 i 的结点到汇点 t 连一条边, 容量为 X-w[i](如果该容量为负则可以直接判定无解). 做从 s 到 t 的最大流, 如果最大流等于从源点 s 出发的边的容量之和则有解, 否则无解.
1 TEST
模拟.
2 PRIME1
生成40000以内素数表, 再对每个输入范围内的数字一一判断.
时间复杂度 O(t*(n-m)*k), 其中k是一个不到40000的小常数. 实际很快, 我的程序2.x秒就出解了.
5 PALIN
一道构造的题目. 将数字的前半部分对称的贴到后面, 如果不符合条件则给最中间的数加1再做一次.
时间复杂度 O( K * len ), 其中len是数字串的长度.
51 TOUR
分析后发现如果a能赢b就连一条a->b边, 得到一个图, 图中所有能到其他所有点的点即为满足的点. 暴力做会超时, 对图求一次强连通分量, 如果存在唯一一个入度为0的连通块则答案为连通块内点的个数, 否则答案为0.
时间复杂度 O( n + m )
53 KAMIL
乘法原理解决.要求代码尽可能短, 我用c++写了一个229字节的代码, 去掉了所有空白字符. 据yangyi巨牛的表格, 此题用PERL, RUBY等语言解决得分更高.
时间复杂度 O( L ), L是输入字符串长度.
54 JULKA
简单的解方程, 加上高精度运算. 第一次写操作符重载, 爽..
58 PICAD
排序, 然后统计.
66 CRSCNTRY
求两串的最长公共部分, 就是位置不一定要连续. 简单的二维dp, 没有任何陷井.
