随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

SGU 100 - 109 解题报告

100 A+B                                                测试题
101 Domino                                           图论:欧拉回路
102 Coprimes                                        数论:欧拉函数
103 Traffic Lights                                  搜索:广度优先搜索
104 Little shop of flowers                     动态规划:二维背包
105 Div 3                                               数学题
106 The equation                                  数论:扩展欧几里得
107 987654321 problem                       搜索:深度优先搜索
108 Self-numbers 2                               位压缩 + 二分枚举
109 Magic of David Copperfield II        模拟题


100 A+B

      测试题

101 Domino

      欧拉回路判定(度数判定+并查集) +  Fleury算法 + 无向图强联通判桥

       
      题意:给定N个多米诺骨牌,每个骨牌两端分别是两个06的数字,问能不能通过一种方法将所有骨牌排列起来,并且相邻的骨牌的数字相同,(骨牌可进行翻转),如果存在,要求输出路径。

      题解:这题的模型是经典的欧拉路问题,首先要判断这个图是否存在欧拉路径,对于连通的无向图G有欧拉路径的充要条件是:G中奇度数顶点(连接的边数量为奇数的顶点)的数目等于0或者2

    判是否连通,可以通过并查集或者dfs遍历图来解决。由于顶点只有7个,并查集集合很小,不需要压缩路径。奇度数顶点只需要记录一个数组,扫描一次即可。

       如果是一个连通图,并且奇度数的个数等于02,那么可用Fleury算法求解欧拉回路。

     传统求欧拉回路的算法为Fleury算法:

(1) 任取v0属于v(G),P0=v0;

(2) Pi=v0e1v1e2…eivi已经遍历,按下面方法来从E(G)-{e1,e2,…..ei}中任取ei+1 满足:

  (a): ei+1vi相关联:

  (b): 除非无别的边可供遍历,否则ei+1不应该为Gi=G-{e1,e2,….ei}中的桥.

(3) (2)不能再进行时,算法停止.

 

由于这题不一定有回路,所以第(1)步需要稍作修改。

(1) 取任意一个奇度数点v0属于v(G), P0=v0 (如果没有,则任意取);

(2) Pi=v0e1v1e2…eivi已经遍历,按下面方法来从E(G)-{e1,e2,…..ei}中任取ei+1 满足:

  (a): ei+1vi相关联:

  (b): 除非无别的边可供遍历, 否则ei+1不应该为Gi=G-{e1,e2,….ei}中的桥.

(3) (2)不能再进行时,算法停止.

 

具体做法就是:

(1) 不断从剩余的边集合中取边,直到所有边取遍,路径也就找出来了。

(2) 将当前的剩余边复制一份(反向边),目的是将无向图变为有向图,然后从P0开始进行一次DFS, u = P0, 并且标记它为根结点root

(3) 记录u的时间戳dfn[u]以及最小时间戳low[u]为当前时间time(全局计时变量)

(4) 对于u的相邻边(u, v):

  (a) 如果vu的父亲,并且是u第一次访问到v,则忽略;

  (b) 如果v未曾被访问,则(u, v)为一条前向边(树边),访问v, 进入(3), 访问完毕后:

       (i)如果v的最小时间戳low[v]小于等于u的最小时间戳low[u],那么更新low[u] low[v],说明v可以访问到u的祖先结点,即存在环。

    (ii)否则,说明v以及它的子孙没有向u的后向边,则表明(u, v)是一条割边,即桥,将它记录到cutE集合中。

  (c) 如果v已经被访问过,更新u的最小时间戳low[u] min( low[u], dfn[v] )

(5) P0的邻接边中取出一条不是cutE(割边)中的边E,如果所有邻接边都在割边集中,那么随便取一条邻接边E

(6) 从原图中删除边E(P0, v),更新P0 = v,重复(1)直到所有的边都被筛选出来。

102 Coprimes

      欧拉函数

      题意:给定N,求小于等于N并和N互素的数的个数。

      题解:欧拉函数。

      n = p1e1 p2e2 ... pnen (pi 为素数)

      那么小于n并且和n互素的数的个数为f = (p1-1)p1(e1-1) * (p2-1)p2(e2-1)*...* (pn-1) pn(en-1)


 
103 Traffic Lights

    贪心 + BFS

      
    题意:给定一个无向图G(V, E),图上的顶点Vi会变色(经过Tib时间变成蓝色,经过Tip时间变成紫色,循环往复),只有当两个顶点的颜色一样的时候,它们之间的路才能通行,通行的边上时间各不相同,问从起点到终点的最小时间。

      题解:贪心式的广搜。可以这样考虑,由于任意两个顶点之间的连通性取决于时间,因为时间不同,顶点颜色不同,导致本来 连通的边会变成不连通(当然,本来就不连通的边,也不会因为顶点颜色相同的那一刻变得连通),所以如果假设时间确定的情况下,我们是可以知道这个图的连通性的;还有一点,当我们来到一个顶点后,可以选择等待,并且等待的原因只有两个:

     1) 让当前顶点变色

     2) 让和当前顶点连通的点变色

    好让图的连通性变化,可以扩展更多的点。

     对于每个结点需要计算两个辅助函数:

     1、根据某个时间T计算当前结点的颜色。

     2、在当前时间T基础上计算出下一次变换颜色 的时间点。

 

     有了这两个函数就可以进行贪心式搜索了。

     1)起点进队。

     2)弹出队列首的一个元素,扩展它的邻接表。

     3)对于当前点u和与u连通的点v,利用1 判断它们在 当前时间 的信号灯颜色是否相同。

        a) 如果相同,则判断到下个点所用的时间是否最少(可能之前已经去过那个点),如果比之前优,入队。

        b) 如果不同,利用2 计算 当前点 下个点 最近的一次变换颜色的时间(这就是贪心所在了)。

            i) 如果两者时间相同,继续b,直到反复进行两次还是没找到,那么说明永远不可达(因为一共就两个颜色,如果他们经            过两次变换颜色还是一致,那绝对是真爱...)。

            ii) 如果时间不相同,取小的那个时间就是要等待的最近时间点,进入a) 的判断。

      4)搜索完毕,输出结果。
    这题需要保存路径,所以在每个结点上需要保存一个前驱结点,一次迭代就能把路径逆序求出来了。

 

104 Little shop of flowers

    动态规划

      
    题意:在一个N*M的二维矩阵aN个数之和保持最大,并且每行只能取一个,第i行取的数的列号j一定要大于i-1行的。

       题解:用dp[i][j]保存i*j这个子矩阵的最优值。

    那么状态转移方程为:

 

       a) i == 0

         i)  j == 0 (0,0)这个格子必须取, dp[i][j] = a[0][0];

         ii)  j != 0  dp[i][j] = max(a[i][j], dp[i][j-1]); (要么取当前这个格子,要么取前面某次的最优值)

      b) i != 0

         dp[i][j] = max( dp[i-1][j-1] + a[i][j], dp[i][j-1]); (当前格取与不取两种情况的大者)

      dp[n-1][m-1] 就是最后要求的答案,需要保存路径,每次状态转移的时候用一个数组将当前结点的前驱保存下来即可。


105 Div 3

      规律题

      题意:给定1, 12, 123, 1234, ..., 12345678910, ...这个序列的前N(N < 2^31)项,求其中能被3整除的数的个数。

      题解:数学归纳法。
       n % 3 == 2 时 2 * (n / 3) + 1 否则 2 * (n / 3)


106 The equation

      扩展欧几里得 + 区间求交

       题意:ax + by + c = 0  (x1<=x<=x2,   y1<=y<=y2) 求满足情况的(x,y)的解数。

       题解:首先对于ab分别为零的情况进行特殊判断:

      a = 0

            b = 0

               c  = 0

                  恒等式,方程解 (x2 - x1 + 1) * (y2 - y1 + 1)

               c != 0

                  无解

            b != 0

                  b*y + c = 0  ->  y=-c/b

                  如果c % b == 0并且y1 <= -c/b && -c/b <= y2

                        方程解 (x2 - x1 + 1)

                    否则

                        无解

      a != 0

            b = 0

                  a*x + c = 0  ->  x=-c/a

                  如果c % a == 0并且x1 <= -c/a && -c/a <= x2

                        方程解 (y2 - y1 + 1)

                  否则

                        无解

      否则当 a b 均不为0时,可采用扩展欧几里得求方程的一个可行解, 即线性同余方程:

         ax + by = -c

         如果 c | GCD(a, b),则方程有解,否则无解。

         c' = c / GCD(a, b)

         通过扩展欧几里得求得方程 ax + by = 1 的一个可行解 (x, y)

         那么ax + by = -c的解则是 (x*(-c'), y*(-c'))

         x 的解集合可以表示为 { X = x + k1 * b }

         y 的解集合可以表示为 { Y = y + k2 * a }

         Y = (-c - a * X) / b,于是有:
                   x1 <= x + k1 * b <= x2

                   y1 <=  (-C-A*x)/B - A*k1 <= y2
      问题转化成了两个关于k1的不等式求可行解的问题,可以转化成区间求交。得到的k1的可行解就是最后的答案个数,这里的k1为任意整数,所以在不等式判断左右区间的时候需要对左区间进行上取整,右区间进行下取整。

注意:在使用扩展欧几里得求解的时候,得到的xmod b,否则在后面的乘法计算中可能导致值很大而超过64位整数。

 107 987654321 problem

      深搜 + 排列组合

       题意:N位数中平方的最后几位等于987654321的数的个数。

       题解:利用dfs从最后面一位digit开始枚举0-9,模拟相乘后对应位的余数,如果和987654321中对应位不相符则不进行下一步搜索,枚举完后发现九位数的答案为8个解,小于9位数的解为0

       假设xxxxxxxxx 平方的后九位是987654321,那么对于N=14位数的答案为[A-B]这个区间中的所有数,那么根据乘法原理,N位数解的个数就是 9*10^(N - 10) * 8

      A = 10000xxxxxxxxx

      B = 99999xxxxxxxxx

108 Self-numbers 2

      二进制位压缩 + 二分查找


      题意:将一个数N的所有位数相加再加上本身可以得到一个数N',如果一个数不能通过这种方式得到,那么它称为self-number,需要求N = 10^7以下的第Kself-number以及小于Nself-number的总数。

      题解:基本思路是用一个10000000的数组标记对应的数是否是self-number

遍历i 属于 [1,10000000]。如果iself-number,则模拟生成它的下一个数,标记那个数为非self-number,以此类推,直到遇到下一个非self-number。遍历完毕,即可得到所有的self-number标记数组。

       这样做之后发现内存开销太大,不符合本题 4096kb 的空间需求。

于是可以稍微进行一些空间上的优化,因为标记数组只需要标记是或不是,所以可以采用二进制位压缩。

一个32位的数二进制有32个标志位

00000000 00000000 00000000 00000000

理论上,它可以记录 0-31 是否是self-number,例如1 3 5 7 9 20 31self-number,则可以用一个数来储存,即:

10000000 00010000 00000010 10101010

(右数为低位,左数为高位,从右往左分别表示 0 - 31是否是 self-number 1表示是,0表示否)

预处理数组的大小为 ceil(10000000/32),比原先的数组空间上压缩了32倍。

       解决本题还需要一个辅助数组FF[i]表示 [0, (i+1)*32 - 1] 这个区间内 self-number 的个数,可以通过一次性的扫描保存下来,这里涉及到求一个数中1的个数,因为计算量就一次,所以随便采用什么办法都行。

       然后就可以通过这个辅助数组求出小于等于Nself-number的个数。因为辅助数组的有序性,可以采用二分查找来找到第Kself-number的值。


109 Magic of David Copperfield II
      模拟 + 递归


       
题意:有这么一个游戏,对于一个N*N的拼盘,一开始手指放在1上,移动K1次,然后移除M1块方块(移除的时候手指不能在移除的方块上)。然后手指再移动K2次,每次移动不能进入已经移除的方块上,继续移除M2块方块,以此往复,知道最后手指在某个方块上,并且没有其他方块,题目就是要你模拟这个过程。

       题解:基本思路是当N为奇数的时候可以转化成N-2的情况求解,当N为偶数的时候可以转化为N-1的情况求解。

             对于偶数的情况:

1   2  3  4

5   6  7  8

9  10  11 12

13  14  15 16

 

      即上面这个矩阵可以先将 139 移除, 然后将24513移除,这样就转化成了

 

6  7  8

10  11 12

14  15 16

 

      这个子矩阵,也就是 3X3 的情况了。

             对于奇数的情况:

       可以先将最外层的包边移除,这样就可以转化成N-2的子矩阵求解了。

       至于K1为大于N的最小奇数,Ki - Ki-1 = 2,这样就能保证当N = 100的时候 Ke = 299 < 300 了。注意下标的处理就可以了。


posted on 2014-06-10 13:43 英雄哪里出来 阅读(1300) 评论(0)  编辑 收藏 引用 所属分类: Sgu 题解


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理